Stochastic Facility Location Model

I am solving a stochastic facility location model using Benders decomposition (L-shaped algorithm). In each scenario, I want to allocate demands from origin to a fixed number of closest open facilities. For example, I have about 70 candidate facilities and about 370 demand locations (census blocks). I want to make sure in each scenario demand will be allocated to the closest 30 facilities from each demand location to ensure that people do not have to travel too far. If you worked on any similar problem, Would you share how you construct your constraints?

• Can you provide more details of your problem? What are the input parameters? What is the source of uncertainty? E.g. is the opening cost of the facility uncertain? Or the distance of the candidates to the facility? Or the actual set of candidates? Does each candidate have unit-demand, or can the demand be more than 1 and each facility has limited capacity? Sep 13, 2021 at 18:34
• Inputs are demand, capacity, cost between demand and facility locations, cost of opening and operating facility, and cost of unmet demand. Only demand and capacity are uncertain. The output is the amount of demand allocated to the open facility from each demand location and the amount of unmet demand at each demand location for each scenario.
– mars
Sep 16, 2021 at 13:30
• @JorisKinable I added the deterministic equivalent formulation to my post!
– mars
Sep 16, 2021 at 14:29

To impose the distance restriction, use a sparse index set of $$(i,j)$$ pairs rather than the full Cartesian product $$I \times J$$.
Also, you might consider omitting constraint $$(2)$$, which will naturally be satisfied unless the penalty for unmet demand is too small to encourage opening any facilities, and constraint $$(5)$$, which is logically implied by $$(3)$$ and $$(4)$$. It is possible for these unnecessary constraints to tighten the formulation, but it is also likely that their inclusion would just artificially inflate the problem size, making the underlying LP solves slower.
• I think you might not have understood that I mean to keep only those $(i,j)$ pairs for which $j$ is one of the 30 closest facility facilities to demand location $i$. That way, you implicitly enforce the rule without needing an explicit constraint. Sep 17, 2021 at 1:27