How good is the MILP solver in SAS/OR?

0

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 limite, 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.

Share

About Author

Imre Pólik

Principal Operations Research Specialist

Imre Pólik is an Optimization Solver Developer for SAS/OR, working on the linear and mixed-integer optimization solvers. He earned his M.S. in Mathematics from Eötvös University in Budapest, Hungary, and his Ph.D. in Mathematics from McMaster University, Hamilton, Ontario, Canada. He has worked for SAS since 2010, following a couple of years as a visiting assistant professor at Lehigh University.

Leave A Reply

Back to Top