13
$\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!

$\endgroup$
  • $\begingroup$ Have you seen the comparisons to SCIP? $\endgroup$ – Ali Nov 1 '13 at 12:22
13
$\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.

$\endgroup$
6
$\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.

$\endgroup$
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.

$\endgroup$
  • 1
    $\begingroup$ You need to seriously consider [openMDAO][1], which is developed/supported by NASA and it is quite flexible! $\endgroup$ – T3rmInAt0r Nov 7 '13 at 11:16
3
$\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.

$\endgroup$
  • $\begingroup$ Does the JuMP framework add much overhead? $\endgroup$ – naught101 Dec 12 '16 at 6:03
  • $\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 '16 at 6:07
  • $\begingroup$ @ChrisRackauckas What solver works better for nonlinear problems with nonlinear constraints? $\endgroup$ – skan Mar 9 '18 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 '18 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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