Vtgyjfy

Please have a look at my solution to the following problem.

Firstly, I think that there are two ways to interpret this problem. If we need to make sure all students in $mathscr{L}$ pass and all students in $mathscr{D}$ fail, this problem doesn't need to be a linear program since the constraints are already enough to determine the solutions (i.e. the average grades of the favorite students are at least 60%, and those of the disliked students less than 60%).

But there are of course situations where the above constraints could not all be met (e.g. a favorite student scoring lower than a disliked student in all 12 assignments), so I think the objective of the program should be to choose the weights so that as many students in $mathscr{L}$ pass as possible, and as many students in $mathscr{D}$ fail as possible.

To that end, my idea is to maximize the difference between the favorite students' grades and the pass/fail score, and also that between the pass/fail score and the disliked students' grades.

Note that we can use the total score as the pass/fail mark, instead of the average score. This means that in my solution, a student $i$ would pass if: $$sum_{j=1}^{12} frac{p_{i,j}w_j}{12} geq 0.6 sum_{j=1}^{12} 20w_j Rightarrow sum_{j=1}^{12} p_{i,j}w_j geq 12 sum_{j=1}^{12} w_j $$

(the 0.6 is from the condition that the pass/fail score is 12/20)

So we can set up the linear program as follows:

Let $|mathscr{L}| = m$ and $|mathscr{D}| = n$, where $m,n in mathbb{Z}^{+}$ and are given.

$$ text{max} left[left(sum_{i:S_i in mathscr{L}; 1 leq j leq 12} p_{i,j}w_jright) - left(12msum_{1 leq j leq 12}w_jright)right] + left[left( 12nsum_{1 leq j leq 12}w_jright) - left(sum_{i:S_i in mathscr{D}; 1 leq j leq 12} p_{i,j}w_jright)right]$$

$$text{subject to:} w_j geq 0, text{where} 1leq j leq 12$$

I think you're absolutely right in your overall analysis that there are two different ways to interpret the question, and that, in the first way, the problem may be unsolvable. However, I'm pretty sure you should be analyzing it in the first way anyway.

The conditions that each liked student passes, and each disliked student fails, are all themselves linear constraints which you can write down. So that gives you a linear program to solve (with trivial objective function, or any objective function you like). It is possible that in some cases the linear program will have no feasible solutions. This is fine! It just means that the answer in those cases is "there is no way for the professor to do this."

The solution you've given, as an attempt to solve the second interpretation of the question, has two problems. One is that you haven't specified a scale for the $w_j$. So if you have any feasible solution where the value of the objective function is positive, you can get another one where it's twice as big just by doubling the value of every $w_j$. You could fix this by adding some additional constraint on the $w_j$ like forcing their sum to be $1$.

The second problem is harder to deal with. Essentially, you're requiring the favored students to pass by as much as possible and the disfavored students to fail by as much as possible. But that doesn't guarantee that the number of students who have the right outcome is large. It might just be that you've chosen weights which are really good for some specific favored student (or really bad for some specific disfavored student) while being relatively neutral for everyone else. Another way to think about this is that the question is asking about outcomes in a pass/fail system, and your solution optimizes for situations where grades are a lot more granular (like one where percentages are reported).

Fundamentally the issue is that the objective function you actually want under the second interpretation is "number of students with the correct outcome." This is nonlinear (and discontinuous!), so you can't use a linear program to maximize it. This is why I believe that the first interpretation is the correct one.

If you wanted to solve the second interpretation of the problem, you could do it by removing students from $mathcal{L}$ and $mathcal{D}$ one by one until you got a feasible solution, but this would be computationally expensive — there are a lot of combinations to try. It is unlikely that there's a rapid way to solve the second interpretation; this kind of problem with integer variables is usually NP-hard.