使用matlab/octave進行線性規劃的程序分支和帶軸平行線的覆蓋點

Question

我正在嘗試使用軸平行線來覆蓋點的分支和邊界技術。對於每個子問題，我正在考慮將我的LP解決方案作爲LB和迭代舍入解決方案作爲UB。起初，我正在考慮一個小數值變量（應用LP之後），對於0和1值，我正在考慮將SP1和SP2作爲我的子問題。對於每個SP1我有UB1和LB1，對於每個SP2我都有UB2和LB2，如前所述。然後我檢查

i）如（LB1 = UB1或LB2 = UB2）然後停止

ii）如（UB1> = LB2）然後求解SP2

iii）如（UB2> = LB1 ）然後解決SP1

我不確定，我正在考慮正確的方法。因爲在大多數節點中，情況ii）和iii）都在發生（儘管在某個時刻只有一個'如果'正在執行）。我使用正確的方法嗎？任何幫助將不勝感激。

謝謝。

Answer 1

我不熟悉你的「迭代舍入」過程，但我會認爲它是正確的。

如果您比較上限和下限，您可能會滿足條件ii）和iii），特別是在解決方案過程的開始階段，因爲您的解決方案GAP可能很大。更常見的方法是從所有可用的支持問題中解決具有最有希望的下限的子問題。

您收到的答案看起來是否合理？