3
$\begingroup$

I am new to the field of stochastic programming and saw that the general formulation of a two-stage stochastic programming problem is given by: $$\min_{x\in X}\{ g(x)= f(x) + E_{\xi}[Q(x,\xi)]\}$$

where $\xi$ is the realization of uncertain data. Techniques such as Benders' Decomposition can be applied to solve these problems. However, I did not come across examples where $\xi$ is dependent on our decision in the first stage $x$, i.e. we would deal with $\xi(x)$. Can the same solution methods be applied for such cases and if not, what are standard approaches to solve such decision dependent scenarios?

$\endgroup$
1
  • $\begingroup$ I just a found a paper dealing with this type of problem: Albina Galiullina, Nevin Mutlu, Joris Kinable, Tom Van Woensel (2024) Demand Steering in a Last-Mile Delivery Problem with Home and Pickup Point Delivery Options. Transportation Science 0(0). doi.org/10.1287/trsc.2023.0287 $\endgroup$
    – PeterD
    Jan 23 at 14:22

1 Answer 1

4
$\begingroup$

Stochastic programming with decision dependent uncertainty is far less a beaten track than stochastic programming with fully exogenous uncertainty.

A short, not well thought through, answer to your question would be: No, you cannot apply Benders (L-shaped method) to such problems directly, at least not in all cases.

A hopefully more useful answer would be to study the specific problem at hand. Particularly, how does your decision $x$ influence $\xi$? Is your $\xi$ continuous or discrete? (probably the latter since you say scenarios). There are at least two ways in which $x$ can influence $\xi$. It can influence the timing when $\xi$ is revealed (probably not your case), see for example this article. Or it can influence the distribution function or support of your $\xi$ (probably your case, I guess). In the latter case, one can still distinguish a couple of cases:

  • A. Where you can obtain infinitely many different distributions of $\xi$ as a result of $x$
  • B. Where you can obtain finitely many distributions

For class B. see this article and, particularly, this article. Both are presented for a multistage setting, but can equally well describe your case (after all you have a multistage problem with only two stages). You will probably see that in case B. you might be able to use Benders though within a broader scheme (e.g., you might have to solve several stochastic programs). In case A. things are a bit more involved and I am not sure there is much out there.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer! Indeed, my $\xi$ is discrete and there is a finite amount of distributions, but still potentially exponentially many. $\endgroup$
    – PeterD
    Aug 2, 2022 at 11:24

Your Answer

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

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