3
$\begingroup$

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?

Deterministic Equivalent Problem

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – Joris Kinable
    Sep 13, 2021 at 18:34
  • $\begingroup$ 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. $\endgroup$
    – mars
    Sep 16, 2021 at 13:30
  • $\begingroup$ @JorisKinable I added the deterministic equivalent formulation to my post! $\endgroup$
    – mars
    Sep 16, 2021 at 14:29

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The removal of constraints makes sense. Thanks so much for the input. I used a cartesian product for I and J in the description but in my solver I see have (i,j) I will fix that in the description. I am still trying to figure out how to add a constraint that will allow demand to be allocated to only a set number of closest facilities. $\endgroup$
    – mars
    Sep 17, 2021 at 1:00
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Sep 17, 2021 at 1:27
  • $\begingroup$ I got it now. I was trying to add a. constraint so that I can just change the constraint for other distance thresholds. But instead of adding a constraint, using a subset of the data with (i,j) pair with a set distnace makes it easier to solve. Thanks so much! $\endgroup$
    – mars
    Sep 17, 2021 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.