两阶段特殊结构混合0-1规划的分解算法
A Decomposition Method for Solving Two-Stage Mixed 0-1 Programming with Special Structure作者机构:清华大学经济管理学院北京100084
出 版 物:《运筹与管理》 (Operations Research and Management Science)
年 卷 期:2009年第18卷第4期
页 面:1-6页
学科分类:12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学]
主 题:混合0-1规划 分解算法 原始-对偶分解 CPLEX 9.0 分枝剪枝法
摘 要:本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现。该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性。实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高。算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解。