A subgradient-based branch-and-bound algorithm for the capacitated facility location problem

By Simon Görtz and Andreas Klose
Working Papers
No. 01, March 2009

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. In order 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 more faster and robust than other state-of-the-art methods for solving the CFLP exactly.

Keywords: Mixed-integer programming; Lagrangean relaxation; Capacitated Facility Location; Subgradient optimization; Volume algorithm; Branch-and-bound

Format available: PDF (299.1 kb)