作者：中科院數學與系統科學研究院優化與應用研究中心

轉載自柚子優化：中科院CMIP混合整數規劃求解器正式發布歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。

敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：『運籌OR帷幄』大數據人工智慧時代的運籌學

本文已發佈於微信公眾號『運籌OR帷幄』：【資訊】中科院CMIP混合整數規劃求解器正式發布

小編推薦：著名陳省身數學獎獲得者、馮康科學計算獎獲得者、中國科學院數學與系統科學院戴彧虹研究員帶領CMIP團隊從2015年開始，歷經30個月，終於自主研發了我國第一個具有國際水平的整數規劃求解器CMIP，並於2018年3月確定版本為CMIP 1.0版本。

混合整數規劃（以下簡稱整數規劃）在工業、經濟、國防、醫療等各行各業應用十分廣泛。另一方面，整數規划具有建模通用性強和全局解可驗證的優點，因此受到優化理論與應用界的長期重視，尤其是美國、德國、俄羅斯、英國等發達國家。根據美國NEOS（帶有64個求解器的）優化平臺發布的數據，2016年用戶共遞交了1,040,764個優化問題，其中超過三分之二的問題（696,160個）是整數規劃問題。

最早的整數規劃研究可追溯至上個世紀五十年代。1954年，線性規劃之父喬治·丹齊格（George Dantzig）教授、網路流優化專家Fulkerson、Johnson開始對旅行商問題進行研究，建立了整數規劃模型，並通過手動計算，求解了49個城市的旅行商問題，引起了巨大的轟動。從此之後，整數規劃得到了蓬勃發展。早期的整數規劃求解器開發始於二十世紀七十年代，有FMPS、UMPIRE、MPSX、MPS III、APEX、MPSX/370等。

然而，由於整數規劃問題本身固有的NP困難性，實際應用中常常需要使用各式各樣的技巧去求解不同的整數規劃問題。因此，成熟的整數規劃求解器需要擁有處理多種整數規劃問題的能力，這就導致整數規劃求解器的開發極其困難。目前，僅有少數幾個發達國家擁有自己的整數規劃求解器，如美國有GUROBI、CPLEX、SAS、MATLAB、CBC、SYMPHONY，德國有SCIP，俄羅斯有MIPCL和GLPK，英國有XPRESS（後被美國FICO公司收購），芬蘭有LPSOLVE。

以下是國際上成熟整數規劃求解器的簡單介紹！

在美國斯坦福大學葉蔭宇講座教授、中國科學院袁亞湘院士等各方大力鼓勵與支持下，著名陳省身數學獎獲得者、馮康科學計算獎獲得者、中國科學院數學與系統科學院戴彧虹研究員帶領CMIP團隊從2015年開始，歷經30個月，終於自主研發了我國第一個具有國際水平的整數規劃求解器CMIP，並於2018年3月確定版本為CMIP 1.0版本。CMIP代碼總量已經超過五萬行，涵蓋國際現有求解器預處理、啟發式、割平面、分支、節點選擇、區域傳播等各種功能模塊，並已經較好地具備了求解大規模整數規劃的能力。例如對於MIPLIB2010測試庫中具有164547個變數、328818個約束的例子MAP18，CMIP僅需847秒可求得全局最優解。

CMIP整數規劃求解器採用了一種廣義係數縮緊割平面(GCSC)的技術。該割平面技術由CMIP團隊自主提出，對於一般的整數規劃問題具有一定的改善效果，尤其對於網路設計問題效果顯著。通過MIPLIB2010國際公認標準整數規劃測試庫的測試對比，CMIP求解器的性能已經超過傳統的求解器GLPK（俄國2000，Google Optimization Tools中的整數規劃求解器）以及LPSOLVE（芬蘭2004，GAMS高級建模系統調用其解決整數規劃問題）。

CMIP團隊數年以來，同時努力致力於解決來自各行各業的一些整數規劃等難題，例如電力調度問題、天然氣輸運問題、物流道口分佈問題、石油混流優化問題等，並得到了中國電科院、中石油管科中心、菜鳥物流公司、北京時林公司等需求方的好評。

如果您有整數規劃理論、演算法和應用方面的任何問題，歡迎通過郵箱[email protected]隨時與CMIP團隊進行聯繫，也歡迎大家發送整數規劃問題算例試算（目前要求數據輸入文件為LP格式或MPS格式）。

CMIP整數規劃求解器的開發依託於中國科學院數學與系統科學研究院「優化與應用研究中心」。目前，袁亞湘院院士為研究中心名譽主任，戴彧虹研究員擔任主任，郭田德研究員擔任副主任，學術委員會主任是美國斯坦福大學葉蔭宇教授。該研究中心旨在促進優化理論、計算與應用研究與融合，經過若干年的努力，建設成為面向科學發展前沿、面向國家建設和社會發展需要、在國際上有影響的優化與應用的學術研究、人才培養及學術交流中心。

國際整數規劃的研究雖然已經長達六十年之久，但在其理論、演算法和應用方面依然存在大量並不斷出現特別具有挑戰性的難題。真誠歡迎有志者們加盟CMIP團隊，共同探討整數規劃的奧妙。

---

推薦閱讀：