Created
October 1, 2022 21:47
-
-
Save tonicanada/878b1fd2f19cde0253150eedd865a92c to your computer and use it in GitHub Desktop.
linearprogramming_maxnetworkflow_medium.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "provenance": [], | |
| "collapsed_sections": [], | |
| "authorship_tag": "ABX9TyNe/5Y0gIzvf8wa6I+iPOZA", | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| }, | |
| "language_info": { | |
| "name": "python" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/tonicanada/878b1fd2f19cde0253150eedd865a92c/linearprogramming_maxnetworkflow_medium.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "### Solving Maximum Network Flow with PuLP library" | |
| ], | |
| "metadata": { | |
| "id": "hrOhDwIGsifU" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "EEPTAQiNrLL3", | |
| "outputId": "5316a108-09c6-430e-9d54-a1962ba28999" | |
| }, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n", | |
| "Collecting pulp\n", | |
| " Downloading PuLP-2.6.0-py3-none-any.whl (14.2 MB)\n", | |
| "\u001b[K |████████████████████████████████| 14.2 MB 2.0 MB/s \n", | |
| "\u001b[?25hInstalling collected packages: pulp\n", | |
| "Successfully installed pulp-2.6.0\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "!pip install pulp" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from pulp import *\n", | |
| "import pprint\n", | |
| "import numpy as np" | |
| ], | |
| "metadata": { | |
| "id": "PJW1W9GVrRTj" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "" | |
| ], | |
| "metadata": { | |
| "id": "KcrijAGts49f" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# capacities_graph network (first row should correspond to S, last to T)\n", | |
| "capacities_graph = [\n", | |
| " [0, 18, 0, 15, 0, 0],\n", | |
| " [0, 0, 9, 2, 10, 0],\n", | |
| " [0, 0, 0, 0, 0, 13],\n", | |
| " [0, 0, 0, 0, 3, 0],\n", | |
| " [0, 0, 5, 0, 0, 12],\n", | |
| " [0, 0, 0, 0, 0, 0],\n", | |
| "]" | |
| ], | |
| "metadata": { | |
| "id": "uC-F2K9UtBDJ" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Function to label nodes \n", | |
| "def create_node_labels(graph):\n", | |
| " n = len(graph)\n", | |
| " labels = []\n", | |
| " for i in range(n):\n", | |
| " if i == 0:\n", | |
| " labels.append(\"S\")\n", | |
| " elif i == n-1:\n", | |
| " labels.append(\"T\")\n", | |
| " else:\n", | |
| " labels.append(chr(64+i))\n", | |
| " return labels" | |
| ], | |
| "metadata": { | |
| "id": "P2ZHOHZ2tHaV" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "vertex = create_node_labels(capacities_graph)" | |
| ], | |
| "metadata": { | |
| "id": "Qjq-j3A0vsr4" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Function to create the variables\n", | |
| "def create_variables(graph):\n", | |
| " edges = []\n", | |
| " node_labels = create_node_labels(graph)\n", | |
| " n = len(graph)\n", | |
| " for i in range(n):\n", | |
| " for j in range(n):\n", | |
| " if capacities_graph[i][j] > 0:\n", | |
| " edges.append(f\"{node_labels[i]}_{node_labels[j]}\")\n", | |
| " return edges" | |
| ], | |
| "metadata": { | |
| "id": "kRO8K45JthcP" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "edges = create_variables(capacities_graph)" | |
| ], | |
| "metadata": { | |
| "id": "LULqiT7CuI6_" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Define PuLP problem\n", | |
| "prob = LpProblem(\"Network Max Flow\",LpMaximize)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "gISPAiNGvETH", | |
| "outputId": "09659401-027a-4955-ef97-bed8b85b9bb7" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stderr", | |
| "text": [ | |
| "/usr/local/lib/python3.7/dist-packages/pulp/pulp.py:1352: UserWarning: Spaces are not permitted in the name. Converted to '_'\n", | |
| " warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Creating a Set of Variables\n", | |
| "x = LpVariable.dicts(\"Edge\", edges, 0,cat = \"Integer\")\n", | |
| "pprint.pprint(x)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "3PfUmPr3vSHS", | |
| "outputId": "a2b04018-d212-40eb-ea12-b920bcaa5aeb" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "{'A_B': Edge_A_B,\n", | |
| " 'A_C': Edge_A_C,\n", | |
| " 'A_D': Edge_A_D,\n", | |
| " 'B_T': Edge_B_T,\n", | |
| " 'C_D': Edge_C_D,\n", | |
| " 'D_B': Edge_D_B,\n", | |
| " 'D_T': Edge_D_T,\n", | |
| " 'S_A': Edge_S_A,\n", | |
| " 'S_C': Edge_S_C}\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def flow_sent_from_source(edgs):\n", | |
| " edges_from_source = []\n", | |
| " for edge in edgs:\n", | |
| " if edge[0] == \"S\":\n", | |
| " edges_from_source.append(edge)\n", | |
| " return edges_from_source" | |
| ], | |
| "metadata": { | |
| "id": "ADE69fvixOJn" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "edges_from_source = flow_sent_from_source(edges)" | |
| ], | |
| "metadata": { | |
| "id": "HM55v1qmx9Z-" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Defining cost function\n", | |
| "prob += sum(x[i] for i in edges_from_source)" | |
| ], | |
| "metadata": { | |
| "id": "1R06KjDKyGhw" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Fuction that receives an edge and returns capacity\n", | |
| "def get_capacity(edge, cap_graph):\n", | |
| " vertex_from = edge[0]\n", | |
| " vertex_to = edge[-1]\n", | |
| " vertex_from_idx = vertex.index(vertex_from)\n", | |
| " vertex_to_idx = vertex.index(vertex_to)\n", | |
| " return cap_graph[vertex_from_idx][vertex_to_idx] " | |
| ], | |
| "metadata": { | |
| "id": "Pn3RVFq8vZCF" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "get_capacity(\"S_A\", capacities_graph)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "rFiPUTNJvjgQ", | |
| "outputId": "568880e6-c460-4334-de70-c1bf8342b131" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "18" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 31 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Adding constraints conservation of flow\n", | |
| "for v in vertex:\n", | |
| " flow_in = []\n", | |
| " flow_out = []\n", | |
| " for edge in x.keys():\n", | |
| " if edge[-1] == v:\n", | |
| " flow_in.append(edge)\n", | |
| " if edge[0] == v:\n", | |
| " flow_out.append(edge)\n", | |
| " if (len(flow_in)>0 and len(flow_out) >0):\n", | |
| " print(flow_in, flow_out)\n", | |
| " prob += sum(x[i] for i in flow_in) == sum(x[i] for i in flow_out)" | |
| ], | |
| "metadata": { | |
| "id": "E3xjgPHev8KC", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "ee59845b-368f-4503-c307-ca0c247ae1d0" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "['S_A'] ['A_B', 'A_C', 'A_D']\n", | |
| "['A_B', 'D_B'] ['B_T']\n", | |
| "['S_C', 'A_C'] ['C_D']\n", | |
| "['A_D', 'C_D'] ['D_B', 'D_T']\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Adding constraints capacitites of flow\n", | |
| "for e in edges:\n", | |
| " capacity_edge = get_capacity(e, capacities_graph)\n", | |
| " prob += x[e] <= capacity_edge\n", | |
| "\n", | |
| "print(prob)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "6gTaWRpzwWd3", | |
| "outputId": "0ea53707-664c-4382-87b7-de628a6b70dd" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Network_Max_Flow:\n", | |
| "MAXIMIZE\n", | |
| "None\n", | |
| "SUBJECT TO\n", | |
| "_C1: - Edge_A_B - Edge_A_C - Edge_A_D + Edge_S_A = 0\n", | |
| "\n", | |
| "_C2: Edge_A_B - Edge_B_T + Edge_D_B = 0\n", | |
| "\n", | |
| "_C3: Edge_A_C - Edge_C_D + Edge_S_C = 0\n", | |
| "\n", | |
| "_C4: Edge_A_D + Edge_C_D - Edge_D_B - Edge_D_T = 0\n", | |
| "\n", | |
| "_C5: - Edge_A_B - Edge_A_C - Edge_A_D + Edge_S_A = 0\n", | |
| "\n", | |
| "_C6: Edge_A_B - Edge_B_T + Edge_D_B = 0\n", | |
| "\n", | |
| "_C7: Edge_A_C - Edge_C_D + Edge_S_C = 0\n", | |
| "\n", | |
| "_C8: Edge_A_D + Edge_C_D - Edge_D_B - Edge_D_T = 0\n", | |
| "\n", | |
| "_C9: Edge_S_A <= 18\n", | |
| "\n", | |
| "_C10: Edge_S_C <= 15\n", | |
| "\n", | |
| "_C11: Edge_A_B <= 9\n", | |
| "\n", | |
| "_C12: Edge_A_C <= 2\n", | |
| "\n", | |
| "_C13: Edge_A_D <= 10\n", | |
| "\n", | |
| "_C14: Edge_B_T <= 13\n", | |
| "\n", | |
| "_C15: Edge_C_D <= 3\n", | |
| "\n", | |
| "_C16: Edge_D_B <= 5\n", | |
| "\n", | |
| "_C17: Edge_D_T <= 12\n", | |
| "\n", | |
| "VARIABLES\n", | |
| "0 <= Edge_A_B Integer\n", | |
| "0 <= Edge_A_C Integer\n", | |
| "0 <= Edge_A_D Integer\n", | |
| "0 <= Edge_B_T Integer\n", | |
| "0 <= Edge_C_D Integer\n", | |
| "0 <= Edge_D_B Integer\n", | |
| "0 <= Edge_D_T Integer\n", | |
| "0 <= Edge_S_A Integer\n", | |
| "0 <= Edge_S_C Integer\n", | |
| "\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "prob.solve()" | |
| ], | |
| "metadata": { | |
| "id": "KScVx0VMxDG8", | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "outputId": "2eda601e-451f-4c48-c822-cca86591a930" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "1" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 44 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "print(\"Status:\", LpStatus[prob.status])" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "zdc9npzrydv8", | |
| "outputId": "96e80438-cb87-4f79-dcd4-904c8a3c0292" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Status: Optimal\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Solution\n", | |
| "for e in edges:\n", | |
| " print(x[e], x[e].value())" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "_eSlxO5Wyfhn", | |
| "outputId": "cfaae5ed-5fb9-4813-d217-26ba0d60cb28" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Edge_S_A 18.0\n", | |
| "Edge_S_C 3.0\n", | |
| "Edge_A_B 9.0\n", | |
| "Edge_A_C 0.0\n", | |
| "Edge_A_D 9.0\n", | |
| "Edge_B_T 13.0\n", | |
| "Edge_C_D 3.0\n", | |
| "Edge_D_B 4.0\n", | |
| "Edge_D_T 8.0\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Maximum amount of flow\n", | |
| "value(prob.objective)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "1ARRMVAZyhKX", | |
| "outputId": "c8e06f10-110e-4672-f1a5-7d0fff6d2f48" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "execute_result", | |
| "data": { | |
| "text/plain": [ | |
| "21.0" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "execution_count": 48 | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [], | |
| "metadata": { | |
| "id": "IXv5vVBpyujN" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment