如何使用JuMP向MIP請求第二個最佳解決方案

Question

我有一個混合整數編程問題。 我可以使用JuMP來找到最佳解決方案。 但是我怎樣才能找到第二個最好的解決方案？ 或第三種最好等

這可能可能是另一種同樣最優解， 或者它可能是一個糟糕的解決方案， 也可能是:Infeasible - 有可能是沒有大多數解決方案。

我知道TSP類問題，我可以通過逐步刪除最佳路徑上的鏈接（即將一些城市之間的距離設置爲無限）來找到其他解決方案。 對於調度類型問題，我可以類似地逐步設置要禁用的最佳路徑中使用的時隙的可用性。

但是有沒有一個這樣做的一般方法，沒有編碼自己問題特定的方法來禁止此解決方案？

Answer 1

您可以添加一個剪切來禁止找到並再次解決問題的最佳解決方案。假設你的模型有二元變量x(i)。讓a(i):=x*(i)成爲先前找到的最佳解決方案。然後添加線性約束：

sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1 

，再解決。 （這個東西是派生的here）。如果x是一個整數變量，事情變得更加複雜。

像Cplex和Gurobi這樣的解算器也有一些稱爲解決方案池的解決方案池也可以做到這一點。