BiqCrunch

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

**Small problems**
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

**Large problems set 1**
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.

**Large problems set 2**
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).

**MIS**
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.

**QSSP**
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

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

**EQKP n=150**
	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

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**
Instances	n	Nodes	CPU time	Opt. Value
Chr12a	144	23	44.02	9552
Chr12b	144	23	42.97	9742
Chr12c	144	23	48.32	11156
Chr15a	225	33	355.78	9896
Chr15b	225	27	118.29	7990
Chr15c	225	37	272.92	9504
Chr18a	324	11	541.23	11098
Chr18b	324	217	15318.73	1534
Chr20a	400	3	709.32	2192
Chr20b	400	1	416.96	2298
Chr20c	400	45	1703.62	14142
Chr22a	484	3	1903.54	6156
Chr22a	484	1	1177.92	6194
Had12	144	1	5.26	1652
Had14	196	1	20.42	2724
Had16	256	1	42.83	3720
Had18	324	3	426.15	5358
Had20	400	3	741.05	6922
Nug12	144	11	62.79	578
Nug14	196	5	181.03	1014
Nug15	225	15	303.76	1150
Nug16a	256	17	978.40	1610
Nug16b	256	37	2320.98	1240
Nug17	289	55	2487.80	1732
Nug18	324	119	12884.33	1930
rou12	144	25	52.69	235528
rou15	225	55	518.58	354210
Scr12	144	53	163.21	31410
Scr15	225	57	244.07	51140
Scr20	400	267	15769.04	110030
Tai12a	144	25	40.46	224416
Tai15a	225	219	2079.80	388214
Tai17a	289	277	24407.14	491812

↑ top of page

A semidefinite branch-and-bound method for solving binary quadratic problems

Contacts

Max-Cut problem

Numerical Results (BiqCrunch 1.0)

k-cluster problem

Numerical Results (BiqCrunch 2.0)

Max independent set problem

Numerical Results (BiqCrunch 2.0)

Quadratic Stable Set Problem (QSSP)

Numerical Results (BiqCrunch 2.0)

Exact Quadratic Knapsack Problem

Numerical Results (BiqCrunch 1.0)

Quadratic Assignment Problem

Numerical Results (BiqCrunch 2.0)