在整数规划中进行最小化的算法

Question

我明白在整数规划中做最小化是一个非常复杂的问题。但是是什么让这个问题如此困难呢？

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

Answer 1

I'm wondering what sort of roadblocks I will face when attempting to apply this technique programatically.

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

分支定界或分支切割等技术试图修剪搜索树，从而加快运行时间。但是整个问题树仍然呈指数级增长，这就是问题所在。