9
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ Have you tried the COIN-OR solvers? $\endgroup$
    – LarrySnyder610
    Commented May 13, 2020 at 1:00
  • $\begingroup$ 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 $\endgroup$
    – S moran
    Commented May 13, 2020 at 1:12
  • $\begingroup$ Would you see MIPCL solver? It has a nice Python API and is open-source. Also, its performance is good. $\endgroup$
    – A.Omidi
    Commented May 13, 2020 at 11:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Haukinger
    Commented May 13, 2020 at 12:51
  • $\begingroup$ @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. $\endgroup$
    – S moran
    Commented May 13, 2020 at 13:23

3 Answers 3

Reset to default
8
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$
    – T_O
    Commented May 13, 2020 at 11:04
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.