如何產生的削減和找到一個整數解

Question

我有一個整數規劃問題，看起來例如像這樣，但有更多的變量和約束

這等於3SAT問題。沒有對象函數，所以任何整數解都是最優的。

現在我可以找到與cplex非整數解決方案，我想手動添加切割平面。現在我的問題是，我不知道在第一次放鬆之後如何產生切割。我發現了很多關於派系剪輯的文章，但都是理論性的，並沒有顯示算法如何去做。我希望有人能給我提示如何產生這些削減並解決這個問題。

Answer 1

那麼我看到兩個主要選擇。使用User Cuts或Lazy Constraints。

在這兩種情況下，你可以重新與IloExpr削減，其中對砍的變量可以使用+=運營商加入的LHS，削減被添加到您的IloModel先天或後天的，換句話說，你可以決定在.solve()指令之前或之後添加您的用戶剪切，如果您檢測到任何違反剪輯。一個普通的排建築讓您一次使用以下兩種方法之一添加一個甚至多個切口：假設變量

cplex.addCut(IloConstraint cut) 
cplex.addCuts(IloConstraintArray cuts) 

要對砍添加存儲在IloIntArray VarInCut(env);和您正在使用IloNumVarArray x(env);或模型中的IloIntVarArray x(env);變量，可以構建IloConstraint cut如CPLEX-C++的任何常規約束每行施工：

IloIntArray VarInCut(env); 
IloExpr LHS; 
for (int i=0; i<VarInCut.getSize(); i++) { LHS += x[VarInCut[i]]; } 

因此，通過切割作爲LHS <= RHS或LHS == RHS在不等的情況下/平等切表達，其中RHS可以引用另一個IloExpr或數字/整數值。

另一方面，懶惰約束通常實現爲更復雜的CallBack，它可能導致應用程序中出現錯誤行爲的風險增加，因此更難調試。查看關於UserCuts，LazyConstraints和一些博客的CPLEX文檔，here和here。

一個很高興能爲您服務！