Geek Answers Handbook

Integer linear programming: an example and good tools?

Find a vector x that minimizes c. x subject to the restriction m. x> = b, x integer.

Here's an example input:

c : {1,2,3} m : {{1,0,0}, {0,1,0}, {1,0,1}} b : {1,1,1}

With an exit:

 x = {1,1,0}

What are good tools to solve these kinds of problems and examples of their use?

+4
source share
7 answers

Mathematica

Mathematica has this feature built in. (NB: Mathematica is not free software.)

 LinearProgramming[c, m, b, Automatic, Integers]

outputs:

 {1, 1, 0}
+1
source

GLPK

I offer an answer using GLPK glpsol , but I hope that there are much better ways to do this (it seems GLPK is too powerful / general for such a simple simple case of a linear programming problem):

To generate the .mps file below, you must separate your matrices in a series of lines into a system of equations, so the description of the problem will look like this:

 minimize cost = 1 x_1 + 2 x_2 + 3 x_3 st constraints: S1 = 1 x_1 + 0 x_2 + 0 x_3 S2 = 0 x_1 + 1 x_2 + 0 x_3 S3 = 1 x_1 + 0 x_2 + 1 x_3 S1 >= 1 S2 >= 1 S3 >= 1 0 <= x1 <= 1 0 <= x2 <= 1 0 <= x3 <= 1

The GLPK documentation contains detailed information about the .mps format, but you specify rows, columns, edges, and borders. In the ROWS section, 'N' and 'G' indicate the type of restriction (number and more than, respectively). In the BOUNDS section, 'UI' indicates that the bounds are the top integer type, causing the decision to be integer.

To run the solver according to the problem specification:

 > glpsol --freemps example.mps -o example.out

example.mps file:

 NAME VM ROWS N cost G S1 G S2 G S3 COLUMNS x_1 cost 1.0 x_1 S1 1.0 x_1 S3 1.0 x_2 cost 2.0 x_2 S2 1.0 x_3 cost 3.0 x_3 S3 1.0 RHS RHS1 cost 0.0 RHS1 S1 1.0 RHS1 S2 1.0 RHS1 S3 1.0 BOUNDS UI BND1 x_1 1.0 UI BND1 x_2 1.0 UI BND1 x_3 1.0 ENDATA

outputs:

 Problem: VM Rows: 4 Columns: 3 (3 integer, 3 binary) Non-zeros: 7 Status: INTEGER OPTIMAL Objective: cost = 3 (MINimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 cost 3 2 S1 1 1 3 S2 1 1 4 S3 1 1 No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 x_1 * 1 0 1 2 x_2 * 1 0 1 3 x_3 * 0 0 1 Integer feasibility conditions: INT.PE: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality INT.PB: max.abs.err. = 0.00e+00 on row 0 max.rel.err. = 0.00e+00 on row 0 High quality End of output

Also, I don't understand how to directly get the vector x, which solves the problem, although it is encoded in the output above in this section:

  No. Column name Activity ------ ------------ ------------- 1 x_1 * 1 2 x_2 * 1 3 x_3 * 0
+4
source

You indicated a problem with pure integer programming. In most practical applications, the so-called mixed integer programming is usually used, where only some of the variables are integer. Here you can find a fairly short tutorial and essay on the topic:

http://mat.gsia.cmu.edu/orclass/integer/integer.html

Typical methods for resolving IP problems are dynamic programming, or branch and bind. Searching under these conditions will help you find a free, shareware or academic code.

Good luck.

+2
source

Python: PULP

+1
source

These simple problems can also be solved with a technique called constraint programming. You can find more information about technology and free and commercial solutions to solve these problems from the corresponding wikipedia entry . If the problems associated with integer variables are more complex than what you are talking about, it is better to consider linear programming / general-purpose integer programming solutions (e.g. GLPK). There are several, some names: LPSOLVE (free), IBM ILOG CPLEX (Commercial).

+1
source

I am using Python and Pyomo. There is a good overview of the benefits on the project website: http://www.pyomo.org

+1
source

There is a similar question on scicomp.stackexchange.com and an answer that lists several libraries.

0
source

More articles:


All Articles