ILP example in python

ILP.ipynb

{
 "metadata": {
  "name": "ilp"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "The purpose of this IPython notebook is to illustrate solving ILP problems using GLPK in CVXOPT in Python."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "from cvxopt.glpk import ilp\nimport numpy as np\nfrom cvxopt import matrix",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "We will be trying to solve the following ILP problem:\n    \n$$Min~x_0+x_1+x_2+x_3+x_4+x_5$$\n\nGIven the following constraints:\n\n$$x_0+x_1\\ge1$$\n$$x_0+x_1+x_5\\ge1$$\n$$x_2+x_3\\ge1$$\n$$x_2+x_3+x_4\\ge1$$\n$$x_3+x_4+x_5\\ge1$$\n$$x_1+x_4+x_5\\ge1$$\n$$x_0,x_1,x_2,x_3,x_4,x_5\\in~Z$$\n\n\n\n\n    "
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Now, GLPK ILP solver assumes the following form of the problem."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print help(ilp)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "Help on built-in function ilp in module cvxopt.glpk:\n\nilp(...)\n    Solves a mixed integer linear program using GLPK.\n    \n    (status, x) = ilp(c, G, h, A, b, I, B)\n    \n    PURPOSE\n    Solves the mixed integer linear programming problem\n    \n        minimize    c'*x\n        subject to  G*x <= h\n                    A*x = b\n                    x[I] are all integer\n                    x[B] are all binary\n    \n    ARGUMENTS\n    c            nx1 dense 'd' matrix with n>=1\n    \n    G            mxn dense or sparse 'd' matrix with m>=1\n    \n    h            mx1 dense 'd' matrix\n    \n    A            pxn dense or sparse 'd' matrix with p>=0\n    \n    b            px1 dense 'd' matrix\n    \n    I            set with indices of integer variables\n    \n    B            set with indices of binary variables\n    \n    status       'optimal', 'primal infeasible', 'dual infeasible', \n                 'invalid MIP formulation', 'maxiters exceeded', \n                 'time limit exceeded', 'unknown'\n    \n    x            an optimal solution if status is 'optimal';\n                 None otherwise\n\nNone\n"
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Thus, for the given problem we have\n\n1. c: is a 6*1 matrix (since $x_0,..x_x5$ are the decision variables)\n2. 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\n3. h: -1* ones(6*1). There are 6 constraints\n4. A and b are empty\n5. I={0,1,2,3,4,5} since all the decision variables are integer\n6. B={} "
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "c=matrix(np.ones(6,dtype=float))",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print c",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "[ 1.00e+00]\n[ 1.00e+00]\n[ 1.00e+00]\n[ 1.00e+00]\n[ 1.00e+00]\n[ 1.00e+00]\n\n"
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "coeff=np.array([[1,1,0,0,0,0],\n                [1,1,0,0,0,1],\n                [0,0,1,1,0,0],\n                [0,0,1,1,1,0],\n                [0,0,0,1,1,1],\n                [0,1,0,0,1,1]\n                ],dtype=float)",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "G=matrix(-coeff)",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print G",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "[-1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00 -0.00e+00]\n[-1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00]\n[-0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -0.00e+00 -0.00e+00]\n[-0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -1.00e+00 -0.00e+00]\n[-0.00e+00 -0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00 -1.00e+00]\n[-0.00e+00 -1.00e+00 -0.00e+00 -0.00e+00 -1.00e+00 -1.00e+00]\n\n"
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "h=matrix(-1*np.ones(6))",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "I=set(range(6))",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "B=set()",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print I,B",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "set([0, 1, 2, 3, 4, 5]) set([])\n"
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),I,B)",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "status",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 13,
       "text": "'optimal'"
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print x",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "[ 0.00e+00]\n[ 1.00e+00]\n[ 0.00e+00]\n[ 1.00e+00]\n[ 0.00e+00]\n[ 0.00e+00]\n\n"
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Thus, an optimal solution is found. This solution is consistent with the solution given by the instructors."
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "What if we constrained the problem to be 0-1 ILP. We can do that simply by swapping the I and the B set."
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "(status,x)=ilp(c,G,h,matrix(1., (0,6)),matrix(1., (0,1)),B,I)",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "print status\nprint x",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": "optimal\n[ 0.00e+00]\n[ 1.00e+00]\n[ 0.00e+00]\n[ 1.00e+00]\n[ 0.00e+00]\n[ 0.00e+00]\n\n"
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "We obtain the same solution, which is a special case, when ILP solution is the same as 0-1 ILP solution."
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": "Contact: [Website](http://www.nipunbatra.wordpres.com), [Twitter](https://twitter.com/nipun_batra)"
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}