A heuristic lagrangean algorithm for the capacitated plant location problem (Q797475): Difference between revisions

This paper considers the capacitated plant location problem with non- splitting constraints. The model chosen is a pure 0-1 programming problem. The authors first relax the requirements constraints, and the Lagrangean subproblems decompose into a plant selection problem and an assignment problem. Based on analysis of optimal LP multipliers and reduced costs, a first stage heuristic proceeds with the plant selection, and this is followed by an interchange heuristic (only if needed). Then an assignment of plants to customers must be made, and this again is done in two stages, the first one a direct assignment phase, the second one a reassignment phase which is performed only if the first assignment violates the capacity of some currently open plant. Finally a complementary interchange heuristic is proposed to reduce the duality gap if any. The authors report good results, but give no computational evidence to that effect. The referencing is inadequate. For example, the quantities \({}_ j(u^ k)\) which play a central role in this paper were defined (as gain functions) in two papers of \textit{K. Spielberg} [Oper. Res. 17, 85-111 (1969; Zbl 0165.541); Manage. Sci. (1969)]. Also dual ascent methods for SPLP [see \textit{O. Bilde} and \textit{J. Krarup}, ''Computation of the optimal location of production sites'', IMSOR Res. Rep. (1967), and \textit{D. Erlenkotter}, Oper. Res. 26, 992-1009 (1978; Zbl 0422.90053)] and for CPLP [the reviewer and \textit{K. Spielberg}, Math. Program. 17, 198-228 (1979; Zbl 0416.90052)] which solve problems quite similar to what the authors treat are not mentioned.