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.

Contact: Website, Twitter

In [ ]: