差异LP/MIP和CP

Question

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

Answer 1

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

示例:假设我们需要在计算机上对一组任务进行排序.每个任务我都有一个特定的固定处理时间p _i.每个任务可以后的发行日期r参数开始_我的,必须其限期d之前完成_我.任务不能及时重叠.时间表示为一组离散的时间点,例如{1,2,...,H}(H代表地平线)

MIP型号:

• 变量:二进制变量x _ij表示任务i是否在时间段j开始
• 约束:
  
  • 每个任务都在一个时间点开始
    
    • Σ _Ĵ X _IJ = 1对于所有的任务我
      
  • 尊重发布日期和截止日期
    
    • 对于所有任务i和(j <r _i)或(j> d _i - p _i),j*x _ij = 0
      
  • 任务不能重叠
    
    • 变体1:Σ _我 X _IJ ≤1所有的时间中点J,我们还需要采取的处理时间考虑; 这变得凌乱
      
    • 变式2:引入二进制变量b _i,表示在任务k必须链接到x _ij之前任务_i是否到来; 这变得凌乱的MIP模型因此由线性/二次优化函数,线性/二次优化约束和二进制/整数变量组成.

CP型号:

• 变量:*让我们开始_我代表任务的开始时间我从域{1,2,...,H}获取一个值 - 这立即确保每个任务从恰好一个时间点开始
  
• 约束条件:*尊重发布日期和截止日期
  - [R _我 ≤开始_我 ≤ð _我 - P _我 *任务不能重叠:所有任务i和j(开始_我 +过去分词_我 <启动_Ĵ)OR(开始_我 +过去分词_我 <开始_我)
  就是这样!

您可能会说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 则源于 2007 年的逻辑编程。人工智能领域以声明方式建模和解决问题。但有一个很好的例子表明，这两个领域都在研究同一问题。请注意，甚至还有一个大型共享会议：CPAIOR。

总而言之，我认为 MIP 和 CP 在大多数方面都是相同的，除了各自典型算法中使用的主要技术之外。