限制最佳化

限制最佳化 (或稱限製程式設計) 是指派的名稱，用來從眾多候選項目中識別可行解決方案，並依據任意限制來建模。許多科學和工程領域都面臨 CP 問題(「程式設計」這個詞有點失誤，類似於「電腦」原本代表「運算人員」的情況。這裡的「程式設計」是指方案的安排，而不是以電腦程式語言的程式設計。)

CP 的根據可行性 (尋找可行的解決方案) 而非最佳化 (尋找最佳解決方案)，其重點在於限制與變數，而非目標功能。事實上，CP 問題甚至並沒有客觀的功能，而目標可能是透過在問題中新增限制，把非常龐大的可能解決方案範圍縮小到更易於管理的子集。

例如員工安排員工，即為 CP 適用的問題。當公司持續營運 (例如工廠) 並為員工建立每週時間表時，就會發生問題。以下舉例簡化：某間公司每天進行 3 次輪班 8 小時轉乘，其中四名員工每天指派不同的班表，同時剩下第四名員工這一天。即便如此，可能的時間表也相當龐大：每天都有 4! = 4 * 3 * 2 * 1 = 24 名員工可能指派，所以每週還有 50 份排程。通常還會有其他限制來減少可行解決方案的數量，例如每個員工每週至少工作天數。CP 方法會追蹤您在新增限制時仍然可行的解決方案，這使得這項強大工具可以解決實際發生的大規模排程問題。

CP 在世界各地擁有蓬勃發展的社群，設有專門的科學期刊、研討會和各種不同解決方案的技術。已成功在規劃、排程和許多其他有異質限制的網域中應用 CP。

工具

Google 提供以下幾種解決 CP 問題的方法：

• CP-SAT 解題工具：採用 SAT (符合性) 方法的限製程式設計解決方案。
• 原始 CP 解題工具：路由程式庫中使用的限製程式設計解析工具。

如果您可以運用線性目標和線性限制來建模，那麼您會有線性程式設計問題，並且應考慮使用 MPSolver。不過，即使轉送問題能以線性模型表示，使用我們的車輛路由程式庫通常還是最能解決轉送問題。

示例

下一節說明 CP-SAT 解題工具，這是限製程式設計的主要 OR-Tools 解題工具。(SAT 代表「滿意度」：解題工具會使用各種技巧和 CP 方法解決 SAT 問題)。

以下列舉幾個適用於 CP-SAT 解析工具的排程問題範例：

• 員工安排工作
• 工作坊的問題

傳統的 CP 問題為「N 皇后問題」和「加密編譯謎題」。