COMPUTATIONAL RESULTS FROM A NEW LAGRANGEAN RELAXATION ALGORITHM FOR THE CAPACITATED PLANT LOCATION PROBLEM

In this paper we present an algorithm for the capacitated plant location problem based on a reformulation obtained by 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. We present a complete algorithmic procedure including solution procedures for subproblems, heuristics for the generation of feasible solutions and suggestion for branching rules. We also present numerical results for capacitated plant location problems of the size m X n where m element-of [10,20], n element-of [20,50].