判断整数规划是否不可行

Question

假设我们有一个整数或混合整数程序，它有几千个约束。

如何确定此IP / MIP是否可行？

Answer 1

假设我们有一个具有数千个约束的整数或混合整数规划问题。

number of constraint不需要在不可行的情况下进行缩放:通常，约束会限制必须枚举的可能性的数量。另一个相关的问题是随机3-SAT，例如，最困难的问题是那些约束数量与变量数量相比约为四倍的问题。

我们如何才能认识到这个问题是可行的呢？

有好的(混合的)整数规划解算器可以在合理的时间内解决一些(困难的)问题。然而，一般整数规划问题是已知的NP-hard。这意味着在合理的时间内通常不太可能找到解决这些问题的算法。有时我们很幸运，整数规划问题有一些结构，我们可以利用它来有效地找到解决方案，但正如所说的:一般来说，这是一个困难的问题。

求解器通常使用branch-and-bound，其中通过松弛限制变量的域，直到达到稳定条件。然后，求解器为其中一个变量选择一个值(首先对哪个变量和哪个值进行了深入的研究，因为这些变量对找到解决方案有很大的影响)。然后，问题被进一步放松，直到证明不存在具有该值的解决方案，或者系统必须分配新值。如果一个模型被证明对给定的赋值变量集是不可满足的，系统会回溯:它撤消一些赋值的变量，并为这些变量重新赋值，然后继续搜索。最终会找到一个解决方案(但可能需要很长时间)，或者求解器可以证明问题是不可满足的(不存在解决方案)。如果找到了解决方案，我们还没有完成:因为我们通常对某个优化函数的最优解感兴趣。在这种情况下，我们添加了一个约束，从现在开始，我们寻找比到目前为止建立的解决方案更好的解决方案。我们一直这样做，直到我们用完了新的解决方案，在这种情况下，我们已经证明了最优性。

这里考虑的是满足硬约束的解决方案的“解空间”。如果我们耗尽了时间，我们将返回到目前为止的最佳解决方案。虽然我们从来没有保证我们有最优解，但元启发式通常工作得很好，并返回一个接近最优解。一些元启发式算法，如模拟退火，可以对解的质量做出统计保证。

Answer 2

您可以肯定地说，如果线性松弛问题已经不可行，那么整数规划问题也是不可行的。