optimization - 约束规划与线性规划 : Speed and quality of solution

Question

我一直在研究优化算法，遇到了一些找不到答案的问题。

a) CP 比 LP 快吗？与 MILP 相比如何？
b) CP和MILP会提供相同的目标函数值吗？
c) 我什么时候应该使用 CP 而不是 MILP？ (如果我有一个混合整数线性问题)

谢谢。

Answer 1

我曾与 CP 和 LP/MILP 合作过，也许我可以就您的疑问提供一些见解。 CP 和 LP 唯一的共同点是“编程”一词。

• 变量类型不同(CP=离散整数值/LP=连续values/MILP=一些变量是离散的，其他变量是连续的)。
• 处理的约束类型不同(CP 涉及非线性，LP 是当然在使用的变量中是线性的)。

a) CP 比 LP 快吗？在大多数情况下，我会认为 CP 更慢，因为 CP 中没有明确的算法。它依赖于搜索。然而，CP 模型往往需要较少的变量。只有线性约束，需要更多变量来建模(例如，使用大型 M 方程)。

b) CP 和 MILP 给出相同的目标函数值 - 如果约束都是线性的，并且所有变量都是整数，那么使用 CP 来解决问题就没有意义了，因为它的性能会降低。

c) 当问题约束在 CP 方程中得到很好的表达，和/或在线性(大 M)方程中表达不佳时，我们应该使用 CP，其中向最优收敛不好或很慢。

检查这个question .一些整合这两种方法的研究工作产生了开源软件，如 CLP(r) .