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