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

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]

Biq: min x'Qx s.t. x in {0,1}^n [tar.gz-file][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
      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.

Beasley instances [sparse.tar.gz-file][individual files]

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].

Glover, Kochenberger and Alidaee instances [mat.tar.gz-file][sparse.tar.gz-file][individual files]

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.

Billionnet and Elloumi instances [mat.tar.gz-file][sparse.tar.gz-file][individual files]

The diagonal coefficients for all these instances are from the interval [-100,100], off-diagonal coefficients from [-50,50]. All coefficients are integers.

Mac: Max Cut [tar.gz-file][individual files]

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.

Max-Cut instances generated with rudy [tar.gz-file][individual files]

Max-Cut instances from applications in statistical physics (generated by Frauke Liers [Lie04], [LJRR04]) [tar.gz-file][individual files]


[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
Angelika Wiegele, September 2007
Department of Mathematics, Alpen-Adria-Universität Klagenfurt, Austria.