{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Solving a maximum flow problem using linear programming\n",
    "Below we will use the '<a href=\"https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html\">scipy.optimize.linprog</a>' function to solve a _maximum flow_ problem on a directed graph.\n",
    "\n",
    "We want to send as much _flow_ from node A to node F in the below graph. Edges are numbered 0..8 (red labels), and each edge has a maximum _capacity_ (blue).\n",
    "\n",
    "scipy.optimize.linprog can solve linear programs of the form: \n",
    "\n",
    "* **Minimize**: $c^\\mathrm{T} x$\n",
    "* **Subject to**: $A_\\mathrm{ub}x \\leq b_\\mathrm{ub}$ and $A_\\mathrm{eq}x=b_\\mathrm{eq}$\n",
    "\n",
    "We will let $x$ be a vector describing the flow along each of the edges.\n",
    "\n",
    "We will let $c$ be a vector that can add the flow along the edges (7 and 8) to the sink (F), i.e. a function computing the _value of the flow_.\n",
    "\n",
    "We let add $A_\\mathrm{eq}$ and $b_\\mathrm{eq}$ be a set of constraints where we have a constraint for each non-source and non-sink node (B, C, D, E), requiring that the flow into the node equals the flow out of the node, i.e. _flow conservation_.\n",
    "\n",
    "We let add $A_\\mathrm{ub}$ and $b_\\mathrm{ub}$ be a set of constraints where we have for each edge a constraint requiring that the flow along an edge is upper bounded by the flow constraint of the edge, i.e. _capacity constraints_.\n",
    "\n",
    "<img src=\"max-flow.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     con: array([0., 0., 0., 0.])\n",
      "     fun: -5.0\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 13\n",
      "   slack: array([2., 0., 0., 0., 1., 0., 0., 1., 0.])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([2., 3., 1., 1., 2., 1., 3., 0., 5.])\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from scipy.optimize import linprog\n",
    "\n",
    "edges = 9\n",
    "\n",
    "#                          0  1  2  3  4  5  6  7  8\n",
    "conservation = np.array([[ 0,-1, 0, 0, 1, 1, 0, 0, 0],  # B\n",
    "                         [-1, 0, 1, 1, 0, 0, 0, 0, 0],  # C\n",
    "                         [ 0, 0, 0,-1, 0,-1,-1, 0, 1],  # D\n",
    "                         [ 0, 0,-1, 0,-1, 0, 1, 1, 0]]) # E\n",
    "\n",
    "#                 0  1  2  3  4  5  6  7  8\n",
    "sinks = np.array([0, 0, 0, 0, 0, 0, 0, 1, 1])\n",
    "\n",
    "#                    0  1  2  3  4  5  6  7  8\n",
    "capacity = np.array([4, 3, 1, 1, 3, 1, 3, 1, 5])\n",
    "                 \n",
    "res = linprog(-sinks, \n",
    "              A_eq=conservation, \n",
    "              b_eq=np.zeros(conservation.shape[0]),\n",
    "              A_ub=np.eye(edges), \n",
    "              b_ub=capacity)\n",
    "\n",
    "print(res)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}