Integer programming problem, 5 pens and 10 bags

Question

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.

Answer 1

Each bag contains just two pens or one pen, and given that you must have at least $5$ (different) pens, you must have at minimum of $3$ bags. For minimum weight, two bags must each contain $2$ pens and the final bag can contain $1$ pen (if possible).

This is quite easy to achieve.

• Pick any bag you like containing two pens but not pen 3 (call it bag A).
• Pick another bag that contains the two pens not in bag A and not pen 3. (Call it bag B.)
• Pick another bag that contains the only missing pen. (Call it bag C.)

I easily found: $\{ 1,6,5 \}$.

But try others!

Answer 2

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$.