A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem
Authors:
- 1 November 2012
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 24 (4) , 597-610
Abstract
This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much faster and more robust than other state-of-the-art methods for solving the CFLP exactly.Keywords
This publication has 23 references indexed in Scilit:
- A cutting plane algorithm for the capacitated facility location problemComputational Optimization and Applications, 2007
- Primal-dual subgradient methods for convex problemsMathematical Programming, 2007
- Two “well-known” properties of subgradient optimizationMathematical Programming, 2007
- The volume algorithm revisited: relation with bundle methodsMathematical Programming, 2002
- The volume algorithm: producing primal solutions with a subgradient methodMathematical Programming, 2000
- Ergodic, primal convergence in dual subgradient schemes for convex programmingMathematical Programming, 1999
- A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network FlowsOptimization, 1997
- Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programsOperations Research Letters, 1996
- A Lagrangian heuristic for the capacitated plant location problem with single source constraintsEuropean Journal of Operational Research, 1993
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990