Facility location : not so difficult (with the proper tools)

In a previous post, I generated a few capacitated facility location instances (CFLP) and I ran these through MIP solvers. The instances were solved pretty quickly overall. In a comment, professor Matteo Fischetti suggested I compare my results with some instances from the literature, which I did. Overall, the results are quite fast; CPLEX takes only 21 minutes on average to solve the largest instances (1000 facilities, 1000 customers). When the paper was published (received for publication in 2007) these problems were intractable.

Experiments & Results

For this test, I used the 100 instances from Avella & Boccia (2009). These are grouped in 5 sets of 20 instances each, having between 300 and 1000 facilities and customers, respectively. The data for the instances are available here; I simply wrote a program to parse the input file and send them to the solver. For those who wonder, I did check that the reported optimal values in Avella & Boccia match with the values I got in my tests. Each instance is run on CPLEX 12.6.2 with default parameters on a recent 4-core machine. I computed the geometric means of solution times (in seconds) for each group of 20 instances:

CFLP results from Avella & Boccia (2009)

The 300 x 300 instances are solved pretty quickly, with 9 seconds on average. The 300 x 1000 and 500 x 500 are solved under a minute of run times and even the largest only take 21 minutes on average (the longest takes about 56 minutes). Interestingly, 35% of the 300×1000 instances are solved directly at the root node through a combination of implied bound cuts and heuristics.

What do these results mean?

If we refer to the more direct application of CFLP, that is, deciding the location of warehouses or production facilities in a supply chain, even 300 facilities is a pretty large number. Also, as facility location is considered a strategic problem, 20 minutes to get an optimal solution is very acceptable. For direct application purposes in the supply chain domain, the solvers are performing well enough that customized algorithms are not necessary. This being said, the CFLP is often embedded as a subproblem in larger supply chain network design problems, and as such, specialized algorithms may still be necessary in some specific contexts.

Of course, these results benefit from the tremendous advances in both hardware and software. It merely shows that the state-of-the-art tools used for optimization are getting better, and they are improving pretty fast. I also ran the tests on Gurobi and the results are pretty similar.

[1] P. Avella and M. Boccia. A cutting plane algorithm for the capacitated facility location problem. Computational Optimization and Applications, 43(1):39–65, 2009.

Speak Your Mind

*