cplex - 如何在 CPLEX 中检查 MILP 是否有可行的解决方案

Question

我想知道是否有一种快速的方法来检查具有给定输入的 MILP 是否有可行的解决方案。我有一个 MILP 公式，并试图随机生成问题的输入，这些输入可能有也可能没有可行的解决方案。我想通过使用 CPLEX 来检查这一点。

我知道检查问题是否具有可行解的一种方法是将目标函数设置为常数（例如，0），以便 CPLEX 将返回找到的第一个可行解。如果我们生成的输入以某种方式具有可行的解决方案，这可能是最快的方法。

如果我们以某种方式生成没有可行解决方案的问题输入怎么办，我想知道使用 CPLEX 检查生成的输入是否没有可行解决方案的最快方法是什么。

谢谢你。

标签： cplex

Answer 1

通常，可行性与最优性一样难，因此通常您必须以一种或另一种方式解决 MIP。检测（不）可行性的一种方法确实是将目标归零，然后查看 CPLEX 是否找到可行的解决方案。但是，根据您的问题结构，有意义的目标值可能比全 0 目标更有效。您可以将“解限制”参数设置为 1，以便 CPLEX 在这种情况下停止在第一个可行解。

另一种选择是使用 CPLEX 的 feasopt 功能，请参阅此处。CPLEX 尝试找到最小松弛。它从一个总是可行的问题开始。如果您的原始模型可行，那么 feasopt 最终将以目标值为 0 的解终止。如果您的初始模型不可行，那么 CPLEX 对 feasopt 模型的最佳界限最终将超过 0，此时可以停止算法。这有时会更快地发现不可行。