# 如何制定一個MIP，以給定一組子集的組合使成本最小化？

$$\ {1 \} = 8$$$$\ {2 \} = 9$$$$\ {3 \} = 7$$$$\ {1,2 \} = 9$$$$\ {1,3 \} = 18$$$$\ {2,3 \} = 15$$$$\ {1,2,3 \} = 24$$

You can introduce a binary variable $$x_s \in \{0,1\}$$ for each of your sets. Then, for every element $$e$$, you add an inequality that implies that exactly one set containing it may be selected: $$\sum_{s \ni e} x_s = 1$$. Now you can simply minimize $$\sum_{s}c_s x_s$$ for the cost coefficients $$c$$.

A few suggestions:

1. If possible, relax to a set covering problem ($$\ge 1$$ instead of $$=1$$).
2. Use a greedy heuristic to generate a good feasible starting solution.
3. Instead of listing all the sets $$s$$ explicitly, reformulate the problem compactly, with binary variable $$y_{i,k}$$ indicating whether element $$i$$ appears in the $$k$$th set. This approach requires a way to express the cost as a function of $$y$$.
4. Use a dynamic column generation approach to add promising sets as needed.