我需要解決一個工作情感問題，我想找到最好的高效算法來解決這個問題。哪個算法可以解決這個約束規劃問題？
假設有一些工人可以完成幾種任務。我們也有每週必須完成的一系列任務。每項任務都需要一些時間。每個任務都必須由某人來完成。每名工作人員必須每週工作N到P小時。
這個問題的第一部分似乎是約束規劃算法的一個很好的候選者。
但是，這是複雜的：因爲工人可以做不同的任務，他們也可能有偏好（或願望）。如果一個人想滿足所有人的願望，那麼這個問題就沒有解決辦法（太多的限制）。
所以我需要一個算法來解決這個問題。如果完美的車輪已經存在，我不想重新發明車輪。
該算法必須公平（如果可以定義這個詞），例如我應該能夠添加一個約束，如「試圖滿足每個人至少一個願望」。我不確定這個問題可以通過這裏描述的約束層次結構方法來解決：Constraint Herarchies。事實上，我不確定「公平」和願望可以通過對這類算法的有效約束來表達。
有沒有一個約束編程專家給我一些建議？我是否需要用一些啓發式方法開發新車輪，而不是使用高效的CP算法？
謝謝！
您的問題很複雜，一般的解決方案可能需要制定一個linear-integer問題。另一方面，如果您可以放鬆某些要求，則可以使用更簡單的方法。例如，bipartite matching將允許您安排多個工作人員進行多項工作，甚至可以處理偏好，但無法執行一般的「公平性」約束。見例如這related SO question。 Vertex colouring具有強制執行作業分離約束的高效算法。
其他海報已提及simplex和job shop scheduling。 Simplex是一種優化算法 - 它遍歷一個尋求最大化某些目標函數的解決方案空間。制定目標函數當然可以完成，但不是微不足道的。經典的作業車間調度，如雙向匹配，可以模擬問題的某些方面，但不是全部。例如，沒有優先約束。有擴展版本可以處理一些限制，例如在任務上放置時間限制。
如果您對現有的實現感興趣，Python networkx庫的實現爲this matching algorithm。可能感興趣的開源時間表程序的一個例子是Tablix。
這聽起來像是job shop scheduling。
我已經完成了時間表，這可以被認爲是一種約束規劃的形式。您有嚴格的（不可侵犯的）約束和軟約束（如間隔首選項）。
線性整數規劃通常在超過30個變量後變得毫無用處，這也可以說是單純形。
這是針對找到解決方案的啓發式算法的特定領域優化。
使用了啓發式算法是simmulated annealing，genetic algorithms，metaheuristic算法和類似，但最終的最好的結果是由一個「智能」域中提供定製greedy search算法。
基本上，你可能會得到一些體面的結果，其中一種啓發式方法在這裏，但主要問題是能夠識別問題是否過度約束。
研究的一個很好的開源工具是HeuristicLab。
我同意這裏提出的建議。然而，由於商業代碼（Xpress，Cplex，Gurobi）或開源（Coin-Or/Cbc），現在幾乎解決了非常大的MIP（混合整數編程問題）（遠遠超過30個變量！此外，諸如OPL Studio，GAMS，AMPL，Flop等花哨的建模語言允許輕鬆編寫數學模型而不是使用API。
您可以利用NEOS服務器（http://neos.mcs.anl.gov/neos/solvers/index.html）嘗試使用非常不同的可用MIP。您以AMPL格式發送模型。雖然AMPL是免費的有限版本，但NEOS可以處理無限的實例。
對於CP（COMET/OPL Studio）和本地搜索（COMET），也存在建模語言。
隨時通過我的網站www.rostudel.com（「接觸」頁）
大衛
取得聯繫我