Lagrangean relaxation and constraint generation procedures for capacitated plant location problems with single sourcing

Constraint generation procedures for identifying facet-induced inequalities violated by the optimal solution to the current LP relaxation have been widely used to solve integer programming problems. For capacitated plant location problems, Barcelo has recently tested computationally the performance of one such procedure. Hallefjord and Jörnsten have shown how these procedures can lead to better bounds when used with Lagrangean relaxations instead of the classical LP ones. The authors describe a Lagrangean relaxation heuristic algorithm for the capacitated location problem that in each iteration expands the dual space by adding to the dual Lagrangean function a new valid inequality for the problem generated from the current partial solution. Examples and computational results are included.