BiqCrunch will not modify your model before solving it, so be cautious when formulating the input files. The semidefinite bound will be impacted and consequently the efficiency of the solver. In particular, if one wants to get a stronger underlying SDP relaxation, the corresponding constraints (redundant in the initial 0-1 model) must be added in the model. For example, this is the case for the k-cluster and the Exact Quadratic Knapsack Problems presented here.

Max-Cut problem

Given an edge-weighted graph with n vertices, the objective is to maximize the total weight of the edges between a subset of vertices and its complement. This problem can be stated as :

\begin{align*} \max \quad & \sum_{1\le i, j \le n} w_{ij}x_i (1 - x_j)\\ \mbox{subject to}\quad & x \in \{0,1\}^n & \end{align*}

Numerical Results (BiqCrunch 1.0)

We solve the problems described in Biq Mac library by Angelika Wiegele. Detailed results are available here, and also at http://hal.archives-ouvertes.fr/hal-00665968

Minimum / mean / maximum CPU time (s) for Biq Mac and BiqCrunch (preliminary version) to solve problems in the Biq Mac Library
Biq Mac BiqCrunch
Min Mean Max Min Mean Max
bqp500.110.705.030.170.220.26
bqp100 0.92 3.77 22.29 1.40 2.58 11.12
bqp250 526.18 7052.28 54277.92 47.13 1736.11 14714.12
gkaa 0.06 0.55 1.37 0.06 0.65 2.11
gkab 1.11 1650.88 10719.44 0.10 787.00 5104.21
gkac 0.16 0.62 1.02 0.13 0.85 1.95
gkad 1.53 32.98 79.33 1.63 18.06 55.72
gkae 126.98 6116.31 25721.41 21.77 3897.82 16654.15
be100.d100 16.70 42.88 108.69 3.79 33.51 114.88
be120.d30 4.52 32.64 113.27 5.01 17.68 76.30
be120.d80 39.12 146.09 211.55 32.60 142.54 268.07
be150.d30 39.21 367.92 844.33 7.74 285.44 767.08
be150.d80 441.62 506.15 561.98 363.55 500.04 608.20
be200.d30 1079.71 8223.51 43850.81 102.61 4852.01 32612.82
be200.d80 1210.52 10692.92 35247.12 596.22 6759.69 25518.98
be250.d10 328.64 2437.95 3754.20 27.98 409.71 905.98
g05.n60 0.26 5.74 13.27 0.67 7.42 24.84
g05.n80 6.39 63.09 274.50 2.80 63.10 296.10
g05.n100 93.45 803.88 4197.29 96.05 721.25 3382.27
pm1s80.d090 0.58 4.76 23.96 0.96 3.92 13.40
pm1s100.d010 1.15 49.87 130.28 1.85 34.70 88.48
pm1d80.d090 24.56 71.90 212.47 13.74 56.31 138.19
pm1d100.d090 106.24 945.40 2868.06 56.94 620.76 1800.63
w100.d010 1.37 23.15 131.45 1.71 23.47 152.09
w100.d050 109.99 563.27 1152.49 81.02 475.32 1061.46
w100.d090 38.67 836.25 2945.89 26.50 997.06 4675.78
pw100.d010 1.64 65.34 228.70 2.06 34.88 113.86
pw100.d050 122.67 715.95 1798.61 81.34 732.48 2506.69
pw100.d090 209.02 606.82 1297.98 201.61 509.48 1061.18
ising100 7.74 12.76 19.86 2.62 3.04 3.87
ising150 42.55 60.31 85.74 7.74 10.70 12.89
ising200 150.39 233.99 403.19 19.72 27.26 37.59
ising250 165.79 981.56 2161.49 47.88 138.27 406.84
ising300 991.28 4268.83 11858.56 97.43 455.77 1628.66
t2g10 1.63 2.22 3.04 3.50 4.14 5.30
t2g15 56.55 66.36 73.34 38.87 42.45 46.03
t2g20 1014.38 4676.45 11132.18 351.37 1159.24 2748.55
t3g5 3.22 4.42 5.49 7.18 7.39 7.71
t3g6 52.34 159.36 367.12 41.85 218.22 566.66
t3g7 81.37 5931.61 17601.56 123.46 3838.06 11234.02
↑ top of page

k-cluster problem

Given an edge-weighted graph with n vertices and a natural number k, the objective is to maximize the total weight of a subgraph of k nodes. This problem can be stated as:

\begin{align*} \max\quad & \sum_{1 \le i < j \le n} w_{ij}x_i x_j\\ \mbox{subject to}\quad & \sum_{i = 1 \dots n} x_i = k &\\ & x \in \{0,1\}^n & \end{align*}

Numerical Results (BiqCrunch 2.0)

First, we give the number of nodes and CPU times, averaged over five instances for each triple (n,k,d) where d is the graph density, required to solve a library of 270 k-cluster problems. 96.6% of the test problems are solved within three hours with a DELL T-1600 Intel Xeon E3-1270 3.40GHz (using single core). Note that the basic model is reenforced with product constraints. Details about the model, the entire set of results (using BiqCrunch first release) and the graphs are available at hal.archives-ouvertes.fr/hal-00717212. All the numerical tests have been updated using the second release of BiqCrunch.

Small problems
nkd(%)nodesCPU time (s)
4010251.00.07
  501.00.07
  751.00.15
 20251.00.07
  501.00.08
  751.00.07
 30251.00.11
  501.00.11
  751.00.08
8020253.02.42
  507.46.02
  7512.67.42
 40251.00.58
  501.00.57
  752.62.52
 60251.00.91
  501.00.78
  751.00.67
100252515.421.24
  5031.035.32
  7528.229.14
 50252.23.37
  5021.031.81
  751.01.46
 75251.01.61
  501.01.73
  751.01.73
Large problems set 1
nkd(%)nodesCPU time (s)
120302564.6133.04
  50110.6177.20
  75236.6297.84
 602528.659.09
  5043.890.65
  7519.038.95
 90251.03.53
  506.228.79
  751.02.38
1403525221.0529.51
  50600.61154.11
  75861.81506.71
 702569.0178.69
  50400.21055.58
  7528.671.89
 105251.04.71
  504.223.03
  752.613.30
1604025501.01927.53
  506064.615411.7
  754427.810798.5
 8025207.4854.28
  50505.81791.06
  752017.47242.98
 1202510.274.53
  507.063.66
  753.830.64
↑ top of page

Second, we give the number of nodes and CPU times, averaged over five instances for each triple (n,k,d) where d is the graph density, required to solve the problems available online at Library of k-cluster problems by Amélie Lambert from CEDRIC.

Large problems set 2
nkd(%)nodesCPU time (s)
120302514.630.74
  5038.282.19
  7562.2146.19
 60255.410.81
  5023.060.62
  7528.680.35
 90251.03.46
  501.03.53
  751.02.83
140352597.4314.50
  50285.0820.00
  75445.4958.87
 702539.8138.41
  50242.6676.04
  75119.4331.66
 105251.46.81
  505.827.69
  751.810.69
1604025203.8835.01
  50865.43161.45
  75914.62636.98
 802558.2224.67
  50380.21323.67
  751064.63932.32
 120251.06.96
  501.411.17
  753.023.49
↑ top of page

Max independent set problem

Given a weighted graph G=(V,E) where V is the set of vertices of G (|V|=n) and E is the set of edges of G (|E|=m). A weight is assigned to each vertex. The objective is to maximize the total weight of the vertices in the independent set (An independent set is a set S of vertices such that no two vertices of S are joined by an edge in E). It can be stated as :

\begin{align*} \max \quad & \displaystyle{\sum_{i=1}^n} w_ix_i\\ \mbox{subject to}\quad & x_ix_j=0 & \forall (i,j) \in E\\ & x_i \in \{0,1\} & \forall i=1 \dots n\\ \end{align*}

Numerical Results (BiqCrunch 2.0)

The fist results had been obtained by Geoffrey Kozak, student of the engineering school Sup Galilée, during his summer internship in 2012 in the LIPN-AOC team. The results have been updated using the last version of BiqCrunch (second release).
MIS
Instancesnmd(%)NodesCPU timeOpt. Value
hamming6-2641921010.0132
hamming6-46413126510.174
hamming8-22561024311.29128
johnson16-2-4120168026412.618
johnson8-4-4705602310.0614
MANN_a94572753.9016
keller4171510035155155.2411
san200_0.7_120059703012.0530
san200_0.7_220059703013.7218
san200_0.9_120019901010.9270
san200_0.9_220019901010.8260
san200_0.9_320019901014.3744
brock200_120050662613931822.8121
brock200_220010024515387.0112
brock200_3200785239107157.4515
brock200_4200681134185263.3217
↑ top of page

Quadratic Stable Set Problem (QSSP)

Given a weighted graph G=(V,E) where V is the set of vertices of G (|V|=n) and E is the set of edges of G (|E|=m). A weight is assigned to each vertex and to each (i,j) (i and j are in {1,...,n}). The objective is to maximize the total weight of an independent set (an independent set is a set S of vertices such that no two vertices of S are joined by an edge in E). It can be stated as :

\begin{align*} \max \quad & \displaystyle{\sum_{i,j}^n Q_{ij}x_ix_j + \sum_{i=1}^n} w_ix_i\\ \mbox{subject to}\quad & x_ix_j=0 & \forall (i,j) \in E\\ & x_i \in \{0,1\} & \forall i=1 \dots n\\ \end{align*}

Numerical Results (BiqCrunch 2.0)

These problems have been provided by Fabio Furini (see http://www.optimization-online.org/DB_HTML/2012/10/3652.html). Biqcrunch is used here only with the generic heuristic (DELL T-1600 Intel Xeon E3-1270 3.40GHz, using single core). For these problems, the new release of BiqCrunch is 3.5 times faster, on average, than the first release.
QSSP
Instancesndensity of edges (%)positive costs (%)NodesCPU timeOpt. Value
1100252534.63882
210025251321.26813
310025251938.38792
110025501521.552576
210025502126.892468
310025501324.562509
110025757170.804758
210025756766.494877
310025752729.005014
1100502512.96607
2100502535.75459
31005025118.86542
11005050714.531163
21005050914.781138
31005050915.461002
110050751117.951829
21005075711.192047
310050751320.331748
1100752534.61267
2100752533.21378
3100752513.10273
1100755057.74483
2100755034.04507
3100755013.00525
110075751732.03607
2100757597.77757
3100757513.97843
1150252531129.521248
215025251768.241229
315025252395.611116
1150255073205.463322
21502550195497.263016
3150255063183.093225
11502575193425.746962
215025755251023.266438
31502575333667.566332
115050251341.58665
215050252169.89627
315050251968.06642
115050502374.421500
2150505037125.011317
3150505039121.971322
1150507543126.742377
2150507573196.142053
3150507539104.562293
11507525514.02451
215075251332.69384
315075251337.10347
11507550714.21787
2150755016.74873
31507550933.30663
115075752574.05895
2150757537111.69877
315075752792.56888
↑ top of page

Exact Quadratic Knapsack Problem

This problem can be stated as:

\begin{align*} \max\quad & \sum_{i=1}^{n-1}\sum_{j=i+1}^n W_{ij}x_i x_j + \sum_{i=1}^n W_{ii} x_i \\ \mbox{subject to}\quad & \sum_{i=1}^n x_i = k &\\ & \sum_{i=1}^n a_i x_i \leq b &\\ & x \in \{0,1\}^n & \end{align*}

Numerical Results (BiqCrunch 1.0)

To solve EQKP, we add the product constraints made from the cardinality constraint, and we replace the knapsack constraint by a stronger one (for the underlying SDP relaxation). For details, see e.g. CWINLP13. Hereafter, we give the number of nodes and CPU times to reach optimality (with a DELL T-1600 Intel Xeon E3-1270 3.40GHz, 8 Go RAM, under Linux, using single core), averaged over ten instances for each (n,d) where d is the graph density. The problems and a specific heuristic have been provided by Lucas Létocart. The original files can be downloaded here for n=50 and here for n=100.

EQKP
nd(%)nodesCPU time (s)
502588.2013.85
 5098.8032.83
 75256.4042.02
 100201.8035.19
100251090.20685.00
 502342.201103.94
 753101.001966.30
 1003171.67884.42

For larger problems (n=150), we give the number of nodes and gaps (between the best current feasible solution and the weakest bound in the search tree). We set a time limit of 3600 seconds, and the results are averaged over ten instances for each d (density of quadratic terms given by W). Here, BiqCrunch is compared with CPLEX and QCR.

EQKP n=150
 d=25%d=50% d=75% d=100%
  gapnodesgapnodesgapnodesgapnodes
Cplex 12.582.119358185110.616372566321.716915377208.212277632
QCR2.450383023.661735539.996995953.96154597
BiqCrunch1.6493.40.7739.512.2360.61.2309.6
↑ top of page

Quadratic Assignment Problem

Consider the problem of allocating a set of facilities to a set of locations, with the cost being a function of the distance and flow between the facilities, plus costs associated with a facility being placed at a certain location. The objective is to assign each facility to a location such that the total cost is minimized. It can be stated as a quadratic 0-1 problem:

\begin{align*} \min \quad & \sum_{i,j,k,l} C_{ijkl}x_{ij}x_{kl} + \sum_{i,j}c_{ij}x_{ij}\\ \mbox{subject to}\quad & \sum_{j} x_{ij}=1 & \forall i= 1 \dots n\\ & \sum_{i} x_{ij}=1 & \forall j= 1\dots n\\ & x \in \{0,1\}^{n^2} & \end{align*}

Numerical Results (BiqCrunch 2.0)

Problems are available at QAPLIB home page. Here, the basic model is reenforced with product constraints and non-negativity constraints. For details, see e.g. CWINLP13. In addition, generic heuristics of BiqCrunch and greedy heuristics are also used. The test problems are solved with a DELL T-1600 Intel Xeon E3-1270 3.40GHz (using single core).

Quadratic Assignment Problem
InstancesnNodesCPU timeOpt. Value
Chr12a1442344.029552
Chr12b1442342.979742
Chr12c1442348.3211156
Chr15a22533355.789896
Chr15b22527118.297990
Chr15c22537272.929504
Chr18a32411541.2311098
Chr18b32421715318.731534
Chr20a4003709.322192
Chr20b4001416.962298
Chr20c400451703.6214142
Chr22a48431903.546156
Chr22a48411177.926194
Had1214415.261652
Had14196120.422724
Had16256142.833720
Had183243426.155358
Had204003741.056922
Nug121441162.79578
Nug141965181.031014
Nug1522515303.761150
Nug16a25617978.401610
Nug16b256372320.981240
Nug17289552487.801732
Nug1832411912884.331930
rou121442552.69235528
rou1522555518.58354210
Scr1214453163.2131410
Scr1522557244.0751140
Scr2040026715769.04110030
Tai12a1442540.46224416
Tai15a2252192079.80388214
Tai17a28927724407.14491812
↑ top of page