3
$\begingroup$

So I am solving a purely integer linear optimization problem with Pyomo on a single computer (core i-5, 12 GB RAM). The problem has around 10000 variables and 300 constraints. For doing this, I am calling the solver GLPK. However, I find that the problem cannot be solved in a timely manner. Yesterday I let it run for 14 hours straight and, during that time, only a feasible solution was found (failed to certify optimality). Is this expected for problems of this size given my hardware? What problem size should I expect to be able to manage within 1-5 hours? I have no experience with this practical side and thus my intuition of what is a big problem could be flawed.

Curiously enough, the relaxation of the same problem is solved within a second. I know that I cannot expect the solution time to be roughly the same on both cases but the difference is so much that it feels like I am doing something wrong.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Check this post: yalmip.github.io/slowmilp $\endgroup$
    – Kuifje
    Feb 7 at 19:36
  • $\begingroup$ Thanks @Kuifje for the important comment. Apparently, in this case it was just that an issue of glpk with the problem: Cbc was done with it in 12 seconds. $\endgroup$
    – John D
    Feb 7 at 20:25

1 Answer 1

Reset to default
6
$\begingroup$

This very much depends on the solver (glpk) and not so much on the modelling language (Pyomo). In my experience, glpk is not among the best free ILP solvers. You may try cbc, which I think is somewhat better than glpk.

Next step is a licensed solver like cplex, gurobi, or something in that calibre.

Regarding expected problem sizes solvable in reasonable, it is quite difficult to predict solution time from size alone. It also depends on the strength of the LP relaxation, density of the constraint matrix, how “heuristic-friendly” the model is, and many other things.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer @Sune. Do you think these running times are weird? Could you please share some experience of yours about running times for problems of this size? I really have no idea. $\endgroup$
    – John D
    Feb 7 at 19:33
  • $\begingroup$ @JohnD everything about MILP running times is weird. But no, glpk is not great and you can spend a long time waiting for it to prove optimality. $\endgroup$
    – Sune
    Feb 7 at 19:38
  • 1
    $\begingroup$ Thanks! Switching to cbc made the problem solvable in 13 seconds. Amazing! I am moving away from glpk ... :) $\endgroup$
    – John D
    Feb 7 at 20:22

Your Answer

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