Graph partitioning: results with random graphs

Results obtained using Gurobi for solving the Graph Partitioning Problem (GPP), using the models described in Mathematical Optimization: Solving Problems using Python and Gurobi. CPU time limited to 300 seconds. (Click on values for selecting data to display.)

Benchmark instances analysed
Instance family	Type	Description
p=0.50	random	probability (graph density): 0.50
p=0.10	random	probability (graph density): 0.10
p=0.05	random	probability (graph density): 0.05
p=0.01	random	probability (graph density): 0.01

GPP: Results for random graphs with p=0.50

Legend for columns in the next tables
Label	Description
size	Size of the graph
gpp	Time used by the standard formulation
gpp_qo	Time used by the formulation in quadratic optimization
gpp_soco	Time used by a formulation using second-order cone optimization

(click on values for detailed output)

chart

Average CPU per instance size, p=0.50
size	gpp	gpp_qo	gpp_soco
2	0.00	0.01	0.01
3	0.01	0.01	0.03
4	0.00	0.01	0.05
5	0.01	0.01	0.07
6	0.01	0.01	0.11
7	0.01	0.01	0.13
8	0.01	0.01	0.18
9	0.01	0.01	0.23
10	0.01	0.01	0.28
11	0.02	0.01	0.33
12	0.02	0.01	0.39
13	0.02	0.01	0.47
14	0.03	0.03	0.55
15	0.03	0.05	0.66
16	0.05	0.06	0.79
17	0.09	0.10	0.96
18	0.16	0.18	1.16
19	0.21	0.24	1.29
20	0.29	0.39	1.51
21	0.44	0.63	2.35
22	0.89	1.24	3.66
23	1.23	2.01	4.79
24	1.89	3.48	6.62
25	3.15	6.46	11.14
26	3.88	10.58	13.02
27	5.87	19.46	23.86
28	8.13	34.62	26.15
29	11.55	55.92	38.74
30	18.67	164.04	69.88
31	31.31	-	110.38
32	39.62	-	178.81
33	63.72	-	-
34	122.21	-	-
35	-	-	-

CPU for instance size 2
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.01	0.01
1	0.00	0.01	0.03
2	0.00	0.01	0.00
3	0.00	0.00	0.02
4	0.00	0.00	0.02
5	0.00	0.01	0.00
6	0.00	0.01	0.00
7	0.00	0.01	0.02
8	0.00	0.01	0.02
9	0.00	0.00	0.02

CPU for instance size 3
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.00	0.03
1	0.01	0.02	0.01
2	0.00	0.00	0.01
3	0.00	0.01	0.04
4	0.01	0.00	0.04
5	0.00	0.00	0.00
6	0.01	0.01	0.02
7	0.00	0.01	0.03
8	0.01	0.00	0.02
9	0.01	0.01	0.05

CPU for instance size 4
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.01	0.05
1	0.00	0.00	0.07
2	0.01	0.01	0.02
3	0.00	0.00	0.05
4	0.02	0.02	0.08
5	0.00	0.00	0.00
6	0.00	0.01	0.05
7	0.01	0.00	0.05
8	0.00	0.00	0.06
9	0.01	0.00	0.05

CPU for instance size 5
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.01	0.07
1	0.00	0.01	0.08
2	0.00	0.01	0.06
3	0.01	0.00	0.07
4	0.01	0.00	0.10
5	0.01	0.01	0.02
6	0.01	0.01	0.07
7	0.01	0.00	0.08
8	0.01	0.01	0.09
9	0.01	0.01	0.06

CPU for instance size 6
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.00	0.09
1	0.00	0.01	0.12
2	0.01	0.01	0.08
3	0.01	0.00	0.11
4	0.00	0.01	0.14
5	0.00	0.01	0.06
6	0.01	0.00	0.09
7	0.02	0.00	0.14
8	0.01	0.02	0.12
9	0.01	0.00	0.11

CPU for instance size 7
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.01	0.11
1	0.01	0.00	0.15
2	0.01	0.01	0.12
3	0.02	0.00	0.11
4	0.00	0.01	0.16
5	0.02	0.00	0.10
6	0.00	0.01	0.12
7	0.02	0.01	0.16
8	0.02	0.01	0.18
9	0.01	0.01	0.14

CPU for instance size 8
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.02	0.15
1	0.02	0.01	0.20
2	0.01	0.01	0.17
3	0.01	0.02	0.17
4	0.01	0.01	0.18
5	0.02	0.01	0.15
6	0.01	0.01	0.15
7	0.01	0.00	0.22
8	0.00	0.02	0.23
9	0.01	0.01	0.17

CPU for instance size 9
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.00	0.18
1	0.02	0.01	0.30
2	0.00	0.02	0.22
3	0.01	0.00	0.18
4	0.01	0.00	0.22
5	0.01	0.01	0.19
6	0.00	0.01	0.21
7	0.01	0.01	0.27
8	0.01	0.01	0.28
9	0.02	0.00	0.26

CPU for instance size 10
inst	gpp	gpp_qo	gpp_soco
0	0.00	0.01	0.24
1	0.02	0.01	0.35
2	0.00	0.00	0.24
3	0.00	0.01	0.24
4	0.01	0.00	0.25
5	0.00	0.01	0.24
6	0.01	0.00	0.22
7	0.01	0.01	0.34
8	0.01	0.02	0.33
9	0.01	0.01	0.32

CPU for instance size 11
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.01	0.30
1	0.02	0.00	0.37
2	0.01	0.01	0.28
3	0.02	0.01	0.27
4	0.01	0.00	0.33
5	0.01	0.01	0.33
6	0.02	0.01	0.29
7	0.02	0.01	0.40
8	0.02	0.02	0.36
9	0.02	0.01	0.40

CPU for instance size 12
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.00	0.32
1	0.01	0.01	0.45
2	0.02	0.02	0.35
3	0.02	0.01	0.31
4	0.02	0.01	0.41
5	0.01	0.01	0.38
6	0.01	0.00	0.36
7	0.02	0.00	0.44
8	0.02	0.02	0.44
9	0.02	0.01	0.46

CPU for instance size 13
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.01	0.39
1	0.02	0.01	0.53
2	0.00	0.00	0.38
3	0.01	0.01	0.39
4	0.02	0.02	0.52
5	0.02	0.02	0.47
6	0.03	0.02	0.48
7	0.03	0.02	0.49
8	0.02	0.02	0.53
9	0.02	0.01	0.55

CPU for instance size 14
inst	gpp	gpp_qo	gpp_soco
0	0.02	0.02	0.41
1	0.04	0.01	0.55
2	0.02	0.02	0.45
3	0.02	0.02	0.47
4	0.03	0.03	0.59
5	0.03	0.04	0.55
6	0.02	0.02	0.55
7	0.02	0.04	0.64
8	0.03	0.03	0.72
9	0.04	0.05	0.62

CPU for instance size 15
inst	gpp	gpp_qo	gpp_soco
0	0.01	0.03	0.49
1	0.02	0.03	0.62
2	0.02	0.04	0.59
3	0.02	0.03	0.53
4	0.07	0.08	0.76
5	0.03	0.04	0.67
6	0.02	0.03	0.67
7	0.04	0.06	0.73
8	0.03	0.07	0.79
9	0.04	0.08	0.78

CPU for instance size 16
inst	gpp	gpp_qo	gpp_soco
0	0.03	0.04	0.58
1	0.05	0.06	0.71
2	0.03	0.02	0.70
3	0.02	0.04	0.67
4	0.08	0.09	0.93
5	0.05	0.06	0.80
6	0.07	0.07	0.80
7	0.06	0.07	0.84
8	0.08	0.11	0.95
9	0.07	0.08	0.92

CPU for instance size 17
inst	gpp	gpp_qo	gpp_soco
0	0.05	0.04	0.72
1	0.07	0.09	0.89
2	0.07	0.04	0.80
3	0.06	0.08	0.79
4	0.09	0.13	1.10
5	0.07	0.11	1.04
6	0.08	0.13	0.98
7	0.10	0.14	1.10
8	0.15	0.14	1.16
9	0.12	0.14	1.03

CPU for instance size 18
inst	gpp	gpp_qo	gpp_soco
0	0.06	0.11	0.88
1	0.14	0.18	1.11
2	0.17	0.15	1.06
3	0.06	0.11	0.97
4	0.15	0.17	1.26
5	0.10	0.11	1.04
6	0.15	0.15	1.27
7	0.26	0.26	1.32
8	0.36	0.31	1.42
9	0.16	0.21	1.23

CPU for instance size 19
inst	gpp	gpp_qo	gpp_soco
0	0.05	0.07	0.97
1	0.17	0.17	1.33
2	0.24	0.25	1.24
3	0.17	0.17	1.11
4	0.18	0.25	1.37
5	0.23	0.21	1.23
6	0.21	0.28	1.23
7	0.22	0.37	1.55
8	0.36	0.24	1.38
9	0.28	0.42	1.46

CPU for instance size 20
inst	gpp	gpp_qo	gpp_soco
0	0.18	0.25	1.34
1	0.28	0.32	1.47
2	0.21	0.23	1.34
3	0.25	0.37	1.44
4	0.26	0.45	1.78
5	0.24	0.31	1.33
6	0.48	0.38	1.53
7	0.36	0.56	1.84
8	0.25	0.65	1.44
9	0.37	0.39	1.62

CPU for instance size 21
inst	gpp	gpp_qo	gpp_soco
0	0.33	0.49	2.55
1	0.42	0.67	1.92
2	0.20	0.38	1.68
3	0.22	0.26	1.47
4	0.29	0.38	1.67
5	0.34	0.51	1.54
6	0.54	0.58	1.88
7	0.52	1.02	3.73
8	0.56	1.04	3.44
9	1.01	1.01	3.60

CPU for instance size 22
inst	gpp	gpp_qo	gpp_soco
0	0.43	0.88	1.92
1	0.91	0.98	4.13
2	0.94	1.16	2.16
3	0.43	0.40	1.72
4	0.49	1.24	3.87
5	0.98	1.28	4.19
6	1.07	1.78	4.80
7	1.02	1.49	4.61
8	0.95	1.40	4.52
9	1.66	1.78	4.68

CPU for instance size 23
inst	gpp	gpp_qo	gpp_soco
0	1.06	2.50	4.30
1	0.81	1.79	5.31
2	1.52	2.97	4.88
3	0.64	1.29	2.23
4	1.39	1.79	4.48
5	0.85	1.00	3.80
6	1.68	2.39	7.99
7	1.55	2.81	6.46
8	0.50	1.59	3.93
9	2.34	1.95	4.55

CPU for instance size 24
inst	gpp	gpp_qo	gpp_soco
0	1.58	1.90	2.44
1	1.29	2.53	5.98
2	1.53	2.94	5.15
3	1.39	2.63	5.19
4	1.46	3.17	7.57
5	1.96	3.43	5.55
6	3.31	4.88	7.08
7	1.25	3.20	7.46
8	2.07	3.42	8.81
9	3.01	6.72	10.95

CPU for instance size 25
inst	gpp	gpp_qo	gpp_soco
0	2.19	3.82	6.70
1	3.31	7.92	10.35
2	1.80	4.89	9.29
3	2.75	4.75	10.87
4	4.19	7.48	15.18
5	2.65	5.95	10.48
6	5.39	10.07	13.62
7	2.78	6.81	9.78
8	2.29	4.76	13.03
9	4.11	8.20	12.09

CPU for instance size 26
inst	gpp	gpp_qo	gpp_soco
0	2.81	10.42	12.53
1	4.07	11.88	12.72
2	3.18	9.89	11.62
3	2.74	5.81	10.77
4	3.06	11.40	11.53
5	5.83	8.93	11.39
6	5.03	10.49	15.42
7	3.25	10.77	14.27
8	3.33	8.24	12.11
9	5.49	17.99	17.79

CPU for instance size 27
inst	gpp	gpp_qo	gpp_soco
0	9.54	21.54	21.77
1	6.27	23.55	22.90
2	4.72	10.61	23.47
3	4.35	15.09	19.17
4	5.96	21.62	25.84
5	4.96	16.02	23.06
6	6.06	21.19	21.51
7	5.13	17.38	26.30
8	5.43	23.01	28.64
9	6.30	24.60	25.96

CPU for instance size 28
inst	gpp	gpp_qo	gpp_soco
0	7.46	37.09	30.36
1	10.34	28.33	26.09
2	8.66	38.27	31.40
3	8.69	35.92	29.33
4	6.54	31.22	23.02
5	5.84	16.27	14.74
6	6.05	22.29	21.23
7	8.59	54.91	30.95
8	8.74	26.20	22.92
9	10.36	55.71	31.48

CPU for instance size 29
inst	gpp	gpp_qo	gpp_soco
0	11.25	51.91	41.58
1	12.74	62.03	39.67
2	10.05	39.75	31.52
3	14.48	73.48	43.60
4	12.25	49.13	28.99
5	12.10	66.89	44.65
6	8.60	39.81	37.99
7	14.64	59.71	37.77
8	8.40	48.65	29.40
9	10.97	67.86	52.25

CPU for instance size 30
inst	gpp	gpp_qo	gpp_soco
0	23.66	177.33	105.92
1	20.88	201.60	91.52
2	15.44	121.93	37.77
3	19.75	209.81	70.23
4	11.82	88.06	45.28
5	11.23	80.41	43.30
6	19.82	168.23	57.95
7	21.40	232.23	74.26
8	13.91	127.21	72.47
9	28.83	233.62	100.06

CPU for instance size 31
inst	gpp	gpp_qo	gpp_soco
0	24.92	266.65	112.51
1	64.17	299.83	112.51
2	32.87	-	83.72
3	17.67	-	101.14
4	16.76	-	81.92
5	38.47	-	140.68
6	32.88	-	107.80
7	22.55	-	105.05
8	23.43	-	67.78
9	39.39	-	190.68

CPU for instance size 32
inst	gpp	gpp_qo	gpp_soco
0	36.85	-	193.79
1	48.47	-	163.41
2	30.98	-	124.70
3	35.15	-	172.54
4	35.56	-	180.98
5	33.47	-	196.78
6	77.62	-	171.02
7	42.19	-	252.31
8	17.00	-	140.55
9	38.94	-	192.01

CPU for instance size 33
inst	gpp	gpp_qo	gpp_soco
0	50.48	-	223.81
1	52.97	-	244.00
2	62.67	-	299.85
3	41.99	-	-
4	70.21	-	-
5	68.51	-	-
6	109.42	-	-
7	102.79	-	-
8	40.54	-	-
9	37.58	-	-

CPU for instance size 34
inst	gpp	gpp_qo	gpp_soco
0	72.93	-	-
1	97.37	-	-
2	114.48	-	-
3	177.49	-	-
4	67.44	-	-
5	175.69	-	-
6	139.91	-	-
7	184.22	-	-
8	30.00	-	-
9	162.53	-	-

CPU for instance size 35
inst	gpp	gpp_qo	gpp_soco
0	226.82	-	-
1	78.86	-	-
2	151.18	-	-
3	121.25	-	-
4	174.69	-	-
5	299.84	-	-
6	-	-	-
7	-	-	-
8	-	-	-
9	-	-	-