Facility location : mistake, issue and results

About two weeks ago, I generated a few capacitated facility location instances (CFLP) for some students to play with. When I ran these through the CPLEX and Gurobi solvers, all of them were solving very quickly. Gurobi in fact seemed to find the optimal solution during the presolve stage. I made a quick blog post about it, but I should have been more thorough in my validation of results.

I am commited to provide accurate results on this blog, so please accept my most sincere apologies for not validating sufficiently enough before posting it here. I also thank Professor Andrea Lodi and his students for spotting the source of the error in the data files. I also wish to thank Professor Matteo Fischetti for expressing doubts about the results of my previous post.

Source of the error

When preparing test problems like this, I usually create LP files instead of creating instances in memory as it is easier to distribute them to students and to run the models through different solvers. I also found that students have a much easier time reading LP files rather than MPS. The LP format has its disadvantages, however, as it can be interpreted differently between solvers. In particular, I forgot to put a space between the coefficient and the last variable in a constraint (for instance 1.255Y1 <= 1 instead of 1.255 Y1 <= 1).  CPLEX interprets it the way it was intended and separates the coefficient 1.255 from the variable Y1 even though there is no space, but Gurobi assumes 1.255Y1 is a new variable that is different from Y1. To be clear, the mistake is mine, not Gurobi’s, but differences in interpretation are sometimes difficult to spot.

When I generated the models, I ran them through CPLEX first, and checked the solutions. Then, out of curiosity, I ran the same set of models through Gurobi, and the results were much faster. I assumed wrongly that the models were fine, so I did not check the solutions out of Gurobi. What is very ironic is that I wrote a blog post about this very issue less than two years ago and I failed to follow my own advice this time. The corrected LP files are now available here.

Corrected results

Running the corrected moels yields a different picture. Most models are solved quite quickly and efficiently by the solvers, abeit not during the presolve stage.

  • 38% of the models were solved at the root node, usually by a combination of cuts and heuristics;
  • 68% of the models are solved in less than a second;
  • 78% of the models are solved in less than a minute.

The largest instance that is solved at the root node has 75 facilities and 250 customers, while the largest instances that are solved in less than a second are of sizes 75 x 250 and 80 x 150, respectively. The largest instances in the set (100 facilities and 2000 customers) take about 1 to 2 hours to solve on Gurobi. CPLEX is in the same ballpark in terms of solving times.

Is that fast?

The interesting question that arises is “are these solving times fast enough?” to be actually used in practice. There are many potential applications to the CFLP, but I will focus on supply chain management. While benchmark instances are sometimes much larger than the models solved in this test, I have never encountered or heard of a company who wanted to locate or relocate 100 or more facilities simultaneously. Usually, the number of potential locations is much smaller, but the problem is made complex by adding more types of decision such as alternate transport mode selection, alternative capacities or technologies and facilities, and so on. These interdependent decisions, more than sheer size of the instance, makes the problem much more difficult to solve.

Of course, in general, faster is always better, and there is place for faster customized algorithms that solve the biggest instances in a few seconds. But if you are working on a project to relocate 100 warehouses, my bet is that you can wait 90 minutes to get the optimal solution.

Comments

  1. Wow! Gurobi allows variable names to start with a digit? Off the top of my head, I can’t think of any programming language (or any modeling language) I’ve ever used that allows that. I would have expected the missing space either to be handled as CPLEX did or to result in an exception being raised.

    • Ed Rothberg says:

      File formats aren’t programming languages, though. Check out the stein family of models from MIPLIB, where the variables are named 0001, 0002, etc. MPS format will accept nearly any string of characters as a variable name.

      We print a warning when a variable name in a .lp file starts with a number. Rejecting such models outright would reduce compatibility between MPS and LP formats.

Trackbacks

  1. […] a previous post, I generated a few capacitated facility location instances (CFLP) and I ran these through MIP […]

Speak Your Mind

*