假设我们有一个带有几千个约束的整数或混合整数程序。
如何判断这个IP/MIP是否可行？
问问题
580 次
2 回答
3
假设我们有一个具有数千个约束的整数或混合整数规划问题。
约束的数量不一定随着不可行性而扩展：通常约束限制了必须枚举的可能性的数量。另一个相关问题是随机3-SAT，例如，其中最难的问题是约束数量与变量数量相比大约以因子四缩放的问题。
我们如何才能意识到这个问题是完全可行的？
有很好的（混合）整数规划求解器可以在合理的时间内解决一些（困难的）问题。然而，众所周知，通用整数规划问题是NP-hard。这意味着不太可能在合理的时间内找到解决这些问题的算法。有时我们很幸运，整数规划问题是否有一些我们可以利用的结构来有效地找到解决方案，但正如所说：一般来说，这是一个难题。
求解器通常使用分支定界，通过松弛限制变量的域，直到达到稳定条件。然后求解器为其中一个变量选择一个值（首先对哪个变量和什么值进行深入研究，因为这些对找到解决方案有很大影响）。然后问题被进一步放宽，直到证明不存在具有该值的解决方案，或者系统必须分配一个新值。如果一个模型被证明不能满足一组给定的分配变量，则系统回溯：它撤消分配的一些变量并重新分配这些变量的值并继续搜索。最终会找到解决方案（但可能需要很长时间），或者解决者可以证明问题无法满足（不存在解决方案）。如果找到了解决方案，我们还没有完成：因为我们通常对某个优化函数的最优解决方案感兴趣。在这种情况下，我们添加一个约束，从现在开始，我们寻找比迄今为止建立的解决方案更好的解决方案。我们一直这样做，直到我们用完新的解决方案，在这种情况下，我们已经证明了最优性。
如果很容易找到正确的解决方案（关于硬约束），但很难获得最佳解决方案，可以使用元启发式逼近最佳解决方案。这里考虑满足硬约束的解决方案的“解决方案空间”。通过构造一些“变异函数”，将一个有效的解决方案转化为另一个解决方案，人们可以通过迭代地操作解决方案来生成一种搜索最佳解决方案的算法。如果我们用完了时间，我们会返回迄今为止最好的解决方案。虽然我们从来没有保证我们有最优解，但元启发式通常工作得很好，并且返回一个接近最优的解决方案。一些像模拟退火这样的元启发式算法可以对解决方案的质量做出统计保证。
于 2017-09-20T20:04:14.767 回答
3
您可以肯定地说的一件事是，如果问题的线性松弛已经不可行，那么整数规划问题也是如此。
于 2017-09-22T06:56:34.197 回答