I encounter an integer programming problem like this:

Suppose a student needs to take exams in n courses {math, physics, literature, etc}. To pass the exam in course i, the student needs to spend an amount of effort e_i on course i. The student can graduate if she/he passes 60% of the n courses (courses have different weights). The objective is to allocate her/his efforts to different courses such that the student can graduate with the minimal amount of efforts spent on courses.

I think this problem is similar to bin covering problem when there is only one bin. The formulation is simple. Use x_i\in{0,1} to denote whether the student allocates effort to course i. Let w_i denote the weight of course i in calculating the final score.

Min \sum x_i e_i

s.t. \sum x_i w_i >= 60% * n (or some other predetermined threshold)

My question is, is there a simple heuristic solution for this problem?

  • $\begingroup$ Can't you solve the problem exactly by sorting the efforts from smallest to largest and to spend effort on the easiest 60% of classes? $\endgroup$
    – Tony Huynh
    Jul 19 '21 at 2:07
  • $\begingroup$ Yes, you are right. This should be the optimal strategy if the courses have the same weight. But if the courses have different weights, I doubt. My original question is not clear, I will update it. $\endgroup$
    – Yorknight
    Jul 19 '21 at 2:23
  • 1
    $\begingroup$ People often worry that students will try to use Q&A sites like mathoverflow to pass their courses with the minimal amount of effort, but usually not in this way! $\endgroup$
    – Will Sawin
    Jul 26 '21 at 21:34

This is equivalent to a special case of the 0-1 knapsack problem, and the greedy heuristic suggested by @TonyHuynh is well known but not necessarily optimal for the general case, which you can solve exactly with dynamic programming.

In your special case, where each $x_i$ has the same constraint coefficient, greedy is optimal.

  • $\begingroup$ Thank you. This is very helpful. $\endgroup$
    – Yorknight
    Jul 19 '21 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.