差异LP / MIP和CP

Question

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

Answer 1

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

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

MIP Model:

• 变量：二进制变量xij表示任务i是否在时间段j开始
• 约束： 每个任务都在一个时间点开始 所有任务的Σjxij= 1 i 尊重发布日期和截止日期 对于所有任务i和（j <ri）或（j> di-pi），j * xij = 0 任务不能重叠 变量1：对于所有时间点j，Σixij≤1我们还需要考虑处理时间;这变得凌乱 变式2：引入二进制变量bi，表示在任务k必须链接到xij之前任务i是否到来;这变得凌乱的MIP模型因此由线性/二次优化函数，线性/二次优化约束和二进制/整数变量组成。

CP model:

• 变量：*让starti代表任务的开始时间我从域{1,2，...，H}获取一个值 - 这可以立即确保每个任务从恰好一个时间点开始
• 约束：*尊重发布日期和截止日期 ri≤starti≤di - pi *任务不能重叠：对于所有任务i和j（starti + pi <startj）OR（starti + pi <starti） 就是这样！

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

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

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

优化差异：

• 约束编程引擎对变量和值做出决策，并在每次决策后执行一组逻辑推断，以减少剩余变量域的可用选项。相比之下，在离散优化的背景下，数学编程引擎使用松弛（由切割平面加强）和“分支和束缚”的组合。
• 约束编程引擎通过表明没有比当前解决方案更好的解决方案来证明最优性，而数学编程引擎使用由切割和线性松弛提供的下限证明。
• 约束编程引擎不对解空间的数学属性（凸性，线性等）做出假设，而数学编程引擎要求模型属于明确定义的数学类别（例如混合整数二次规划（ MIQP）。

在决定如何定义问题时 - 如MIP或CP，Google Optimization工具指南建议： -

1. 如果问题的所有约束必须保持解决方案可行（由“和”语句连接的约束），那么MIP通常更快。
2. 如果许多约束具有其中只有一个需要保持解决方案可行的属性（由“或”语句连接的约束），那么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源于人工智能，运筹学和计算机科学的问题，因此它与计算机程序设计密切相关。 - 此区域中的问题将符号值分配给需要满足某些约束的变量。 - 这些符号值具有有限域，可以用整数标记。 - CP建模语言更灵活，更接近自然语言。 引用其中一个IBM文档，约束编程是一种技术，其中：

• 使用比传统上在数学优化中发现的更丰富的建模语言来模拟业务问题
• 结合树搜索，人工智能和图论技术解决问题

最常见的约束（全局）是“不同的”约束，它确保决策变量假定整数值的一些排列（非重复排序）。防爆。如果问题的领域是5个决策变量即。 1,2,3,4,5，它们可以任何非重复的方式订购。

Answer 2

这个问题的答案取决于您是将MIP和CP视为算法，问题还是科学研究领域。

例如，每个MIP问题显然都是CP问题，因为MIP问题的定义是找到一组线性约束的（n最优）解，而CP问题的定义是找到（n最优）解决方案一组（非指定）约束。另一方面，许多重要的CP问题可以直接转换为线性约束集，因此通过MIP视角查看CP问题也是有意义的。

在算法上，CP算法历史上倾向于涉及更多的搜索分支和复杂的约束传播，而MIP算法在很大程度上依赖于解决问题的LP松弛。虽然存在混合算法（例如，SCIP，字面意思是“解决约束整数程序”），并且最先进的解算器经常从另一方借用技术（例如，起源于CP的不良学习和回跳，但现在也出现在MIP解算器中）。

从科学研究领域来看，差异纯粹是历史性的：MIP是运营研究的一部分，起源于二战结束时出于优化大规模“运营”的需要，而CP则源于逻辑编程。人工智能领域以声明的方式模拟和解决问题。但是有一个很好的例子，这两个领域都研究同样的问题。请注意，甚至还有一个大型的共享会议：CPAIOR。

总而言之，我会说MIP和CP在大多数方面是相同的，除了每种方法的典型算法中使用的主要技术。