为什么 CPLEX 将不相关的变量设置为 1？

Question

我一直在研究可以建模为整数线性规划的组合优化问题。我在 Visual Studio 2017 和 CPLEX1271 中将它实现为一个 C++ 项目。由于有成倍数的约束，我通过 IloCplex::LazyConstraintCallbackI 实现了惰性约束。在我看来，以下过程是如何产生最优解的：每次确定一个整数解时，LazyConstraintCallbackI 将检查它并向模型添加一些违反约束，直到获得最优整数解。

但是，我对不同输入的实现给出的目标值并不总是正确的。经过将近一年的间歇性调试和测试，我终于找到了原因，这与问题非常相关，但可以通过以下小示例来解释（希望如此）：涉及四个布尔变量 x1、x2、x3 和 x4 的整数线性规划

minimize x1
subject to: 
x1  ?  x2
x1  ?  x3
x1  ?  x4
x2  + x3  ? 1
x1, x2, x3 and x4  ? {0, 1}?

cplex给出的结果是：

Solution status = Optimal
Objective value = 1
x1 = 1
x2 = 1
x3 = 1
x4 = 1?

毫无疑问，目标值是正确的。奇怪的是cplex设置x4 = 1。虽然x4等于1或0对这个编程中的目标值没有影响。但是，当使用惰性约束回调时，这可能会通过添加一些不正确的约束而导致问题，并且整数编程可以通过迭代添加违反约束来解决。我想知道：

1. 为什么 cplex 将“无关”变量 x4 设置为 1，而不是 0？
2. 我应该怎么做才能告诉 CPLEX 我想将这种“无关”变量保留为 0？

Answer 1

由于在最优解中没有强制 x4=0 的内容，因此不能保证 CPLEX 将设置 x4=0？为什么会呢？为什么 0 比 1 更受欢迎？该模型有两种最优解，一种是 x4=0，一种是 x4=1。两者都具有目标值 1。CPLEX 可以完全自由地选择其中之一。

就像 sascha 在他的评论中所说的那样，在最佳解决方案中强制 x4=0 的唯一方法是将此约束添加到模型中，例如通过将目标系数设置为一个小的正值。

但是，您的惰性约束回调会从整数可行解中生成无效约束，这似乎很奇怪。这看起来像一个错误：要么回调对模型做出无效假设（即在任何最佳解决方案中 x4=0），要么回调逻辑中的某处存在错误。请注意，在手头的模型中，回调截断 x4=1 的解实际上是没问题的，因为这仍然会留下 x4=0 的等效最优解，而 CPLEX 最终会找到它。