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

 Biq Mac BiqCrunch Min Mean Max Min Mean Max bqp50 0.11 0.70 5.03 0.17 0.22 0.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.

 n k d(%) nodes CPU time (s) 40 10 25 1.0 0.07 50 1.0 0.07 75 1.0 0.15 20 25 1.0 0.07 50 1.0 0.08 75 1.0 0.07 30 25 1.0 0.11 50 1.0 0.11 75 1.0 0.08 80 20 25 3.0 2.42 50 7.4 6.02 75 12.6 7.42 40 25 1.0 0.58 50 1.0 0.57 75 2.6 2.52 60 25 1.0 0.91 50 1.0 0.78 75 1.0 0.67 100 25 25 15.4 21.24 50 31.0 35.32 75 28.2 29.14 50 25 2.2 3.37 50 21.0 31.81 75 1.0 1.46 75 25 1.0 1.61 50 1.0 1.73 75 1.0 1.73
 n k d(%) nodes CPU time (s) 120 30 25 64.6 133.04 50 110.6 177.20 75 236.6 297.84 60 25 28.6 59.09 50 43.8 90.65 75 19.0 38.95 90 25 1.0 3.53 50 6.2 28.79 75 1.0 2.38 140 35 25 221.0 529.51 50 600.6 1154.11 75 861.8 1506.71 70 25 69.0 178.69 50 400.2 1055.58 75 28.6 71.89 105 25 1.0 4.71 50 4.2 23.03 75 2.6 13.30 160 40 25 501.0 1927.53 50 6064.6 15411.7 75 4427.8 10798.5 80 25 207.4 854.28 50 505.8 1791.06 75 2017.4 7242.98 120 25 10.2 74.53 50 7.0 63.66 75 3.8 30.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.

 n k d(%) nodes CPU time (s) 120 30 25 14.6 30.74 50 38.2 82.19 75 62.2 146.19 60 25 5.4 10.81 50 23.0 60.62 75 28.6 80.35 90 25 1.0 3.46 50 1.0 3.53 75 1.0 2.83 140 35 25 97.4 314.50 50 285.0 820.00 75 445.4 958.87 70 25 39.8 138.41 50 242.6 676.04 75 119.4 331.66 105 25 1.4 6.81 50 5.8 27.69 75 1.8 10.69 160 40 25 203.8 835.01 50 865.4 3161.45 75 914.6 2636.98 80 25 58.2 224.67 50 380.2 1323.67 75 1064.6 3932.32 120 25 1.0 6.96 50 1.4 11.17 75 3.0 23.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).
 Instances n m d(%) Nodes CPU time Opt. Value hamming6-2 64 192 10 1 0.01 32 hamming6-4 64 1312 65 1 0.17 4 hamming8-2 256 1024 3 1 1.29 128 johnson16-2-4 120 1680 26 41 2.61 8 johnson8-4-4 70 560 23 1 0.06 14 MANN_a9 45 72 7 5 3.90 16 keller4 171 5100 35 155 155.24 11 san200_0.7_1 200 5970 30 1 2.05 30 san200_0.7_2 200 5970 30 1 3.72 18 san200_0.9_1 200 1990 10 1 0.92 70 san200_0.9_2 200 1990 10 1 0.82 60 san200_0.9_3 200 1990 10 1 4.37 44 brock200_1 200 5066 26 1393 1822.81 21 brock200_2 200 10024 51 53 87.01 12 brock200_3 200 7852 39 107 157.45 15 brock200_4 200 6811 34 185 263.32 17
↑ 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.
 Instances n density of edges (%) positive costs (%) Nodes CPU time Opt. Value 1 100 25 25 3 4.63 882 2 100 25 25 13 21.26 813 3 100 25 25 19 38.38 792 1 100 25 50 15 21.55 2576 2 100 25 50 21 26.89 2468 3 100 25 50 13 24.56 2509 1 100 25 75 71 70.80 4758 2 100 25 75 67 66.49 4877 3 100 25 75 27 29.00 5014 1 100 50 25 1 2.96 607 2 100 50 25 3 5.75 459 3 100 50 25 11 8.86 542 1 100 50 50 7 14.53 1163 2 100 50 50 9 14.78 1138 3 100 50 50 9 15.46 1002 1 100 50 75 11 17.95 1829 2 100 50 75 7 11.19 2047 3 100 50 75 13 20.33 1748 1 100 75 25 3 4.61 267 2 100 75 25 3 3.21 378 3 100 75 25 1 3.10 273 1 100 75 50 5 7.74 483 2 100 75 50 3 4.04 507 3 100 75 50 1 3.00 525 1 100 75 75 17 32.03 607 2 100 75 75 9 7.77 757 3 100 75 75 1 3.97 843 1 150 25 25 31 129.52 1248 2 150 25 25 17 68.24 1229 3 150 25 25 23 95.61 1116 1 150 25 50 73 205.46 3322 2 150 25 50 195 497.26 3016 3 150 25 50 63 183.09 3225 1 150 25 75 193 425.74 6962 2 150 25 75 525 1023.26 6438 3 150 25 75 333 667.56 6332 1 150 50 25 13 41.58 665 2 150 50 25 21 69.89 627 3 150 50 25 19 68.06 642 1 150 50 50 23 74.42 1500 2 150 50 50 37 125.01 1317 3 150 50 50 39 121.97 1322 1 150 50 75 43 126.74 2377 2 150 50 75 73 196.14 2053 3 150 50 75 39 104.56 2293 1 150 75 25 5 14.02 451 2 150 75 25 13 32.69 384 3 150 75 25 13 37.10 347 1 150 75 50 7 14.21 787 2 150 75 50 1 6.74 873 3 150 75 50 9 33.30 663 1 150 75 75 25 74.05 895 2 150 75 75 37 111.69 877 3 150 75 75 27 92.56 888
↑ top of page

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.

 n d(%) nodes CPU time (s) 50 25 88.20 13.85 50 98.80 32.83 75 256.40 42.02 100 201.80 35.19 100 25 1090.20 685.00 50 2342.20 1103.94 75 3101.00 1966.30 100 3171.67 884.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.

 d=25% d=50% d=75% d=100% gap nodes gap nodes gap nodes gap nodes Cplex 12.5 82.1 19358185 110.6 16372566 321.7 16915377 208.2 12277632 QCR 2.4 5038302 3.6 6173553 9.9 9699595 3.9 6154597 BiqCrunch 1.6 493.4 0.7 739.5 12.2 360.6 1.2 309.6
↑ top of page