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

">開始{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}

## 非常重要

• $$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建議將問題改寫為

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}

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.