中科院CMIP混合整数规划求解器正式发布
2018/4/5 中国科学院数学与系统科学研究院
小编推荐：著名陈省身数学奖获得者、冯康科学计算奖获得者、中国科学院数学与系统科学院戴彧虹研究员带领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求解器基本功能模块图
CMIP整数规划求解器采用了一种广义系数缩紧割平面(GCSC)的技术。该割平面技术由CMIP团队自主提出，对于一般的整数规划问题具有一定的改善效果，尤其对于网络设计问题效果显著。通过MIPLIB2010国际公认标准整数规划测试库的测试对比，CMIP求解器的性能已经超过传统的求解器GLPK(俄国2000，Google Optimization Tools中的整数规划求解器)以及LPSOLVE(芬兰2004，GAMS高级建模系统调用其解决整数规划问题)。
开源整数规划求解器时间性能对比图
CMIP团队数年以来，同时努力致力于解决来自各行各业的一些整数规划等难题，例如电力调度问题、天然气输运问题、物流道口分布问题、石油混流优化问题等，并得到了中国电科院、中石油管科中心、菜鸟物流公司、北京时林公司等需求方的好评。
如果您有整数规划理论、算法和应用方面的任何问题，欢迎通过邮箱cmip@amss.ac.cn随时与CMIP团队进行联系，也欢迎大家发送整数规划问题算例试算(目前要求数据输入文件为LP格式或MPS格式)。
CMIP整数规划求解器的开发依托于中国科学院数学与系统科学研究院“优化与应用研究中心”。目前，袁亚湘院院士为研究中心名誉主任，戴彧虹研究员担任主任，郭田德研究员担任副主任，学术委员会主任是美国斯坦福大学叶荫宇教授。该研究中心旨在促进优化理论、计算与应用研究与融合，经过若干年的努力，建设成为面向科学发展前沿、面向国家建设和社会发展需要、在国际上有影响的优化与应用的学术研究、人才培养及学术交流中心。
国际整数规划的研究虽然已经长达六十年之久，但在其理论、算法和应用方面依然存在大量并不断出现特别具有挑战性的难题。真诚欢迎有志者们加盟CMIP团队，共同探讨整数规划的奥妙。
CMIP团队成员照片
谢谢阅读
本文供稿：中科院数学与系统科学研究院优化与应用研究中心
转自：柚子优化
中国科学院数学与系统科学研究院
微信号：cas-amss
长按二维码—识别—关注
投稿或法律相关事宜请通过邮件联系我们
邮箱：amss01@amss.ac.cn
http://weixin.100md.com
返回 中国科学院数学与系统科学研究院 返回首页 返回百拇医药