GurobiPy implementation of Min Cost Flow

mcf.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a1deb958",
   "metadata": {},
   "source": [
    "# Min Cost Flow ILP\n",
    "\n",
    "### Author: [Ben Rosenberg](https://www.youtube.com/@benjaminrosenberg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0f5bec8",
   "metadata": {},
   "source": [
    "### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "329c03b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24c9db72",
   "metadata": {},
   "source": [
    "### Input data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "28f949e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = range(4)\n",
    "\n",
    "edges = [(0,1), (0,3), (2,1), (2,3)]\n",
    "\n",
    "# cost[i,j] is the cost of sending one unit of flow along edge (i,j)\n",
    "cost = {\n",
    "    (0,1) : 0,\n",
    "    (0,3) : 4,\n",
    "    (2,1) : 2,\n",
    "    (2,3) : 8\n",
    "} \n",
    "\n",
    "# capacity[i,j] is the capacity of edge (i,j)\n",
    "capacity = {\n",
    "    (0,1) : 5,\n",
    "    (0,3) : 2,\n",
    "    (2,1) : 3,\n",
    "    (2,3) : 2\n",
    "}\n",
    "\n",
    "# supply[i] is the supply (if positive) or demand (if negative) of node i\n",
    "supply = [5, -6, 3, -2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58be6964",
   "metadata": {},
   "source": [
    "### Model Definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "4c9080eb",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Set parameter TuneOutput to value 3\n",
      "Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 12 rows, 16 columns and 16 nonzeros\n",
      "Model fingerprint: 0xaf2c58bd\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [2e+00, 8e+00]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [2e+00, 6e+00]\n",
      "Presolve removed 12 rows and 16 columns\n",
      "Presolve time: 0.01s\n",
      "Presolve: All rows and columns removed\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    1.4000000e+01   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 0 iterations and 0.01 seconds (0.00 work units)\n",
      "Optimal objective  1.400000000e+01\n",
      "\n",
      "[Total time used: 0 minutes, 0 seconds]\n",
      "\n",
      "Objective value found: 14.0\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "model = gp.Model()\n",
    "\n",
    "# set output level to max\n",
    "model.Params.TuneOutput = 3\n",
    "\n",
    "# add variable f\n",
    "f = model.addVars(nodes, nodes, vtype=GRB.CONTINUOUS, name='f')\n",
    "\n",
    "# add constraint representing supply/demand\n",
    "for i in nodes:\n",
    "    model.addConstr(gp.quicksum(f[i,j] for (x,j) in edges if x == i) -\n",
    "                    gp.quicksum(f[j,i] for (j,x) in edges if x == i)\n",
    "                   == supply[i])\n",
    "\n",
    "# add constraint on edge flows w.r.t. capacities\n",
    "for (i,j) in edges:\n",
    "    model.addConstr(f[i,j] <= capacity[i,j])\n",
    "\n",
    "# add constraint on edge flows w.r.t. 0\n",
    "for (i,j) in edges:\n",
    "    model.addConstr(f[i,j] >= 0)\n",
    "    \n",
    "# set objective\n",
    "model.setObjective(gp.quicksum(cost[i,j] * f[i,j] for (i,j) in edges), GRB.MINIMIZE)\n",
    "\n",
    "model.optimize()\n",
    "\n",
    "end_time = time.time()\n",
    "\n",
    "diff = time.gmtime(end_time - start_time)\n",
    "print('\\n[Total time used: {} minutes, {} seconds]'.format(diff.tm_min, diff.tm_sec))\n",
    "\n",
    "try:\n",
    "    print(f'\\nObjective value found: {model.objVal}')\n",
    "except AttributeError as e:\n",
    "    print(f'\\nCould not find an objective value. \\nTraceback:\\n\\t{e}')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "ee39859b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f[0,1] = 3.0\n",
      "f[0,3] = 2.0\n",
      "f[2,1] = 3.0\n",
      "f[2,3] = 0.0\n"
     ]
    }
   ],
   "source": [
    "# optimal solution\n",
    "for (i,j) in edges:\n",
    "    print('f[{},{}] = {}'.format(\n",
    "        i, j, f[i,j].x\n",
    "    ))"
   ]
  }
 ],
 "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

Video link: YouTube