{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Lab 5 (Part 2) - Stochastic Optimization\n", "\n", "#### Authors:\n", "\n", "##### v1.0 (2015 Fall) Kabir Chandrasekher \\*, Max Kanwal \\*, Kangwook Lee \\*\\*, Kannan Ramchandran \\*\\*\n", "\n", "As you may have noticed, many quantities in the real world are random and many problems that we face involve optimizing in the presence of uncertainty. In this lab, we will look at some optimization methods where some of the constraints are random. \n", "\n", "For a motivating exapmle, we can look at scheduling in healthcare. Hospitals lose large amounts of money each year due to scheduling problems. One of the biggest culprits for this loss of money is the scheduling of surgeries. Recent studies estimate that it costs $\\sim \\$62$ each minute to keep an operating room running$^1$. It is easy to imagine a scenario in which a seemingly decent schedule incurs huge amounts of cost for the hospital: for example scheduling $8$ surgeries for an hour each and having each surgery finish $10$ minutes early. This seems like a rather innocuous schedule, but at the end of the day lost the hospital $\\$4960$! \n", "\n", "The hardness of this problem stems from the random nature of surgery times (which we will call processing times), and hospitals today don't have an efficent way of dealing with these processing times. For example, many hospitals have scheduling departments that construct weekly schedules by hand. In this lab, we are going to use what we have learned about probability and try to help the hospitals out. We will focus on creating offline schedules (so that we know nothing about the realization of job durations) in this lab." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## A Brief Primer on Linear Programming and Optimization\n", "\n", "Linear programs are defined by a set of decision variables, a linear cost function (called the objective), and a set of linear inequalities involving the decision variables. Often, when we model problems as linear programs, we consider a cost vector $c=(c_1,c_2,...c_n)$, a decision vector $x=(x_1,x_2,...,x_n)$, a constraint matrix $A=(A_1,A_2,...,A_n)$ where $A_i$ is the $ith$ column. We additionally consider a \"goal\" vector $b$ of dimension $n$. The \"standard form\" linear program is:\n", "\n", "$$\n", "\\begin{equation}\n", "\\begin{split}\n", "& \\underset{x}{\\text{min }} c'x \\\\\n", "& \\text{subject to } Ax \\le b \\\\\n", "& x \\ge 0\n", "\\end{split}\n", "\\end{equation}\n", "$$\n", "\n", "In a general optimization problem, we need not restrict ourselves to linear objective functions (although linear objectives are much nicer to deal with), we simply have an objective function $F(x)$ whose domain is the set of decision variables $x$. \n", "\n", "In this lab, we will be using the Python library PuLP as our LP-solver, as we have found it is the fastest and easiest to use. For your projects, you are free to use any optimization software you want (such as cvxopt, etc.). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathcal{Q}1.$ Scheduling Night Shifts (Bertsimas)\n", "\n", "A hospital wants to make a weekly night shift (12pm-8am) schedule for its nurses. The demand for nurses for the night shift on day $j$ is an integer $d_j, j=1,...,7$. Every nurse works $5$ days in a row on the night shift. The problem is to find the minimal number of nurses the hospital needs to hire. \n", "\n", "Let's define our decision variables to be $x=(x_1,x_2,..,x_7)$, where $x_i$ denotes the number of nurses starting their week on day $j$ (do you see why this is a good model?). This gives us the following linear program:\n", "\n", "$$\n", "\\begin{equation}\n", "\\begin{split}\n", "& \\text{minimize} \\sum_{i=1}^{7} x_i \\\\\n", "\\text{subject to } & x_1 + x_4 + x_5 + x_6 + x_7 \\ge d_1 \\\\\n", "& x_1 + x_2 + x_5 + x_6 + x_7 \\ge d_2 \\\\\n", "& x_1 + x_2 + x_3 + x_6 + x_7 \\ge d_3 \\\\\n", "& x_1 + x_2 + x_3 + x_4 + x_7 \\ge d_4 \\\\\n", "& x_1 + x_2 + x_3 + x_4 + x_5 \\ge d_5 \\\\\n", "& x_2 + x_3 + x_4 + x_5 + x_6 \\ge d_6 \\\\\n", "& x_3 + x_4 + x_5 + x_6 + x_7 \\ge d_7 \\\\\n", "& x_j \\ge 0\n", "\\end{split}\n", "\\end{equation}\n", "$$\n", "Now, let's write a function to solve this lp given a $d$ vector:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Populating the interactive namespace from numpy and matplotlib\n" ] } ], "source": [ "%pylab inline\n", "import numpy as np\n", "from pulp import *\n", "import matplotlib.pyplot as plt\n", "\n", "def night_shifts(d):\n", " \"\"\"\n", " Determine the optimal night schedule \n", " Inputs: d- a vector of 7 integers representing how many nurses\n", " need to be available to work on each day\n", " Outputs: a vector of 7 integers (the x vector) representing how many nurses \n", " start working on each day\n", " \"\"\"\n", " prob = LpProblem(\"schedule\",LpMinimize) ###Create the linear program\n", " \n", " ### Variable Creation ###\n", " x = np.empty( 7,'object') ##number of nurses starting on each day\n", " for i in range(7):\n", " x[i] = LpVariable(\"x {0}\".format(i), lowBound = 0,cat='Continuous')\n", " \n", " ### Objective Formulation ###\n", " prob += lpSum(x)\n", " \n", " ###Constraint Formulation ###\n", " prob += (x[0] + x[3] + x[4] + x[5] + x[6] >= d[0])\n", " prob += (x[0] + x[1] + x[4] + x[5] + x[6] >= d[1])\n", " prob += (x[0] + x[1] + x[2] + x[5] + x[6] >= d[2])\n", " prob += (x[0] + x[1] + x[2] + x[3] + x[6] >= d[3])\n", " prob += (x[0] + x[1] + x[2] + x[3] + x[4] >= d[4])\n", " prob += (x[1] + x[2] + x[3] + x[4] + x[5] >= d[5])\n", " prob += (x[2] + x[3] + x[4] + x[5] + x[6] >= d[6])\n", " \n", " for i in xrange(7):\n", " prob += (x[i] >= 0)\n", " \n", " ### Solve the lp ###\n", " prob.solve()\n", " \n", " ### Extract ###\n", " print \"x =\", [value(p) for p in x]\n", " rounded_x = [np.ceil(value(p)) for p in x]\n", " print \"The total number of nurses needed is: {}\".format(sum(rounded_x))\n", " return prob" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x = [0.0, 3.0, 0.0, 2.0, 5.0, 0.0, 12.0]\n", "The total number of nurses needed is: 22.0\n" ] } ], "source": [ "d_vals = np.array([5,20,10,17,10,10,19])\n", "schedule = night_shifts(d_vals)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that one can't have a non-integral number of nurses start work on a certain day, so this is an integer linear programming problem, which is NP-hard. In the code above, we \"relax\" the integrality constraints, and can round the $x$-values to get an answer (that is no longer guaranteed to be optimal). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Stochastic Programming\n", "\n", "Now that we know what linear programs are, we can increase the difficulty a bit with stochastic optimization. Linear programming for scheduling is useful when we know exactly what the job durations are and there is no variation, but what happens when the job durations are random variables?\n", "\n", "This is where stochastic optimization comes in. Say that, like in linear programming, we have a cost function $F(A,P)$ which gives the cost of a schedule whose starting times are $A=(A_1,A_2,...,A_n)$ and processing times are $P=(p_1,p_2,...,p_n)$. In stochastic programming, the $P$ vector is a random vector, so our objective becomes $\\underset{x}{\\text{min }}E_p\\bigl[F(x,P)\\bigr]$. Thus, we consider the problem:\n", "$$\n", "\\begin{equation}\n", "\\begin{split}\n", "&\\underset{x}{\\text{min }}E_p\\bigl[F({x},P)\\bigr] \\\\\n", "& \\text{subject to }Ax \\le b \\\\\n", "& x \\ge 0\n", "\\end{split}\n", "\\end{equation}\n", "$$\n", "This is the stochastic programming equivalent of the standard form linear optimization problem. \n", "\n", "\n", "### Sampling Approximation to Stochastic Programming\n", "Of course, most linear program solvers don't take random variables as input; they only solve deterministic linear programs. To deal with this, we consider leting the objective be:\n", "$$\n", "\\begin{equation}\n", "\\begin{split}\n", "&\\underset{x}{\\text{min }}\\frac{1}{L}\\sum_{i=1}^{L}F(x,P_i) \\\\\n", "& Ax \\le b \\\\\n", "& x \\ge 0\n", "\\end{split}\n", "\\end{equation}\n", "$$\n", "This implies that we give the linear program $L$ realizations of the processing times vector ($P$) and minimize over the average of the objective evaluated at each realization." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathcal{Q}2.$ Maximizing Patient Happiness\n", "\n", "Let's return to scheduling surgery cases. In some hospitals around the world, the accepted version of scheduling is to tell all patients to show up at the beginning of the day and wait until the hospital can perform their operation. Assume the hospital you are working with has decided to try to increase patient happiness, but is unwilling to change this method of scheduling. Thus, they want to minimize the total waiting time of the patients. We will model this by trying to minimize the maximum $\\textit{flow time}$. Intuitively, this means that if there are $n$ cases scheduled to be performed on a day, the flowtime of the first case is the processing time of its surgery, and then it exits the system, whereas the $i$th case is in the system for all preceding cases, so has a flowtime of the sum of all of these cases with its own: $F_i = p_1 + p_2 + ... + p_i$. The hospital has found that its surgeons and patients are happiest when the flow time is the smallest. Thus, the objective we would like to look at is $\\underset{x}{\\text{min }}{\\sum_{i=1}^{n}F_i}$ where $F_i$ is the flow time of the $i$th case and $x_i$ is the starting time of the $i$th case. Note that here, the *sequence* of cases is variable, that is if the sequence $N={1,2,...,n}$ of cases are to be scheduled, the order of the cases will be some permutation $\\pi(N)$. Now that we have the preliminaries, we will write a function to minimize the total flowtime of the system. We will assume that each case duration has an exponential distribution with some passed in parameters.\n", "\n", "\n", "### a. Write a function to generate the samples of case durations." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def generate_samples(n, K, parameters):\n", " \"\"\"\n", " Generate K samples of n exponential random variables with the given parameters\n", " Inputs: n- the number of cases to be scheduled\n", " K- the number of samples to be taken\n", " parameters- a list of length n\n", " Outputs\n", " \"\"\"\n", " assert len(parameters) == n\n", " ret = np.empty( (n,K) , 'object')\n", " for i in xrange(n):\n", " ret[i] = np.random.exponential(parameters[i], K)\n", " return ret" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### b. Formulate a stochastic LP for this problem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's outline the variables:\n", "\n", "- $x_{ij}$ is the indicator variable that case $i$ is scheduled in slot $j$\n", "- $D_{li}$ is the duration of case $i$ in sample $l$\n", "\n", "The objective:\n", "$$\n", "\\frac{1}{L}\\sum_{l=1}^{L}\\biggl(\\sum_{k=0}^{n}\\sum_{j=0}^{k}\\sum_{i=0}^{n}x_{ij}D_{li}\\biggr)\n", "$$\n", "This is an intimidating sum with a simple explanation. The outside sum is over all samples; we average over everything in parentheses. Inside the parentheses we sum over all cases happening in a day with a temporary variable $k$. Then, we sum over all cases that have occurred up to slot $k$ by summing from $j=0 \\rightarrow k$. Finally, within this sum, we add the appropriate duration. Note that $\\sum_{i=0}^{n}x_{ij}D_{li} = P_{lj}$ where $P_{lj}$ can be considered the processing time of case $j$ in sample $i$. \n", "\n", "The constraints:\n", "\n", "- $\\sum_{i=0}^{n}x_{ij} = 1$ There can only be one case scheduled in each slot and each case must be scheduled\n", "- $\\sum_{j=0}^{n}x_{ij} = 1$ Only one case of each type can be scheduled\n", "\n", "In this formulation, the $x_{ij}$ are the decision variables, and the $D_{li}$ are known." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### c. Write a function to solve the above problem." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def stochastic_flowtime(samples):\n", " \"\"\"\n", " Put stuff here\n", " \"\"\"\n", " (n, L) = samples.shape\n", " \n", " prob = LpProblem(\"schedule\",LpMinimize) ###Create the linear program\n", " \n", " ### Variable Creation ###\n", " D = samples\n", " x = np.empty( (n,n) ,'object') #indicator\n", " for i,j in itertools.product(xrange(n), xrange(n)):\n", " x[i, j] = LpVariable(\"x {0} {1}\".format(i, j), cat='Binary') \n", " \n", " ### Objective Formulation ###\n", " obj = []\n", " for l in xrange(L):\n", " inner_obj = []\n", " for k in xrange(n):\n", " for j in xrange(k):\n", " for i in xrange(n):\n", " inner_obj.append(x[i,j] * D[i,l])\n", " obj.append(lpSum(inner_obj))\n", " prob += lpSum(obj) * 1.0/L\n", " \n", " ### Constraint Formulation ###\n", " for j in xrange(n):\n", " prob += lpSum(x[:,j]) == 1\n", " \n", " for i in xrange(n):\n", " prob += lpSum(x[i,:]) == 1\n", " \n", " ### Solve the lp ###\n", " prob.solve()\n", " \n", " ### Extract ###\n", " schedule = []\n", " for j in xrange(n):\n", " for i in xrange(n):\n", " if not value(x[i,j]) == 0:\n", " print x[i,j], value(x[i,j])\n", " schedule.append(i)\n", " \n", " print \"\\n\"\n", " for j in xrange(n):\n", " print \"The case in slot {0} is case {1}\".format(j,schedule[j])\n", " print \"The average duration for this case is: {} \\n\"\\\n", " .format(np.sum(samples[schedule[j],:])/L)\n", " return schedule" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x_1_0 1.0\n", "x_2_1 1.0\n", "x_0_2 1.0\n", "\n", "\n", "The case in slot 0 is case 1\n", "The average duration for this case is: 1.08941861881 \n", "\n", "The case in slot 1 is case 2\n", "The average duration for this case is: 8.85515719155 \n", "\n", "The case in slot 2 is case 0\n", "The average duration for this case is: 9.80458312884 \n", "\n" ] }, { "data": { "text/plain": [ "[1, 2, 0]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "### Example ###\n", "case_parameters = [10,1,9]\n", "samples = generate_samples(3, 100, case_parameters)\n", "stochastic_flowtime(samples)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice that the order of cases is in increasing order of their expectations. It turns out that for this specific example, we can show that ordering by expectation is optimal! Unfortunately, in many scheduling problems this is not true, and simple heuristics such as that turn out to give poor results. \n", "\n", "Feel free to play around with different parameters, number of samples and number of cases in the previous example. You won't be expected to do so, but it will help you get a feel for these types of problems. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Project Requirements" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Hopefully, this lab was a gentle introduction to linear programming, scheduling, and stochastic scheduling. For the project this semester, you have the choice of formulating and solving a stochastic optimization model. Within this scope, you may choose to do one of the following:\n", "\n", "#### #1. In the real world, the objective function for scheduling in healthcare used is not nearly as nice as what we have used in this lab. Most hospitals would like to optimize for their own costs (by increasing operating room utilization) while simultaneously optimizing for patient happiness. Thus, the objective function normally considered is of the form: \n", "$$\n", "\\sum_{i=1}^{n} \\alpha E \\bigl[W_i\\bigr] + \\beta E\\bigl[I_i\\bigr]\n", "$$\n", "where $W_i = (C_{i} - A_{i+1})^{+}$ and $I_i=(A_{i+1} - C_{i})^{+}$, $A_i$ gives the appointment time of case $i$ and $C_{i}$ gives the completion time of case $i$.\n", "\n", "\n", "\n", "#### #2. Find a situation where you think stochastic optimization would help such as airport scheduling, datacenter scheduling, warehouse stocking etc. Formulate a stochastic lp (or some other optimization model as you see fit) and solve it. \n", "\n", "\n", "#### NOTE: Option 1 is very challenging; if you would like to pursue it, please talk to the staff\n", "\n", "## References\n", "[1] A. Macario. What does one minute of operating room time cost? In Journal of Clinical Anesthesia, 2010" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.5" } }, "nbformat": 4, "nbformat_minor": 0 }