Gurobi 不可约子集 ISS 包含没有冲突？

Question

我正在使用 Gurobi 的 C++ 接口来解决混合整数编程问题。这个模型看起来工作得很好，但是当将结果与本地搜索启发式进行比较时，我发现一个简单的贪婪本地搜索产生了更好（和可行）的解决方案。为了查看导致问题的原因，我为一个小实例添加了一些额外的约束，强制解决方案与本地搜索过程找到的解决方案相同。

不出所料，这导致了一个不可行的问题，我让 Gurobi 从中确定了不可约子集 (ISS)。然而，当手动检查生成的 ISS 时 我发现方程中没有冲突 。

问题是一个简单的多模式调度问题，其中 x[i][m] 是一个二元变量，代表 activity i 模式 m 的选择。因此，通过为每个 activity 选择一个模式来构造一个解决方案（=1 表示已选择一个模式，由约束 c1 强制执行）。 DEBUG 约束应该针对所有活动强制执行关于 activity 模式的特定决定。

约束类型 c2 只是根据优先关系计算活动的完成时间，为每个 activity 的其他不受约束的完成时间变量 f[i] 分配值。然后在c_linduration约束中使用最终activity的完成时间来计算变量I^D表示的objective函数值（的一部分）。同样，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 中产生任何变化。我正在使用以下语句创建 ISS：

//Optimize the model
model.optimize();

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

是否有我可能错过的 Gurobi 设置或我可以尝试的其他设置？还是我建造这个国际空间站的方式有问题？我已经考虑了很长时间了，我真的不知道如何解决这个问题……如果重要的话，我正在 OS X 上使用 Gurobi 6.0 和 LLVM C++ 编译器.

非常感谢所有帮助！

L

Answer 1

问题已由 Kostja Siefen 在 Gurobi google 组论坛上发现：问题是我错误地假设 I^D 变量的默认下限是 -infinity，而Gurobi 的默认下限实际上是 0。因此，通过将下限设置为 -GRB_INFINITY 来解决问题。

Gurobi 不可约子集 ISS 包含没有冲突？

Gurobi Irreducible Subset ISS contains no conflict?

linear-programming

gurobi