MATP6620/DSES6760 Combinatorial Optimization and Integer Programming
Uncapacitated facility location problems with m facilities and n=3m customers. Results with a disaggregated formulation and with an aggregated formulation. Results with cplex cut generation, and with cplex cut generation turned off.
The disaggregated results are better than the aggregated results. The cut generation routines in cplex help the aggregated formulation considerably, but they don't make much difference to the disaggregated formulation. For smaller problems, the two formulations are comparable, with cut generation turned on. The aggregated formulation can't solve larger problems.
| m | time | nodes | simplex | |||
| uflRdisagg | ||||||
| 20 | 0.104137 | 0 | 480 | |||
| 40 | 4.13291 | 114 | 14048 | |||
| 60 | 24.1969 | 77 | 16998 | |||
| 80 | 393.583 | 1461 | 444491 | |||
| 100 | 4297.36 | 11001 | 3505958 | |||
| uflRagg | ||||||
| 20 | 0.269296 | 52 | 1368 | |||
| 40 | 7.65573 | 865 | 35026 | |||
| 60 | 257.869 | 25431 | 770770 | |||
| 80 | memory | |||||
| 100 | memory | |||||
| uflRdisagg | ||||||
| mipcuts=-1 | ||||||
| 20 | 0.07881 | 0 | 441 | |||
| 40 | 4.82521 | 144 | 16408 | |||
| 60 | 27.297 | 348 | 58013 | |||
| 80 | 371.534 | 1421 | 433540 | |||
| 100 | 3669.83 | 8348 | 2912548 | |||
| uflRagg | ||||||
| mipcuts=-1 | ||||||
| 20 | 1.23681 | 4871 | 21190 | |||
| 40 | 1919.65 | 3432040 | 17851487 | |||
| 60 | memory | |||||
| 80 | memory | |||||
| 100 | memory | |||||
| n=3m | ||||||
| most results are with at least four cplex calls running simultaneously | ||||||
| times in seconds on a 2008 mac pro with 8 processors | ||||||
| times with uflRdisagg look approximately exponential in m^2 | ||||||
| times with uflRagg grow even more quickly. | ||||||