Solving the problem of locating single-source capacitated plants in two stages by means of Fenchel cutting plans

Abstract

In the present study, we applied the Fenchel cutting plans methodology to solve the problem of Locating Single-Source Capacitated Plants in two stages (TSCFL). Fenchel inequalities describe the convex envelope of an X⊂R^n set without explicitly knowing the structure. Fenchel relaxation is a linear relaxation obtained by adding the most violated Fenchel inequalities obtained as a solution to the separation problem associated with the primal problem. The value of the Fenchel relaxation constitutes a strong lower dimension for the localization problem. Simultaneously, a heuristic based on the Fenchel relaxation is applied to obtain a feasible solution which constitutes a higher dimension. Both dimensions are integrated to the Ramification and Dimensioning algorithm based on linear programming to obtain the overall optimum. Likewise, Fenchel cuts present efficient computational properties.