# 對於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$$也是一個優化變量（整數/連續）

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

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.