期刊
EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION
卷 2, 期 1-2, 页码 55-75出版社
ELSEVIER
DOI: 10.1007/s13675-014-0020-9
关键词
Multicommodity capacitated fixed-charge network design; Column generation; Branch-and-price-and-cut
资金
- Natural Sciences and Engineering Council of Canada (NSERC)
We present a branch-and-price-and-cut algorithm for solving large-scale instances of the multicommodity capacitated fixed-charge network design problem. We assume good feasible solutions are already known and we focus on an efficient algorithm for proving the optimality of the solutions. The restricted master problem solved at each column generation iteration is obtained directly from the compact arcbased model by considering only a subset of the commodity flow variables. The pricing subproblem corresponds to a Lagrangian relaxation of the flow conservation and capacity constraints, leaving in the Lagrangian subproblem only the strong inequalities. The column generation procedure is completed by a cut generation step based on strong inequalities. The resulting column-and-row generation procedure is embedded within an enumerative scheme. Computational experiments on a large set of randomly generated instances are presented and analyzed.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据