views:

319

answers:

4

Hi all, 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.

A: 

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?

JB King
+1  A: 

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.

Potatoswatter
+3  A: 

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

Tristram Gräbener
Thank you very much. My problem is basically jobs mapping to machines on a task graph for scheduling. So supose I have a task graph. Each node represents a job which needs to be operated on a machine. Different mapping of jobs to machines results in different total scheduling time on the critical path. My goal is to find the minimun scheduling time of some jobs-to-machines assignment. So do anyone know any easy use solver which does not require strong programming backgound for me to use ? Thank you very much. Cassie
Cassie
Well, this kind of scheduling is a complete research domain on its own.Some problems can be solved by a shortest path algorithm (if you have no constraints on simultaneous tasks).If your machines are premptible, then there are simple polynomial algorithms.Otherwise, chances are good that you have a difficult problem. Try using CBC as a blackbox (but you will need to learn how to model those problems in a linear model), or try to code your own branching code :)
Tristram Gräbener
A: 

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.

ravenspoint