Computational results from a new Lagrangian relaxation algorithm for the capacitated plant location problem

In this paper the authors present an algorithm for the capacitated plant location problem based on a reformulation obtained by the introduction of auxiliary variables. By relaxation of the coupling constraints two separate subproblems are obtained. This is the basis for the so called ‘variable splitting’ approach. The authors present a complete algorithmic procedure including solution procedures for subproblems, heuristics for the generation of feasible solutions and suggestion for branching rules. They also present numerical results for capacitated plant location problems of the size m×n where m∈[10,20], n∈[20,50].