對於MILP問題是否有貪婪的啟發式方法?


8

我有以下優化問題,這是MILP。我可以用MILP求解器解決它。

">開始{alignat} {1} \ max_ {x_n,t} \,&\ quad \\\ text {st}&\ quad \ sum_ {n= 1} ^ {N} x_n \,&= M \\&\ quad \ qquad \!s_c&\ ge t d_c \ end {alignat}

其中

  • $ s_c = \ sum \ limits_ {n = 1} ^ {N} B_ {n,c} x_ {n} $
  • $ B $ 是大小為 $ N \ times C $ 的給定矩陣,元素 $ \ ge 0 $

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

  • $ M $ 是已知參數

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

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

我想將其轉換為LP,而不是MILP。可以說我沒有MILP求解器。

因此,我正在尋找一種啟發式的解決方案來解決上述問題。

我已嘗試使用@prubin建議的解決方案來解決問題:Is there a heuristic approach to the MILP problem?,但這不起作用。它正在選擇 $ B $ 的同一行在每次迭代中。

6

Unlike the problem from the linked post, the objective here is “flat” at the initial solution in the sense that increasing some $x_n$ by 1 unit will not change the objective value, which is initially 0. The LP rounding approaches still apply if you linearize the $\min_c$, which you can do by introducing $t$ with $t\le s_c/d_c$.


6

Here is a somewhat greedy heuristic. First, to simplify notation a bit, let $$f_{c}(x)=\frac{1}{d_c}\sum_{n=1}^N B_{n,c}x_n\, \forall c.$$ So we want to maximize $$t=\min_c f_c(x)$$ subject to $$\sum_n x_n = M.\quad (1)$$

Now start with some arbitrary (let's say randomly generated) $x$ satisfying (1). Calculate all the $f_c(x)$, and for each $n$ calculate two values: the change $\delta_n$ in $t$ if $x_n$ increases by 1, and the change $\gamma_n$ in $t$ if $x_n$ decreases by 1. (If $x_n=0$, set $\gamma_n=-\infty$, since $x_n$ cannot go below zero.) Choose $n$ that maximizes $\delta_n$ and $m$ that maximizes $\gamma_m$. If the net change $\delta_n + \gamma_m$ is positive, increase $x_n$ by 1 and decrease $x_m$ by 1, preserving satisfaction of (1), and repeat.

If the net change is less than or equal to zero, compare the current $t$ to the best solution so far. If it is better, record $x$ as the new best solution. At this point, you can either stop or generate a new random $x$ and continue from there.