Gurobi Irreducible Subset ISS不包含衝突嗎？

我正在使用Gurobi的C++接口來解決混合整數編程問題。這個模型似乎運作得很好，但是當將結果與局部搜索啓發式進行比較時，我發現簡單的貪婪局部搜索產生了更好（可行）的解決方案。要查看導致問題的原因，我爲小實例添加了一些額外的約束，強制解決方案與本地搜索過程找到的解決方案相同。如預期的那樣，這導致了一個不可行的問題，我從Gurobi確定了不可約子集（ISS）。但是，當手動檢查生產的ISS 時，我發現在方程中沒有衝突。Gurobi Irreducible Subset ISS不包含衝突嗎？

該問題是一個簡單的多模式調度問題，其中x[i][m]是一個二進制變量，它代表活動i的模式m的選擇。因此，通過爲每個活動選擇單一模式來構造解決方案（= 1表示已經選擇了模式，如約束c1所強制的）。約束條件應強制執行關於所有活動的活動模式的具體決定。

約束類型c2根據它們的優先關係簡單地計算活動的完成時間，爲每個活動分配其他無約束的完成時間變量f[i]。然後在c_linduration約束中使用最終活動的完成時間來計算由變量I^D表示的目標函數值（的一部分）。同樣，I^D變量不受任何其他方程的約束（如果是的話，約束條件當然也應該存在於ISS中）。

Maximize 

Subject To 
c1[1]: x[1][0] + x[1][1] + x[1][2] + x[1][3] = 1 
c1[2]: x[2][0] + x[2][1] + x[2][2] + x[2][3] = 1 
c1[5]: x[5][0] + x[5][1] + x[5][2] + x[5][3] + x[5][4] + x[5][5] + x[5][6] 
    + x[5][7] = 1 
DEBUG[1]: x[1][1] = 1 
DEBUG[2]: x[2][0] = 1 
DEBUG[5]: x[5][2] = 1 
c2[1][0]: - 7.709549903869629 x[1][0] - 11.21389961242676 x[1][1] 
    - 11.91479969024658 x[1][2] - 8.410420417785645 x[1][3] - f[0] + f[1] 
    >= 0 
c2[2][0]: - 11.00800037384033 x[2][0] - 7.770349979400635 x[2][1] 
    - 7.122819900512695 x[2][2] - 7.122819900512695 x[2][3] - f[1] + f[2] 
    >= 0 
c2[5][0]: - 2.499399900436401 x[5][0] - 2.883919954299927 x[5][1] 
    - 3.84522008895874 x[5][2] - 3.268440008163452 x[5][3] 
    - 3.076179981231689 x[5][4] - 3.460700035095215 x[5][5] 
    - 2.307130098342896 x[5][6] - 2.499399900436401 x[5][7] - f[2] + f[5] 
    >= 0 
c2[7][1]: - f[5] + f[7] >= 0 
c3: f[0] = 0 
c_linduration: 0.2000000029802322 f[7] + I^D[0] = 4.390739887814817 
Bounds 
x[1][0] free 
x[1][1] free 
x[2][0] free 
x[2][1] free 
-infinity <= x[2][2] <= 1 
-infinity <= x[2][3] <= 1 
x[5][2] free 
x[5][6] free 
f[0] free 
f[1] free 
f[2] free 
f[5] free 
f[7] free 
Generals 
x[1][0] x[1][1] x[1][2] x[1][3] x[2][0] x[2][1] x[2][2] x[2][3] x[5][0] 
x[5][1] x[5][2] x[5][3] x[5][4] x[5][5] x[5][6] x[5][7] 
End

我也試圖降低從1e-9的整數精度1e-6，因爲我認爲這可能是一個四捨五入的問題，但是這並沒有影響。刪除c1或c3約束類型也不會在生成的ISS中進行更改。

//Optimize the model 
model.optimize(); 

//calculate the ISS in case the model is infeasibel 
model.computeIIS(); 
model.write("model.ilp");

是否有Gurobi設置我可能會錯過或別的東西，我可能會嘗試：我用下面的語句創建ISS？或者，我在構建這個ISS的方式會有問題嗎？我一直在想這個問題已經有一段時間了，我真的不知道如何解決這個問題......如果有問題，我正在使用Gurobi 6.0和OS X上的LLVM C++編譯器。

所有幫助非常感謝！

大號

來源

2015-11-02 Louis-Philippe

這裏使用C++標籤看起來並不合適，因爲這不是關於C++的問題。 – legalize

我已經刪除了標籤，我已經添加了它，因爲我使用了C++接口，但是您是對的，它與C++無關。謝謝！ –

問題已經鑑定Kostja Siefen在Gurobi谷歌小組論壇：這個問題是我錯誤地假設，下界爲I^D變量的缺省值是負無窮大，而默認下界Gurobi實際上是0.因此，通過設置下限等於-GRB_INFINITY解決了問題。

來源

2015-11-02 19:06:14

這是線性規劃的標準慣例：變量的下界爲零。 –

...如果沒有指定。 –

Gurobi Irreducible Subset ISS不包含衝突嗎？

回答

相關問題