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:


GIven the following constraints:


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:

    Solves a mixed integer linear program using GLPK.
    (status, x) = ilp(c, G, h, A, b, I, B)
    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
    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


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]:
In [4]:
print c
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]
[ 1.00e+00]

In [5]:
In [6]:
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]:
In [9]:
In [10]:
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]:
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
[ 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 [ ]: