Biq Mac Library - Binary quadratic
and Max cut
Library
This site offers a collection of
Max-Cut instances and quadratic 0-1 programming problems of
medium size. Most of the instances were
collected while
developing Biq Mac, an
SDP based Branch & Bound code (see
[RRW07] or [Wie06]). The
dimension of the problems (i.e., number of variables or number
of vertices in the graph) ranges from 20 to 500. The instances
are mainly ment to be used for testing exact solution methods
for quadratic 0-1 programming or Max-Cut problems.
Any comments or further instances to be added are welcome!
Please
contact angelika.wiegele@aau.at.
The structure of the directories is as follows:
|--- beasley
|---- Biq ---|--- gka
| |--- be
|
Biq Mac --- |
| |--- rudy
|---- Mac ---|
|--- ising
Here is a pdf-file
(tex-file), describing all the
datasets, giving the optimal
values (or lower/upper bounds), and the generators.
The overall collection:
[tar.gz-file] (9.6 MB)
[individual files]
Matrix Q is assumed to be symmetric and indexed by the numbers
from 1 up to n. Most of the instances can be downloaded in two
different versions, as
matrix or list of matrix elements (sparse format). The .mat files
are of the form
n
q_{1,1} q_{1,2} q_{1,3} ... q_{1,n}
q_{1,2} q_{2,2} q_{2,3} ... q_{2,n}
...
q_{1,n} q_{2,n} q_{3,n} ... q_{n,n}
The .sparse files are of the form
n m
i_1 j_1 q_{i_1,j_1}
i_2 j_2 q_{i_2,j_2}
...
i_m j_m q_{i_m,j_m}
where n is the number of variables and m the number of entries of Q
specified in the subsequent list.
Note that the beasley-datasets are available in sparse format only.
The datasets can be obtained from this site or from the
OR-Library. Note
that in the OR-library the problems are given for maximization!
The coefficients of Q are integer values from the interval [-100,100].
- bqp50-i Ten instances with
dimension n=50 and density 0.1.
- bqp100-i Ten instances with
dimension n=100 and density 0.1.
- bqp250-i Ten instances with
dimension n=250 and density 0.1.
- bqp500-i Ten instances with
dimension n=500 and density 0.1.
Also these datasets can be obtained from this website or from
the OR-Library.
Note that in the OR-library the problems are given for maximization!
The coefficients of Q are integer values.
- gkaia Eight instances
with dimensions from 30 to 100, densities from 0.0625 to
0.5. Diagonal coefficients from [-100,100], off-diagonal
coefficients from [-100,100].
- gkaib Ten instances
with dimensions from 20 to 125, density 1.
Diagonal coefficients from [-63,0], off-diagonal
coefficients from [0,100].
- gkaic Seven instances
with dimensions from 40 to 100, densities from 0.1 to
0.8. Diagonal coefficients from [-100,100], off-diagonal
coefficients from [-50,50].
- gkaid Ten instances
with dimension 100, densities from 0.1 to 1.
Diagonal coefficients from [-75,75], off-diagonal
coefficients from [-50,50].
- gkaie Five instances
with dimension 200, densities from 0.1 to 0.5.
Diagonal coefficients from [-100,100], off-diagonal
coefficients from [-50,50].
- gkaif Five instances
with dimension 500, densities from 0.1 to 1.
Diagonal coefficients from [-75,75], off-diagonal
coefficients from [-50,50].
The diagonal coefficients for all these instances are
from the interval [-100,100], off-diagonal coefficients from [-50,50]. All coefficients are integers.
- be100.i Ten instances with
dimension n=100 and density 1.
- be120.3.i Ten instances with
dimension n=120 and density 0.3.
- be120.8.i Ten instances with
dimension n=120 and density 0.8.
- be150.3.i Ten instances with
dimension n=150 and density 0.3.
- be150.8.i Ten instances with
dimension n=150 and density 0.8.
- be200.3.i Ten instances with
dimension n=200 and density 0.3.
- be200.8.i Ten instances with
dimension n=200 and density 0.8.
- be250.i Ten instances with
dimension n=250 and density 0.1.
For each graph, there is a text-file in the following format
(rudy-output format):
n m
h_1 t_1 c_{h_1,t_1}
h_2 t_2 c_{h_2,t_2}
...
h_m t_m c_{h_m,t_m}
where n is the number of nodes, m the number of edges and for each edge, h_i and
t_i are the end-nodes and c_{h_i,t_i} the weight.
Nodes are numbered from 1 up to n.
- g05_n.i For each dimension ten unweighted graphs with edge probability 0.5. n=60,80,100.
- pm1s_n.i For each dimension ten
weighted graphs with edge weights chosen uniformly
from {-1,0,1} and density 0.1. n=80,100
- pm1d_n.i For each dimension ten
weighted graphs with edge weights chosen uniformly
from {-1,0,1} and density 0.99. n=80,100
- wd_100.i For each density ten graphs with integer edge weights chosen from [-10,10] and
density d=0.1,0.5,0.9, n=100.
- pwd_100.i For each density ten graphs with integer edge weights chosen from [0,10] and
density d=0.1,0.5,0.9, n=100.
Max-Cut instances from applications in statistical physics (generated by
Frauke Liers [Lie04], [LJRR04])
[tar.gz-file][individual files]
- t2gn_seed For each dimension three two-dimensional toroidal grid graphs with
gaussian distributed weights and dimension n times n, n=10,15,20.
- t3gn_seed For each dimension three three-dimensional toroidal grid graphs with
gaussian distributed weights and dimension n times n times n, n=5,6,7.
- ising2.5-n_seed For each dimension three one-dimensional Ising chain instances.
n=100,150,200,250,300.
- ising3.0-n_seed For each dimension three one-dimensional Ising chain instances.
n=100,150,200,250,300.
[Bea90] John
E. Beasley. Or-library,1990.
[BE07] Alain Billionnet and Sourour Elloumi. Using a mixed integer quadratic programming
solver for the unconstrained quadratic 0-1 problem. Math. Programming, 109(1, Ser.
A):55-68,
2007. Springer
link
[BJR89] Francisco Barahona, Michael Jünger, and Gerhard Reinelt. Experiments in quadratic 0-1
programming. Math. Programming, 44(2, (Ser. A)):127-137,
1989. Springer
link
[GKA98] Fred Glover, Gary Kochenberger, and Bahram Alidaee. Adaptative memory tabu search
for binary quadratic programs. Management Sci., 44(3):336-345,
1998.
[Lie04] Frauke Liers. Contributions to Determining Exact Ground-States of Ising Spin-Glasses
and to their Physics. PhD thesis, Universität zu Köln, 2004.
[LJRR04] Frauke Liers, Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi. Computing exact
ground states of hard ising spin glass problems by branch-and-cut. In
Alexander Hartmann and Heiko Rieger, editors, New Optimization
Algorithms in Physics, pages 47-68.
Wiley,
2004. Wiley
link
[PR90] Panos M. Pardalos and Gregory P. Rodgers. Computational aspects of a branch and
bound algorithm for quadratic zero-one programming. Computing,
45(2):131-144,
1990. Springer
link
[Rin] Giovanni
Rinaldi. Rudy.
[RRW07] Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele. A branch and bound algorithm
for Max-Cut based on combining semidefinite and polyhedral relaxations. In Integer
programming and combinatorial optimization, volume 4513 of Lecture Notes in Comput.
Sci., pages 295-309. Springer, Berlin,
2007. Springer
link
[Wie06] Angelika Wiegele. Nonlinear optimization techniques applied to combinatorial optimization
problems. PhD thesis, Alpen-Adria-Universität Klagenfurt,
2006. pdf-file