examples/section_allocation/section_allocation.ipynb

{
 "metadata": {
  "language": "Julia",
  "name": "",
  "signature": "sha256:5bafa07346f87de0d2d3621be9267c8fc67b2f9fdb9a99f84bd18c7ec489a284"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Section Allocation\n",
      "Suppose you have $n$ students in a class who need to be assigned to $m$ discussion sections. Each student needs to be assigned to exactly one section. Each discussion section should have between 6 and 10 students. Suppose an $n \\times m$ preference matrix $P$ is given, where $P_{ij}$ gives student $i$'s ranking for section $j$ (1 would mean it is the student's top choice, 10,000 or a large number would mean the student can not attend that section).\n",
      "\n",
      "The goal will be to get an allocation matrix $X$, where $X_{ij} = 1$ if student $i$ is assigned to section $j$ and $0$ otherwise. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "using Convex, GLPKMathProgInterface\n",
      "# data.jl has our preference matrix, P\n",
      "include(\"data.jl\");\n",
      "\n",
      "X = Variable(size(P), :Bin)\n",
      "\n",
      "# We want every student to be assigned to exactly one section. So, every row must have exactly one non-zero entry\n",
      "# In other words, the sum of all the columns for every row is 1\n",
      "# We also want each section to have between 6 and 10 students, so the sum of all the rows for every column should \n",
      "# be between these\n",
      "constraints = [sum(X, 2) == 1, sum(X, 1) <= 10, sum(X, 1) >= 6]\n",
      "\n",
      "# Our objective is simple sum(X .* P), which can be more efficiently represented as vec(X)' * vec(P)\n",
      "# Since each entry of X is either 0 or 1, this is basically summing up the rankings of students that were assigned to them.\n",
      "# If all students got their first choice, this value will be the number of students since the ranking of the first choice is 1.\n",
      "p = minimize(vec(X)' * vec(P), constraints)\n",
      "\n",
      "solve!(p, GLPKSolverMIP())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    }
   ],
   "metadata": {}
  }
 ]
}