我想知道组合优化和离散优化之间有什么关系和区别？谢谢！
最初通过阅读维基百科，我认为离散优化包括组合优化和整数优化，其中组合优化是搜索有限的解决方案集，整数优化是搜索可数无限的解决方案集。
但是在阅读了 Bernhard Korte 和 Jens Vygen Combinatorial Optimization: Theory and Algorithms的目录后，我看到他们在他们的组合优化书中包含了整数规划。现在我很困惑。
谢谢！
组合优化、离散优化和整数规划的关系和区别
计算科学
优化
2021-12-14 02:41:00
2个回答
这三个主题大致相同（因为可以通过多种方式重新表述相同的问题），只是从不同的角度看待，因此通常以不同的深度处理理论和实践的不同部分。
- 组合优化强调问题的组合起源、公式或解决算法。
- 离散优化强调与连续优化的区别。
- 整数规划强调在公式或解决方案中使用整数（或二进制整数）值变量。
好问题！这是我的看法。有一个层次结构如下：整数规划离散优化组合优化。
所以组合是最广泛的领域。任何涉及从一组离散的备选方案中做出决策的问题，我都会归类为组合问题。这里的问题定义可能非常复杂。
现在，假设我们可以使用离散变量来表述问题，即精确地陈述问题的决策变量并使用目标函数以及这些变量中的有限数量的约束来表述它。在这种情况下，我会将问题归类为离散优化问题。
最后，我想说整数编程更多地处理整数编程的算法方面。例如，比较不同的公式、开发算法、分析问题和算法复杂性。