mathematical-optimization - 判断一个整数规划是否不可行

Question

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

如何判断这个IP/MIP是否可行？

Answer 1

Suppose we have a integer or mixed-integer programming problem with couple thousand of constraints.

约束数量不必因不可行性而扩展:通常约束会限制必须枚举的可能性的数量。另一个相关的问题是随机 3-SAT，例如，最难的问题是约束数量与变量数量相比大约成四倍的问题。

How we can realize this problem is feasible at all?

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

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

如果很容易找到正确的解决方案(相对于硬约束)，但很难获得最佳解决方案，可以使用元启发式来 近似 最好的解决方案。这里考虑满足硬约束的解决方案的“解决方案空间”。通过构建许多采用有效解决方案并将其转换为另一种解决方案的“变异函数”，人们可以通过迭代操作解决方案来生成搜索最佳解决方案的算法。如果时间用完，我们将返回迄今为止的最佳解决方案。虽然我们从来没有保证我们有最优解，但通常元启发式算法工作得很好，并且返回接近最优解。一些元启发式(如模拟退火)可以对解决方案的质量做出统计保证。