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

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?

1. If possible, relax to a set covering problem ($$\ge 1$$ instead of $$=1$$).
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$$.
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$$.