How can I formulate this problem as a linear program?

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?

• What are you trying to minimize here? The total overtime cost? – Math1000 Mar 23 '18 at 22:49
• I am not sure about your objective function. How did you come up with it? Consider writing the model more synthetically with $\sum$ symbols. Also, your equations $x_{ij}=500$ are clearly wrong. Do you see why? – Kuifje Mar 26 '18 at 13:11
• The objective function is the sum of max$\{0,x_{Aj}+x_{Bj}-m_j\}$ which is not necessarily equal to $(x_{Aj}+x_{Bj} -m_j)$. You wrote $x_{ij}=500$, but you need $\sum_{j}x_{ij}=500$. – Kuifje Mar 26 '18 at 13:28
• Don't write over your post. – user223391 Mar 28 '18 at 16:08
• @xnc1234 Why have you tried to delete/hide everything? – Kuifje Mar 28 '18 at 16:43

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 ?

• Your welcome. Do not post your answer in the answer section. Post it in your question, underneath the attached picture. Did you linearize the objective function? – Kuifje Mar 26 '18 at 12:56
• Also, to maximize feedback: 1. use mathjax to write your equations and 2. State that your model is inspired from the answer below ;) – Kuifje Mar 26 '18 at 13:09
• There are two problems with your model: 1. In your objective function, what happens if for example $x_{A1}+x_{B1}-100 <0$ ? In this case you are minimizing a negative term...are you sure this is what you want ? 2. Why are your constraints in the form $=200$ and not $=500$ ? – Kuifje Mar 28 '18 at 7:41
• Ok I understand why you changed it to $200$, I didn't see that you had changed the data in the question. – Kuifje Mar 28 '18 at 9:28