New facets for the two-stage uncapacitated facility location polytope (Q2655408): Difference between revisions

The paper deals with special characteristics of the convex hull, which is induced by integer solutions of the two-stage uncapacitated facility location problem. The two stage uncapacitated facility location problem differs from the well-known uncapacitated facility location problem in the primary source location (plant) determination. While only one plant with fixed location is considered in the original uncapacitated facility location problem, in the two stage problem there is given a set of possible plant locations and their resulting number and locations are to be determined as well as the number and locations of co-called depots. When the two-stage uncapacitated facility location problem is solved using e.g. branch and bound technique employing the objective function value of LP-relaxation as a lower bound, the necessity of gap diminishing emerges. One way, how to master this task, is to append some specific constraints to the LP-relaxation of the two-stage uncapacitated facility location problem to cut off some portion of non-integer solutions of the associated polytope. The authors focused on analysis and construction of the specific constraints called facet cuts. They reformulated the two-stage uncapacitated facility location problem to a set packing problem and then they rearranged the problem of facet cut detection to a problem of finding a special sub-graph. They proved that each clique in the induced graph is a facet cut and then they found several other sub-graphs (odd chordless cycle and so-called fan), which corresponds with facet cuts under some assumptions. The paper is concluded by series of numerical experiments, where the authors demonstrate usefulness of the derived facet constrains in a process of the two-stage uncapacitated facility location problem solving. They were successful in considerable reducing both the gap and the computational time of the solving process.