Facility Location Optimization with capacity constraints- Customers -1000 & Potential facilities 1000 - not reaching solutions

Hi,

The code for facility location optimization with capacity constraints takes distancematrix and demand as input from csv files and computes the best location, however works only for small set of data upto 100 to 200 customers. When the input file has more than 1000 potential customers and warehouses, the code never reaches to the solution.

Code output from one of the test runs

Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5958 rows, 987042 columns and 5404972 nonzeros
Model fingerprint: 0x97f4b50a
Variable types: 986049 continuous, 993 integer (993 binary)
Coefficient statistics:
Matrix range [1e-01, 6e+03]
Objective range [9e-04, 1e+07]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+03]
Found heuristic solution: objective 6.150691e+09
Presolve removed 3972 rows and 0 columns
Presolve time: 3.70s
Presolved: 1986 rows, 987042 columns, 1973091 nonzeros
Variable types: 986049 continuous, 993 integer (993 binary)

Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 6.833120e+02 0.000000e+00 6s

Starting sifting (using dual simplex for sub-problems)...

Iter Pivots Primal Obj Dual Obj Time
0 0 infinity 0.0000000e+00 6s
1 10446 6.6748958e+09 2.3585522e+04 6s
2 14919 4.9899783e+09 4.1455484e+04 6s
3 17776 2.8523804e+08 4.8475126e+04 7s
4 20353 2.8077755e+08 4.9750477e+04 7s
5 22941 7.2940331e+07 4.1613445e+06 7s
6 25691 7.2930265e+07 6.2841497e+06 7s
7 28437 7.2916801e+07 8.6457718e+06 7s
8 31160 7.2907582e+07 1.1163534e+07 7s
9 33858 7.2903111e+07 1.4640264e+07 7s
10 36869 7.2891198e+07 2.5233406e+07 8s
11 39760 7.2887861e+07 5.4543883e+07 8s
12 42652 7.2886643e+07 6.3314659e+07 8s
13 45561 7.2886591e+07 7.2821485e+07 8s
14 48418 7.2886589e+07 7.2864502e+07 8s
15 50875 7.2886589e+07 7.2880277e+07 8s

Sifting complete

52940 7.2886611e+07 0.000000e+00 0.000000e+00 9s

Root relaxation: objective 7.288661e+07, 52940 iterations, 2.88 seconds (2.25 work units)

0 0 7.2887e+07 0 838 6.1507e+09 7.2887e+07 98.8% - 9s
H 0 0 3.710003e+09 7.2887e+07 98.0% - 10s
H 0 0 3.700022e+09 7.2887e+07 98.0% - 11s
H 0 0 8.016805e+07 7.2887e+07 9.08% - 21s
0 0 7.2900e+07 0 646 8.0168e+07 7.2900e+07 9.07% - 24s
H 0 0 8.016677e+07 7.2900e+07 9.06% - 41s
0 0 7.2900e+07 0 646 8.0167e+07 7.2900e+07 9.06% - 42s
0 0 7.2911e+07 0 588 8.0167e+07 7.2911e+07 9.05% - 44s
H 0 0 8.016571e+07 7.2911e+07 9.05% - 58s
0 0 7.2911e+07 0 576 8.0166e+07 7.2911e+07 9.05% - 59s
0 0 7.2911e+07 0 579 8.0166e+07 7.2911e+07 9.05% - 59s
0 0 7.2919e+07 0 526 8.0166e+07 7.2919e+07 9.04% - 62s
0 0 7.2919e+07 0 526 8.0166e+07 7.2919e+07 9.04% - 63s
0 0 7.2925e+07 0 494 8.0166e+07 7.2925e+07 9.03% - 66s
0 0 7.2925e+07 0 494 8.0166e+07 7.2925e+07 9.03% - 66s
0 0 7.2931e+07 0 499 8.0166e+07 7.2931e+07 9.02% - 72s
0 0 7.2931e+07 0 500 8.0166e+07 7.2931e+07 9.02% - 73s
0 0 7.2937e+07 0 516 8.0166e+07 7.2937e+07 9.02% - 78s
0 0 7.2937e+07 0 513 8.0166e+07 7.2937e+07 9.02% - 80s
0 0 7.2941e+07 0 501 8.0166e+07 7.2941e+07 9.01% - 84s
0 0 7.2941e+07 0 477 8.0166e+07 7.2941e+07 9.01% - 266s
H 0 0 8.016073e+07 7.2941e+07 9.01% - 284s
H 0 2 8.015371e+07 7.2941e+07 9.00% - 518s
0 2 7.2941e+07 0 475 8.0154e+07 7.2941e+07 9.00% - 518s
1 4 7.2941e+07 1 477 8.0154e+07 7.2941e+07 9.00% 66.0 521s
3 8 7.2941e+07 2 477 8.0154e+07 7.2941e+07 9.00% 91.3 530s

Jaromił Najman

Gurobi Staff

March 31, 2022 08:24
Edited

You model is pretty large and even after presolve it has ~2 million non zeros, which might be an indicator that the problem is very complex even thou it has "only" 993 binary variables.

When the input file has more than 1000 potential customers and warehouses, the code never reaches to the solution.

What exactly do you mean by "never"? Usually problems of this size and complexity require more than an hour to converge to satisfactory MIPGap. For this particular model, you could increase the desired MIPGap to, e.g., 0.1% or 1%, instead of the default 0.01%. This is usually enough for most practical applications.

In addition, you should try experimenting with the Sifting parameter. You could also experiment with the MIPFocus parameter to test different optimization strategies and the No Relaxation Heuristic to find feasible points earlier. You can find a list of most important parameters for MIPs in our documentation.

Best regards,
Jaromił

Facility Location Optimization with capacity constraints- Customers -1000 & Potential facilities 1000 - not reaching solutions

Comments

Didn't find what you were looking for?