Facility location: results for a nonlinear model with random instances


Results obtained using Gurobi for solving a nonlinear Facility Location Problem (FLP), using the models described in Mathematical Optimization: Solving Problems using Python and Gurobi.

Parameters used: number of facilities is 10% of the number of customers.

CPU time limited to 300 seconds. (Click on values for selecting data to display.)

Benchmark instances analysed
Instance familyTypeDescription
Num.Int=2 random Number of linear segments in the approximation: 2
Num.Int=5 random Number of linear segments in the approximation: 5
Num.Int=10 random Number of linear segments in the approximation: 10
Num.Int=20 random Number of linear segments in the approximation: 20
Num.Int=50 random Number of linear segments in the approximation: 50
Num.Int=100 random Number of linear segments in the approximation: 100
Num.Int=200 random Number of linear segments in the approximation: 200
Num.Int=500 random Number of linear segments in the approximation: 500
Num.Int=1000 random Number of linear segments in the approximation: 1000

FLP: results for a nonlinear model with random instances

Linearization with 500 segments.

Legend for columns in the next tables
LabelDescription
mselect multiple selection model
cc_dis disaggregated convex combination model
cc_dis_log disaggregated convex combination model with a logarithmic number of variables
cc_agg (aggregated) convex combination model
cc_agg_log (aggregated) convex combination model with a logarithmic number of variables
sos model using sos constraints of type 2
(click on values for detailed output)

chart
Average CPU per instance size, Num.Int=500
sizemselectcc_discc_dis_logcc_aggcc_agg_logsos
10 0.04 0.05 0.13 0.18 0.09 0.01
20 0.08 0.11 0.27 0.50 0.25 0.02
50 0.61 2.97 1.01 1.57 0.42 0.05
100 8.07 51.13 1.79 2.78 1.15 0.13
200 - - 5.20 4.76 2.57 0.30
500 - - 26.27 29.08 11.69 2.15
1000 - - - - 85.19 18.63

CPU for instance size 10
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.04 0.05 0.12 0.15 0.12 0.02
1 0.04 0.04 0.23 0.19 0.05 0.01
2 0.04 0.05 0.11 0.18 0.13 0.01
3 0.05 0.05 0.11 0.18 0.05 0.01
4 0.04 0.06 0.12 0.15 0.08 0.01
5 0.05 0.06 0.09 0.17 0.14 0.01
6 0.04 0.06 0.06 0.23 0.12 0.02
7 0.04 0.07 0.09 0.24 0.05 0.01
8 0.04 0.05 0.10 0.17 0.09 0.01
9 0.04 0.05 0.24 0.16 0.04 0.02

CPU for instance size 20
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.08 0.10 0.29 0.45 0.30 0.02
1 0.07 0.11 0.21 0.53 0.23 0.02
2 0.08 0.11 0.23 0.55 0.37 0.01
3 0.07 0.10 0.31 0.50 0.18 0.02
4 0.09 0.11 0.25 0.45 0.38 0.01
5 0.09 0.11 0.25 0.52 0.16 0.02
6 0.09 0.13 0.43 0.51 0.25 0.03
7 0.08 0.09 0.23 0.52 0.22 0.01
8 0.08 0.10 0.26 0.47 0.22 0.01
9 0.08 0.10 0.25 0.48 0.20 0.02

CPU for instance size 50
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.32 0.24 0.21 0.45 0.07 0.02
1 0.42 2.27 0.78 1.74 0.53 0.05
2 0.96 9.58 0.91 1.37 0.38 0.05
3 0.38 2.49 1.55 1.96 0.32 0.04
4 1.84 1.40 1.01 1.31 0.40 0.05
5 0.40 1.01 1.08 1.50 0.73 0.05
6 0.38 0.70 1.14 1.74 0.44 0.04
7 0.58 7.47 1.21 1.41 0.27 0.05
8 0.38 3.30 1.23 2.03 0.47 0.04
9 0.46 1.28 0.94 2.19 0.63 0.06

CPU for instance size 100
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.48 0.31 0.32 0.69 0.15 0.04
1 5.15 38.45 2.19 3.50 1.24 0.12
2 7.93 18.63 0.73 3.35 1.08 0.12
3 1.80 32.49 2.34 3.13 1.37 0.13
4 6.77 12.63 1.63 1.90 1.25 0.11
5 19.96 36.79 1.92 2.98 1.20 0.14
6 0.58 9.30 1.51 3.12 1.00 0.10
7 7.37 165.28 2.47 3.54 1.42 0.29
8 0.81 13.44 1.82 2.09 1.16 0.14
9 29.86 183.95 2.97 3.46 1.66 0.13

CPU for instance size 200
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 273.75 282.39 4.75 3.47 2.51 0.30
1 - - 4.64 6.19 2.32 0.26
2 - - 5.81 5.58 3.32 0.31
3 - - 4.77 4.81 3.09 0.37
4 - - 4.55 4.02 3.02 0.35
5 - - 3.19 4.90 2.07 0.27
6 - - 3.59 5.37 2.39 0.29
7 - - 8.77 5.41 2.99 0.29
8 - - 6.81 4.93 1.85 0.32
9 - - 5.08 2.95 2.15 0.24

CPU for instance size 500
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 - - 24.00 12.01 8.70 1.77
1 - - 28.19 20.75 12.17 1.72
2 - - 21.30 58.28 19.37 2.27
3 - - 17.53 30.46 10.13 1.96
4 - - 42.79 12.91 15.31 1.83
5 - - 5.16 9.82 2.51 0.95
6 - - 26.01 10.64 11.17 1.66
7 - - 46.19 18.81 13.99 3.19
8 - - 34.49 110.37 14.21 4.86
9 - - 17.00 6.79 9.33 1.27

CPU for instance size 1000
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 - - 273.28 277.95 110.12 25.31
1 - - 161.26 - 62.46 10.93
2 - - 263.95 - 116.91 17.74
3 - - 251.88 - 133.77 37.38
4 - - 196.46 - 63.38 10.75
5 - - 276.46 - 147.59 33.79
6 - - - - 63.90 14.37
7 - - - - 60.42 13.10
8 - - - - 79.68 18.41
9 - - - - 13.63 4.53