The purpose of this IPython notebook is to illustrate solving ILP problems using GLPK in CVXOPT in Python.

In [1]:
from cvxopt.glpk import ilp
import numpy as np
from cvxopt import matrix


We will be trying to solve the following ILP problem:

$$Min~x_0+x_1+x_2+x_3+x_4+x_5$$

GIven the following constraints:

$$x_0+x_1\ge1$$$$x_0+x_1+x_5\ge1$$$$x_2+x_3\ge1$$$$x_2+x_3+x_4\ge1$$$$x_3+x_4+x_5\ge1$$$$x_1+x_4+x_5\ge1$$$$x_0,x_1,x_2,x_3,x_4,x_5\in~Z$$

Now, GLPK ILP solver assumes the following form of the problem.

In [2]:
print help(ilp)

Help on built-in function ilp in module cvxopt.glpk:

ilp(...)
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

minimize    c'*x
subject to  G*x <= h
A*x = b
x[I] are all integer
x[B] are all binary

ARGUMENTS
c            nx1 dense 'd' matrix with n>=1

G            mxn dense or sparse 'd' matrix with m>=1

h            mx1 dense 'd' matrix

A            pxn dense or sparse 'd' matrix with p>=0

b            px1 dense 'd' matrix

I            set with indices of integer variables

B            set with indices of binary variables

status       'optimal', 'primal infeasible', 'dual infeasible',
'invalid MIP formulation', 'maxiters exceeded',
'time limit exceeded', 'unknown'

x            an optimal solution if status is 'optimal';
None otherwise

None


Thus, for the given problem we have

1. c: is a 6*1 matrix (since $x_0,..x_x5$ are the decision variables)
2. G: -1* Coeff. Matrix (Coeff. matrix contains entries $g_{i,j}$ which are either 0 or 1 depending on whether $x_j$ is present in $i^{th}$ constraint or not. NB: -1 is needed since the expected form is Gx<=h, whereas we have >= inequalities
3. h: -1 ones(61). There are 6 constraints
4. A and b are empty
5. I={0,1,2,3,4,5} since all the decision variables are integer
6. B={}
In [3]:
c=matrix(np.ones(6,dtype=float))

In [4]:
print c

[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]


In [5]:
coeff=np.array([[1,1,0,0,0,0],
[1,1,0,0,0,1],
[0,0,1,1,0,0],
[0,0,1,1,1,0],
[0,0,0,1,1,1],
[0,1,0,0,1,1]
],dtype=float)

In [6]:
G=matrix(-coeff)

In [7]:
print G

[-1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00 -0.00e+00]
[-1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00]
[-0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -1.00e+00 -0.00e+00]
[-0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -1.00e+00]
[-0.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00]


In [8]:
h=matrix(-1*np.ones(6))

In [9]:
I=set(range(6))

In [10]:
B=set()

In [11]:
print I,B

set([0, 1, 2, 3, 4, 5]) set([])

In [12]:
(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),I,B)

In [13]:
status

Out[13]:
'optimal'
In [14]:
print x

[ 0.00e+00]
[ 1.00e+00]
[ 0.00e+00]
[ 1.00e+00]
[ 0.00e+00]
[ 0.00e+00]



Thus, an optimal solution is found. This solution is consistent with the solution given by the instructors.

What if we constrained the problem to be 0-1 ILP. We can do that simply by swapping the I and the B set.

In [15]:
(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),B,I)

In [16]:
print status
print x

optimal
[ 0.00e+00]
[ 1.00e+00]
[ 0.00e+00]
[ 1.00e+00]
[ 0.00e+00]
[ 0.00e+00]



We obtain the same solution, which is a special case, when ILP solution is the same as 0-1 ILP solution.