{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#import sys\n",
    "#!{sys.executable} -m pip install ortools \n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import random\n",
    "from ortools.linear_solver import pywraplp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "InputData = pd.read_excel(\"Residence.xlsx\", sep=\"\\t\")\n",
    "InputData"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Determine the start time\n",
    "StartTime = time.process_time()\n",
    "\n",
    "# Define our Linear Program\n",
    "Solver = pywraplp.Solver('Solver', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
    "\n",
    "# Define the Preference Coefficient P[i,j], for Residence Assistant i working in Shift j\n",
    "n=18\n",
    "m=33\n",
    "\n",
    "P = np.zeros(shape=(n, m), dtype=int)\n",
    "blocks = [\"RA 1\", \"RA 2\", \"RA 3\", \"RA 4\", \"RA 5\", \"RA 6\", \"RA 7\", \"RA 8\", \"RA 9\", \n",
    "          \"RA 10\", \"RA 11\", \"RA 12\",\"RA 13\", \"RA 14\", \"RA 15\", \"RA 16\", \"RA 17\", \"RA 18\"]\n",
    "\n",
    "for j in range(m):\n",
    "    for i in range(n):\n",
    "        P[i,j] = InputData[blocks[i]][j]\n",
    "        \n",
    "# Define the binary variable X[i,j], which will equal 1 if Residence Assistant i is assigned to Shift j\n",
    "X = {}\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        X[i,j] = Solver.IntVar(0, 1, 'X[%d, %d]' % (i,j))\n",
    "        \n",
    "# Set up our Happiness Function, which maximizes the total number of Happiness Points\n",
    "HappinessFunction = Solver.Sum(P[i,j]*X[i,j] for i in range(n) for j in range(m))\n",
    "Solver.Maximize(HappinessFunction)\n",
    "\n",
    "# Include our first constraint: Nobody works more than one block break or special weekend\n",
    "for i in range(n):\n",
    "    Solver.Add(Solver.Sum([X[i,j] for j in [8,16,24,26,30,32]]) <= 1)\n",
    "                       \n",
    "# Include our second constraint: Each week must be covered by exactly two RAs\n",
    "for j in range(m):\n",
    "    Solver.Add(Solver.Sum([X[i,j] for i in range(n)]) == 2)\n",
    "\n",
    "# Include our third constraint: Each RA must work at least 6 points and at most 7 points\n",
    "for i in range(n):\n",
    "    Solver.Add(Solver.Sum([X[i,j] for j in range(m)]) + Solver.Sum([X[i,2*j] for j in range(16)])\n",
    "               + Solver.Sum([X[i,j] for j in [8,16,24,26,30,32] ]) >= 6)\n",
    "for i in range(n):\n",
    "    Solver.Add(Solver.Sum([X[i,j] for j in range(m)]) + Solver.Sum([X[i,2*j] for j in range(16)])\n",
    "               + Solver.Sum([X[i,j] for j in [8,16,24,26,30,32] ]) <= 7)\n",
    "    \n",
    "# Solve the Integer Linear program\n",
    "Output = Solver.Solve()\n",
    "TotalPoints = round(Solver.Objective().Value())\n",
    "\n",
    "# Determine the total time of running the program.\n",
    "TotalTime = round(time.process_time() - StartTime, 4)\n",
    "\n",
    "# Output one of the possible optimal solutions.\n",
    "print(\"Python returns a solution with\", TotalPoints, \"Total Happiness Points in\", TotalTime, \"seconds\")\n",
    "pd.options.mode.chained_assignment = None\n",
    "OutputData = InputData.copy()\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if X[i,j].solution_value()==0:\n",
    "            OutputData[blocks[i]][j] = \"\"\n",
    "OutputData "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if X[i,j].solution_value()==1:\n",
    "            print(blocks[i], \"works\", InputData[\"On-Call Week\"][j], \"with score\", P[i,j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for j in range(m):\n",
    "    for i in range(n):\n",
    "        if X[i,j].solution_value()==1:\n",
    "            print(InputData[\"On-Call Week\"][j], \"works\", blocks[i], \"with score\", P[i,j])"
   ]
  },
  {
   "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": 2
}