How can I formulate this problem as a linear program?

Question

I'm stuck on a problem where the scenario is as follows, say for example -

200 candidates have two tests (a and b). They have to be allocated to 8 examiners who have they own individual traits, a total of 400 tests to mark for all.

The examiners have to mark a certain amount of test as part of their contract but there is not enough to cover the total number that need to be marked. They will be have to paid overtime.

The marking has to be finished in three days, each day has six hours in which the examiners can mark. They don't have to reach the number of exams in their contract but they still get paid if they do less.

Below attached is a picture of the data for the problem. How can this be formulated as a linear program (identifying constraints, control variables and cost function)?

The problem to hand aims to minimize the overall cost of the number of overpaid exams:

Z = 5(xA1 + xB1 – 100) + 6(xA2 + xB2 – 120) + 4(xA3 + xB3 – 80) + 2(xA4 + xB4 – 60) + 6(xA5 + xB5 - 50) 5(xA6 + xB6 - 25) + 12(xA7 + xB7 - 20) + 3(xA8 + xB8 - 50)

Since the marking has to be done in three days (i.e. 1080 minutes) and all 400 tests have to be marked the minimising function is subject to constraints:

• 14xA1 + 10xB1 ≤ 1080

...

• 6xA8 + 7xB8 ≤ 1080

• xA1 + ... + xA8 = 200

• xB1 + .... + xB8 = 200

• xA1 ≥ 0

• xB1 ≥ 0

What do you think of this? Would this be linear now? Also how can I include the fact that they don't get a refund if the markers don't reach the number of exams in their contract?

Answer 1

Let $x_{ij}$ denote the number of exams of type $i \in \{A,B\}$ marked by marker $j\in \{1,...,12\}$. The number of overpaid exams for marker $j$ thus equals $\max\left\{0,x_{Aj}+x_{Bj}-m_j\right\}$.

You want to minimize the overall cost of the number of overpaid exams: $$ \sum_{j}c_j\max\left\{0,x_{Aj}+x_{Bj}-m_j\right\} $$ under the constraints:

• The marking has to be done in three days (i.e., $1 080$ minutes): $$ \sum_{j}a_jx_{Aj}+b_jx_{Bj} \le 1 080 $$
• All $1000$ tests have to be marked: $$ \sum_{j}x_{Aj}=500, \quad \sum_{j}x_{Bj}=500 $$
• Variables are integers: $$ x_{ij}\in \mathbb{N} $$

Note that the model as is is not linear, but is easy to linearize. Can you finish ?