COIN-OR

维基百科,自由的百科全书
跳转至: 导航搜索
COIN-OR
80x80
创立时间 2000
网站 http://www.coin-or.org

COIN-OR作業研究(Operations Research)計算基礎架構(Computational Infrastructure)的縮寫,這是一個致力於"為公開文獻上數學理論之數學軟體而建立(create for mathematical software what the open literature is for mathematical theory)"的專案。公開文獻(例如研究期刊)提供作業研究社群文件的審查與保存。作業研究期刊上的數學理論,論文裡經常有計算案例的數值結果。產生這些數值結果所開發的軟體、模型與資料通常並未公開。這會阻礙需要重現計算結果、進行公平比較,以求精益求精的研究人員。

Linux, Apache與其他專案的成功推動軟體開發的開源模式。一群IBM研究人員提議以類似開放源碼方式"發布"軟體、模型與資料。COIN-OR被認為是在作業研究計算社群推動開放源碼的一項倡議,並提供開源軟體專案營運所需的線上資源與服務。

COIN-OR網站於2000年與喬治亞州亞特蘭大市第17屆數學程式設計國際研討會一起開張時帶有實驗性質。2007年時COIN-OR有25個專案,包括線性規劃(linear programming 如 COIN-OR CLP),非線性規劃(nonlinear programming 如 IPOPT),整數規劃(integer programming 如 CBC, Bcp 與 COIN-OR SYMPHONY), 代數建模語言(algebraic modeling languages 如 Coopr)等工具。COIN-OR由作業研究與管理科學協會(Institute for Operations Research and the Management Sciences, INFORMS)主持,並由教育性,非營利的COIN-OR基金會營運。

專案[编辑]

CLP[编辑]

CLP(COIN-OR 線性規劃)是一套以 C++ 寫的開放源碼線性規劃求解軟體。 因為採公用授權條款,所以可用於商業軟體且不受GNU通用公眾授權條款的任何影響。 雖然可以做成執行檔,CLP 主要作為程式庫使用。 它設計的像商業軟體般可靠(也許速度沒那麼快),並且能夠處理非常大型的問題。

CLP 是為解決線性規劃的問題而設計的:

求最小值 c_1 x_1 + c_2 x_2\,
  • 限制條件
a_{11} x_1 + a_{12} x_2 \le b_1
a_{21} x_1 + a_{22} x_2  \le b_2
a_{31} x_1 + a_{32} x_2  \le b_3
  • 值大於零的變數
x_1 \ge 0
x_2 \ge 0

可以有上百萬個變數跟限制條件。主要的演算法為單純形法。 CLP 也用於 COIN-OR 的其他計畫如 SYMPHONY, BCP(Branch Cut and Price), CBC (COIN-OR Branch and Cut)等。

CBC[编辑]

CBC(COIN-OR beanch and cut)是一套以 C++ 寫的開放源碼混合整數規劃求解軟體。 可獨立執行或作為程式庫(由AMPL[原生支援], GAMS[利用 COIN-OR 最佳化服務(Optimization Services, OS)以及 GAMSlinks 專案], MPL[藉由 CoinMP 專案], AIMMS[藉由 AIMMSlinks 專案], 或 PuLP 呼叫使用)

SYMPHONY[编辑]

SYMPHONY(單工或多工最佳化網路求解)是一套在異質網路上求解混合整數規劃(MIPs), 開放源碼之分枝切面法(branch and cut)框架-並且可以使用 CLP, CPLEX, XPRESS 或其他線性規劃求解軟體求解線性問題。

SYMPHONY 是一套同時實作循序(sequential)及平行(parallel)處理分枝切面與定價(branch, cut, and price)以求解 MILPs 的程式庫。 分枝切面與定價法類似分支界限法(branch and bound),但還包括切面法(Cutting-plane methods)與定價(pricing)演算法。 藉由提供特定的副程式以讀取自訂資料檔、生成特定切割平面或應用自訂分枝規則,使用者可以任意自訂客制化的分枝與切面演算法。 演算法大部分的元件,如搜尋樹管理、線性規劃方案管理、切割池(cut pool)管理、通訊管理都含在程式庫內,使用者無須操心。 執行程式可以有各種配置方式,從循序執行到有獨立的切割產生器(cur generators)、切割池與線性規劃求解之完全平行處理。 目前分散式版本可在任何 PVM 支援的環境執行。相同的程式碼也可用任何 OpenMP 相容的編譯器編譯為共享記憶體架構。

PuLP[编辑]

PuLP 是一套以 Python 寫的線性規劃建模軟體。可以產生 MPS 或 LP 檔案並呼叫 GLPK, CLP/CBC, CPLEX 以及 Gurobi 求解。