I am looking for a reliable open source solver to solve LP and MILP (with a few thousand variables). How can I evaluate the performance of a given solver for a particular use case?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
4
The pitfall is to only focus on performance, will ignoring scalability, maintenance, integration and reliability. Some of these are easier to measure than others:
- Performance: if I give 2 constraint solvers a - for example a VRP - dataset with 100 visits, which one is better after 5 minutes. See Marco's answer on this question and my blog post on benchmarking.
- Scalability: if I give a constraint solver 3 VRP datasets, one with 100 visits, one with 1000 and one with 10 000 visits, for 5 minutes each. How does it scale up? Don't just focus on solution quality, also look at memory consumption.
- Maintenance: How easy is it to write a constraint? How easy is it to hire juniors and train them to write constraints? Most business constraints change often. Some even completely pivot their business problem.
- Integration: How easy does it integrate with other Java/C++/Python/Kotlin/Scala/... libraries. Can you reuse an existing date & time API (just watch this video why you too will fail at writing your own)? Is available in the library repository (Maven Central / Ruby Gems / Nuget / ...)?
- Reliability: Does it fail-fast (or pretend nothing is wrong when things go very wrong)? Does it eat exceptions? Does debug or even trace logging show you what's going on inside the black box?
And that's just the tip of the iceberg. See also my slides on What makes an open source project mature? which covers fun topics such as which licenses are open source ok to build your proprietary business on and which are not.
-
2$\begingroup$ I liked the slides, thanks. Do you have some references for the claim that BSD & MIT are widely accepted, while EPL & MPL are disliked by legal departments? $\endgroup$ Jul 5, 2019 at 7:34
-
2$\begingroup$ No, just personal experience I am afraid. Note that EPL & MPL are disliked by some legal departments, but those aren't the majority. Same for LGPL. It doesn't make much sense to me though. The far majority do ban import statements to GPL libs (to avoid having to release as GPL themselves, which does make sense to me). $\endgroup$ Jul 5, 2019 at 8:22
-
2$\begingroup$ Thanks for the info nonetheless. Most of the software I use (as dependencies) is MIT licensed, so I should be future proof for potential commerical ventures. The exception being COIN OR solvers that are often EPL licensed. $\endgroup$ Jul 5, 2019 at 8:41
-
1$\begingroup$ Yes, the survivors usually use non-exotic licenses (including MIT, ASL & EPL) or have long since switched. When I started OptaPlanner in 2006, it had no license (it was very amateuristic at the time - things have changed a lot) and I ended up with ASL (Apache Software License) in 2007 due following the practices of other successful open source projects. In hindsight, I got lucky, it was the best choice :) ASL is MIT/BSD with patent protection for users - and it also has trademark (= reputation) abuse protection for the authors/community. $\endgroup$ Jul 5, 2019 at 9:39
$\begingroup$
$\endgroup$
1
For the evaluation of several solvers you need
- several solvers
- a testset of instances
- a performance measure
Several solvers you probably already have in mind. The testset of instances is a bit tricky, because ideally, this is a not too small, not too large, not trivial, not too hard, still representative set of instances (that is, LPs or MIPs) that you will later see when solving actual instances. There are several ideas how to choose such a testset, I think the MIPLIB2010 paper is still a very good reference for this. Then you run your solvers on the testset, gather the results, and plot them in a way that you can interpret them. For performance (mainly: runtime to optimality, or runtime to a "good" solution) I would use performance profiles as described by Dolan and More. They are kind of an industry standard in the optimization community.
-
2$\begingroup$ On performance profiles the note of Gould & Scott is useful, which shows that relative performance has to judged carefully. $\endgroup$ Jul 5, 2019 at 11:24
$\begingroup$
$\endgroup$
2
If you're just trying to "evaluate performance" to decide what to use, then avoid LP_SOLVE and GLPK (and the results above are also indicative of their LP performance) and the solution time for LPs (and MIPs, so long as they aren't really nasty) won't be an issue. I suggest Clp/HiGHS for LP and HiGHS/SCIP for MIP.
-
1$\begingroup$ GLPK has the advantage that it's open-source (while SCIP is not) and that it can be customized easily with callbacks (which is more difficult with CBC?). $\endgroup$ Jul 8, 2019 at 6:33
-
1$\begingroup$ HiGHS is so much better than GLPK and CBC, and soon will have callbacks as well $\endgroup$ Feb 16, 2022 at 9:25
$\begingroup$
$\endgroup$
2
Meindl and Templ published the paper Analysis of commercial and free and open source solvers for linear optimization problems in 2012 in which they investigate the running times and solving percentages of various solvers. The main table is replicated below. \begin{array}{cr}\hline\sf{solver}&\sf{running\,time}&\sf{instances\,solved}&\sf{solved}\,(\%)\\\hline\sf CBC&10.20&41&47.13\\\sf{CPLEX}&1.45&73&83.91\\\sf{GLPK}&22.11&3&3.45\\\sf{GUROBI}&1.00&77&88.51\\\sf{LP\text{_}SOLVE}&19.40&5&5.75\\\sf{SCIP\,\text{-}\,C}&3.76&63&72.41\\\sf{SCIP\,\text{-}\,L}&6.40&52&59.77\\\sf{SCIP\,\text{-}\,S}&5.33&57&65.52\\\sf{XPRESS}&1.29&74&85.06\\\hline\end{array}
The following data are based on data from the 9th of January of 2012. The following solvers have been used in the test on PC with an Intel Xeon X5680 processor with 2 x 6 cores, 32 gigabytes of RAM on a Linux 64-bit operating system. A total of 9 different solvers were compared using a single thread.
You can thus try to replicate some of the analysis used in the paper where possible.
Reference
[1] Meindl, B., Templ, M. (2012). Analysis of commercial and free and open source solvers for linear optimization problems. Technische Universität Vienna, Austria. Available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455.3926&rep=rep1&type=pdf. [Accessed 5 July 2019].
answered Jul 5, 2019 at 7:21
-
3$\begingroup$ Too bad they didn't use geometric mean time instead. $\endgroup$– TLWJul 6, 2019 at 3:26
-
$\begingroup$ These results are now 10 years old, so don't include HiGHS or newer commercial solvers. Get proper up-to-date benchmark results from Mittelmann $\endgroup$ Feb 16, 2022 at 9:28