19
$\begingroup$

I have a mixed integer programming problem. And I am current using GLPK as my solver. But I found that GLPK is good for Linear Programming problem, but for Mixed Integer programming, it requires much longer time, therefore doesn't meet our requirement. I am so seeking other software. Is there any other good open source tools to solve mixed integer programming problem with fast speed? Thanks!

Improve this question
$\endgroup$
2

5 Answers 5

Reset to default
17
$\begingroup$

If you want something open-source, you probably want to try COIN's CBC code (they also have a couple other MILP solvers, like a branch-and-price framework, or SYMPHONY).

Gurobi and CPLEX will be considerably faster, and as of the 2011 or 2012 INFORMS meeting, Gurobi was faster than CPLEX (though the performance metrics are of course problem dependent). On the MILPs solved in my thesis, Gurobi was approximately 15-100 times faster than CBC, and CPLEX was almost as fast as Gurobi, but very slightly slower (like 12-80 times faster).

Although the worst-case performance is indeed exponential, the execution time will depend heavily on problem structure. It's unlikely that you'll be able to solve an MILP with millions of variables unless you exploit special structure (maybe if it's a stochastic program that can be decomposed into many much smaller problems), but it's entirely possible to solve nontrivial MILPs with thousands of variables in under a minute. (Of course, it's also possible for these problems to take an hour or more to solve.)

As Brian Borchers notes, CPLEX and Gurobi both have free licenses available for some researchers, one of these two software packages would really be the best to use as a general-purpose MILP solver.

Improve this answer
$\endgroup$
8
$\begingroup$

Mixed integer linear programming problems are much harder to solve than linear programming problems. In terms of computational complexity, LP's can be solved in polynomial time while solving MILP is an NP-Hard problem. The known algorithms for solving MILP's have exponential worst case complexity.

There are other software packages for mixed integer linear programming that you could look at, including SCIP (free for academic use), CPLEX (commercial but has an academic licensing option) and GUROBI (also commercial with an academic licensing option.) One or more of these packages might be substantially faster than GLPK on your problems, but don't expect any of them to be nearly as fast at solving MILP as they are in solving similarly sized LP's.

Improve this answer
$\endgroup$
8
$\begingroup$

If you want to try a bunch of different solvers, give Julia's JuMP modeling framework a try. It lets you write your model as a JuMP model, and then switch out the solvers with one line of code. For example, for MILP problems you can choose from the Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi, and MOSEK solvers. Because of this, if you write it in JuMP, you can just try all the solvers that Geoff mentioned and see what works without having to write a bunch of code. Your own personal tests will be the best source of knowledge for what the fastest algorithms are for your problems.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Does the JuMP framework add much overhead? $\endgroup$
    – naught101
    Dec 12, 2016 at 6:03
  • 2
    $\begingroup$ No, JuMP is done via macros so it's at compile-time. In fact, what JuMP does it use macros to re-write code and use autodifferentiation to compute efficient functions for gradients, Jacobians, and Hessians, so it will be faster in cases where you would have otherwise not provided an analytical form for the gradient/Jacobian/Hessian. You can actually check via @code_llvm to check the resulting assembly code to see that the glue code is essentially nothing (this is also because Julia naively uses function pointers and the same bit arrays as C/Fortran). $\endgroup$
    – Chris Rackauckas
    Dec 12, 2016 at 6:07
  • $\begingroup$ @ChrisRackauckas What solver works better for nonlinear problems with nonlinear constraints? $\endgroup$
    – skan
    Mar 9, 2018 at 18:55
  • $\begingroup$ That's a completely different question should it probably shouldn't be asked in a comment, but I tend to use JuMP with NLopt or IPOPT depending on the required constraints and whether I need global or local optimization. $\endgroup$
    – Chris Rackauckas
    Mar 10, 2018 at 11:47
3
$\begingroup$

Following others' suggestions, I have used (the commercial) GAMS for many projects. It is very straight forward; all you have to do is to put the mathematic formulation of your problem. It picks up the variables, constraints, objective functions and all the input data. Then, it provides a range of solvers (optimisers) for any case. Depending on your case, you add more sophisticated solvers.

Certainly, EASY is worth a look. Open-source framework.

The term "fast" is very vague! You need to be more specific; Fast in terms of number of iterations? number of evaluations? elapsed time? combination of these?

However, if you are not looking for a software, and you just want to solve the problem, I could suggest to use the global optimiser NSGA-II, which is an open-source optimiser of very high reputation and performance.

If you provided more information, I could guide precisely.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ You need to seriously consider [openMDAO][1], which is developed/supported by NASA and it is quite flexible! $\endgroup$
    – T3rmInAt0r
    Nov 7, 2013 at 11:16
2
$\begingroup$

I'd recommend SCIP or HiGHS (www.highs.dev). On the industry standard benchmarks (http://plato.asu.edu/bench.html) their relative performance is similar, but on specific classes of MIPs one may be very much better. The performance of HiGHS on MIPs is improving rapidly, so will probably overtake SCIP meaningfully in 2022

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Dec 21, 2021 at 16:54

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.

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