Lagrangean dual ascent algorithms for computing bounds in capacitated plant location problems (Q2640440)

The authors continue their studies of applying the Lagrangean dual ascent technique [see the first author and \textit{M. B. Rosenwein}, ibid. 43, No.2, 197-205 (1989; Zbl 0682.90066); the first author and \textit{K. Spielberg}, Methods Oper. Res. 57, 131-142 (1987; Zbl 0613.90073)], for bounding a mixed-integer programming problem. In this paper the common scheme is tailored for the capacitated plant location problem (CPLP). Dualization of linking constraints in CPLP induces a decomposition of the Lagrangean relaxed problem (strengthened by valid inequalities) into a transportation problem and a 0-1 knapsack problem. A coordination of parametric analysis between these two problems enables to realize ascent steps yielding an improved bound for CPLP in most cases. Computational experiments are reported based on some very simple ascent steps.