一種啟發式方法來解決MILP問題?


6

我有以下優化問題,這是MILP。我可以用MILP求解器解決它。我在這裡Is there a heuristic approach to the MILP problem?

由於我還有其他但非常重要的限制,因此我將其作為新文章發布。我正在尋找一種啟發式方法來解決此問題。有提示嗎?

">開始{alignat} {2} \ min_t&\ quad t \\\ text {st}&\ quad d_ {c} -t \ le \ sum_ {n = 1} ^ {N} B_ {n,c} x_ {n} \ le d_ {c} + t,\ quad&\ forall c \ in \ {1,2,\ cdots,C \} \\&\ quad \ sum_{n = 1} ^ {N} x_n = M \\&\ quad x_n \ le M y_n,\ quad \ forall n \\&\ quad \ sum_ {n = 1} ^ N y_n \ le 3\ end {alignat}

非常重要

這是另一個問題的一部分,我發現這不能滿足我的實際需求。我想再施加一個約束。只能有給定數量的非零 $ x_n $ ,例如,對於前面的示例,我們可以有最大的 $ 3 $ 非零 $ x_n $ s。

其中

  • $ B $ 是大小為 $ N \ times C $

  • $ d $ 是一個已知向量,其正數大小為 $ 1 \乘以C $

  • $ M $ 是已知參數

  • $ x_n $ 是一個優化變量(整數變量, $ x_n \ ge 0 $ $ x_n \ in \ {0,1,2,3,\ cdots,M \} $

  • $ y_n $ 是二進制變量

  • $ t $ 也是一個優化變量(整數/連續)

@prubin建議將問題改寫為

如果我們設置 $ S_c = \ {n:B_ {n,c} = 1 \} $ ,我們可以將問題重寫為 $$ \開始{align *}\ min_ {t}和\ quad t \\\ text {st}和\ quad \ left | \ sum_ {n \ in S_ {c}} x_ {n} -d_ {c} \ right | \ le t,\ quad \ forall c \ in \ {1,2,\ cdots,C \} \\&\ quad \ sum_ {n = 1} ^ {N} x_ {n} = M。\ end {align *} $$ 一個簡單的貪婪啟發式是從 $ x_n = 0 \,\ forall n $ 開始,在每次迭代中,將 $ x $ 變量之一增加1,選擇最可改進的 $ x_n $ (或最小降級) $ t $ ,直到滿足相等約束。

5

Introduce binary variables $y_n$ and constraints \begin{align} x_n &\le M y_n &&\text{for all $n$}\\ \sum_n y_n &\le 3 \end{align}


1

Here is a modification of the bumping heuristic, assuming that you are limited to using $K$ of the $x$ variables (so $K=3$ in your example):

  1. Select $K$ distinct values of the index $n$ randomly.
  2. Apply the bumping heuristic, but limit it to bumping those $K$ variables. Note that the heuristic may not bump all of them.
  3. Record the new solution if it beats the previous incumbent.
  4. Repeat ad nauseum.