examples/guide-to-ilp.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Explaining Integer Linear Programming (ILP)\n",
    "\n",
    "This is a very short guide that shows how [*Integer Linear Programming*](https://en.wikipedia.org/wiki/Integer_linear_programming) works. We will use the [Gurobi Optimizer](https://www.gurobi.com/) using Python for this (see this [example](ilp.ipynb) for details on how to set this up).\n",
    "\n",
    "<!-- https://www.gurobi.com/documentation/9.0/refman/py_python_api_details.html -->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start by creating a model for the Gurobi optimizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "model = gp.Model();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variables\n",
    "\n",
    "*Integer Linear Programming* is about finding assignments for integer variables that satisfy a set of constraints (of a particular form)—and that optionally are optimal with respect to some optimization statement.\n",
    "\n",
    "Let's start with adding some variables to the model. We can add an *integer variable* $u_1$ as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "u1 = model.addVar(vtype=GRB.INTEGER, name=\"u1\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we introduce a variable, we can also set a *lower bound* and an *upper bound* on the values that this variable is allowed to get. For example, let's add a variable whose value must be at least 0 and at most 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "u2 = model.addVar(vtype=GRB.INTEGER, lb=0, ub=5, name=\"u2\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the case where we have an integer variable with lower bound 0 and upper bound 1 (a *binary variable*), we can use the following notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "u3 = model.addVar(vtype=GRB.BINARY, name=\"u3\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Often, it is convenient to add a sequence of variables. For example, suppose we want to add four binary variables. We can do this as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = model.addVars(4, vtype=GRB.BINARY, name=\"v\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This creates four variables that we can access as `v[0]`, `v[1]`, `v[2]` and `v[3]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear constraints\n",
    "\n",
    "Once we have added variables to the model, we can add constraints on the combinations of values that these variables are allowed to get. In *Integer Linear Programming*, we can only add so-called *linear constraints*. These are constraints of the form $c_1 * v_1 + \\dotsm + c_n * v_n \\leq d$, where $c_1,\\dotsc,c_n$ and $d$ are constants, and $v_1,\\dotsc,v_n$ are variables.\n",
    "\n",
    "For example, we can add the constraint that $v_0 + 2*v_2 + 3*v_3 \\leq 4$ as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.addConstr(v[0] + 2*v[2] + 3*v[3] <= 4);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we combine several such linear constraints, we can also express constraints of the form $c_1 * v_1 + \\dotsm + c_n * v_n = d$. We can do this by adding the constraints $c_1 * v_1 + \\dotsm + c_n * v_n \\leq d$ and $-c_1 * v_1 + \\dotsm + -c_n * v_n \\leq -d$. However, to make things easier, we can directly express this.\n",
    "\n",
    "For example, we can add the constraint that $v_0+v_1+v_2 = 1$ as follows (`gp.quicksum()` expresses the sum of a list of variables)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.addConstr(gp.quicksum([v[i] for i in [0,1,2]]) == 1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimization\n",
    "\n",
    "We can also express an optimization statement: either maximizing or minimizing the value for some linear combination of variables.\n",
    "\n",
    "For example, we can tell the solver to maximize the sum of $u_2$ and $u_3$ as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.setObjective(gp.quicksum([u2, u3]), GRB.MAXIMIZE);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Finding an optimal model\n",
    "\n",
    "Now that we have added variables, constraints and an optimization statement, we can tell the solver to find an assignment to the variables that satisfies all the lower and upper bounds on the variable values, the constraints that we added, and that is optimal with respect to the minimization/maximization statement that we added.\n",
    "\n",
    "We do this as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (mac64)\n",
      "Optimize a model with 2 rows, 7 columns and 6 nonzeros\n",
      "Model fingerprint: 0x6389371b\n",
      "Variable types: 0 continuous, 7 integer (5 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 3e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 5e+00]\n",
      "  RHS range        [1e+00, 4e+00]\n",
      "Found heuristic solution: objective 6.0000000\n",
      "\n",
      "Explored 0 nodes (0 simplex iterations) in 0.00 seconds\n",
      "Thread count was 1 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 6 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 6.000000000000e+00, best bound 6.000000000000e+00, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.optimize();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Gurobi optimizer gave us some statistics about the search process when we called `model.optimize()`.\n",
    "\n",
    "If we want to access the values of the variables in the optimal model, we can do so as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "u1: -0.0\n",
      "u2: 5.0\n",
      "u3: 1.0\n",
      "v[0]: 1.0\n",
      "v[1]: -0.0\n",
      "v[2]: -0.0\n",
      "v[3]: -0.0\n"
     ]
    }
   ],
   "source": [
    "if model.status == GRB.OPTIMAL:\n",
    "    for v in model.getVars():\n",
    "        print(\"{}: {}\".format(v.varName, v.x));\n",
    "else:\n",
    "    print(\"No optimal model found!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The optimization statement is optional. We could also have left it out. If we don't add an optimization statement, the Gurobi optimizer will simply give us some assignment that satisfies all the constraints if we call `model.optimize()` (if such an assignment exists)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mixed-Integer Programming\n",
    "\n",
    "Gurobi also allows us to add variables whose values are not restricted to integers (so-called *continuous variables*). The case where we combine integer variables and continuous variables is called *Mixed-Integer Programming (MIP)*.\n",
    "\n",
    "For example, we can add two continuous variable $w_0,w_1$ with lower bound 0 and upper bound 2 as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = model.addVars(2, vtype=GRB.CONTINUOUS, lb=0, ub=2, name=\"w\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see if these variables are really allowed to get non-integer values, let's add another constraint, and change the optimization statement to something else, and call `model.optimize()` again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (mac64)\n",
      "Optimize a model with 3 rows, 9 columns and 8 nonzeros\n",
      "Model fingerprint: 0x0bed1549\n",
      "Variable types: 2 continuous, 7 integer (5 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 7e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 5e+00]\n",
      "  RHS range        [1e+00, 4e+00]\n",
      "\n",
      "MIP start from previous solve produced solution with objective 0.666667 (0.00s)\n",
      "Loaded MIP start from previous solve with objective 0.666667\n",
      "\n",
      "Presolve removed 3 rows and 9 columns\n",
      "Presolve time: 0.00s\n",
      "Presolve: All rows and columns removed\n",
      "\n",
      "Explored 0 nodes (0 simplex iterations) in 0.01 seconds\n",
      "Thread count was 1 (of 8 available processors)\n",
      "\n",
      "Solution count 1: 0.666667 \n",
      "No other solutions better than 0.666667\n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 6.666666666667e-01, best bound 6.666666666667e-01, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.addConstr(7*w[0] + 3*w[1] == 2);\n",
    "\n",
    "model.setObjective(gp.quicksum([w[i] for i in [0,1]]), GRB.MAXIMIZE);\n",
    "\n",
    "model.optimize();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we now inspect the values of the variables in the assignment that the Gurobi optimizer gave us, we see that $w_1$ got a non-integer value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "u1: -0.0\n",
      "u2: -0.0\n",
      "u3: 0.0\n",
      "v[0]: 0.0\n",
      "v[1]: 1.0\n",
      "v[2]: 0.0\n",
      "v[3]: 0.0\n",
      "w[0]: 0.0\n",
      "w[1]: 0.6666666666666666\n"
     ]
    }
   ],
   "source": [
    "if model.status == GRB.OPTIMAL:\n",
    "    for v in model.getVars():\n",
    "        print(\"{}: {}\".format(v.varName, v.x));\n",
    "else:\n",
    "    print(\"No optimal model found!\");"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}