Biq Mac Library  Binary quadratic
and Max cut
Library
This site offers a collection of
MaxCut instances and quadratic 01 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 01 programming or MaxCut problems.
Any comments or further instances to be added are welcome!
Please
contact angelika.wiegele@uniklu.ac.at.
The structure of the directories is as follows:
 beasley
 Biq  gka
  be

Biq Mac  
  rudy
 Mac 
 ising
Here is a pdffile
(texfile), describing all the
datasets, giving the optimal
values (or lower/upper bounds), and the generators.
The overall collection:
[tar.gzfile] (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 beasleydatasets are available in sparse format only.
The datasets can be obtained from this site or from the
ORLibrary. Note
that in the ORlibrary the problems are given for maximization!
The coefficients of Q are integer values from the interval [100,100].
 bqp50i Ten instances with
dimension n=50 and density 0.1.
 bqp100i Ten instances with
dimension n=100 and density 0.1.
 bqp250i Ten instances with
dimension n=250 and density 0.1.
 bqp500i Ten instances with
dimension n=500 and density 0.1.
Also these datasets can be obtained from this website or from
the ORLibrary.
Note that in the ORlibrary 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], offdiagonal
coefficients from [100,100].
 gkaib Ten instances
with dimensions from 20 to 125, density 1.
Diagonal coefficients from [63,0], offdiagonal
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], offdiagonal
coefficients from [50,50].
 gkaid Ten instances
with dimension 100, densities from 0.1 to 1.
Diagonal coefficients from [75,75], offdiagonal
coefficients from [50,50].
 gkaie Five instances
with dimension 200, densities from 0.1 to 0.5.
Diagonal coefficients from [100,100], offdiagonal
coefficients from [50,50].
 gkaif Five instances
with dimension 500, densities from 0.1 to 1.
Diagonal coefficients from [75,75], offdiagonal
coefficients from [50,50].
The diagonal coefficients for all these instances are
from the interval [100,100], offdiagonal 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 textfile in the following format
(rudyoutput 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 endnodes 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.
MaxCut instances from applications in statistical physics (generated by
Frauke Liers [Lie04], [LJRR04])
[tar.gzfile][individual files]
 t2gn_seed For each dimension three twodimensional toroidal grid graphs with
gaussian distributed weights and dimension n times n, n=10,15,20.
 t3gn_seed For each dimension three threedimensional toroidal grid graphs with
gaussian distributed weights and dimension n times n times n, n=5,6,7.
 ising2.5n_seed For each dimension three onedimensional Ising chain instances.
n=100,150,200,250,300.
 ising3.0n_seed For each dimension three onedimensional Ising chain instances.
n=100,150,200,250,300.
[Bea90] John
E. Beasley. Orlibrary,1990.
[BE07] Alain Billionnet and Sourour Elloumi. Using a mixed integer quadratic programming
solver for the unconstrained quadratic 01 problem. Math. Programming, 109(1, Ser.
A):5568,
2007. Springer
link
[BJR89] Francisco Barahona, Michael Jünger, and Gerhard Reinelt. Experiments in quadratic 01
programming. Math. Programming, 44(2, (Ser. A)):127137,
1989. Springer
link
[GKA98] Fred Glover, Gary Kochenberger, and Bahram Alidaee. Adaptative memory tabu search
for binary quadratic programs. Management Sci., 44(3):336345,
1998.
[Lie04] Frauke Liers. Contributions to Determining Exact GroundStates of Ising SpinGlasses
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 branchandcut. In
Alexander Hartmann and Heiko Rieger, editors, New Optimization
Algorithms in Physics, pages 4768.
Wiley,
2004. Wiley
link
[PR90] Panos M. Pardalos and Gregory P. Rodgers. Computational aspects of a branch and
bound algorithm for quadratic zeroone programming. Computing,
45(2):131144,
1990. Springer
link
[Rin] Giovanni
Rinaldi. Rudy.
[RRW07] Franz Rendl, Giovanni Rinaldi, and Angelika Wiegele. A branch and bound algorithm
for MaxCut based on combining semidefinite and polyhedral relaxations. In Integer
programming and combinatorial optimization, volume 4513 of Lecture Notes in Comput.
Sci., pages 295309. Springer, Berlin,
2007. Springer
link
[Wie06] Angelika Wiegele. Nonlinear optimization techniques applied to combinatorial optimization
problems. PhD thesis, AlpenAdriaUniversität Klagenfurt,
2006. pdffile