差異LP/MIP和CP

Question

約束規劃（CP）和線性規劃（LP）或混合整數規劃（MIP）有什麼區別？我知道LP和MIP是什麼，但不瞭解與CP的區別 - 或者CP與MIP和LP相同？我對此感到困惑......

Answer 1

這可能有點窮舉，但我會盡量提供所有信息以涵蓋此主題的良好範圍。 我將從示例開始，相應的信息將更有意義。

示例：假設我們需要在一臺機器上對一組任務進行排序。每個任務我都有一個特定的固定處理時間p _i。每個任務可以在其發佈日期後開始r _i，並且必須在其截止日期前完成d _i。任務不能及時重疊。時間被表示爲一組離散的時間點，說{1，2，...，H}（H表示地平線）

MIP型號：

• 變量：二進制變量x _IJ表示是否任務開始我在時間段Ĵ
• 約束：
  
  • 每個任務的正是一個時間點開始
    
    • Σ_Ĵ X _IJ = 1對於所有的任務我
      
  • 尊重發行日期和截止日期
    
    • Ĵ* X _IJ = 0對所有的任務我和（j <或（j> d _i - p _i）
      
    所有的時間中點J，我們還需要採取的處理時間考慮 Σ _我 X _IJ≤1;：
  • 任務不能重疊
    
    • 變1這成爲凌亂
      
    • 變體2： 引入二進制變量b _我表示i是否任務到達之前任務ķ必須鏈接至x _IJ;這變得凌亂 MIP模型因此由線性/二次優化函數，線性/二次優化約束和二進制/整數變量組成。

CP模式：

• 變量： *讓開始_我代表任務的啓動時間我需要從域{1,2的值，...，H } - 這立即確保每個任務開始只有一個時間點
  
• 約束： *尊重發布日期和截止日期
  [R _我≤開始_我≤d _我 - P _我 *任務不能重疊： 所有任務i和j（開始_我 + P _我 <開始_Ĵ） 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 ，谷歌優化工具指南建議： -

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文檔的一個報價，約束規劃是其中一項技術：

• 業務問題，使用比在數學優化傳統上發現了一個更豐富的建模語言建模
  

• 問題通過樹搜索，人工智能和圖論理論技術的結合來解決
  

最常見的約束（全局）是「alldifferent」約束，它確保決策變量假定整數值的一些排列（非重複排序）。防爆。如果問題的領域是5個決策變量即， 1,2,3,4,5，他們可以以任何不重複的方式訂購。