什么限制使我的问题不可行？

Question

我正在使用CPLEX 12.8来建模我的论文项目，我遇到了一个我无法解决的问题。我得到以下输出：

CPLEX 12.8.0.0: integer infeasible.
1828 MIP simplex iterations
316 branch-and-bound nodes
No basis.

有没有办法知道哪些约束相互矛盾？

Answer 1

欢迎来到SO！

CPLEX和类似的求解器能够为不可行的问题生成约束（IIS）的“不可约的不可行集”。这是原始约束的子集，具有以下属性：

• 在所有IIS约束都处于活动状态时，无法解决问题。
• 删除这些约束中的任何一个都可以解决问题。

检查IIS通常有助于找到矛盾的约束。请注意，有些问题会有多个IIS;解算器每次运行时只会找到一个IIS，所以如果有多个冲突，您可能需要重复几次，直到找到并修复所有这些。查找IIS可能会非常慢。

从你的标签我假设你通过AMPL使用CPLEX。 Here is some documentation讨论了如何通过AMPL访问CPLEX IIS功能。基本上，在“求解”之前和之后插入以下命令：

option cplex_options 'iisfind 1';
solve;
display {i in 1.._ncons: _con[i].iis <> "non"} (_conname[i], _con[i].iis);

这将列出不可行性中涉及的约束。你也可以使用'iisfind 2'，它较慢，但试图找到一个较小的IIS。

有时，AMPL的预解析功能会妨碍使用IIS查找程序。 AMPL运行“预解决”步骤，尝试通过识别冗余约束等来减小问题的大小。

通常这很有用，因为它减少了内存需求和求解时间，但它可能会妨碍不可行性调试。 Presolve可能意味着并非所有约束都传递给求解器（在这种情况下，您的IIS可能不是真正的IIS，因为解算器没有看到冗余约束），有时AMPL识别预求解中的不可行性，在这种情况下它永远不会将它发送给解算器，因此您无法使用IIS功能。

在您的情况下，看起来好像AMPL正在将它发送给求解器，因此上面的代码应该可以工作。但是，如果您确实遇到了在预解决中检测到不可行性的情况，并且您想要确定问题的原因，则可以关闭预解决方案：

 option presolve 0; #set to 10 to re-enable presolve

我希望这有助于你的问题。