The purpose of this IPython notebook is to illustrate solving ILP problems using GLPK in CVXOPT in Python.
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.
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
c=matrix(np.ones(6,dtype=float))
print c
[ 1.00e+00] [ 1.00e+00] [ 1.00e+00] [ 1.00e+00] [ 1.00e+00] [ 1.00e+00]
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)
G=matrix(-coeff)
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]
h=matrix(-1*np.ones(6))
I=set(range(6))
B=set()
print I,B
set([0, 1, 2, 3, 4, 5]) set([])
(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),I,B)
status
'optimal'
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.
(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),B,I)
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.