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

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。这是一些讨论如何通过 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 运行“预求解”步骤，尝试通过识别冗余约束等来减小问题的规模。

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

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

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

我希望这有助于解决您的问题。