Bundle-based relaxation methods for multicommodity capacitated fixed charge network design

DOI10.1016/S0166-218X(00)00310-3zbMath1026.90010OpenAlexW2127635925WikidataQ118165520 ScholiaQ118165520MaRDI QIDQ5946817

Antonio Frangioni, Teodor Gabriel Crainic, Bernard Gendron

Publication date: 30 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00310-3

zbMATH Keywords

Lagrangian relaxationBundle methodsCapacitaded fixed-charge networksNetwork designSubgradient methods

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (75)

A genetic algorithm based on relaxation induced neighborhood search in a local branching framework for capacitated multicommodity network design ⋮ The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design ⋮ A capacity scaling heuristic for the multicommodity capacitated network design problem ⋮ A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm ⋮ An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: application to the MDPVRP ⋮ Improved branching disjunctions for branch-and-bound: an analytic center approach ⋮ A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem ⋮ An enhanced dynamic slope scaling procedure with tabu scheme for fixed charge network flow problems ⋮ Minimum-Cost Network Design with (Dis)economies of Scale ⋮ Prim-based support-graph preconditioners for min-cost flow problems ⋮ Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks ⋮ A continuous bi-level model for the expansion of highway networks ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ Model-based automatic neighborhood design by unsupervised learning ⋮ A comparison of formulations and relaxations for cross-dock door assignment problems ⋮ A cutting plane algorithm for the capacitated connected facility location problem ⋮ A hub location problem with fully interconnected backbone and access networks ⋮ A stabilized structured Dantzig-Wolfe decomposition method ⋮ Cyclic preference scheduling of nurses using a Lagrangian-based heuristic ⋮ New partial aggregations for multicommodity network flow problems: an application to the fixed-charge network design problem ⋮ The transit time constrained fixed charge multi-commodity network design problem ⋮ Revisiting Lagrangian relaxation for network design ⋮ A method for convex minimization based on translated first-order approximations ⋮ Mathematical formulations for multi-period network design with modular capacity adjustments ⋮ Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods ⋮ Alternating Lagrangian decomposition for integrated airline crew scheduling problem ⋮ An exact algorithm for the service network design problem with hub capacity constraints ⋮ Avoiding unnecessary demerging and remerging of multi‐commodity integer flows ⋮ Scalable timing-aware network design via Lagrangian decomposition ⋮ Consensus-based Dantzig-Wolfe decomposition ⋮ On the computational efficiency of subgradient methods: a case study with Lagrangian bounds ⋮ Fixed charge multicommodity network design using \(p\)-partition facets ⋮ A Combined Matheuristic for the Piecewise Linear Multicommodity Network Flow Problem ⋮ Incremental Bundle Methods using Upper Models ⋮ Benders, metric and cutset inequalities for multicommodity capacitated network design ⋮ A class of Dantzig-Wolfe type decomposition methods for variational inequality problems ⋮ An interior-point Benders based branch-and-cut algorithm for mixed integer programs ⋮ A three-phase heuristic algorithm for fixed-charge capacitated material flow network design with input/output points location ⋮ The Benders Dual Decomposition Method ⋮ Service network design models for two-tier city logistics ⋮ Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design ⋮ A hybrid algorithm for large-scale service network design considering a heterogeneous fleet ⋮ Accelerating the Benders Decomposition Method: Application to Stochastic Network Design Problems ⋮ On the minimum cost multiple-source unsplittable flow problem ⋮ MIP Neighborhood Search Heuristics for a Capacitated Fixed-Charge Network Design Problem ⋮ Metric inequalities and the network loading problem ⋮ A Lagrangian relaxation approach for expansion of a highway network ⋮ Multi-commodity variable upper bound flow models ⋮ Bundle methods for sum-functions with ``easy components: applications to multicommodity network design ⋮ Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design ⋮ Efficient metaheuristics to solve the intermodal terminal location problem ⋮ A first multilevel cooperative algorithm for capacitated multicommodity network design ⋮ A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem ⋮ Bundle-based relaxation methods for multicommodity capacitated fixed charge network design ⋮ Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design ⋮ Linear programming and Lagrangian relaxation heuristics for designing a material flow network on a block layout ⋮ Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints ⋮ Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design ⋮ Reconstructing (0,1)-matrices from projections using integer programming ⋮ A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints ⋮ Solving network design problems via iterative aggregation ⋮ Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité ⋮ 0-1 reformulations of the multicommodity capacitated network design problem ⋮ Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design ⋮ Benders Decomposition for Capacitated Network Design ⋮ A local branching heuristic for the capacitated fixed-charge network design problem ⋮ Directed fixed charge multicommodity network design: a cutting plane approach using polar duality ⋮ Service network design in freight transportation ⋮ Planning models for long-haul operations of postal and express shipment companies ⋮ Memetic algorithms ⋮ COLE: a new heuristic approach for fixed charge problem computational results ⋮ New approaches for optimizing over the semimetric polytope ⋮ A note on ``A dual-ascent approach to the fixed-charge capacitated network design problem ⋮ About Lagrangian methods in integer optimization ⋮ Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Models for planning capacity expansion in local access telecommunication networks
• Topological design of telecommunication networks --- local access design methods
• Conditional subgradient optimization -- theory and applications
• On improvements to the analytic center cutting plane method
• Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
• Solving semidefinite quadratic problems within nonsmooth optimization algorithms
• The Cutting-Plane Method for Solving Convex Programs
• A generalization of Polyak's convergence result for subgradient optimization
• Networks synthesis and optimum network design problems: Models, solution methods and applications
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
• A Simplex-Based Tabu Search Method for Capacitated Network Design
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• Validation of subgradient optimization
• Generalized Bundle Methods
• Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems
• Modeling and Solving the Two-Facility Capacitated Network Loading Problem
• Minimization of unsmooth functionals
• Capacitated Network Design—Polyhedral Structure and Computation
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design

This page was built for publication: Bundle-based relaxation methods for multicommodity capacitated fixed charge network design