确定一个整数程序是否不可行

假设我们有一个具有几千个约束的整数或混合整数程序。确定一个整数程序是否不可行

我们如何确定这个IP/MIP是否可行？

来源

2017-09-20 Faraz Ramtin

一般来说：只要把它扔在求解器上，看它是否返回“不可行”或其他东西。在实践中：证明不可行性可能非常昂贵。 –

https://en.wikipedia.org/wiki/Halting_problem是一个类似的问题。（而且约束的数量并没有真正发挥作用，“大”数只会让它听起来更复杂）。 – Ronald

不，暂停问题是不可判定的，这意味着即使您给计算机无限的时间，也无法解决问题。可行的手段是否可以在合理的时间内计算出来。 –

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

的数量限制做没有必要的规模与不可行性：通常的约束限制了必须列举可能性量。另一个相关的问题是随机 3-SAT，其中例如最难的问题是约束的数量与变量的数量相比约四倍的那些问题。

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

有很好的（混合）整数规划求解器可用，可以解决在合理的时间内一些（硬）的问题。尽管如此，通用的整型编程问题已知为NP-hard。这意味着找到在合理时间内总体解决这些问题的算法不太可能。有时我们很幸运，整数编程问题有一些我们可以利用的结构来有效地找到解决方案，但是正如所说：总的来说，这是一个难题。

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

在情况下，它是很容易找到正确的解决方案（相对于硬约束），但很难获得最佳的解决方案，可以使用启发式到近似的最佳解决方案。这里考虑一个解决方案的“解决方案空间”满足严格的约束。通过构建许多采用有效解决方案并将其转化为另一个解决方案的“变异函数”，可以通过迭代操作解决方案来生成搜索最佳解决方案的算法。如果我们耗尽时间，我们会返回迄今为止最好的解决方案。虽然我们从来没有保证我们有最佳的解决方案，但通常metaheuristics工作得很好，并且返回接近最佳解决方案的接近。一些metaheuristics像模拟退火可以统计保证解决方案的质量。

来源

2017-09-20 20:04:14

很好的概述。但是，imho：3-SAT的相变评论只是**随机** 3SAT的观察结果（否则它可能看起来非常不同，例如经典的[鸽子问题]（http://user.it.uu.se /〜tjawe125 /软件/归档/））。 MIP解算器正在大量使用这里未提及的切割平面（分支和切割），在证明不可行的情况下，这些未知数甚至变得更加重要。 – sascha

像品牌和边界一样的确切方法通过解决LP松弛来解决问题。如果遇到大问题，这些方法在计算上花费很大，并且不能保证它能找到任何整数解。启发式算法在我提出的问题中也不起作用，因为这些方法从一个可行的解决方案开始！如果我们有可行的解决方案，那么我们知道我们的问题是可行的但是，如果遇到困难和大问题，我们没有可行的解决方案，所以不像SA这样的算法不可行。 –

@FarazRamtin：但是如果LP松弛已经不可行，那么它绝对不可行。由于LP不是NP-hard：它在P中。所以这意味着它与ILP相比非常有效。所以不行。在这种情况下，你应该放松自己的问题*看看你是否可以删除细节等。 –

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

来源

2017-09-22 06:56:34 mattmilten

确定一个整数程序是否不可行

回答

相关问题