shortestpath.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c2a870a3-86d3-4775-a3a2-45014538060c",
   "metadata": {},
   "source": [
    "![](shortestpath.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5abebc65-2528-4b3a-ab20-75df47a31f4b",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\min z & = 3x_{12} + 2x_{13} + 4x_{14} + 3x_{25} + x_{35} + x_{36} + 2x_{46} + 6x_{57} + 5x_{67} \\\\\n",
    "\\text{Subject to:} \\\\\n",
    "& x_{12} + x_{13} + x_{14} = 1 \\\\\n",
    "& x_{12} - x_{25} = 0 \\\\\n",
    "& x_{13} - x_{35} - x_{36} = 0 \\\\\n",
    "& x_{14} - x_{46} = 0 \\\\\n",
    "& x_{25} + x_{35} - x_{57} = 0 \\\\\n",
    "& x_{36} + x_{46} - x_{67} = 0 \\\\\n",
    "& x_{57} + x_{67} = 1 \\\\\n",
    "& x_{ij} \\in \\{0,1\\} \n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "fc9e8b24-b5d2-4f41-90a0-a36155eb11ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "570c84aa-7e77-4ae5-acd3-81c62e0c6082",
   "metadata": {},
   "outputs": [],
   "source": [
    "using GLPK"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "dc61f7a0-519c-4a22-8742-cccfd1757bd4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "A JuMP Model\n",
       "Feasibility problem with:\n",
       "Variables: 0\n",
       "Model mode: AUTOMATIC\n",
       "CachingOptimizer state: EMPTY_OPTIMIZER\n",
       "Solver name: GLPK"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = Model(GLPK.Optimizer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "6142f199-151a-4263-be7f-6a22c967eebd",
   "metadata": {},
   "outputs": [],
   "source": [
    "@variable(m, x12, Bin)\n",
    "@variable(m, x13, Bin)\n",
    "@variable(m, x14, Bin)\n",
    "@variable(m, x25, Bin)\n",
    "@variable(m, x35, Bin)\n",
    "@variable(m, x36, Bin)\n",
    "@variable(m, x46, Bin)\n",
    "@variable(m, x57, Bin)\n",
    "@variable(m, x67, Bin);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "ce78f165-69e3-45f2-99ad-112b9f2438e5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ 3 x12 + 2 x13 + 4 x14 + 3 x25 + x35 + x36 + 2 x46 + 6 x57 + 5 x67 $$"
      ],
      "text/plain": [
       "3 x12 + 2 x13 + 4 x14 + 3 x25 + x35 + x36 + 2 x46 + 6 x57 + 5 x67"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@objective(m, Min, 3x12 + 2x13 + 4x14 + 3x25 + x35 + x36 + 2x46 + 6x57 + 5x67)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "9a08f531-863d-41ca-ae89-de5532752b0b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x12 + x13 + x14 = 1.0 $$"
      ],
      "text/plain": [
       "x12 + x13 + x14 = 1.0"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x12 + x13 + x14 == 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "dd747f11-5c38-44d4-b867-0842421263cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x12 - x25 = 0.0 $$"
      ],
      "text/plain": [
       "x12 - x25 = 0.0"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x12 - x25 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "32e0cc19-ea6f-409b-b74c-7e540aab8cf5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x13 - x35 - x36 = 0.0 $$"
      ],
      "text/plain": [
       "x13 - x35 - x36 = 0.0"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x13 - x35 - x36 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "d80758db-cf55-4bf7-b2d6-9999aff2c3b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x14 - x46 = 0.0 $$"
      ],
      "text/plain": [
       "x14 - x46 = 0.0"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x14 - x46 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "e0d216bb-f5e8-4a48-8ca7-e9fdb280e733",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x25 + x35 - x57 = 0.0 $$"
      ],
      "text/plain": [
       "x25 + x35 - x57 = 0.0"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x25 + x35 - x57 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "c8439e46-ba07-404b-ac3a-b8e074d6aa9f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x36 + x46 - x67 = 0.0 $$"
      ],
      "text/plain": [
       "x36 + x46 - x67 = 0.0"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x36 + x46 - x67 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "74664159-974e-4c32-aad6-a4e580ceb99f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ x57 + x67 = 1.0 $$"
      ],
      "text/plain": [
       "x57 + x67 = 1.0"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@constraint(m, x57 + x67 == 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "fcab5f12-388f-4965-b691-ba08544fe6a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "optimize!(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "5d8936a7-8611-4449-b36f-8391fdec3504",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Min 3 x12 + 2 x13 + 4 x14 + 3 x25 + x35 + x36 + 2 x46 + 6 x57 + 5 x67\n",
      "Subject to\n",
      " x12 + x13 + x14 = 1.0\n",
      " x12 - x25 = 0.0\n",
      " x13 - x35 - x36 = 0.0\n",
      " x14 - x46 = 0.0\n",
      " x25 + x35 - x57 = 0.0\n",
      " x36 + x46 - x67 = 0.0\n",
      " x57 + x67 = 1.0\n",
      " x12 binary\n",
      " x13 binary\n",
      " x14 binary\n",
      " x25 binary\n",
      " x35 binary\n",
      " x36 binary\n",
      " x46 binary\n",
      " x57 binary\n",
      " x67 binary\n",
      "\n"
     ]
    }
   ],
   "source": [
    "println(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "8721481d-2332-47f7-b1dc-f5f7f66a5fc4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "* Solver : GLPK\n",
       "\n",
       "* Status\n",
       "  Termination status : OPTIMAL\n",
       "  Primal status      : FEASIBLE_POINT\n",
       "  Dual status        : NO_SOLUTION\n",
       "  Message from the solver:\n",
       "  \"Solution is optimal\"\n",
       "\n",
       "* Candidate solution\n",
       "  Objective value      : 8.0\n",
       "  Objective bound      : 8.0\n",
       "\n",
       "* Work counters\n",
       "  Solve time (sec)   : 0.00011\n"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution_summary(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "3aa894a0-68f6-4a68-b6ce-f51ebd6470cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "A JuMP Model\n",
       "Minimization problem with:\n",
       "Variables: 9\n",
       "Objective function type: AffExpr\n",
       "`AffExpr`-in-`MathOptInterface.EqualTo{Float64}`: 7 constraints\n",
       "`VariableRef`-in-`MathOptInterface.ZeroOne`: 9 constraints\n",
       "Model mode: AUTOMATIC\n",
       "CachingOptimizer state: ATTACHED_OPTIMIZER\n",
       "Solver name: GLPK\n",
       "Names registered in the model: x12, x13, x14, x25, x35, x36, x46, x57, x67"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "values(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "4132b7cd-1c12-421e-b4c1-9c3cb663160a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9-element Vector{Tuple{VariableRef, Float64}}:\n",
       " (x12, 0.0)\n",
       " (x13, 1.0)\n",
       " (x14, 0.0)\n",
       " (x25, 0.0)\n",
       " (x35, 0.0)\n",
       " (x36, 1.0)\n",
       " (x46, 0.0)\n",
       " (x57, 0.0)\n",
       " (x67, 1.0)"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(x -> (x, value(x)), [x12, x13, x14, x25, x35, x36, x46, x57, x67])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d7b2afb-dad1-4169-a50e-1b46cbe65234",
   "metadata": {},
   "source": [
    "![](shortestpath-solution.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d2d8f18d-1b46-4ad4-825f-712bf137a84a",
   "metadata": {},
   "source": [
    "$$\n",
    "1 \\rightarrow 3 \\rightarrow  6 \\rightarrow 7\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec5b8245-55f7-49a8-8da8-4c95b68870c0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.7.1",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}