1

我知道在整数编程中进行最小化是一个非常复杂的问题。但是是什么让这个问题如此困难？

如果我要（尝试）编写一个算法来解决它，我需要考虑什么？我只熟悉解决它的分支定界技术，我想知道在尝试以编程方式应用这种技术时会遇到什么样的障碍。

4

4 回答 4

4

我想知道在尝试以编程方式应用这种技术时会遇到什么样的障碍。

没有特别的（假设一个相当简单的实现没有很多技巧）。算法并不复杂——它们很复杂，这是根本的区别。

诸如分支定界或分支切割等技术试图修剪搜索树，从而加快运行时间。但是整个问题树仍然是指数级的大，因此问题。

于 2011-09-05T12:46:29.113 回答
2

就像另一个说的那样，这些问题非常困难，没有简单的解决方案或简单的算法适用于所有类别的问题。

正如您在问题中所说，解决这些问题的“经典”方法是进行分支定界并在每个节点上应用单纯形算法。但是，如果您不是专家，我不建议您自己实施。

至于很多数值方法，很难做到正确（良好的参数值、良好的优化），并且已经做了很多工作（参见 CPLEX、COIN_OR 等）。

并不是你不能这样做：分支定界部分非常简单，但是如果没有所有技巧，你的程序会非常慢。

此外，您将需要一个单工实现，这不是您想要自己做的事情：无论如何您都必须使用第三方库。

最有可能的是

  • 如果您的数据集不是那么大（试试看！），并且您对真正快速解决它不感兴趣：使用 COIN-OR 或 lp_solve 之类的方法和默认方法，它会起作用；
  • 如果您的数据集非常大（和/或您每次都需要快速找到解决方案），您需要与该领域的专家合作。

我的主要观点是，只有有经验的人才能知道哪种算法在您的问题上表现更好，哪种形式的模型最容易解决，应用哪种方法以及您可以尝试哪种优化。

如果你对这些问题感兴趣，我会推荐这本书来介绍这一切背后的数学（有很多例子）。它非常广阔，因此您可能想去图书馆而不是购买它：Nemhauser 和 Wolsey。

于 2011-09-06T09:09:53.080 回答
2

整数规划是NP 难的。这就是为什么它如此困难。

有一个你可能感兴趣的教程。

于 2011-09-05T12:47:10.427 回答
0

在解决任何数学优化问题之前，你要做的第一件事就是对它进行分类。除特殊情况外，大多数情况下，整数规划问题都是 np-hard。因此，您将使用“启发式”，而不是使用“算法”。您将找到的最终解决方案不会是保证的最佳解决方案，但它将是解决现实生活问题的一个很好的解决方案。

您的主要障碍将是您的编程技能。启发式编程需要良好的编程理解水平。因此，与其编写自己的启发式方法，不如使用众所周知的包（例如，COIN-OR，免费）。这样你就可以专注于你的问题而不是启发式的。

于 2011-09-05T13:51:44.560 回答