差异 LP/MIP 和 CP
Difference LP/MIP and CP
约束规划 (CP) 和线性规划 (LP) 或混合整数规划 (MIP) 有什么区别？我知道 LP 和 MIP 是什么，但不明白与 CP 的区别 - 或者 CP 是否与 MIP 和 LP 相同？我对此感到困惑......
这可能有点详尽，但我会尽力提供所有信息以涵盖该主题的大部分范围。
我将从一个 示例 开始，相应的信息会更有意义。
示例：假设我们需要在一台机器上对一组任务进行排序。每个任务i都有一个特定的固定处理时间pi。每个任务都可以在其发布日期 ri 之后开始，并且必须在其截止日期 di 之前完成。任务不能及时重叠。时间表示为一组离散的时间点，例如 {1, 2, ..., H}（H 代表 horizon）
MIP 型号：
- Variables：二进制变量xij表示任务i是否在时间段j
开始
- 限制条件：
- 每项任务恰好在一个时间点开始
- ∑j xij = 1 对于所有任务 i
- 尊重发布日期和截止日期
- j*xij = 0 对于所有任务 i 和 (j < ri ) 或 (j > di - pi )
- 任务不能重叠
- 变体 1：
∑i xij ≤ 1 对于所有时间点 j 我们还需要考虑处理时间；这变得凌乱
- 变体 2：
引入二进制变量 bi 表示任务 i 在任务 k 之前是否必须链接到 xij；这变得凌乱
因此，MIP 模型由 linear/quadratic 优化函数、线性/二次优化约束和 binary/integer 变量组成。
CP型号：
- 变量：
* 让 starti 表示任务 i 的开始时间从域 {1,2,…, H} 中取值 - 这立即确保每个任务都在恰好一个时间点开始
- 约束：
* 遵守发布日期和截止日期
ri ≤ starti ≤ di - pi
* 任务不能重叠：
对于所有任务 i 和 j (starti + pi < startj) 或 (starti + pi < starti)
就是这样！
您可能会说 CP 模型和 MIP 模型的结构是相同的：使用决策变量、objective 函数和一组约束。 MIP 和 CP 问题都是 non-convex 并且使用了一些系统和详尽的搜索算法。
但是，我们看到了建模能力的主要差异。使用 CP，我们有 n 个变量和一个约束。在 MIP 中，我们有 nm 个变量和 n+m 个约束。这种使用二进制变量将全局约束映射到 MIP 约束的方法非常通用
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于生成的问题树的每个节点发生了什么。在 MIP 中，通常会解决问题的线性松弛问题，并使用结果来指导搜索。这是一个分支定界搜索。在 CP 中，执行基于每个全局约束的组合性质的逻辑推理。这是隐式枚举搜索。
优化差异：
- 约束编程引擎对变量和值做出决策，并在每次决策后执行一组逻辑推理，以减少剩余变量域的可用选项。相反，在离散优化的上下文中，数学规划引擎使用松弛（由 cutting-planes 加强）和 "branch and bound."
的组合
- 约束规划引擎通过证明找不到比当前解决方案更好的解决方案来证明最优性，而数学规划引擎使用由切割和线性松弛提供的下限证明。
- 约束规划引擎不对解决方案的数学属性space（凸性、线性等）做出假设，而数学规划引擎要求模型落在well-defined 数学类别（例如混合整数二次规划 (MIQP)。
在决定您应该如何定义问题时 - 作为 MIP 或 CP，Google 优化 工具指南建议：-
- 如果问题的所有约束都必须成立才能使解决方案可行（约束由 "and" 语句连接），那么 MIP 通常更快。
- 如果许多约束具有 属性，只有其中一个约束需要满足才能使解决方案可行（约束由 "or" 语句连接），那么 CP 通常更快。
我的2美分：
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于生成的问题树的每个节点发生了什么。在 MIP 中，通常会解决问题的线性松弛问题，并使用结果来指导搜索。这是一个分支定界搜索。在CP中，执行基于每个全局约束的组合性质的逻辑推理。
对于您将使用哪种方法来制定模型和解决问题，没有一个具体的答案。当变量数量增加很多并且问题难以使用线性等式来制定约束时，CP 可能会更好。如果 MIP 松弛很紧，它可以提供更好的结果 - 如果您在遍历 MIP 问题时下界移动不够，您可能需要考虑更高程度的 MIP 或 CP。当问题可以用全局约束表示时，CP 工作得很好。
更多关于 MIP 和 CP 的阅读：
Mixed-Integer 编程 问题的某些决策变量在最优解时被限制为整数 (-n … 0 … n)。这使得根据数学程序定义问题变得更加容易。 MP 专注于特殊 class 问题，对于解决松弛或子问题（垂直结构）很有用。
数学模型示例：
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源于AI、运筹学和计算机科学中的一个问题，因此它与计算机编程密切相关。
- 该领域的问题将符号值赋给需要满足某些约束的变量。
- 这些符号值有一个有限域，可以用整数标记。
- CP建模语言更灵活，更接近自然语言。
引自其中一个 IBM 文档，约束编程是一种技术，其中：
使用比数学优化中传统的建模语言更丰富的建模语言对业务问题进行建模
结合树搜索、人工智能和图论技术解决问题
最常见的约束（全局）是 "alldifferent" 约束，它确保决策变量假设整数值的某种排列（non-repeating 排序）。前任。如果问题的领域是 5 个决策变量，即。 1,2,3,4,5，它们可以按任何 non-repetitive 方式排序。
这个问题的答案取决于您是将 MIP 和 CP 视为算法、问题还是科学研究领域。
例如，每个 MIP 问题显然都是一个 CP 问题，因为 MIP 问题的定义是找到一组线性约束的（n 个最优）解，而 CP 问题的定义是找到一个一组 (non-specified) 约束的（n 最优）解。另一方面，许多重要的 CP 问题可以直接转换为线性约束集，因此从 MIP 角度看 CP 问题也很有意义。
在算法上，CP 算法历来倾向于涉及更多的搜索分支和复杂的约束传播，而 MIP 算法在很大程度上依赖于解决问题的 LP 松弛。虽然存在混合算法（例如，SCIP，字面意思是 "Solving Constraint Integer Programs"），并且 state-of-the-art 求解器经常从另一端借用技术（例如，no-good 学习和回跳起源在 CP 中，但现在也存在于 MIP 求解器中）。
从科学研究领域的角度来看，差异纯粹是历史性的：MIP 是运筹学的一部分，起源于二战末期出于优化的需要 large-scale "operations" ，而 CP 源于人工智能领域的逻辑编程，以声明方式建模和解决问题。但是有一个很好的例子可以证明这两个领域研究的是同一个问题。请注意，甚至还有一个大型共享会议：CPAIOR.
所以总而言之，我想说 MIP 和 CP 在大多数方面都是相同的，除了每个典型算法中使用的主要技术。
LP和MIP是用数学规划求解的，而约束规划问题有特定的求解方法。以下参考资料有助于理解差异：
http://ibmdecisionoptimization.github.io/docplex-doc/mp_vs_cp.html
约束规划 (CP) 和线性规划 (LP) 或混合整数规划 (MIP) 有什么区别？我知道 LP 和 MIP 是什么，但不明白与 CP 的区别 - 或者 CP 是否与 MIP 和 LP 相同？我对此感到困惑......
这可能有点详尽，但我会尽力提供所有信息以涵盖该主题的大部分范围。 我将从一个 示例 开始，相应的信息会更有意义。
示例：假设我们需要在一台机器上对一组任务进行排序。每个任务i都有一个特定的固定处理时间pi。每个任务都可以在其发布日期 ri 之后开始，并且必须在其截止日期 di 之前完成。任务不能及时重叠。时间表示为一组离散的时间点，例如 {1, 2, ..., H}（H 代表 horizon）
MIP 型号：
- Variables：二进制变量xij表示任务i是否在时间段j 开始
- 限制条件：
- 每项任务恰好在一个时间点开始
- ∑j xij = 1 对于所有任务 i
- ∑j xij = 1 对于所有任务 i
- 尊重发布日期和截止日期
- j*xij = 0 对于所有任务 i 和 (j < ri ) 或 (j > di - pi )
- j*xij = 0 对于所有任务 i 和 (j < ri ) 或 (j > di - pi )
- 任务不能重叠
- 变体 1：
∑i xij ≤ 1 对于所有时间点 j 我们还需要考虑处理时间；这变得凌乱
- 变体 2： 引入二进制变量 bi 表示任务 i 在任务 k 之前是否必须链接到 xij；这变得凌乱 因此，MIP 模型由 linear/quadratic 优化函数、线性/二次优化约束和 binary/integer 变量组成。
- 变体 1：
∑i xij ≤ 1 对于所有时间点 j 我们还需要考虑处理时间；这变得凌乱
- 每项任务恰好在一个时间点开始
CP型号：
- 变量：
* 让 starti 表示任务 i 的开始时间从域 {1,2,…, H} 中取值 - 这立即确保每个任务都在恰好一个时间点开始
- 约束：
* 遵守发布日期和截止日期
ri ≤ starti ≤ di - pi * 任务不能重叠： 对于所有任务 i 和 j (starti + pi < startj) 或 (starti + pi < starti)
就是这样！
您可能会说 CP 模型和 MIP 模型的结构是相同的：使用决策变量、objective 函数和一组约束。 MIP 和 CP 问题都是 non-convex 并且使用了一些系统和详尽的搜索算法。
但是，我们看到了建模能力的主要差异。使用 CP，我们有 n 个变量和一个约束。在 MIP 中，我们有 nm 个变量和 n+m 个约束。这种使用二进制变量将全局约束映射到 MIP 约束的方法非常通用
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于生成的问题树的每个节点发生了什么。在 MIP 中，通常会解决问题的线性松弛问题，并使用结果来指导搜索。这是一个分支定界搜索。在 CP 中，执行基于每个全局约束的组合性质的逻辑推理。这是隐式枚举搜索。
优化差异：
- 约束编程引擎对变量和值做出决策，并在每次决策后执行一组逻辑推理，以减少剩余变量域的可用选项。相反，在离散优化的上下文中，数学规划引擎使用松弛（由 cutting-planes 加强）和 "branch and bound."
- 约束规划引擎通过证明找不到比当前解决方案更好的解决方案来证明最优性，而数学规划引擎使用由切割和线性松弛提供的下限证明。
- 约束规划引擎不对解决方案的数学属性space（凸性、线性等）做出假设，而数学规划引擎要求模型落在well-defined 数学类别（例如混合整数二次规划 (MIQP)。
在决定您应该如何定义问题时 - 作为 MIP 或 CP，Google 优化 工具指南建议：-
- 如果问题的所有约束都必须成立才能使解决方案可行（约束由 "and" 语句连接），那么 MIP 通常更快。
- 如果许多约束具有 属性，只有其中一个约束需要满足才能使解决方案可行（约束由 "or" 语句连接），那么 CP 通常更快。
我的2美分：
CP 和 MIP 以不同的方式解决问题。两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地拆分为子问题。主要区别在于生成的问题树的每个节点发生了什么。在 MIP 中，通常会解决问题的线性松弛问题，并使用结果来指导搜索。这是一个分支定界搜索。在CP中，执行基于每个全局约束的组合性质的逻辑推理。
对于您将使用哪种方法来制定模型和解决问题，没有一个具体的答案。当变量数量增加很多并且问题难以使用线性等式来制定约束时，CP 可能会更好。如果 MIP 松弛很紧，它可以提供更好的结果 - 如果您在遍历 MIP 问题时下界移动不够，您可能需要考虑更高程度的 MIP 或 CP。当问题可以用全局约束表示时，CP 工作得很好。
更多关于 MIP 和 CP 的阅读：
Mixed-Integer 编程 问题的某些决策变量在最优解时被限制为整数 (-n … 0 … n)。这使得根据数学程序定义问题变得更加容易。 MP 专注于特殊 class 问题，对于解决松弛或子问题（垂直结构）很有用。
数学模型示例：
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源于AI、运筹学和计算机科学中的一个问题，因此它与计算机编程密切相关。
- 该领域的问题将符号值赋给需要满足某些约束的变量。
- 这些符号值有一个有限域，可以用整数标记。
- CP建模语言更灵活，更接近自然语言。
引自其中一个 IBM 文档，约束编程是一种技术，其中：
使用比数学优化中传统的建模语言更丰富的建模语言对业务问题进行建模
结合树搜索、人工智能和图论技术解决问题
最常见的约束（全局）是 "alldifferent" 约束，它确保决策变量假设整数值的某种排列（non-repeating 排序）。前任。如果问题的领域是 5 个决策变量，即。 1,2,3,4,5，它们可以按任何 non-repetitive 方式排序。
这个问题的答案取决于您是将 MIP 和 CP 视为算法、问题还是科学研究领域。
例如，每个 MIP 问题显然都是一个 CP 问题，因为 MIP 问题的定义是找到一组线性约束的（n 个最优）解，而 CP 问题的定义是找到一个一组 (non-specified) 约束的（n 最优）解。另一方面，许多重要的 CP 问题可以直接转换为线性约束集，因此从 MIP 角度看 CP 问题也很有意义。
在算法上，CP 算法历来倾向于涉及更多的搜索分支和复杂的约束传播，而 MIP 算法在很大程度上依赖于解决问题的 LP 松弛。虽然存在混合算法（例如，SCIP，字面意思是 "Solving Constraint Integer Programs"），并且 state-of-the-art 求解器经常从另一端借用技术（例如，no-good 学习和回跳起源在 CP 中，但现在也存在于 MIP 求解器中）。
从科学研究领域的角度来看，差异纯粹是历史性的：MIP 是运筹学的一部分，起源于二战末期出于优化的需要 large-scale "operations" ，而 CP 源于人工智能领域的逻辑编程，以声明方式建模和解决问题。但是有一个很好的例子可以证明这两个领域研究的是同一个问题。请注意，甚至还有一个大型共享会议：CPAIOR.
所以总而言之，我想说 MIP 和 CP 在大多数方面都是相同的，除了每个典型算法中使用的主要技术。
LP和MIP是用数学规划求解的，而约束规划问题有特定的求解方法。以下参考资料有助于理解差异： http://ibmdecisionoptimization.github.io/docplex-doc/mp_vs_cp.html