Open source MILP solver for quick “good enough” solution

Question

I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained than optimality constrained. I have an academic version of gurobi and it is able to provide feasible, good enough solutions quite fast (a few minutes). I am looking for a solver that I can use in python that will return the best solution once it hits a max time limit.

I have been using google ORtools with the CBC and SAT integer solvers, but any time I try to invoke a time limit it starts solving and then either ignores the time limit or when it hits, because it hasn’t found the “optimal” solution it returns no solution.

Yes, I have been trying to get the CBC solver, it runs and goes through pre process and gets into primal / dual stuff but when it hits wall clock it says no optimal solution, but doesn’t even return a feasible one — S moran, May 13 '20 at 01:12
Would you see MIPCL solver? It has a nice Python API and is open-source. Also, its performance is good. — A.Omidi, May 13 '20 at 11:19
OR-Tools only ever returns the optimal solution at the end. To get non-optimal solutions, you have to look for the callback the presents the intermediate solutions and store one of those. — Haukinger, May 13 '20 at 12:51
@Haukinger, can you give any more explanation on that? I tried looking for some documentation, but what you described sounds exactly what I am looking for. — S moran, May 13 '20 at 13:23
@A.Omidi MIPCL seems to have disappeared from the internet, http://www.mipcl-cpp.appspot.com/ is error 404. — Nikos Kazazakis, May 13 '20 at 13:50
@Smoran I used the C# wrapper a while ago, but in python, there should be the same things... does this example help? https://github.com/google/or-tools/blob/554cbccaa95b4c11eced13f145de1bf468e1f919/ortools/sat/samples/solve_and_print_intermediate_solutions_sample_sat.py — Haukinger, May 13 '20 at 16:31
@Nikos Kazazakis, some days ago I check it and its host was true. The link I added is in the GitHub. Would you try this if it is interested? — A.Omidi, May 13 '20 at 16:33
@A.Omidi the snag is that MIPCL is not actually open source, so the GitHub repo doesn't have the solver. We used to be able to download it from the link mentioned on the GitHub page, but that's now error 404..! — Nikos Kazazakis, May 13 '20 at 16:47
@Nikos Kazazakis, you are right. it seems that the host is turned off!!! — A.Omidi, May 14 '20 at 04:06

score 8 · Accepted Answer · answered May 13 '20 at 10:39

8

When I use CBC from time to time, it returns the best solution it has found even if it runs into the time limit. I guess, in your case, it has not even found a feasible solution.

I call it this way:

cbc file.lp sec 600 solve printi csv solu mysolution.csv

On difficult binary problems, I had some success enabling zero-half cuts or adding more cuts then by default. Have you tried that?

answered May 13 '20 at 10:39

T_O

186
2

6

I cannot yet comment to other people's posts, so I post this here. Marco suggested SCIP. While SCIP is a great tool and might be helpful here, we have to keep in mind that SCIP's license is not as permissive as CBC's. If this were academic the author could use his academic Gurobi license. – T_O May 13 '20 at 11:04

Marco Lübbecke · Answer 2 · 2020-05-14T07:49:36.287

Interestingly enough, one of the best source-open (!= open source) solvers is often overlooked: SCIP (download here); there is a Python interface (PySCIPOpt), too.

The parameter you need is limits/time.

edit: right, SCIP comes with a license and is not entirely free. AFAIK, the price tag is small when you use it commercially, the revenues are used mainly to directly support and sustain the research and development.

score 3 · Answer 3 · answered May 13 '20 at 16:52

Depending on your time window, you could try compiling and running CBC in threaded mode. Time is key here because although CBC is many times faster in threaded mode, it takes forever to initialize each new thread, especially for problems that size.

If your time window is enough to account for the generation overhead, CBC could do the trick.

To be honest, however, once we start going to 1m+ variables, that's really pushing the limits of what open source is capable of.

Open source MILP solver for quick “good enough” solution

3 Answers3