限制最佳化

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

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

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

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

工具

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

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

示例

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

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

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