這個問題是否屬於任何常見的問題定義。...背包?


2

我正在努力尋找可解決此優化難題的代表性問題。我已經在Matlab中實現了MILP,但是運行時間花費了超過一天的時間。我的目標是查看它是否適合其他一些常見問題的方法,在這裡我可能可以應用一些眾所周知的啟發式方法。

給出一組 $ S $ 的一組 $ n $ 離散項, $ i $ $ k $ 子集, $ M $ $ S $ $$ S:= \ {i_1,i_2,i_3 \ dots,i_n \} $$ $$ M_ {1,2,3,\點k} \ subseteq S $$

準確選擇 $ X $ 子集 $ M $ ,這樣 $$ X 以最大程度地減少 $ i $ 中2個或多個 $ X $ 子集。

ADDT'L註釋

  1. 如果選擇 $ i $ 項0或1次,而少於2次,則沒有任何額外價值
  2. 每個項目 $ i $ 不是必須都需要選擇
  3. 每個子集都是預定義的,並且是偽隨機的

$$ ----以下只是另一種形式的嘗試---- $$

我試圖使它更加面向數學定義,但是簡化問題的另一種方法是(使用一些編程方面的知識):

1)我有一個邏輯矩陣M(i行,j col),其中行表示總體,列表示可用的子集。2)目標是優化列向量(j,1)的F,該向量表示對每個子集(M的列)的選擇,以使M x F≥2的元素數量最少;3)F受制於您必須精確選擇X個子集的情況。

需要定義列邏輯向量F(j行1列),以使F具有K個真實條目(代表子集選擇),其餘為false

i = 1e6;j = 150;X = 140

Set_Matrix = randi([0 1],i,j);

將F優化為最小化:sum(sum(sum(Set_Matrix * F)> = 2)其中sum(F)== X(即從150個子集中選擇140個)

4

Here is a MILP formulation, in case you did something different. Let binary variable $F_j$ indicate whether subset $j$ is chosen. Let binary variable $T_i$ indicate whether item $i$ appears in two or more of the chosen subsets. The problem is to minimize $\sum_i T_i$ subject to: \begin{align} \sum_j F_j &= 140 \tag1 \\ \sum_j M_{i,j} F_j - 1 &\le 149 T_i &&\text{for all $i$} \tag2 \end{align} Constraint $(1)$ is the cardinality constraint. Constraint $(2)$ enforces $\sum_j M_{i,j} F_j \ge 2 \implies T_i = 1$. If most of these constraints are naturally satisfied anyway, you could generate them dynamically only if they are violated.