c++ - 如何生成切割并找到整数解

Question

我有一个看起来像这样的整数编程问题，但有更多的变量和约束

它等于 3SAT 问题。没有目标函数，所以任何整数解都是最优的。

现在我可以使用 cplex 找到一个非整数解决方案，并且我想手动添加切割平面。我现在的问题是我不知道第一次放松后如何产生削减。我发现了许多关于 clique cut 等的论文，但它们都是理论上的，并没有展示如何做到这一点的算法。我希望有人能给我一个提示，如何生成这些削减并解决这个问题。

Answer 1

好吧，我看到两个主要选择。使用用户剪切或惰性约束。

在这两种情况下，您都可以重新创建剪辑的 LHS，IloExpr其中可以使用+=运算符添加剪辑上的变量，将剪辑添加到您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]]; }

因此，在不等式/等式切割表达式的情况下传递 cut可以引用另一个LHS <= RHS或数字/整数值。LHS == RHSRHSIloExpr

另一方面，惰性约束通常作为回调实现，这更棘手，可能导致应用程序中出现错误行为的风险更高，因此更难以调试。看看关于 UserCuts、LazyConstraints 的 CPLEX 文档和几个博客，这里和这里。

很高兴为您服务！