There has been a lot of speculation over the years about the quality of the optimization solvers in SAS/OR, in particular the mixed integer linear optimization (MILP) solver. Measuring the performance of optimization solvers and comparing different solvers on a test set is a crucial part of modern optimization solver development. For MILP the standard test set is the MIPLIB2010 set, which was assembled from submissions by academics and industry practitioners. It contains a wide variety of problems from easy to hard to unsolved.
Based on this test set Hans Mittelmann is compiling a regular comparison of solvers using different subsets of the MIPLIB2010 set. These are meant to measure different aspects of the solution process. At the recent INFORMS Annual Meeting in Nashville we presented detailed results for all of these categories for the first time. Here we reprint these results for future reference, along with some commentary.
Hardware
We have 96 nodes each with 128GB of RAM and 2 Intel(R) Xeon(R) E5-2630 v3 CPUs with 8 cores each running at 2.40GHz. We run each benchmark set with the same options as Hans Mittelmann does. Note that our hardware is quite a bit slower than what he is using.
Software
We are using the latest release of SAS as of November 22, 2016: SAS 9.4M4 with SAS/OR 14.2. The operating system is Redhat Enterprise Linux 6.5.
The time averages are 10-second shifted geometric means over all instances. Timeouts and failures are counted at the time limit. Deterministic parallel mode was used for the threaded MILP tests.
MIPLIB benchmark set (87 instances, 2 hour time limit)
This set has been the backbone of all MILP benchmarking efforts for the last 6 years. Many of the instances require special techniques to solve them.
1 thread
Solved: 81 out of 87
Average time (s): 240s
4 threads
Solved: 85 out of 87
Average time (s): 121s
12 threads
Solved: 82 out of 87
Average time (s): 95s
Since this is a very small set it is easy to overtune the solvers to perform well. To counter this we ran our solver with 16 other random seeds and took the averages. They are:
1 thread, average of 17 runs
Solved: 82 out of 87
Average time (s): 235s
4 threads, average of 17 runs
Solved: 85 out of 87
Average time (s): 113s
12 threads, average of 17 runs
Solved: 84 out of 87
Average time (s): 84s
This shows that our solver isn't overtuned since the default run is actually quite a bit unlucky, especially in the 12 thread run.
MIPLIB solvable set (214 instances, 2 hour time limit, 12 threads)
These instances are solvable by a commercial MILP solver in an hour on a standard machine.
12 threads
Solved: 170 out of 214
Average time (s): 261s
MIPLIB feasibility set (33 instances, 1 hour time limit, 4 threads)
These instances are solved only to find the first feasible solution. The quality of the solution isn't measured.
Solved: 27 out of 33
Average time (s): 114s
MIPLIB infeasibility set (19 instances, 1 hour time limit, 4 threads)
All of these instances are infeasible. The task is to prove this infeasibility in the shortest time possible.
Solved: 18 out of 19. Only the huge and LP infeasible zib02 instance was not solved.
Average time (s): 47s
MIPLIB pathological set (45 instances, 3 hour time limit, 12 threads)
These instances are typically very hard and have some special feature: numeric instability, size, large trees.
Solved: 24 out of 45
Average time (s): 1956s
You can get the slides of our INFORMS 2016 talk here.
Finally, here are all the data in a table:
| Test set | Solved | Average time (s) |
|---|---|---|
| Benchmark (1 thread) | 81 out of 87 | 240 |
| Benchmark (1 thread, average of 17 runs) | 82 out of 87 | 235 |
| Benchmark (4 threads) | 85 out of 87 | 121 |
| Benchmark (4 threads, average of 17 runs) | 85 out of 87 | 113 |
| Benchmark (12 threads) | 82 out of 87 | 95 |
| Benchmark (12 threads, average of 17 runs) | 84 out of 87 | 84 |
| Solvable (12 threads) | 170 out of 214 | 261 |
| Feasibility | 27 out of 33 | 114 |
| Infeasibility | 18 out of 19 | 47 |
| Pathological | 24 out of 45 | 1956 |
MIPLIB2017
If you have some difficult or interesting MILP instances and you want to shape the future of mixed integer optimization research, then please submit your instances to MIPLIB2017. SAS/OR will be participating in that project along with other leading commercial and open source MILP developers.
