{
 "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": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     con: array([-4.50392168e-10, -4.50387172e-10,  9.00772790e-10,  7.77156117e-15])\n",
      "     fun: -4.999999997267121\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 5\n",
      "   slack: array([ 2.00000000e+00,  1.92361238e-09, -1.22243549e-10,  4.81122364e-10,\n",
      "        6.96208571e-01,  3.03791430e-01,  4.21934063e-01,  2.74274508e-01,\n",
      "        7.25725495e-01])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([2.        , 3.        , 1.        , 1.        , 2.30379143,\n",
      "       0.69620857, 2.57806594, 0.72572549, 4.27427451])\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from scipy.optimize import linprog\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(capacity.size), \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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}