9.3 (The Shortest Path Problem)/prob_1/9.3-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shortest Path Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "9.3-1. You need to take a trip by car to another town that you have never visited before. Therefore, you are studying a map to determine the shortest route to your destination. Depending on which route you choose, there are five other towns (call them A, B, C, D, E) that you might pass through on the way. The map\n",
    "shows the mileage along each road that directly connects two towns without any intervening towns. These numbers are sum- marized in the following table, where a dash indicates that there is no road directly connecting these two towns without going through any other towns.\n",
    "\n",
    "This problem is from Chapter 3, Section 1 (3.1 Prototype Example) of the Introduction to Operations Research,\n",
    "7th edition by Hillier and Lieberman."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div>\n",
    "<img src=\"img_9.3-1_table.png\" width=\"400\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph Notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- ![title](img_9.3-1_network.png) -->\n",
    "<div>\n",
    "<img src=\"img_9.3-1_network.png\" width=\"700\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let V represent the set of vertices in the graph:\n",
    "$$ V =\\{O,A,B,C,D,E,T\\} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let E represent the set of edges in the graph:\n",
    "\n",
    "$$ \n",
    "E = \\{OA, OB, OC, AB, AD, BD, BE, CB, CE, DE, DT, ET\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $u$ represent the first vertice and $v$ represent the second vertice in edge $UV$ in the path $UV-VW$ (U->V->W)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $v$ represent the first vertice and $w$ represent the second vertice in edge $VW$ in the path $UV-VW$ (U->V->W)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $x_{uv}$ $\\epsilon$ $(0,1)$\n",
    "<br>$x_{uv}$ = 1 if edge ${uv}$ is used, 0 otherwise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $d_{uv}$ represent the distance between edge $u$ and $v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mathematical Formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Minimize: Z $\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Z = \\sum_{u,v \\: \\epsilon \\:E} x_{uv}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$ \n",
    "s.t: \n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Constraint 1: Ensures path starts at origin and that each subsequent edge in the path is a continuation from the previous edge. In other words, if the trip enters into a given city (excluding final destination), it must leave the same city on the next leg of the path. \n",
    "<br>\n",
    "<br>\n",
    "$$\n",
    "\\sum_{u,v \\: \\epsilon \\:E} x_{uv} = \n",
    "\\sum_{v,w \\: \\epsilon \\:E} x_{uv} \\qquad \n",
    "\\forall  \\enspace v \\: \\epsilon \\:V\n",
    "$$ \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Constraint 2: Ensures the path reaches the final destination. \n",
    "<br>\n",
    "<br>\n",
    "$$\n",
    "\\sum_{u,t \\: \\epsilon \\:E} x_{ut} = 1 \n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DOCplex.mp Python Model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Install packages (only if needed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Import using conda in the current Jupyter kernel"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import sys\n",
    "# !conda install --yes --prefix {sys.prefix} numpy\n",
    "# !conda install --yes --prefix {sys.prefix} matplotlib\n",
    "# !conda install --yes --prefix {sys.prefix} docplex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or alternitively, import a using pip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import sys\n",
    "# !{sys.executable} -m pip install numpy\n",
    "# !{sys.executable} -m pip install matplotlib\n",
    "# !{sys.executable} -m pip install docplex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Import packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from docplex.mp.model import Model\n",
    "import docplex.mp.solution as Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Intializing the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>origin</th>\n",
       "      <th>destination</th>\n",
       "      <th>OD_pair</th>\n",
       "      <th>distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>O</td>\n",
       "      <td>A</td>\n",
       "      <td>OA</td>\n",
       "      <td>40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>O</td>\n",
       "      <td>C</td>\n",
       "      <td>OC</td>\n",
       "      <td>60</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>O</td>\n",
       "      <td>B</td>\n",
       "      <td>OB</td>\n",
       "      <td>50</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>A</td>\n",
       "      <td>B</td>\n",
       "      <td>AB</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>A</td>\n",
       "      <td>D</td>\n",
       "      <td>AD</td>\n",
       "      <td>70</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>B</td>\n",
       "      <td>D</td>\n",
       "      <td>BD</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>B</td>\n",
       "      <td>E</td>\n",
       "      <td>BE</td>\n",
       "      <td>55</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>C</td>\n",
       "      <td>B</td>\n",
       "      <td>CB</td>\n",
       "      <td>40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>C</td>\n",
       "      <td>E</td>\n",
       "      <td>CE</td>\n",
       "      <td>50</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>D</td>\n",
       "      <td>E</td>\n",
       "      <td>DE</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>D</td>\n",
       "      <td>T</td>\n",
       "      <td>DT</td>\n",
       "      <td>60</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>E</td>\n",
       "      <td>T</td>\n",
       "      <td>ET</td>\n",
       "      <td>80</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   origin destination OD_pair  distance\n",
       "0       O           A      OA        40\n",
       "1       O           C      OC        60\n",
       "2       O           B      OB        50\n",
       "3       A           B      AB        10\n",
       "4       A           D      AD        70\n",
       "5       B           D      BD        20\n",
       "6       B           E      BE        55\n",
       "7       C           B      CB        40\n",
       "8       C           E      CE        50\n",
       "9       D           E      DE        10\n",
       "10      D           T      DT        60\n",
       "11      E           T      ET        80"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Initialize the problem data\n",
    "df = pd.read_csv('data_arc.csv')\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('O', 'A'),\n",
       " ('O', 'C'),\n",
       " ('O', 'B'),\n",
       " ('A', 'B'),\n",
       " ('A', 'D'),\n",
       " ('B', 'D'),\n",
       " ('B', 'E'),\n",
       " ('C', 'B'),\n",
       " ('C', 'E'),\n",
       " ('D', 'E'),\n",
       " ('D', 'T'),\n",
       " ('E', 'T')]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edges = list((t.origin, t.destination) for t in df.itertuples())\n",
    "edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('D', 'T'), ('E', 'T')]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "last_arc_df = df[df['destination'] == 'T']\n",
    "last_arc = list((t.origin, t.destination) for t in last_arc_df.itertuples())\n",
    "last_arc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A', 'B', 'C', 'D', 'E'}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final_destination = 'T'\n",
    "cities = set(df['destination'])\n",
    "cities.remove(final_destination)\n",
    "cities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "# cities = ['A', 'B','C', 'D', 'E']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('O', 'A'): 40,\n",
       " ('O', 'C'): 60,\n",
       " ('O', 'B'): 50,\n",
       " ('A', 'B'): 10,\n",
       " ('A', 'D'): 70,\n",
       " ('B', 'D'): 20,\n",
       " ('B', 'E'): 55,\n",
       " ('C', 'B'): 40,\n",
       " ('C', 'E'): 50,\n",
       " ('D', 'E'): 10,\n",
       " ('D', 'T'): 60,\n",
       " ('E', 'T'): 80}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distance = dict([((t.origin, t.destination),t.distance ) for t in df.itertuples()])\n",
    "distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create the model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = Model('Shortest_Path')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "recall:\n",
    "Let $x_{uv}$ $\\epsilon$ $(0,1)$\n",
    "<br>$x_{uv}$ = 1 if edge ${uv}$ is used, 0 otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create decision variables\n",
    "x = m.binary_var_dict(edges, name = 'x')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color=green>  Objective Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "recall: Minimize Z $$Z = \\sum_{u,v } x_{uv}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: Shortest_Path\n",
      "\n",
      "Minimize\n",
      " obj: 40 x_O_A + 60 x_O_C + 50 x_O_B + 10 x_A_B + 70 x_A_D + 20 x_B_D + 55 x_B_E\n",
      "      + 40 x_C_B + 50 x_C_E + 10 x_D_E + 60 x_D_T + 80 x_E_T\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x_O_A <= 1\n",
      " 0 <= x_O_C <= 1\n",
      " 0 <= x_O_B <= 1\n",
      " 0 <= x_A_B <= 1\n",
      " 0 <= x_A_D <= 1\n",
      " 0 <= x_B_D <= 1\n",
      " 0 <= x_B_E <= 1\n",
      " 0 <= x_C_B <= 1\n",
      " 0 <= x_C_E <= 1\n",
      " 0 <= x_D_E <= 1\n",
      " 0 <= x_D_T <= 1\n",
      " 0 <= x_E_T <= 1\n",
      "\n",
      "Binaries\n",
      " x_O_A x_O_C x_O_B x_A_B x_A_D x_B_D x_B_E x_C_B x_C_E x_D_E x_D_T x_E_T\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "m.minimize(m.sum(distance[uv]*x[uv] for uv in edges))\n",
    "print(m.export_to_string())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### <font color=green>  Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall: Constraint 1:\n",
    "$$\n",
    "\\sum_{u,v \\: \\epsilon \\:E} x_{uv} = \n",
    "\\sum_{v,w \\: \\epsilon \\:E} x_{uv} \\qquad \n",
    "\\forall  \\enspace v \\: \\epsilon \\: Cities\n",
    "$$ \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall: Constraint 2:\n",
    "$$\n",
    "\\sum_{u,t \\: \\epsilon \\:E} x_{ut} = 1 \n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "docplex.mp.LinearConstraint[last_arc](x_D_T+x_E_T,EQ,1)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# constraint 1\n",
    "for c in cities:\n",
    "    m.add_constraint((m.sum(x[(u,v)] for u,v in edges if v==c))== \n",
    "                     (m.sum(x[(v,w)] for v,w in edges if v==c)), ctname='city_'+ c)\n",
    "\n",
    "# constraint 2\n",
    "m.add_constraint(m.sum(x[(i,j)] for i,j in last_arc if j=='T')== 1, ctname='last_arc')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: Shortest_Path\n",
      "\n",
      "Minimize\n",
      " obj: 40 x_O_A + 60 x_O_C + 50 x_O_B + 10 x_A_B + 70 x_A_D + 20 x_B_D + 55 x_B_E\n",
      "      + 40 x_C_B + 50 x_C_E + 10 x_D_E + 60 x_D_T + 80 x_E_T\n",
      "Subject To\n",
      " city_B: x_O_B + x_A_B + x_C_B - x_B_D - x_B_E = 0\n",
      " city_D: x_A_D + x_B_D - x_D_E - x_D_T = 0\n",
      " city_C: x_O_C - x_C_B - x_C_E = 0\n",
      " city_A: x_O_A - x_A_B - x_A_D = 0\n",
      " city_E: x_B_E + x_C_E + x_D_E - x_E_T = 0\n",
      " last_arc: x_D_T + x_E_T = 1\n",
      "\n",
      "Bounds\n",
      " 0 <= x_O_A <= 1\n",
      " 0 <= x_O_C <= 1\n",
      " 0 <= x_O_B <= 1\n",
      " 0 <= x_A_B <= 1\n",
      " 0 <= x_A_D <= 1\n",
      " 0 <= x_B_D <= 1\n",
      " 0 <= x_B_E <= 1\n",
      " 0 <= x_C_B <= 1\n",
      " 0 <= x_C_E <= 1\n",
      " 0 <= x_D_E <= 1\n",
      " 0 <= x_D_T <= 1\n",
      " 0 <= x_E_T <= 1\n",
      "\n",
      "Binaries\n",
      " x_O_A x_O_C x_O_B x_A_B x_A_D x_B_D x_B_E x_C_B x_C_E x_D_E x_D_T x_E_T\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(m.export_to_string())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Version identifier: 12.10.0.0 | 2019-11-27 | 843d4de\n",
      "CPXPARAM_Read_DataCheck                          1\n",
      "CPXPARAM_RandomSeed                              201903125\n",
      "CPXPARAM_MIP_Strategy_Branch                     1\n",
      "CPXPARAM_TimeLimit                               120\n",
      "CPXPARAM_MIP_Tolerances_MIPGap                   0.14999999999999999\n",
      "Tried aggregator 2 times.\n",
      "MIP Presolve added 1 rows and 1 columns.\n",
      "Aggregator did 1 substitutions.\n",
      "Reduced MIP has 6 rows, 12 columns, and 22 nonzeros.\n",
      "Reduced MIP has 11 binaries, 1 generals, 0 SOSs, and 0 indicators.\n",
      "Presolve time = 0.00 sec. (0.03 ticks)\n",
      "Found incumbent of value 160.000000 after 0.00 sec. (0.05 ticks)\n",
      "Probing time = 0.00 sec. (0.00 ticks)\n",
      "Tried aggregator 1 time.\n",
      "Detecting symmetries...\n",
      "MIP Presolve eliminated 1 rows and 1 columns.\n",
      "MIP Presolve added 1 rows and 1 columns.\n",
      "Reduced MIP has 6 rows, 12 columns, and 22 nonzeros.\n",
      "Reduced MIP has 11 binaries, 1 generals, 0 SOSs, and 0 indicators.\n",
      "Presolve time = 0.00 sec. (0.02 ticks)\n",
      "Probing time = 0.00 sec. (0.00 ticks)\n",
      "Clique table members: 8.\n",
      "MIP emphasis: balance optimality and feasibility.\n",
      "MIP search method: dynamic search.\n",
      "Parallel mode: deterministic, using up to 12 threads.\n",
      "Root relaxation solution time = 0.00 sec. (0.01 ticks)\n",
      "\n",
      "        Nodes                                         Cuts/\n",
      "   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap\n",
      "\n",
      "*     0+    0                          160.0000       60.0000            62.50%\n",
      "*     0+    0                          130.0000       60.0000            53.85%\n",
      "      0     0        cutoff            130.0000      130.0000        3    0.00%\n",
      "      0     0        cutoff            130.0000      130.0000        3    0.00%\n",
      "Elapsed time = 0.02 sec. (0.12 ticks, tree = 0.01 MB, solutions = 2)\n",
      "\n",
      "Root node processing (before b&c):\n",
      "  Real time             =    0.02 sec. (0.12 ticks)\n",
      "Parallel b&c, 12 threads:\n",
      "  Real time             =    0.00 sec. (0.00 ticks)\n",
      "  Sync time (average)   =    0.00 sec.\n",
      "  Wait time (average)   =    0.00 sec.\n",
      "                          ------------\n",
      "Total (root+branch&cut) =    0.02 sec. (0.12 ticks)\n"
     ]
    }
   ],
   "source": [
    "m.parameters.timelimit=120\n",
    "m.parameters.mip.strategy.branch=1\n",
    "m.parameters.mip.tolerances.mipgap=0.15\n",
    "\n",
    "soln = m.solve(log_output=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "JobSolveStatus.OPTIMAL_SOLUTION\n"
     ]
    }
   ],
   "source": [
    "print(m.get_solve_status())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solution for: Shortest_Path\n",
      "objective: 130\n",
      "x_O_A = 1\n",
      "x_A_B = 1\n",
      "x_B_D = 1\n",
      "x_D_T = 1\n"
     ]
    }
   ],
   "source": [
    "soln.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'D', 'T']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = []\n",
    "for i in x:\n",
    "    if soln.get_var_value(x[i]) >0:\n",
    "        lst.append(i[1])\n",
    "lst\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "O->A\n",
      "A->B\n",
      "B->D\n",
      "D->T\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[('O', 'A', 'O->A', 40),\n",
       " ('A', 'B', 'A->B', 10),\n",
       " ('B', 'D', 'B->D', 20),\n",
       " ('D', 'T', 'D->T', 60)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = []\n",
    "for u,v in edges:\n",
    "    if soln.get_var_value(x[u,v])> 0:\n",
    "        arc = u+'->'+v\n",
    "        print(arc)\n",
    "        solution = (u, v, arc,distance[u,v])\n",
    "        lst.append(solution)\n",
    "lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>starting_city</th>\n",
       "      <th>next_city</th>\n",
       "      <th>arc_name</th>\n",
       "      <th>distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>O</td>\n",
       "      <td>A</td>\n",
       "      <td>O-&gt;A</td>\n",
       "      <td>40</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>A</td>\n",
       "      <td>B</td>\n",
       "      <td>A-&gt;B</td>\n",
       "      <td>10</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>B</td>\n",
       "      <td>D</td>\n",
       "      <td>B-&gt;D</td>\n",
       "      <td>20</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>D</td>\n",
       "      <td>T</td>\n",
       "      <td>D-&gt;T</td>\n",
       "      <td>60</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  starting_city next_city arc_name  distance\n",
       "0             O         A     O->A        40\n",
       "1             A         B     A->B        10\n",
       "2             B         D     B->D        20\n",
       "3             D         T     D->T        60"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.DataFrame.from_records(lst, columns=['starting_city', 'next_city','arc_name','distance'])\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}