# combinatorial optimization – Integer programming for bin covering problem

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_iin{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?

Posted on Categories Articles