Integer linear programming: example and good tools

问题:

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

Here's a sample input set:

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

With output:

x = {1,1,0}

What are good tools for solving this sort of problem, and examples of how to use them?

回答1:

Mathematica

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

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

outputs:

{1, 1, 0}

回答2:

GLPK

I'm offering an answer using GLPK's glpsol, but I hope there are much better ways to do this (it seems like GLPK is overly powerful/general for this kind of simple special case of a linear programming problem):

In order to generate the .mps file given below you've got to split up your matrices row-wise into a system of equations, so the problem description becomes:

minimize

cost = 1 x_1 + 2 x_2 + 3 x_3

s.t. 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

GLPK documentation has detailed info on the .mps format, but you specify the rows, columns, rhs, and bounds. In the ROWS section the 'N' and 'G' specify the type of constraint (number, and greater than respectively). In the BOUNDS section the 'UI' specifies that the bounds are upper integer type, forcing the solution to be integer.

To run the solver on 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'm not clear on how to directly get the x vector that solves the problem, though 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  

回答3:

You've specified a pure integer programming problem. Most practical applications usually involve what is called mixed integer programming where only some of the variables are integer. A reasonably concise tutorial & essay on the subject can be found here:

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

Typical solution techniques for IP problems are dynamic programming or branch and bound. Searching on these terms should help you find some freeware, shareware, or academic code.

Good luck

回答4:

Python: PULP

回答5:

These type of simple problems can also be solved using a technique called constraint programming. You can find more details about the technique and free and commercial solvers available to solve these problems from the corresponding wikipedia entry. If the problems involving integer variables are more complex than what you mention, it is better to consider general purpose Linear Programming/Integer Programming solvers (like GLPK). There are a bunch of them, some names are: LPSOLVE (free), IBM ILOG CPLEX (Commercial).

回答6:

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

回答7:

There is a similar question on scicomp.stackexchange.com and an answer which lists a few libraries.