Section Allocation

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).

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.

using Convex, GLPK
aux(str) = joinpath(@__DIR__, "aux_files", str) # path to auxiliary files

aux (generic function with 1 method)

Load our preference matrix, P

include(aux("data.jl"))

X = Variable(size(P), BinVar)

Variable
size: (50, 7)
sign: real
vexity: affine
id: 990…581

We want every student to be assigned to exactly one section. So, every row must have exactly one non-zero entry. In other words, the sum of all the columns for every row is 1. We also want each section to have between 6 and 10 students, so the sum of all the rows for every column should be between these.

constraints =
    [sum(X, dims = 2) == 1, sum(X, dims = 1) <= 10, sum(X, dims = 1) >= 6];

Our objective is simple sum(X .* P), which can be more efficiently represented as vec(X)' * vec(P). Since each entry of X is either 0 or 1, this is basically summing up the rankings of students that were assigned to them. If all students got their first choice, this value will be the number of students since the ranking of the first choice is 1.

p = minimize(vec(X)' * vec(P), constraints)

solve!(p, GLPK.Optimizer)

Problem statistics
  problem is DCP         : true
  number of variables    : 1 (350 scalar elements)
  number of constraints  : 3 (64 scalar elements)
  number of coefficients : 874
  number of atoms        : 17

Solution summary
  termination status : OPTIMAL
  primal status      : FEASIBLE_POINT
  dual status        : NO_SOLUTION
  objective value    : 65.0

Expression graph
  minimize
   └─ * (affine; real)
      ├─ reshape (affine; real)
      │  └─ * (affine; real)
      │     ├─ …
      │     └─ …
      └─ 350×1 Matrix{Float64}
  subject to
   ├─ == constraint (affine)
   │  └─ + (affine; real)
   │     ├─ * (affine; real)
   │     │  ├─ …
   │     │  └─ …
   │     └─ Convex.NegateAtom (constant; negative)
   │        └─ …
   ├─ ≤ constraint (affine)
   │  └─ + (affine; real)
   │     ├─ * (affine; real)
   │     │  ├─ …
   │     │  └─ …
   │     └─ Convex.NegateAtom (constant; negative)
   │        └─ …
   └─ ≥ constraint (affine)
      └─ + (affine; real)
         ├─ * (affine; real)
         │  ├─ …
         │  └─ …
         └─ Convex.NegateAtom (constant; negative)
            └─ …

This page was generated using Literate.jl.