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 5 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=5
sizemselectcc_discc_dis_logcc_aggcc_agg_logsos
10 0.00 0.00 0.00 0.00 0.00 0.00
20 0.01 0.00 0.00 0.00 0.00 0.00
50 0.01 0.01 0.01 0.02 0.01 0.01
100 0.02 0.03 0.04 0.03 0.03 0.02
200 0.10 0.14 0.17 0.16 0.15 0.07
500 0.87 1.65 2.03 1.90 1.67 0.96
1000 9.78 15.32 16.34 17.29 15.10 13.14

CPU for instance size 10
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.01 0.00 0.00 0.00 0.01 0.01
1 0.00 0.01 0.00 0.00 0.01 0.00
2 0.00 0.00 0.01 0.00 0.00 0.00
3 0.01 0.00 0.00 0.00 0.00 0.00
4 0.00 0.01 0.01 0.01 0.00 0.00
5 0.00 0.01 0.00 0.00 0.00 0.00
6 0.00 0.00 0.00 0.00 0.01 0.01
7 0.01 0.00 0.00 0.00 0.00 0.01
8 0.00 0.01 0.01 0.00 0.01 0.00
9 0.00 0.00 0.00 0.00 0.00 0.00

CPU for instance size 20
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.01 0.00 0.01 0.00 0.01 0.01
1 0.01 0.00 0.01 0.00 0.01 0.01
2 0.00 0.01 0.00 0.01 0.00 0.00
3 0.00 0.00 0.00 0.01 0.00 0.00
4 0.01 0.00 0.01 0.00 0.00 0.01
5 0.01 0.00 0.00 0.00 0.00 0.01
6 0.01 0.00 0.01 0.00 0.01 0.00
7 0.01 0.01 0.00 0.00 0.01 0.00
8 0.01 0.01 0.00 0.00 0.00 0.00
9 0.01 0.00 0.00 0.00 0.01 0.00

CPU for instance size 50
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.02 0.00 0.00 0.01 0.00 0.00
1 0.00 0.00 0.00 0.01 0.01 0.01
2 0.02 0.01 0.01 0.02 0.02 0.02
3 0.01 0.00 0.01 0.02 0.01 0.01
4 0.02 0.02 0.02 0.02 0.01 0.00
5 0.01 0.01 0.01 0.02 0.00 0.00
6 0.01 0.01 0.01 0.01 0.02 0.01
7 0.01 0.01 0.02 0.03 0.01 0.00
8 0.01 0.01 0.01 0.00 0.00 0.00
9 0.01 0.01 0.02 0.01 0.00 0.01

CPU for instance size 100
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.01 0.01 0.01 0.02 0.01 0.01
1 0.02 0.04 0.04 0.03 0.03 0.03
2 0.01 0.03 0.04 0.03 0.04 0.02
3 0.03 0.04 0.05 0.03 0.04 0.02
4 0.02 0.05 0.06 0.04 0.04 0.03
5 0.05 0.04 0.05 0.04 0.03 0.01
6 0.02 0.02 0.01 0.02 0.02 0.03
7 0.02 0.04 0.03 0.02 0.03 0.01
8 0.02 0.04 0.05 0.04 0.04 0.03
9 0.02 0.02 0.03 0.04 0.05 0.01

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

CPU for instance size 500
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 0.93 1.43 2.24 2.14 2.20 1.47
1 0.91 1.58 2.12 2.05 1.55 1.19
2 0.93 2.10 2.68 2.11 2.19 1.18
3 0.78 1.91 1.97 1.83 2.15 0.92
4 0.85 2.21 3.24 3.04 1.98 0.96
5 0.57 0.56 0.88 0.77 0.58 0.43
6 0.75 1.64 1.88 1.42 1.90 0.93
7 1.62 2.14 2.62 2.70 1.98 1.28
8 0.72 1.72 1.64 1.85 1.27 0.71
9 0.59 1.18 1.03 1.07 0.92 0.51

CPU for instance size 1000
instmselectcc_discc_dis_logcc_aggcc_agg_logsos
0 11.51 23.09 26.04 21.58 20.66 19.58
1 8.53 14.77 21.40 17.18 12.38 10.72
2 10.13 16.88 16.73 16.05 16.55 12.69
3 9.14 18.61 19.98 36.55 15.17 23.34
4 7.02 7.06 6.27 11.19 11.17 6.81
5 12.80 21.37 13.49 20.55 22.44 10.91
6 10.08 16.17 16.75 12.29 18.07 15.57
7 8.91 15.09 16.20 12.87 14.01 14.01
8 14.87 15.34 20.11 20.19 15.92 14.53
9 4.79 4.84 6.45 4.42 4.62 3.26