A Review on the Fenchel Cutting Plane Approach to Capacitated Facility Location Problem

Abstract

The capacitated facility location problem (CFL) is one of the extensively researched challenging problems in combinatorial optimization. CFL consists of deciding which facilities to operate among a set of available locations and how to allocate customers to these opened facilities. Fenchel cuts are a class of cutting planes that solve the separation problem directly with a clear understanding of the polyhedral structure. In this paper, the Fenchel cutting plane method has been used to justify the capacitated facility location problems. A suitable knapsack structure has been chosen to obtain deep cuts using Fenchel cuts. Moreover, a simple heuristic solution is obtained. The comparison of the lower and upper bounds acquired from this method to those subjected to Lagrangian relaxation applied to the demand constraints is reviewed. Specifically, it displayed that the Fenchel cutting planes approach performs better than the Lagrangian one, to obtain bounds and effectiveness when included in a branch or bound algorithm, commencing each relaxation.