linear-programming - LP/MIP 和 CP 的差异

Question

约束规划 (CP) 和线性规划 (LP) 或混合整数规划 (MIP) 之间有什么区别？我知道 LP 和 MIP 是什么，但不明白与 CP 的区别 - 或者 CP 与 MIP 和 LP 相同？我对此很困惑...

Answer 1

这可能有点详尽，但我将尝试提供所有信息以涵盖该主题的一个很好的范围。
我将从 开始示例 并且相应的信息会更有意义。

示例 :假设我们需要在一台机器上对一组任务进行排序。每个任务 i 都有一个特定的固定处理时间 pi。每个任务都可以在其发布日期 ri 之后开始，并且必须在其截止日期 di 之前完成。任务不能在时间上重叠。时间表示为一组离散的时间点，例如 {1, 2,..., H}(H 代表地平线)

MIP 型号:

变量:二元变量 xij 表示任务 i 是否在时间段 j

开始

约束:

每个任务都在一个时间点开始

∑j xij = 1 对于所有任务 i

尊重发布日期和截止日期

j*xij = 0 对于所有任务 i 和 (j < ri ) 或 (j > di - pi )

任务不能重叠

变体 1:
∑i xij ≤ 1 对于所有时间点 j 我们还需要考虑处理时间；这变得凌乱

变体 2:
引入表示任务 i 是否在任务 k 之前的二进制变量 bi 必须链接到 xij；这变得凌乱
MIP 模型因此由线性/二次优化函数、线性/二次优化约束和二进制/整数变量组成。

CP型号:

变量:
* 让 starti 表示任务 i 的开始时间，从域 {1,2,..., H} 取一个值 - 这立即确保每个任务都在一个时间点开始

约束:
*尊重发布日期和截止日期
ri ≤ starti ≤ di - pi
* 任务不能重叠:
对于所有任务 i 和 j (starti + pi < startj) 或 (starti + pi < starti)
就是这样!

您可能会说 CP 模型和 MIP 模型的结构相同:使用决策变量、目标函数和一组约束。 MIP 和 CP 问题都是非凸问题，并且都使用了一些系统且详尽的搜索算法。

但是，我们看到建模能力的主要差异。对于 CP，我们有 n 个变量和一个约束。在 MIP 中，我们有 nm 个变量和 n+m 个约束。这种使用二进制变量将全局约束映射到 MIP 约束的方法非常通用

CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于在生成的问题树的每个节点上发生了什么。在 MIP 中，通常解决问题的线性松弛并使用结果来指导搜索。这是一个分支定界搜索。在 CP 中，执行基于每个全局约束的组合性质的逻辑推理。这是一个隐式枚举搜索。

优化差异:

约束编程引擎对变量和值做出决策，并在每个决策之后执行一组逻辑推理以减少剩余变量域的可用选项。相比之下，数学编程引擎在离散优化的上下文中使用松弛(通过切割平面加强)和“分支和界限”的组合。

约束编程引擎通过表明找不到比当前更好的解决方案来证明最优性，而数学编程引擎使用由切割和线性松弛提供的下界证明。

约束编程引擎不会对解空间的数学属性(凸性、线性等)进行假设，而数学编程引擎要求模型属于明确定义的数学类别(例如混合整数二次规划( MIQP)。

在决定您应该如何定义您的问题 - 作为 MIP 或 CP， 谷歌优化 工具指南建议:-

如果问题的所有约束都必须成立才能使解决方案可行(约束由“and”语句连接)，那么 MIP 通常更快。

如果许多约束具有只有其中一个约束才能使解决方案可行的属性(约束由“或”语句连接)，那么 CP 通常更快。

我的 2 美分:
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于在生成的问题树的每个节点上发生了什么。在 MIP 中，通常解决问题的线性松弛并使用结果来指导搜索。这是一个分支定界搜索。在 CP 中，执行基于每个全局约束的组合性质的逻辑推理。

对于您将使用哪种方法来制定模型和解决问题，没有一个具体的答案。当变量数量增加很多并且问题难以使用线性等式来制定约束时，CP 可能会更好地工作。如果 MIP 松弛很紧，它可以提供更好的结果 - 如果在遍历 MIP 问题时下界移动不够，您可能需要考虑更高程度的 MIP 或 CP。当问题可以用全局约束表示时，CP 效果很好。

更多关于 MIP 和 CP 的阅读:
混合整数规划 问题的一些决策变量在最优解中被限制为整数 (-n … 0 … n​​)。这使得根据数学程序定义问题变得更容易。 MP 专注于特殊类别的问题，可用于解决松弛或子问题(垂直结构)。
数学模型示例:
Objective: minimize cT x
   Constraints: A x = b (linear constraints)
l ≤ x ≤ u (bound constraints)
some or all xj must take integer values (integrality constraints)
或者模型可以由二次函数或约束定义，(MIQP/MIQCP 问题)
Objective: minimize xT Q x + qT x
   Constraints: A x = b (linear constraints)
l ≤ x ≤ u (bound constraints)
xT Qi x + qiT x ≤ bi (quadratic constraints)
some or all x must take integer values (integrality constraints)
用于收敛 MIP 问题的最常用算法是分支定界法。

客服:
CP 源于人工智能、运筹学和计算机科学中的一个问题，因此它与计算机编程密切相关。- 该领域的问题为需要满足某些约束的变量分配符号值。- 这些符号值具有有限域并且可以用整数标记。- CP建模语言更灵活，更接近自然语言。
引自 之一IBM 文档 , 约束编程是一种技术，其中:

业务问题使用比传统数学优化中更丰富的建模语言建模

结合树搜索、人工智能和图论技术解决问题

最常见的约束(全局)是“alldifferent”约束，它确保决策变量采用整数值的某种排列(非重复排序)。前任。如果问题的域是 5 个决策变量，即。 1、2、3、4、5，它们可以以任何非重复的方式订购。