{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "title: Network Flows\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Originally Contributed by**: Arpit Bhatia" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In graph theory, a flow network (also known as a transportation network) is a directed graph where \n", "each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. \n", "Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. \n", "A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, \n", "unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. \n", "A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, \n", "currents in an electrical circuit, or anything similar in which something travels through a network of nodes." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using JuMP\n", "using GLPK\n", "using LinearAlgebra" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Shortest Path Problem\n", "Suppose that each arc $(i, j)$ of a graph is assigned a scalar cost $a_{i,j}$, and \n", "suppose that we define the cost of a forward path to be the sum of the costs of its arcs. \n", "Given a pair of nodes, the shortest path problem is to find a forward path that connects these nodes and has minimum cost." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align*}\n", "\\min && \\sum_{\\forall e(i,j) \\in E} a_{i,j} \\times x_{i,j} \\\\\n", "s.t. && b(i) = \\sum_j x_{ij} - \\sum_k x_{ki} = \\begin{cases}\n", "1 &\\mbox{if $i$ is the starting node,} \\\\\n", "-1 &\\mbox{if $i$ is the ending node,} \\\\\n", "0 &\\mbox{otherwise.} \\end{cases} \\\\\n", "&& x_{e} \\in \\{0,1\\} && \\forall e \\in E\n", "\\end{align*}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Flow" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "objective_value(shortest_path) = 55.0\n", "value.(x) = [0.0 0.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 1.0 0.0; 0.0 1.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0]\n" ] } ], "source": [ "G = [\n", " 0 100 30 0 0;\n", " 0 0 20 0 0; \n", " 0 0 0 10 60;\n", " 0 15 0 0 50;\n", " 0 0 0 0 0;\n", "]\n", "\n", "n = size(G)[1]\n", "\n", "shortest_path = Model(GLPK.Optimizer)\n", "\n", "@variable(shortest_path, x[1:n,1:n], Bin)\n", "@constraint(shortest_path, [i = 1:n, j = 1:n; G[i,j] == 0], x[i,j] == 0) # Arcs with zero cost are not a part of the path as they do no exist\n", "@constraint(shortest_path, [i = 1:n; i != 1 && i != 2], sum(x[i,:]) == sum(x[:,i])) # Flow conservation constraint\n", "@constraint(shortest_path, sum(x[1,:]) - sum(x[:,1]) == 1) # Flow coming out of source = 1\n", "@constraint(shortest_path, sum(x[2,:]) - sum(x[:,2]) == -1) # Flowing coming out of destination = -1 i.e. Flow entering destination = 1 \n", "@objective(shortest_path, Min, dot(G, x))\n", "\n", "optimize!(shortest_path)\n", "@show objective_value(shortest_path);\n", "@show value.(x);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Assignment Problem\n", "Suppose that there are $n$ persons and $n$ objects that we have to match on a one-to-one basis. \n", "There is a benefit or value $a_{i,j}$ for matching person $i$ with object $j$, and \n", "we want to assign persons to objects so as to maximize the total benefit. \n", "There is also a restriction that person $i$ can be assigned to object $j$ only if $(i, j)$ belongs to a given set of pairs $A$. \n", "Mathematically, we want to find a set of person-object pairs $(1, j_{1}),..., (n, j_{n})$ from $A$ such that \n", "the objects $j_{1},...,j_{n}$ are all distinct, and the total benefit $\\sum_{i=1}^{y} a_{ij_{i}}$ is maximized." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align*}\n", "\\max && \\sum_{(i,j) \\in A} a_{i,j} \\times y_{i,j} \\\\\n", "s.t. && \\sum_{\\{j|(i,j) \\in A\\}} y_{i,j} = 1 && \\forall i = \\{1,2....n\\} \\\\\n", "&& \\sum_{\\{i|(i,j) \\in A\\}} y_{i,j} = 1 && \\forall j = \\{1,2....n\\} \\\\\n", "&& y_{i,j} \\in \\{0,1\\} && \\forall (i,j) \\in \\{1,2...k\\}\n", "\\end{align*}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Flow" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "objective_value(assignment) = 20.0\n", "value.(y) = [0.0 1.0 0.0 0.0; 0.0 0.0 1.0 0.0; 1.0 0.0 0.0 0.0; 0.0 0.0 0.0 1.0]\n" ] } ], "source": [ "G = [\n", " 6 4 5 0;\n", " 0 3 6 0;\n", " 5 0 4 3;\n", " 7 5 5 5;\n", "]\n", "\n", "n = size(G)[1]\n", "\n", "assignment = Model(GLPK.Optimizer)\n", "@variable(assignment, y[1:n,1:n], Bin)\n", "@constraint(assignment, [i = 1:n], sum(y[:,i]) == 1) # One person can only be assigned to one object\n", "@constraint(assignment, [j = 1:n], sum(y[j,:]) == 1) # One object can only be assigned to one person\n", "@objective(assignment, Max, dot(G, y))\n", "\n", "optimize!(assignment)\n", "@show objective_value(assignment);\n", "@show value.(y);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## The Max-Flow Problem\n", "In the max-flow problem, we have a graph with two special nodes: the $source$, denoted by $s$, and the $sink$, denoted by $t$. \n", "The objective is to move as much flow as possible from $s$ into $t$ while observing the capacity constraints." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align*}\n", "\\max && \\sum_{v:(s,v) \\in E} f(s,v) \\\\\n", "s.t. && \\sum_{u:(u,v) \\in E} f(u,v) = \\sum_{w:(v,w) \\in E} f(v,w) && \\forall v \\in V - \\{s,t\\} \\\\\n", "&& f(u,v) \\leq c(u,v) && \\forall (u,v) \\in E \\\\\n", "&& f(u,v) \\geq 0 && \\forall (u,v) \\in E \n", "\\end{align*}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Flow" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "objective_value(max_flow) = 6.0\n", "value.(f) = [0.0 3.0 2.0 1.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 3.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 1.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 4.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 2.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0]\n" ] } ], "source": [ "G = [\n", " 0 3 2 2 0 0 0 0;\n", " 0 0 0 0 5 1 0 0;\n", " 0 0 0 0 1 3 1 0;\n", " 0 0 0 0 0 1 0 0;\n", " 0 0 0 0 0 0 0 4;\n", " 0 0 0 0 0 0 0 2;\n", " 0 0 0 0 0 0 0 4;\n", " 0 0 0 0 0 0 0 0;\n", "]\n", "\n", "n = size(G)[1]\n", "\n", "max_flow = Model(GLPK.Optimizer)\n", "\n", "@variable(max_flow, f[1:n,1:n] >= 0)\n", "@constraint(max_flow, [i = 1:n, j = 1:n], f[i,j] <= G[i,j]) # Capacity constraints\n", "@constraint(max_flow, [i = 1:n; i != 1 && i != 8], sum(f[i,:]) == sum(f[:,i])) # Flow conservation contraints\n", "@objective(max_flow, Max, sum(f[1, :]))\n", "\n", "optimize!(max_flow)\n", "@show objective_value(max_flow);\n", "@show value.(f);" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.5.1", "language": "julia", "name": "julia-1.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.5.1" } }, "nbformat": 4, "nbformat_minor": 2 }