Sign up ×

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},
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?

share|improve this question
This is called 'integer programming' in the literature. – High Performance Mark Dec 29 '09 at 19:21

7 Answers 7

up vote 1 down vote accepted


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

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


{1, 1, 0}
share|improve this answer


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:


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
 N cost
 G S1
 G S2
 G S3
 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
 RHS1 cost   0.0
 RHS1 S1     1.0
 RHS1 S2     1.0
 RHS1 S3     1.0
 UI BND1 x_1 1.0
 UI BND1 x_2 1.0
 UI BND1 x_3 1.0


Problem:    VM
Rows:       4
Columns:    3 (3 integer, 3 binary)
Non-zeros:  7
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  
share|improve this answer
How did you specify the integer constraint? – dreeves Dec 28 '09 at 18:23
I edited the answer above.. see where it describes the BOUNDS section. – Bee Dec 29 '09 at 19:13

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:

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

share|improve this answer

Python: PULP

share|improve this answer
Can this do integer programming in addition to linear programming? – dreeves Dec 28 '09 at 18:30

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).

share|improve this answer

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

share|improve this answer

I am using Python & Pyomo. There is a good overview of the advantages on the project website:

share|improve this answer

Your Answer


