A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem

DOI10.1287/ijoc.1110.0468zbMath1460.90099OpenAlexW2080902665MaRDI QIDQ2815470

Andreas Klose, Simon Görtz

Publication date: 29 June 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.1110.0468

zbMATH Keywords

Lagrangean relaxationbranch and boundmixed integer programmingsubgradient optimizationcapacitated facility locationvolume algorithm

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)

Related Items (10)

You've come a long way, Bayesians ⋮ Implementing Automatic Benders Decomposition in a Modern MIP Solver ⋮ A Branch-and-Price Algorithm for the Multiple Knapsack Problem ⋮ Benders decomposition without separability: a computational study for capacitated facility location problems ⋮ Solving a dynamic facility location problem with partial closing and reopening ⋮ Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing ⋮ Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities ⋮ On the computational efficiency of subgradient methods: a case study with Lagrangian bounds ⋮ Weak flow cover inequalities for the capacitated facility location problem ⋮ A fast exact method for the capacitated facility location problem with differentiable convex production costs

Uses Software

• CPLEX
• OR-Library
• Knapsack

Cites Work

• Primal-dual subgradient methods for convex problems
• A comparison of heuristics and relaxations for the capacitated plant location problem
• A cutting plane algorithm for the capacitated facility location problem
• A branch-and-price algorithm for the capacitated facility location problem
• Approximate solutions to large scale capacitated facility location problems
• Two ``well-known properties of subgradient optimization
• The volume algorithm revisited: relation with bundle methods
• Potential function methods for approximately solving linear programming problems: theory and practice.
• The volume algorithm: Producing primal solutions with a subgradient method
• Near-optimal solutions to large-scale facility location problems
• Ergodic, primal convergence in dual subgradient schemes for convex programming
• A Lagrangian heuristic for the capacitated plant location problem with single source constraints
• Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs
• Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A regularized decomposition method for minimizing a sum of polyhedral functions
• A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network Flows
• Lagrangian Relaxation via Ballstep Subgradient Methods
• Unnamed Item

This page was built for publication: A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem