Suppose some students enrol themselves onto a course.
The course has 6 available classes, A,B,C,D,E,F, each at a different time and/or day. All the classes have the same upper limit on size, say some number N.
The students are asked which classes they would be able to attend. For example, one student might only be able to attend class A while another student can only attend classes A,C,D and another can attend any. Note there is no preference given in selected classes, it is assumed the student is happy to attend any choice equally.
Now, the students are each given a test and receive a score as a percentage. The idea is to group students with similar scores in the same class in the best possible way, while also satisfying the constraints of the last 2 paragraphs.
Can this be formulated as a linear programming problem? Or are there other ways to go about this?
You can use mixed integer linear programming as follows. For compatible student-class pairs $(i,c)$, let binary decision variable $x_{i,c}$ indicate whether student $i$ is assigned to class $c$. Let $s_i$ be the score of student $i$. Let decision variables $\ell_c$ and $h_c$ be the lowest and highest scores in class $c$. One way to find a balanced assignment is to minimize $$\sum_c (h_c - \ell_c)$$ subject to \begin{align} \sum_c x_{i,c} &= 1 &&\text{for all $i$} \tag1 \\ \sum_i x_{i,c} &\le N &&\text{for all $c$} \tag2 \\ \ell_c - s_i &\le (1-s_i)(1-x_{i,c}) &&\text{for all $(i,c)$} \tag3 \\ h_c &\ge s_i x_{i,c} &&\text{for all $(i,c)$} \tag4 \end{align} Constraint $(1)$ assigns each student to exactly one compatible class. Constraint $(2)$ enforces the class size. Constraint $(3)$ enforces the logical implication $x_{i,c} = 1 \implies \ell_c \le s_i$. Constraint $(4)$ enforces the logical implication $x_{i,c} = 1 \implies h_c \ge s_i$.