Solving capacitated facility location problems by Fenchel cutting planes

In this paper, we apply the Fenchel cutting planes methodology to Capacitated Facility Location problems. We select a suitable knapsack structure from which depth cuts can be obtained. Moreover, we simultaneously obtain a primal heuristic solution. The lower and upper bounds achieved by our procedure are compared with those provided by Lagrangean relaxation of the demand constraints. As the computational results show, the Fenchel cutting planes methodology outperforms the Lagrangean one, both in the obtaining of the bounds and in the effectiveness of the branch and bound algorithm using each relaxation as the initial formulation.