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


9

我正在嘗試解決以下問題。我有一個 $ \ {1,2,3 \} $ 集合,它給出了其費用的以下子集:

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

哪種子集組合提供了最便宜的選擇,因此每個元素在一個子集中只能出現一次?

對於此示例,解決方案將是: $ \ {1,2 \} $ $ \ {3 \} $ ,總費用為 $ 16 $

我想將其表達為混合整數編程問題,有什麼建議嗎?

編輯:我的程序運行時對子集中的元素有一些附加的時間限制。對於包含15個元素的集合,程序會在合理的時間內解決它,但是對於我添加的每個元素,子集的數量確實會快速增加。因此,我無法解決大型實例。我嘗試隨機抽取x個子集,但這並不是最佳選擇...有一套方法可以解決50個問題嗎?

8

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


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.