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 1000 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=1000
sizemselectcc_discc_dis_logcc_aggcc_agg_logsos
10 0.12 0.12 0.29 0.35 0.17 0.01
20 0.22 1.56 1.01 2.48 0.49 0.03
50 1.52 13.92 1.53 3.69 1.14 0.07
100 - - 4.35 6.09 1.83 0.18
200 - - 12.53 8.45 5.70 0.57
500 - - 62.70 - 20.04 3.16
1000 - - - - 131.32 21.66

CPU for instance size 10
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.12 0.14 0.54 0.31 0.18 0.02
1 0.13 0.13 0.20 0.42 0.22 0.00
2 0.12 0.14 0.21 0.43 0.09 0.01
3 0.12 0.16 0.26 0.33 0.18 0.00
4 0.12 0.09 0.25 0.32 0.21 0.00
5 0.07 0.09 0.52 0.41 0.20 0.01
6 0.13 0.14 0.23 0.44 0.19 0.01
7 0.12 0.15 0.21 0.40 0.07 0.00
8 0.12 0.09 0.22 0.25 0.19 0.02
9 0.13 0.08 0.26 0.24 0.20 0.00

CPU for instance size 20
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.16 1.50 1.74 1.59 0.42 0.04
1 0.17 2.02 0.58 1.83 0.19 0.03
2 0.16 0.99 1.42 1.38 0.75 0.05
3 0.15 0.24 0.79 3.03 0.46 0.04
4 0.25 0.45 0.65 1.41 0.79 0.03
5 0.29 0.56 0.60 3.16 0.59 0.03
6 0.28 3.44 1.55 5.09 0.20 0.04
7 0.29 4.30 0.56 1.52 0.63 0.03
8 0.22 0.29 0.58 3.95 0.19 0.04
9 0.24 1.86 1.60 1.81 0.67 0.02

CPU for instance size 50
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.44 0.33 0.45 1.08 0.13 0.03
1 0.66 7.21 1.55 4.88 1.57 0.08
2 2.27 25.57 0.82 2.97 0.75 0.08
3 0.67 8.25 0.80 4.07 1.39 0.08
4 1.78 4.88 2.37 2.52 0.86 0.08
5 0.69 2.17 1.29 3.18 1.66 0.08
6 0.42 8.39 1.64 5.29 1.50 0.08
7 6.80 59.71 1.58 2.38 0.87 0.09
8 0.66 9.02 1.52 5.25 1.42 0.07
9 0.86 13.68 3.32 5.29 1.25 0.08

CPU for instance size 100
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.73 0.80 0.97 1.92 0.28 0.05
1 16.30 270.13 4.83 8.50 1.95 0.19
2 8.28 99.05 2.31 6.59 1.84 0.19
3 4.08 64.50 4.48 7.07 2.26 0.21
4 14.93 107.96 10.53 3.77 2.15 0.19
5 27.95 231.40 4.99 6.03 1.86 0.18
6 1.20 5.78 4.05 8.09 1.88 0.18
7 286.36 285.22 3.79 7.14 2.36 0.21
8 - - 4.34 5.81 1.75 0.20
9 - - 3.23 5.94 2.01 0.20

CPU for instance size 200
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 - - 15.76 5.75 4.48 0.56
1 - - 14.97 13.24 4.57 0.51
2 - - 19.02 9.10 6.71 0.47
3 - - 8.86 7.90 6.64 0.70
4 - - 14.78 6.74 6.67 0.69
5 - - 12.73 8.23 4.31 0.48
6 - - 4.67 7.99 5.76 0.54
7 - - 6.92 8.38 6.95 0.52
8 - - 17.08 12.90 5.77 0.56
9 - - 10.48 4.26 5.14 0.64

CPU for instance size 500
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 - - 47.79 20.79 21.04 2.30
1 - - 76.58 96.86 19.94 3.20
2 - - 64.62 55.91 29.49 3.11
3 - - 76.18 17.04 13.56 2.76
4 - - 75.10 20.36 22.07 2.73
5 - - 11.31 27.39 4.58 1.58
6 - - 52.43 112.41 19.69 2.94
7 - - 116.01 32.70 25.93 4.34
8 - - 70.35 279.64 26.36 6.94
9 - - 36.60 - 17.76 1.72

CPU for instance size 1000
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 - - 288.39 - 117.73 40.12
1 - - - - 53.87 13.31
2 - - - - 110.30 17.36
3 - - - - 215.43 45.53
4 - - - - 127.41 9.96
5 - - - - 258.29 41.54
6 - - - - 127.56 11.57
7 - - - - 115.75 12.97
8 - - - - 158.96 18.54
9 - - - - 27.85 5.69