Lagrangean Relaxation Applied to Capacitated Facility Location Problems

Abstract

Abstract Lagrangean relaxation, a technique of quite general applicability, is studied in the particular context of the capacitated facility location problem with arbitrary additional constraints. For this class of problems we are able to obtain a reasonably complete algebraic and geometric understanding of how and why Lagrangean relaxation works. Extensive computational results are also reported. Although this work finds immediate application to improved computational procedures for the class of problems studied, our longer term aim is to encourage similar in-depth studies of Lagrangean relaxation for other important classes of problems.