mathematical_programming/schedule_flight_crew/flight_crew_schedule.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e2e93b50",
   "metadata": {},
   "source": [
    "# Import Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e5af8a44",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:05.395527Z",
     "start_time": "2021-07-31T17:55:02.832321Z"
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import cvxpy as cp\n",
    "import numpy as np\n",
    "import gdown"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4a45d599",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.071543Z",
     "start_time": "2021-07-31T17:55:05.398573Z"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Downloading...\n",
      "From: https://drive.google.com/uc?id=1TPXha3ojq2e9ygGN9r2249jPieaKL1ZR\n",
      "To: /Users/khuyen/Data-science/mathematical_programming/schedule_flight_crew/flight_schedule.csv\n",
      "100%|██████████| 545/545 [00:00<00:00, 308kB/s]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'flight_schedule.csv'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "url = \"https://drive.google.com/uc?id=1TPXha3ojq2e9ygGN9r2249jPieaKL1ZR\"\n",
    "output = \"flight_schedule.csv\"\n",
    "gdown.download(url, output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "12f014a6",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.087808Z",
     "start_time": "2021-07-31T17:55:07.076727Z"
    }
   },
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"flight_schedule.csv\", index_col=0, header=1)\n",
    "schedule = df.iloc[:-2]\n",
    "cost = df.iloc[-2]\n",
    "hours = df.iloc[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "819bde6a",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.099532Z",
     "start_time": "2021-07-31T17:55:07.091994Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1    5\n",
       "2    4\n",
       "3    4\n",
       "4    9\n",
       "5    7\n",
       "6    8\n",
       "7    3\n",
       "8    3\n",
       "Name: Cost ($1000) for each sequence, dtype: int64"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "030c95fe",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.107622Z",
     "start_time": "2021-07-31T17:55:07.101835Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1     396\n",
       "2     352\n",
       "3    1022\n",
       "4     847\n",
       "5     687\n",
       "6     531\n",
       "7     236\n",
       "8     179\n",
       "Name: Hours, dtype: int64"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d4e3d00c",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.119576Z",
     "start_time": "2021-07-31T17:55:07.110942Z"
    }
   },
   "outputs": [],
   "source": [
    "schedule = schedule.applymap(lambda x: 1 if x >= 1 else x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "984ca3fe",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.138755Z",
     "start_time": "2021-07-31T17:55:07.122101Z"
    }
   },
   "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>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Requirement (Flight)</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>New York to Buffalo</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>New York to Cincinnati</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>New York to Chicago</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Buffalo to Chicago</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Chicago to Cincinnati</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Cincinnati to Pittsburgh</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Cincinnati to Buffalo</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Buffalo to New York</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Pittsburgh to New York</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Chicago to New York</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                          1  2  3  4  5  6  7  8\n",
       "Requirement (Flight)                            \n",
       "New York to Buffalo       1  0  0  1  0  0  1  0\n",
       "New York to Cincinnati    0  1  0  0  1  0  0  0\n",
       "New York to Chicago       0  0  1  0  0  1  0  1\n",
       "Buffalo to Chicago        1  0  0  1  0  0  0  0\n",
       "Chicago to Cincinnati     0  0  1  1  0  1  0  0\n",
       "Cincinnati to Pittsburgh  0  1  0  1  0  1  0  0\n",
       "Cincinnati to Buffalo     0  0  1  0  1  0  0  0\n",
       "Buffalo to New York       0  0  1  0  1  0  1  0\n",
       "Pittsburgh to New York    0  1  0  1  0  1  0  0\n",
       "Chicago to New York       1  0  0  0  0  0  0  1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82a072d4",
   "metadata": {},
   "source": [
    "# Minimize Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f0e7f74",
   "metadata": {},
   "source": [
    "Input parameters: \n",
    "* $a$: 0-1 matrix\n",
    "* $c_j$: cost for each feasible sequence of flight ($j=1, 2, ..8$)\n",
    "* $b_i$: requirement vector ($i=1, 2, ..., 10$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "32f63055",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.147614Z",
     "start_time": "2021-07-31T17:55:07.144564Z"
    }
   },
   "outputs": [],
   "source": [
    "a = schedule.values\n",
    "c = cost.values\n",
    "b = np.ones(len(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccab3549",
   "metadata": {},
   "source": [
    "Decision variable: \n",
    "\n",
    "$y_j=1$ or $0$: Whether the flight sequence $j$ is selected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "04bb647b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.155428Z",
     "start_time": "2021-07-31T17:55:07.152292Z"
    }
   },
   "outputs": [],
   "source": [
    "y = cp.Variable(len(c), boolean=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59ba8d11",
   "metadata": {},
   "source": [
    "Constraint: ensure that at least one crew is assigned to each flight.\n",
    "\n",
    "For example, to make sure that at least one crew is assigned to the first flight, we have constraint:\n",
    "$$y_1 + y_4 + y_7 \\geq 1$$\n",
    "\n",
    "Generalize this constraint for all 10 flights, we have:\n",
    "\n",
    "$$\n",
    "\\begin{pmatrix}\n",
    "  1  &  0  &  0  &  1  &  0  &  0  &  1  &  0 \\\\\n",
    "  0  &  1  &  0  &  0  &  1  &  0  &  0  &  0 \\\\\n",
    "  0  &  0  &  1  &  0  &  0  &  1  &  0  &  1 \\\\\n",
    "  1  &  0  &  0  &  1  &  0  &  0  &  0  &  0 \\\\\n",
    "  0  &  0  &  1  &  1  &  0  &  1  &  0  &  0 \\\\\n",
    "  0  &  1  &  0  &  1  &  0  &  1  &  0  &  0 \\\\\n",
    "  0  &  0  &  1  &  0  &  1  &  0  &  0  &  0 \\\\\n",
    "  0  &  0  &  1  &  0  &  1  &  0  &  1  &  0 \\\\\n",
    "  0  &  1  &  0  &  1  &  0  &  1  &  0  &  0 \\\\\n",
    "  1  &  0  &  0  &  0  &  0  &  0  &  0  &  1 \n",
    "\\end{pmatrix}\n",
    "\\begin{pmatrix}\n",
    "y_1\\\\\n",
    "y_2\\\\\n",
    "y_3\\\\\n",
    "y_4\\\\\n",
    "y_5\\\\\n",
    "y_6\\\\\n",
    "y_7\\\\\n",
    "y_8\\\\\n",
    "\\end{pmatrix} \\geq\n",
    "\\begin{pmatrix}\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "1\\\\\n",
    "\\end{pmatrix}\n",
    "$$\n",
    "\n",
    "$y_j=0$ or $1$ $j=1,2,...,8$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6a6f579d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.160497Z",
     "start_time": "2021-07-31T17:55:07.157266Z"
    }
   },
   "outputs": [],
   "source": [
    "constraints = [a @ y >= b]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bcd9014",
   "metadata": {},
   "source": [
    "Objective: minimize the total cost of assigning crews to the selected sequence of flights\n",
    "\n",
    "$$\\min \\;\\; z=5y_1 + 4y_2 + 4y_3 + 9y_4 + 7y_5 + 8y_6 + 3y_7 + 3y_8$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "f3366e2e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.165819Z",
     "start_time": "2021-07-31T17:55:07.162664Z"
    }
   },
   "outputs": [],
   "source": [
    "obj = cp.Minimize(c @ y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8728c07c",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.171338Z",
     "start_time": "2021-07-31T17:55:07.168580Z"
    }
   },
   "outputs": [],
   "source": [
    "prob = cp.Problem(obj, constraints)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "0cbca63f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.190545Z",
     "start_time": "2021-07-31T17:55:07.173979Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob.solve(solver=cp.GLPK_MI)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "579fae76",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.198041Z",
     "start_time": "2021-07-31T17:55:07.193277Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal\n"
     ]
    }
   ],
   "source": [
    "print(prob.status)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c47c1989",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.206510Z",
     "start_time": "2021-07-31T17:55:07.201891Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 1. 1. 0. 0. 0. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "print(y.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad7944ac",
   "metadata": {},
   "source": [
    "# Hours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "468567cd",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.215358Z",
     "start_time": "2021-07-31T17:55:07.209546Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 396,  352, 1022,  847,  687,  531,  236,  179])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h = hours.values\n",
    "h"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85f2f082",
   "metadata": {},
   "source": [
    "Constraints:\n",
    "* There must be at least one airplane per flight\n",
    "$$a \\cdot y\\geq b$$\n",
    "\n",
    "* The total hours of flights must be less than or equal to 1700\n",
    "$$h \\cdot y \\leq 1700$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "0755033c",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.221157Z",
     "start_time": "2021-07-31T17:55:07.217843Z"
    }
   },
   "outputs": [],
   "source": [
    "constraints = [a @ y >= b, h @ y <= 1700]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "357eebce",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.225756Z",
     "start_time": "2021-07-31T17:55:07.223226Z"
    }
   },
   "outputs": [],
   "source": [
    "prob = cp.Problem(obj, constraints)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "bbaac0e2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.243097Z",
     "start_time": "2021-07-31T17:55:07.228092Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob.solve(solver=cp.GLPK_MI)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "4899ab4d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-07-31T17:55:07.251831Z",
     "start_time": "2021-07-31T17:55:07.246412Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 0. 0. 0. 1. 1. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "print(y.value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "774bbe55",
   "metadata": {},
   "source": [
    "$$396 + 352 + 1022 = 1770$$\n",
    "$$396 + 687 + 531 = 1614$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22d3e4db",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "hide_input": false,
  "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.8.10"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}