Facility Location with Decision-Dependent Scenario Probabilities: Linked Lifted Cuts and a Scenario-Decomposed Branch-and-Cut

We study two-stage facility location in which the probability of each demand scenario is an affine function of the opening decisions, so the objective multiplies a decision-dependent probability by a decision-dependent recourse value and is bilinear in the binary first stage. The standard treatment linearizes these products with McCormick envelopes over global bounds on the recourse; on our instances its LP relaxation has a root gap of 6 to 10 percent. We propose a linked lifted-cut master. Writing each probability as a posiform splits every product into a factor for an open site and one for a closed site; each factor is the value of the recourse LP at a scaled right-hand side, so every dual vertex of one scenario yields a cut for all of its factors that is linear once the pairwise products of the decisions are lifted. Linking rows tie the factor epigraphs of a scenario together. The relaxation is exact at binary points and its root gap is 0.07 to 0.43 percent on the same instances. Because the linked LP decomposes by scenario with closed-form blocks, its value is computed by a stabilized multicut cutting-plane master whose cuts remain valid at every node of a branch-and-bound tree. The resulting branch-and-cut proves optimality on all 25 test instances with 25 to 50 sites and 20 scenarios, in 4 seconds to 12 minutes, while a McCormick branch-and-cut sharing the same tree code leaves seven of fifteen unproven after two to four hours and, with node-local recourse bounds, still leaves six of 25 unproven and needs several hundred times more nodes; a full MIP solver closes the McCormick gap faster than that tree but is still 1.6 to 13 times slower than the decomposed solver. A node-parallel MPI version reaches a 1.6 to 3.3 times speedup on seven workers, and a sparse-influence variant of the lifting proves instances with 500 sites in under four minutes.

Article

Download

View PDF