整数规划中的最小化算法
我知道在整数规划中进行最小化是一个非常复杂的问题。但是什么让这个问题如此困难呢？
如果我（尝试）编写一个算法来解决它，我需要考虑什么？我只熟悉解决该问题的分支定界技术，我想知道在尝试以编程方式应用此技术时会遇到什么样的障碍。
I understand that doing minimization in integer programming is a very complex problem. But what makes this problem so difficult?
If I were to (attempt) to write an algorithm to solve it, what would I need to take into account? I'm only familiar with the branch-and-bound technique for solving it and I'm wondering what sort of roadblocks I will face when attempting to apply this technique programatically.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
没有什么特别的（假设一个相当简单的实现，没有很多技巧）。这些算法并不复杂——它们复杂，这是根本的区别。
诸如分支定界或分支剪切之类的技术尝试修剪搜索树，从而加快运行时间。但整个问题树仍然呈指数级大，因此出现了问题。
None in particular (assuming a fairly straightforward implementation without a lot of tricks). The algorithms aren’t complicated – they are complex, that’s a fundamental difference.
Techniques such as branch and bound or branch and cut try to prune the search tree and thus speed up the running time. But the whole problem tree is nevertheless exponentially large, hence the problem.
就像其他人所说的那样，这些问题非常困难，并且没有适用于所有类别问题的简单解决方案或简单算法。
解决这些问题的“经典”方法是进行分支定界并在每个节点应用单纯形算法，正如您在问题中所说的那样。但是，如果您不是专家，我不建议您自己实施此操作。
至于很多数值方法，很难做到正确（好的参数值、好的优化），并且已经做了很多工作（参见 CPLEX、COIN_OR 等）。
这并不是说您做不到：分支定界部分非常简单，但如果没有所有技巧，您的程序将非常很慢。
另外，您将需要一个简单的实现，而这不是您想要自己做的事情：无论如何您都必须使用第三方库。
最有可能的是，
我的主要观点是，只有经验丰富的人才知道哪种算法能够更好地解决您的问题、哪种形式的模型最容易解决、应用哪种方法以及您可以尝试哪种优化。
如果您对这些问题感兴趣，我会推荐这本书，介绍所有这一切背后的数学（有很多例子）。它的内容非常广泛，因此您可能想要去图书馆而不是购买它： Nemhauser和沃尔西。
Like the other said, those problem are very hard and there are no simple solution nor simple algorithm that apply to all classes of problems.
The "classic" way of solving those problem is to do a branch-and-bound and apply the simplex algorithm at each node, as you say in your question. However, I would not recommand implementing this yourself if you are not an expert.
As for a lot of numerical methods, it is very hard to get it right (good parameter values, good optimisations), and a lot have been done (see CPLEX, COIN_OR, etc).
It's not that you can't do it: the branch-and-bound part is pretty straigtforward, but without all the tricks your program will be really slow.
Also, you will need a simplex implementation and this is not something you want to do yourself: you will have to use a third-part lib anyway.
Most likely, wether
My main point is that only experienced people will know which algorithm will perform better on your problem, wich form of the model will be the easiest to solve, which method to apply and what kind of optimisations you can try.
If you are interested in those problems, I would recommend this book for an introduction to the math behind all this (with a lot of examples). It is incredibly expansive, so you may want to go to a library instead of buying it: Nemhauser and Wolsey.
整数规划是NP-hard。这就是为什么它如此困难。
您可能会对教程感兴趣。
Integer programming is NP-hard. That's why it is so difficult.
There is a tutorial that you might be interested.
在解决任何数学优化问题之前要做的第一件事就是对其进行分类。除特殊情况外，大多数时候，整数规划问题都是 np 困难的。因此，您将使用“启发式”，而不是使用“算法”。您将找到的最终解决方案不会保证是最佳的，但对于现实生活中的问题来说，它将是一个非常好的解决方案。
你的主要障碍是你的编程技能。启发式编程需要良好的编程理解水平。因此，与其编写自己的启发式程序，不如使用众所周知的包（例如，COIN-OR，免费）。这样你就可以专注于你的问题而不是启发式的。
The first thing you do before you solve any mathematical optimization problem is you categorize it. Except special cases, most of the time, integer programming problems will be np-hard. So instead of using an "algorithm", you will use a "heuristic". The final solution you will find will not be a guaranteed optimum, but it will be a pretty good solution for real life problems.
Your main roadblock will your programming skills. Heuristic programming requires a good level of programming understanding. So instead of programming your own heuristic you are better of using well known package (eg, COIN-OR, free). This way you can focus on your problem instead of the heuristic.