Optimal Distribution of Proctors

Question

In my university, I am responsible with the distribution of proctors with respect to the student placements to the classrooms in freshman math pool courses. I faced a problem which is sticked in my mind for a quite long time. The problem is to define a utility function for the following optimization problem. $$ \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & f(\mathbf{x},\hat{\mathbf{x}}) \\ & \text{subject to} & & \sum_i x_i = N,\\ &&& 0 \le x_i \le \hat{x}_i,\ i = 1, \ldots, m. \end{aligned} $$

where $\hat{x}_i$ is the capacity of $i^{th}$ classroom, $x_i$ is the number of students to be placed to the $i^{th}$ classroom, $N$ is the total number of students to be placed to $m$ classes.

The main purpose of this problem is to minimize number of proctors, which will be assigned to each 30 or less students.

For instance, let $\hat{\mathbf{x}}=\begin{bmatrix}30&40&50&60\end{bmatrix}^T$ and $N=120$. Consider two placements $\mathbf{x}_1=\begin{bmatrix}30&30&30&30\end{bmatrix}^T$ and $\mathbf{x}_2=\begin{bmatrix}30&40&50&0\end{bmatrix}^T$. Since for every 30 or less students one proctor will be assigned, the proctoring assignment vectors are obtained $\mathbf{p}_1=\begin{bmatrix}1&1&1&1\end{bmatrix}^T$ and $\mathbf{p}_2=\begin{bmatrix}1&2&2&0\end{bmatrix}^T$ respectively. Since 4 proctors are used in the first placement, it is a better choice. But I want to find or guarantee the optimal solution.

I have tried CVX tool for this optimization problem in MATLAB with $$ f(\mathbf{x},\hat{\mathbf{x}})=\sum_i ceil(x_i/30) $$ but since there are no round, ceil or remainder function usages in CVX, I can not define such a utility function.

I am considering to use MATLAB, MS Excel or Excel-like program, but I am open to any suggestions.

Answer 1

A linear MIP (Mixed Integer Programming) model may be easier to formulate and solve. Let $y_i$ be the number of proctors needed for room $i$ ($y_i$ is an integer variable). Then solve the model:

$$\begin{align} \min & \sum_i y_i \\ & 30 y_i \ge x_i \\ & \sum_i x_i =N \\ & y_i \ge 0 \text{ (integer variable)}\\ & 0 \le x_i \le U_i \text{ (integer variable)} \end{align}$$

This will give you a proven global optimum.

Answer 2

As you saw, your utility function is nonconvex and so you will not be able to solve this as a convex optimization problem. From here you would have two options: First, you may attempt to solve a nearby convex problem, that is, a problem which approximates your utility function but is also convex. Your second option is to find some other method for finding the minimum.

From discussion, here's my proposed algorithm, using the second option:

Take your total number of students, and put them in groups of 30, and treat the remainder as their own group. Then, starting with the largest room, put 1 group at a time until you can not fit any more groups. Then move to the next largest room and repeat until there are no more groups

If there are no more "spots" of 30 seats in any rooms and yet groups of students still remain, then, starting with the room with the greatest remaining number of seats and fill in students until the room is full or no more students remain. If students still remain move to the next largest room etc.

This algoritm satisfies the example in your question with $$p_1 = \begin{bmatrix}0&1&1&2\end{bmatrix}^T$$

This algorithm is not necessarily rigorous, nor do I have a proof that it will find the global minimum (indeed, there may be multiple "global" minima that satisfy this problem).

Answer 3

Nice! I've altered my code as: xbar=[30 40 50 60]'; N=120;\\ n=length(xbar); %%% CVX cvx_begin variable x(n) variable y(n) minimize(sum(y)) subject to x<=30*y sum(x) == N 0 <= y 0 <= x x <= xbar cvx_end but I get an error like "SDTP3 does not support integer variables.". How can I tell to CVX that I want to use linear MIP. Someone can say that "MIP problems are not convex" but in this link it says there is a mixed-integer support in CVX 2.0.