两阶段特殊结构混合0-1规划的分解算法

A Decomposition Method for Solving Two-Stage Mixed 0-1 Programming with Special Structure

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现。该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性。实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高。算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解。

This paper introduces a primal-dual decomposition method to solve two-stage mixed 0-1 programming problems with a special structure. After deduction and discussion about the algorithm, it＇ s implemented with CPLEX 9.0. The new method divides the original problem into two simple subproblems and has a more balanced structure and rapid convergence speed than traditional decomposition methods. Computational tests show that our approach has higher time efficiency than branch-and-cut algorithm supplied by CPLEX in solving large-scale twostage mixed 0-1 programming problems with higher density and coupling ratio. After heuristic method with 0-1 variables fixed is applied, near-optimal solutions can be obtained.