MATLAB上bintprog的迭代使用

Question

我們有一個問題表達式，如this link所示。

考慮的bintprog第一次調用給出瞭解決方案x，經過一些後處理不充分解決物理問題，是有可能召回bintprog並排除之前的解x？

Answer 1

你需要一個nogood切。

假設您找到一個解決方案\ hat {x}，那麼您決定是不可行的（通過某種後期處理）。讓x和\ hat {x}由i索引。

可以添加以下形式的約束：

\sum_{i : \hat{x}_i = 0} x_i + \sum_{i : \hat{x} = 1} (1-x_i) \geq 1 

這個約束是一個沒有切好的例子：該解決方案必須由至少一個索引i從\帽子{X}不同，否則它是不可行的。如果你的變量不是二元的，那麼沒有貨物可能會更復雜一點。

通過將約束作爲行附加到約束矩陣並使用bintprog（）函數重新解決，您可以爲解決方案添加一個不利條件。我會把它留給你，你用MATLAB的符號重寫它。

你沒有說你的後處理是幹什麼的，但是如果後處理可以從你的解決方案中推斷出其他解決方案也是不可行的，那麼它會更好，並且你可以添加更多每次迭代一行。這是基於邏輯的Benders分解的一種形式，其他不可行解的推論稱爲求解推理對偶（與標準Benders分解相反，在那裏你解決了線性規劃對偶問題）。 More on logic based Benders decomposition來自創造該術語的人，約翰胡克CMU。

對不起，格式化。我需要去但我會找出一種方法來更好地顯示方程。