Some more reading on MIP and CP: Mixed-Integer Programming 问题的一些决策变量在最优解决方案中被约束为整数（-n ... 0 ... n） . 这使得更容易根据数学程序定义问题 . MP专注于特殊类别的问题，对解决松弛或子问题（垂直结构）非常有用 . Example of a mathematical model: 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 docs ，约束编程是一种技术，其中：
1 回答
这可能有点详尽，但我会尝试提供所有信息，以涵盖此主题的良好范围 . 我将从 example 开始，相应的信息将更有意义 .
Example ：假设我们需要在一台机器上对一组任务进行排序 . 每个任务我都有一个特定的固定处理时间pi . 每个任务可以在其发布日期ri之后开始，并且必须在截止日期之前完成 . 任务不能及时重叠 . 时间表示为一组离散的时间点，例如{1,2，...，H}（H代表地平线）
MIP型号：
变量：二进制变量xij表示任务i是否在时间段j开始
限制条件：
每个任务都在一个时间点开始
Σjxij= 1表示所有任务i
尊重发布日期和截止日期
j * xij = 0表示所有任务i和（j <ri）或（j> di - pi）
任务不能重叠
变量1：Σixij≤1对于所有时间点j我们还需要考虑处理时间;这变得凌乱
变体2：引入二进制变量bi，表示在任务k必须链接到xij之前任务i是否到来;这变得凌乱的MIP模型因此由线性/二次优化函数，线性/二次优化约束和二进制/整数变量组成 .
CP型号：
变量：*让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中，执行基于每个全局约束的组合性质的逻辑推断 . 这是一个隐式枚举搜索 .
Optimization differences:
约束编程引擎对变量和值做出决策，并在每次决策后执行一组逻辑推断，以减少剩余变量域的可用选项 . 相比之下，在离散优化的背景下，数学编程引擎使用松弛的组合（由切割平面加强）和"branch and bound."
约束编程引擎通过显示没有比当前解决方案更好的解决方案来证明最优性，而数学编程引擎使用由切割和线性松弛提供的下限证明 .
约束编程引擎不对解空间的数学属性（凸性，线性等）做出假设，而数学编程引擎要求模型属于明确定义的数学类别（例如混合整数二次规划） （MIQP） .
在决定如何定义问题时 - 如MIP或CP， Google Optimization 工具指南建议： -
如果问题的所有约束必须保持解决方案可行（由"and"语句连接的约束），那么MIP通常更快 .
如果许多约束具有其中只有一个需要保持解决方案可行的属性（由"or"语句连接的约束），那么CP通常是快点 .
My 2 cents:
CP和MIP以不同的方式解决问题 . 两者都使用分而治之的方法，通过一次固定一个变量的值，将要解决的问题递归地分解为子问题 . 主要区别在于生成的问题树的每个节点发生了什么 . 在MIP中，通常可以解决问题的线性松弛并使用结果来指导搜索 . 这是一个分支定界搜索 . 在CP中，执行基于每个全局约束的组合性质的逻辑推断 .
对于您使用哪种方法来制定模型并解决问题，没有一个具体的答案 . 当变量数量增加很多时，CP可能会更好地工作，并且难以使用线性等式来制定约束 . 如果MIP放松紧张，它可以提供更好的结果 - 如果在穿越MIP问题时下限不够移动，您可能需要考虑更高程度的MIP或CP . 当问题可以由全局约束表示时，CP运行良好 .
Some more reading on MIP and CP:
Mixed-Integer Programming 问题的一些决策变量在最优解决方案中被约束为整数（-n ... 0 ... n） . 这使得更容易根据数学程序定义问题 . MP专注于特殊类别的问题，对解决松弛或子问题（垂直结构）非常有用 .
Example of a mathematical model:
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 docs ，约束编程是一种技术，其中：
业务问题使用比传统上在数学优化中发现的更丰富的建模语言来建模
通过树搜索，人工智能和图论技术的组合解决了
最常见的约束（全局）是“不同的”约束，它确保决策变量假定整数值的一些排列（非重复排序） . 防爆 . 如果问题的领域是5个决策变量即 . 1,2,3,4,5，它们可以任何非重复的方式订购 .