Is there an Integer Linear Programming software that returns also non-optimal solutions?

Question

I have an integer linear optimisation problem and I'm interested in feasible, good solutions. As far as I know, for example the Gnu Linear Programming Kit only returns the optimal solution (given it exists). This takes endless time and is not exactly what I'm looking for: I would be happy with any good solution, not only the optimal one.

So a LP-Solver that e.g. stops after some time and returns the best solution he found so far, would do the job.

Is there any such software? It would be great if that software was open source or at least free as in beer.

Alternatively: Is there any other way that usually speeds up Integer LP problems? Is this the right place to ask?

Answer 1

Many solvers provide a time limit parameter; if you set the time limit parameter, they will stop once the time limit is reached. If an integer feasible solution has been found, it will return the best feasible solution found to that point.

As you may know, integer programming is NP-hard, and there is a real art to finding optimal solutions as well as good feasible solutions quickly. To compare the different solvers, see Prof. Hans Mittelmann's Benchmarks for Optimization Software. The MILP benchmarks - particularly MIPLIB2010 and the Feasibility Benchmark should be most relevant.

In addition to selecting a good solver, there are many things that can be done to improve solve times including tuning the parameters of the solver and model reformulation. Many people in research and industry - including myself - spend our careers working on improving the solve times of MIP models, both in general and for specific models.

If you are an academic user, note that the top commercial systems like CPLEX and Gurobi are free for academic use. See the respective websites for details.

Finally, you may want to look at OR-Exchange, a sister site to Stack Overflow that focuses on the field of operations research.

(Disclaimer: I currently work for Gurobi Optimization and formerly worked for ILOG, which provided CPLEX).