I am trying to solve an Integer Programming question (trying to come up with a model). The question goes like this: There are 5 pens a person has. He wants to have all 5 of them at the same time. And he has 10 different weighted bags. He wants to cary minimum weight as he can while having all five of the pens. Different bags carry different pens, the distribution is like this:
The weights of the bags are like this: bag 1 --> 4 bag 2 --> 6 bag 3 --> 4 bag 4 --> 2 bag 5 --> 3 bag 6 --> 2 bag 7 --> 4 bag 8 --> 3 bag 9 --> 6 bag 10 --> 3
What I thought is this: Let xi = 1 be that he brings the ith bag and xi = 0 be that he does not bring the ith bag. Then the obj. function is the minimum of sum of all of the x variables multiplied with their weight. And I could think of only one constraint: The sum of all the x variables i = 1..10 should be at most 10 and at least 3.
I could not think of anything else. Dont even know if this is the right path to the solution.
This is a weighted set cover problem. Let $a_{b,p}$ indicate whether bag $b$ contains pen $p$. You want to minimize $\sum_b w_b x_b$ subject to \begin{align} \sum_b a_{b,p} x_b &\ge 1 &&\text{for all $p$}\\ x_b &\in \{0,1\} &&\text{for all $b$} \end{align} For your instance, you want to minimize $$4x_1 + 6x_2 + 4x_3 + 2x_4 + 3x_5 + 2x_6 + 4x_7 + 3x_8 + 6x_9 + 3x_{10}$$ subject to \begin{align} x_1 + x_4 + x_7 &\ge 1 \\ x_2 + x_4 + x_6 + x_9 &\ge 1 \\ x_3 + x_5 + x_8 + x_{10} &\ge 1 \\ x_1 + x_2 + x_7 + x_{10} &\ge 1 \\ x_3 + x_6 + x_9 &\ge 1 \\ x_b &\in \{0,1\} &&\text{for all $b$} \end{align} The unique optimal solution is $x=(0,0,0,1,0,1,0,0,0,1)$, with objective value $2+2+3=7$. For a short certificate of optimality, use the optimal linear programming dual variables $(2, 0, 2, 1, 2)$ for the five constraints and $(1, 5, 0, 0, 1, 0, 1, 1, 4, 0)$ for the lower bounds $x_b \ge 0$.