使用有效不等式求解Maximum Betweenness问题  

Valid Inequalities for Solving Maximum Betweenness Problem

作　　者：王启明[1] 许世明[2] 马峰[2] 乔文孝[2] 

机构地区：[1]中国人民解放军72671部队 [2]解放军理工大学通信工程学院

出　　处：《军事通信技术》2014年第2期62-66,共5页Journal of Military Communications Technology

基　　金：国家自然科学基金资助项目(70971136)

摘　　要：文章主要研究了对maximum betweenness问题的建模与优化。基于Savic提出的混合整数规划模型,通过加入有效不等式使改进后的模型在线性松弛之后更接近原问题整数可行解的凸包。在CPLEX平台下的算法数值试验表明改进后的模型求解速度比原模型的求解速度更快。The binary mixed integer linear programming formulation and optimization for the maximum betweenness problem was discussed. Based on Savic et al. ＇s work to solve maximum betweenness problem, some valid inequalities were proposed to strengthen linear programming relaxations of Savi6 et al. ＇s model. Experimental results on the CPLEX solver demonstrate that the modified model can solve the problem faster.

关 键 词：运筹学 最大中间值 混合整数规划 有效不等式 

分 类 号：O221.4[理学—运筹学与控制论]