How to choose an integer linear programming solver

问题:

I am newbie for integer linear programming. I plan to use a integer linear programming solver to solve my combinatorial optimization problem. I am more familiar with C++/object oriented programming on an IDE. Now I am using NetBeans with Cygwin to write my applications most of time.

May I ask if there is an easy use ILP solver for me? Or it depends on the problem I want to solve ? I am trying to do some resources mapping optimization. Please let me know if any further information is required.

Thank you very much, Cassie.

回答1:

If what you want is linear mixed integer programming, then I would point to Coin-OR (and specifically to the module CBC). It's Free software (as speech) You can either use it with a specific language, or use C++.

Use C++ if you data requires lots of preprocessing, or if you want to put your hands into the solver (choosing pivot points, column generation, adding cuts and so on...).

Use the integrated language if you want to use the solver as a black box (you're just interested in the result and the problem is easy or classic enough to be solved without tweaking).

But in the tags you mention genetic algorithms and graphs algorithms. Maybe you should start by better defing your problem... For graphs I like a lot Boost::Graph

回答2:

I have used lp_solve ( http://lpsolve.sourceforge.net/5.5/ ) on a couple of occasions with success. It is mature, feature rich and is extremely well documented with lots of good advice if your linear programming skills are rusty. The integer linear programming is not a just an add on but is strongly emphasized with this package.

Just noticed that you say you are a 'newbie' at this. Well, then I strongly recommend this package since the documentation is full of examples and gentle tutorials. Other packages I have tried tend to assume a lot of the user.

回答3:

For large problems, you might look at AMPL, which is an optimization interpreter with many backend solvers available. It runs as a separate process; C++ would be used to write out the input data.

Then you could try various state-of-the-art solvers.

回答4:

Look into GLPK. Comes with a few examples, and works with a subset of AMPL, although IMHO works best when you stick to C/C++ for model setup. Copes with pretty big models too.

回答5:

Linear Programming from Wikipedia covers a few different algorithms that you could do some digging into to see which may work best for you. Does that help or were you wanting something more specific?