约束规划（CP）和线性规划（LP）或混合整数规划（MIP）有什么区别？我知道 LP 和 MIP 是什么，但不了解与 CP 的区别 - 还是 CP 与 MIP 和 LP 相同？我对此感到困惑...
问问题
6007 次
3 回答
18
这可能有点详尽，但我将尝试提供所有信息以涵盖该主题的良好范围。我将从一个例子开始，相应的信息会更有意义。
示例：假设我们需要在一台机器上对一组任务进行排序。每个任务 i 都有一个特定的固定处理时间 p i。每个任务都可以在其发布日期 r i之后开始，并且必须在其截止日期 d i之前完成。任务不能在时间上重叠。时间表示为一组离散的时间点，例如 {1, 2,…, H}（H 代表地平线）
MIP 型号：
- 变量：二进制变量 x ij表示任务 i 是否在时间段 j 开始
- 约束：
- 每个任务恰好在一个时间点开始
- ∑<sub>jx ij = 1 对于所有任务 i
- ∑<sub>jx ij = 1 对于所有任务 i
- 尊重发布日期和截止日期
- j*x ij = 0 对于所有任务 i 和 (j < r i ) 或 (j > d i - p i )
- j*x ij = 0 对于所有任务 i 和 (j < r i ) 或 (j > d i - p i )
- 任务不能重叠
- 变体 1：对于所有时间点 j，∑<sub>ix ij ≤ 1 我们还需要考虑处理时间；这变得混乱
- 变体 2：引入二进制变量 b i表示任务 i 是否在任务 k 之前必须链接到 x ij；这变得混乱 MIP 模型因此由线性/二次优化函数、线性/二次优化约束和二进制/整数变量组成。
- 变体 1：对于所有时间点 j，∑<sub>ix ij ≤ 1 我们还需要考虑处理时间；这变得混乱
- 每个任务恰好在一个时间点开始
CP型号：
- 变量： * 让 start i表示任务 i 的开始时间，从域 {1,2,…, H} 中取一个值 - 这立即确保每个任务恰好在一个时间点开始
- 约束： * 尊重发布日期和截止日期
r i ≤ start i ≤ d i - p i * 任务不能重叠：对于所有任务 i 和 j (start i + p i < start j ) OR (start i + p i < start i )
就是这样！
您可能会说 CP 模型和 MIP 模型的结构是相同的：使用决策变量、目标函数和一组约束。MIP 和 CP 问题都是非凸的，并且使用了一些系统的和详尽的搜索算法。
但是，我们看到了建模能力的主要差异。使用 CP，我们有 n 个变量和一个约束。在 MIP 中，我们有 nm 个变量和 n+m 个约束。这种使用二进制变量将全局约束映射到 MIP 约束的方法非常通用
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于结果问题树的每个节点处发生的情况。在 MIP 中，通常解决问题的线性松弛并使用结果来指导搜索。这是一个分支定界搜索。在 CP 中，执行基于每个全局约束的组合性质的逻辑推理。这是一个隐式枚举搜索。
优化差异：
- 约束编程引擎对变量和值做出决策，并在每个决策之后执行一组逻辑推理以减少剩余变量域的可用选项。相反，在离散优化的背景下，数学编程引擎使用松弛（通过切割平面加强）和“分支和边界”的组合。
- 约束编程引擎通过显示没有比当前解决方案更好的解决方案来证明最优性，而数学编程引擎使用由削减和线性松弛提供的下限证明。
- 约束规划引擎不对解空间的数学属性（凸性、线性等）做出假设，而数学规划引擎要求模型属于明确定义的数学类别（例如混合整数二次规划（ MIQP）。
在决定如何定义问题时 - 作为 MIP 或 CP，Google 优化工具指南建议： -
- 如果问题的所有约束条件都必须满足才能使解决方案可行（由“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源于人工智能、运筹学和计算机科学中的一个问题，因此它与计算机编程密切相关。
- 该领域的问题将符号值分配给需要满足某些约束的变量。
- 这些符号值具有有限域，可以用整数标记。
- CP建模语言更灵活，更接近自然语言。
引用自IBM 文档之一，约束编程是一种技术，其中：
使用比传统数学优化中更丰富的建模语言对业务问题进行建模
结合树搜索、人工智能和图论技术解决问题
最常见的约束（全局）是“alldifferent”约束，它确保决策变量采用整数值的某种排列（非重复排序）。前任。如果问题的域是 5 个决策变量，即。1,2,3,4,5，它们可以以任何非重复方式排序。
于 2017-11-17T16:29:39.327 回答
2
这个问题的答案取决于您是否将 MIP 和 CP 视为算法、问题或科学研究领域。
例如，每个 MIP 问题显然是一个 CP 问题，因为 MIP 问题的定义是找到一组线性约束的（n 个最优）解，而 CP 问题的定义是找到一个（n 个最优）解到一组（未指定的）约束。另一方面，许多重要的 CP 问题可以直接转换为线性约束集，因此从 MIP 角度看待 CP 问题也很有意义。
在算法上，CP 算法在历史上倾向于涉及更多的搜索分支和复杂的约束传播，而 MIP 算法在很大程度上依赖于解决问题的 LP 松弛。虽然存在混合算法（例如SCIP，字面意思是“求解约束整数程序”），并且最先进的求解器经常从另一方借用技术（例如，源自 CP 的不良学习和回跳，但现在也出现在 MIP 求解器中）。
从科学的研究领域来看，区别纯粹是历史性的：MIP 是运筹学的一部分，起源于二战末期，出于优化大规模“作战”的需要，而 CP 则源于逻辑编程人工智能领域以声明方式建模和解决问题。但是有一个很好的例子可以证明这两个领域都研究同一个问题。请注意，甚至还有一个大型共享会议：CPAIOR。
所以总而言之，我会说 MIP 和 CP 在大多数方面都是相同的，除了典型算法中使用的主要技术。
于 2019-04-10T09:49:00.297 回答
1
LP 和 MIP 使用数学规划求解，而约束规划问题有特定的求解方法。以下参考资料有助于理解差异：http: //ibmdecisionoptimization.github.io/docplex-doc/mp_vs_cp.html
于 2021-04-08T10:17:36.320 回答