{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Solving a maximum flow problem using linear programming\n",
"Below we will use the 'scipy.optimize.linprog' 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",
""
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" fun: -5.0\n",
" message: 'Optimization terminated successfully.'\n",
" nit: 9\n",
" slack: array([2., 0., 0., 0., 1., 0., 1., 0., 1.])\n",
" status: 0\n",
" success: True\n",
" x: array([2., 3., 1., 1., 2., 1., 2., 1., 4.])\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.6.4"
}
},
"nbformat": 4,
"nbformat_minor": 2
}