How to formulate a MIP that can minimize the costs with a combination of subsets given a set?

Question

I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs:

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

Which combinations of subsets give the cheapest option, so that every element is in one the subsets only once?

For this example the solution would be: $\{1,2\}$ and $\{3\}$, with a total cost of $16$.

I want to formulate this as a mixed-integer programming problem, any suggestions?

EDIT: I have the program running with some additional time constraints for elements in the subsets. For sets with 15 elements, the program solves it in a reasonable time, but for every element I add more, the amount of subsets increase really fast. Therefore I am not able to solve large instances. I tried to random sample, x amount of subsets, but this is not optimal... Is there any method to solve such problem for a set of 50?

Answer 1

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

Answer 2

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.