The Capacitated Facility Location Problem is to locate a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of clients. The Single Source version (SingleCFLP) of the problem has the additional requirement that each client must be assigned to a single facility. In this paper a reformulation of the problem based on Dicut Inequalities is proposed. Based on the observation that Dicut Inequalities are that are knapsack inequalities, an exact knapsack separation procedure is used to derive cutting planes from the inequalities which are valid for the Dicut Polytope. The separation procedure for Dicut inequalities has been embedded into a Branch-and-Cut framework and a computational experience is reported on a wide set of benchmark instances.
A computational study of dicut reformulation for the Single Source Capacitated Facility Location problem
AVELLA, Pasquale;BOCCIA, Maurizio;SALERNO, Saverio
2012-01-01
Abstract
The Capacitated Facility Location Problem is to locate a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of clients. The Single Source version (SingleCFLP) of the problem has the additional requirement that each client must be assigned to a single facility. In this paper a reformulation of the problem based on Dicut Inequalities is proposed. Based on the observation that Dicut Inequalities are that are knapsack inequalities, an exact knapsack separation procedure is used to derive cutting planes from the inequalities which are valid for the Dicut Polytope. The separation procedure for Dicut inequalities has been embedded into a Branch-and-Cut framework and a computational experience is reported on a wide set of benchmark instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
