9
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.
$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ This is called the set partitioning problem or exact cover problem. $\endgroup$ – Rob Pratt Oct 19 '19 at 14:31
  • $\begingroup$ I guess the exact cover problem is technically about the existence of such a cover, while OP wants a minimum one, but yes. $\endgroup$ – Robert Schwarz Oct 19 '19 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.