New facets for the two-stage uncapacitated facility location polytope

The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots. In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted fans, is tested with success.