We improve the mixed-integer programming formulation of the multicommodity capacitated fixed-charge network design problem by incorporating valid inequalities into a cutting-plane algorithm. We use five classes of kno...
详细信息
We improve the mixed-integer programming formulation of the multicommodity capacitated fixed-charge network design problem by incorporating valid inequalities into a cutting-plane algorithm. We use five classes of known valid inequalities: the strong, cover, minimum cardinality, flow cover, and flow pack inequalities. The first class is particularly useful when a disaggregated representation of the commodities is chosen, and the last four are expressed in terms of network cut sets. We develop efficient separation and lifting procedures for these classes of inequalities. We present computational results on a large set of instances of various characteristics, allowing us to measure the impact of the different classes of valid inequalities on the quality of the lower bounds, in particular with respect to the representation of the commodities.
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...
详细信息
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.
作者：
Bernard GendronDIRO
Université de Montréal and CIRRELT C.P. 6128 succ. Centre-ville Montréal Canada H3C 3J7
networkdesign applications are prevalent in transportation and logistics. We consider the multicommodity capacitated fixed-charge network design problem (MCND), a generic model that captures three important features ...
详细信息
networkdesign applications are prevalent in transportation and logistics. We consider the multicommodity capacitated fixed-charge network design problem (MCND), a generic model that captures three important features of networkdesign applications: the interplay between investment and operational costs, the multicommodity aspect, and the presence of capacity constraints. We focus on mathematical programming approaches for the MCND and present three classes of methods that have been used to solve large-scale instances of the MCND: a cutting-plane method, a Benders decomposition algorithm, and Lagrangian relaxation approaches.
This paper describes a slope scaling heuristic for solving the multicomodity capacitatedfixed-chargenetworkdesign problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversificati...
详细信息
This paper describes a slope scaling heuristic for solving the multicomodity capacitatedfixed-chargenetworkdesign problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.
To efficiently derive bounds for large-scale instances of the capacitatedfixed-chargenetworkdesign problem, Lagrangian relaxations appear promising. This paper presents the results of comprehensive experiments aime...
详细信息
To efficiently derive bounds for large-scale instances of the capacitatedfixed-chargenetworkdesign problem, Lagrangian relaxations appear promising. This paper presents the results of comprehensive experiments aimed at calibrating and comparing bundle and subgradient methods applied to the optimization of Lagrangian duals arising from two Lagrangian relaxations. This study substantiates the fact that bundle methods appear superior to subgradient approches because they converge faster and are more robust relative to different relaxations, problem characteristics, and selection of the initial parameter values. It also demonstrates that effective lower bounds may be computed efficiently for large-scale instances of the capacitatedfixed-chargenetworkdesign problem. Indeed, in a fraction of the time required by a standard simplex approach to solve the linear programming relaxation, the methods we present attain very high-quality solutions. (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论