labs/seat_packing/seat_packing_lab_key.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seating Six Feet Apart\n",
    "\n",
    "### Introduction\n",
    "As campuses reopen for the fall semester, implementing social distancing measures is a top priority. Students need to maintain a 6 foot distance in lecture halls which means the seating capacity will drop. This is an issue for large and small classes when it comes to room assignments. For ENGRI 1101, we want to enable as many students as possible to attend in-person labs so that they can get immediate help or use the lab computers.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# imports -- make sure you run this cell\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import math, itertools\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "from ortools.linear_solver import pywraplp as OR\n",
    "import shapely\n",
    "from shapely.geometry import Polygon, Point"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Brainstorming\n",
    "\n",
    "### Questions\n",
    "- How can we decide which seats will be used so that the most number of seats are available without breaking social distancing rules?\n",
    "- How do we turn a classroom layout into something we can solve?\n",
    "\n",
    "A good strategy for tackling complex problems such as this is to work through small examples. Let's get started!\n",
    "\n",
    "**Example 1**\n",
    "Given the following rows of seats, think about how it could be represented as a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ex1 = plt.imread('images-lab/ex1.png')\n",
    "plt.axis('off')\n",
    "plt.imshow(ex1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What are the nodes?  \n",
    "    \n",
    "**A:** <font color='blue'>Chairs</font> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What are the edges? (Hint: What relationship b/w the nodes do we care about? Hint 2: Related to distance, but the edges do not have distance attributes.) \n",
    "\n",
    "**A:** <font color='blue'>Between chairs that cannot be used simultaneously (less than 6 feet)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's visualize the graph by adding the specific nodes and edges you previously described to the lists V and E. Assume that a chair's 6-foot radius includes 2 chairs to either side, front, back, and the diagonals. For example, if someone occupies seat 7, no one can occupy 5, 6, 8, 3, 11, 2, 4, 10, and 12."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Assume someone occupies seat 3. Which seats can not be occupied?\n",
    "\n",
    "**A:** <font color='blue'>Seats 1,2,4,6,7,8</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from seat_packing_lab import ex1\n",
    "\n",
    "V = [1,2,3,4,5,6,7,8,9,10,11,12]\n",
    "E = [(1,2),(1,3),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(2,7),(3,4),(3,6),(3,7),(3,8),(4,7),(4,8),\n",
    "     (5,6),(5,7),(5,9),(5,10),(6,7),(6,8),(6,9),(6,10),(6,11),(7,8),(7,10),(7,11),(7,12),(8,11),(8,12),\n",
    "     (9,10),(9,11),(10,11),(10,12),(11,12)]\n",
    "\n",
    "ex1(V, E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Give a feasible solution for this graph. It does not have to be optimal.  \n",
    "\n",
    "**A:** <font color='blue'>1,7,9</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** In general, what will a feasible solution look like?  \n",
    "\n",
    "**A:** <font color='blue'>A set of nonadjacent nodes</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A set of nonadjacent nodes is called an independent set. We will now look for an independent set of maximum cardinality.\n",
    "\n",
    "## Part 2: Solving\n",
    "\n",
    "To reiterate, an independent set must only contain nodes that are not adjacent to each other; if nodes joined by an edge are in the same set, then the set is not independent. The solution we want is not just any independent set--we want the one with the maximum cardinality or largest in size. It is possible for there to be more than one *maximum independent set* (MIS). This type of problem, also called maximum independent set, can be written as an integer program. Think about what constraints should be in the integer program to give us the optimal solution while working through the next example.\n",
    "\n",
    "**Example 2** Find a MIS."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from seat_packing_lab import ex2\n",
    "V2 = [1,2,3,4,5,6]\n",
    "E2 = [(1,2),(2,3),(1,4),(4,2),(2,5),(5,3),(4,6),(5,6)]\n",
    "ex2(V2, E2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Which nodes are in the maximum independent set? (This example has an unique MIS.)  \n",
    "\n",
    "**A:** <font color='blue'>1,3,6</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What are some strategies you tried or patterns you noticed when getting to the answer?  \n",
    "\n",
    "**A:** <font color='blue'>Will vary</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the edge (1, 2) either 1 or 2 or neither are in the MIS. For the triangle formed by nodes 1, 2, and 4, at most one of the three are in the MIS. The edge example suggests a constraint like $x_1 + x_2 \\leq 1$ where $x_1$ = {0 if node 1 not in MIS, 1 if in MIS} and $x_2$ likewise for node 2. The triangle constraint would be $x_1 + x_2 + x_4 \\leq 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Is the triangle constraint necessary or redundant?\n",
    "    \n",
    "**A:** <font color='blue'>Redundant (but could be a good cutting plane!)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, you are ready to write out the integer program! This OR-Tools model takes an adjacency matrix as an input. An adjacency matrix is a way of representing a graph as a matrix. Here, the entry at $(i,j)$ is 1 if $i$ and $j$ share an edge and 0 otherwise. Below, we load an adjacency matrix representing the 12 seat example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mis_seat_packing_example = pd.read_csv('data/mis_seat_packing_example.csv',index_col=0).astype(int)\n",
    "mis_seat_packing_example.columns = mis_seat_packing_example.columns.astype(int)\n",
    "display(mis_seat_packing_example)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Finish the defining the model below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mis(graph, integer=False):\n",
    "    \"\"\"A model for solving the maximum independent set problem.\n",
    "    \n",
    "    Args:\n",
    "        graph (pd.DataFrame): Graph represented by an adjacency matrix.\n",
    "    \"\"\"\n",
    "    NODES = list(graph.index)                # nodes\n",
    "    EDGES = []                               # edges\n",
    "    for i in NODES:\n",
    "        for j in NODES:\n",
    "            if i <= j and graph.at[i,j] == 1:\n",
    "                EDGES.append((i,j))\n",
    "    \n",
    "    # define model\n",
    "    m = OR.Solver('mis', OR.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
    "    \n",
    "    # decision variables\n",
    "    x = {} \n",
    "    for i in NODES:\n",
    "        if integer:\n",
    "            x[i] = m.IntVar(0, 1, ('%s' % (i)))\n",
    "        else:\n",
    "            x[i] = m.NumVar(0, 1, ('%s' % (i)))\n",
    "    \n",
    "    # objective function\n",
    "    m.Maximize(sum(x[i] for i in NODES))\n",
    "        \n",
    "    # subject to: no vertices in the set share an edge\n",
    "    # TODO: implement this constraint\n",
    "    \n",
    "    ### BEGIN SOLUTION\n",
    "    for i,j in EDGES:\n",
    "        m.Add(x[i] + x[j] <= 1)\n",
    "    ### END SOLUTION\n",
    "\n",
    "    return m,x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(m):\n",
    "    m.Solve()\n",
    "    print('Solution:')\n",
    "    print('Objective value =', m.Objective().Value())\n",
    "    return {var.name() : var.solution_value() for var in m.variables()}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run this cell to find an optimal solution to our first example!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = mis(mis_seat_packing_example, integer=True)\n",
    "solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What was the optimal solution?\n",
    "\n",
    "**A:** <font color='blue'>4 seats could be used (1, 4, 9, 12)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NOTE:** A clique is a set of nodes such that an edge exists for any pair of nodes in the clique. In example 1, {1,2,5,6}, {5,6,9,10}, {3,4,7,8}, and {7,8,11,12} are all the cliques. The union of them is the entire node set. For any clique, at most one node can be picked to be in an independent set; therefore, we have an upper bound of 4 on the cardinality of any independent set in example 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's solve the second example! First, we load the adjacency matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mis_small_example = pd.read_csv('data/mis_small_example.csv',index_col=0).astype(int)\n",
    "mis_small_example.columns = mis_small_example.columns.astype(int)\n",
    "display(mis_small_example)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = mis(mis_small_example, integer=True)\n",
    "solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3: Solving the Actual Data\n",
    "\n",
    "All we are given at the start is a plain room layout like this one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "room = plt.imread('images-lab/floorplan.jpg')\n",
    "plt.subplots(dpi=300)\n",
    "plt.axis('off')\n",
    "plt.imshow(room);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following is the same room layout with chairs and their center point redrawn on top. The drawings are done using the shapely package installed at the beginning. For the exact code, check out the ex_room() function in *seats_lab.py*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from seat_packing_lab import ex_room\n",
    "polys, points = ex_room()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A brief overview:\n",
    "- The layout image is imported.\n",
    "- We find the location of each chair (manually here but can also use computer vision).\n",
    "- Distances are in pixels, so we calculate the scale using the orange bar which we know is 10 feet as reference.\n",
    "- Blue chairs and points are plotted onto the image.\n",
    "\n",
    "To transform into a graph, we determine the edges by making a list of neighbors for each node. The guideline is that the distance between the central point of the original chair and the *boundary* of a potential 'neighbor' chair is no more than 85 pixels (6'). Read through and run the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (code by Sander Aarts)\n",
    "\n",
    "# define a dataframe of Polygons and Points\n",
    "df = pd.DataFrame(list(zip(polys, points)), \n",
    "               columns =['polygon', 'point'])\n",
    "\n",
    "# generate edges from distances\n",
    "df['neighbors'] = None # list of neighbors for each node\n",
    "\n",
    "# populate an adjacency matrix\n",
    "room_233 = np.zeros((len(df),len(df)))\n",
    "\n",
    "for i in range(df.shape[0]):\n",
    "    neighbors = list()     # get empty list\n",
    "    for j in range(df.shape[0]):\n",
    "        if (i != j):\n",
    "            dist = df['polygon'][j].distance(df['point'][i])\n",
    "            if (dist <= 85.0):    # 85 pixels = 6 feet\n",
    "                neighbors.append(df.index[j])\n",
    "                room_233[i,j] = 1\n",
    "    if (len(neighbors) > 0):\n",
    "        df['neighbors'][i] = neighbors\n",
    "room_233 = pd.DataFrame(room_233)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the graph ready, it is time to use the integer program we wrote previously."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = mis(room_233, integer=True)\n",
    "sol = solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a 2 seat (6.66%) improvement from the previous solution!\n",
    "\n",
    "We can update our dataframe and see what the solution looks like after its \"Cinderella\" moment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from seat_packing_lab import ex_room_sol\n",
    "ex_room_sol(df, sol)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge\n",
    "\n",
    "It was mentioned in the introduction that ENGRI 1101 wanted to maximize lab classroom seating. Unlike in lecture halls, the chairs have wheels and can be moved. How will you approach this problem?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show Rhodes 571\n",
    "room = plt.imread('images-lab/labclassroom.png')\n",
    "plt.subplots(dpi=300)\n",
    "plt.axis('off')\n",
    "plt.imshow(room);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imagine that all the chairs in Rhodes 571 are taken outside the room and brought back one at a time. The tables are fixed in place. (Ignore the laptops since they are movable.) Where can you place each chair that is brought back?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Will there be fewer or more nodes than chairs currently in the image?  \n",
    "**A:** <font color='blue'>More</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Describe where there might be nodes. Are they close or far apart?  \n",
    "**A:** <font color='blue'>Nodes will be super close together where there are tables</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# add drawings\n",
    "from seat_packing_lab import ex_lab\n",
    "polys2, points2 = ex_lab()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is this what you pictured? Each rectangle represents a possible chair placement. The distance between these possible chair placements is arbitrary. In reality, there are an infinite number of chair placements but then the problem would be too big. The arbitrary distance used was a good balance between accuracy and the problem size. Run the next cell to see how many nodes and edges we have here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# (code by Sander Aarts)\n",
    "\n",
    "# define a dataframe of Polygons and Points\n",
    "df2 = pd.DataFrame(list(zip(polys2, points2)), \n",
    "               columns =['polygon', 'point'])\n",
    "\n",
    "# populate an adjacency matrix\n",
    "room_571 = np.zeros((len(df2),len(df2)))\n",
    "\n",
    "for i in range(df2.shape[0]):\n",
    "    for j in range(df2.shape[0]):\n",
    "        if (i != j):\n",
    "            dist = df2['polygon'][j].distance(df2['point'][i])\n",
    "            if (dist <= 51):    # 51 pixels = 6 feet\n",
    "                room_571[i,j] = 1\n",
    "room_571 = pd.DataFrame(room_571)\n",
    "\n",
    "print('There are %d nodes and %d edges.' % (df2.shape[0], room_571.sum().sum()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even at this scale, our solvers can solve no problem! (Solving this integer program takes around 30 seconds)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = mis(room_571, integer=True)\n",
    "sol2 = solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "22 is the capacity if chairs are not moved. 29 is a **31.8%** increase!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show solution on room\n",
    "from seat_packing_lab import ex_lab_sol\n",
    "ex_lab_sol(df2, sol2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congratulations! You just got a taste of the actual process used to determine seating configurations subject to 6-feet social distancing requirements for Cornell (and it was done by previous ENGRI 1101 students too!)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}