0
$\begingroup$

Assume an inventory stochastic optimization problem in the following form:

$$\min\limits_{x\in X} c^\top x + \mathbb{E}_{\mathbb{\xi}}[\mathcal{Q}(x, \xi)]$$

Demand is the uncertain parameter, and is realised throughout the horizon. Historical demand data is used as scenarios for a sample average approximation in the second stage. I am solving the problem using a rolling horizon approach. My question is:

Can I derive a lower bound for the stochastic two-stage problem by solving the problem with one scenario only, where that scenario is the future realized demand?

$\endgroup$
1
  • $\begingroup$ There's robust optimization model where a scenario is selected as worst case or sometimes best case and solved to ensure solution remain feasible in all scenarios. $\endgroup$ Jul 21, 2023 at 2:49

2 Answers 2

2
$\begingroup$

The following is a valid lower bound for the stochastic programming problem.

\begin{align} \mathbb{E}_{\mathbb{\xi} \in \varOmega} \min \limits_{x\in X} \left( c^\top x + \mathcal{Q}(x, \xi) \right) \leq \min\limits_{x\in X} c^\top x + \mathbb{E}_{\mathbb{\xi} \in \varOmega}[\mathcal{Q}(x, \xi)] \end{align}

To derive this lower bound, you need to solve $|\varOmega|$ wait-and-see (perfect-information) problems ($\varOmega$ is the set of all the scenarios). The difference between the left-hand side and the right-hand side is: in the left-hand side, the first-stage decision $x$ varies with $\xi$; while in the right-hand side, $x$ is constant for all the $\xi \in \varOmega$.

This can be used to determine appropriate scenario size [1][2][3], and tighten the lower bound for a solution algorithm [1].

Since the relationship between the objective of the stochastic problem and an arbitrary wait-and-see problem is unclear, it is generally impossible to generate a lower bound with a single run of a wait-and-see problem. However, as @Sutanu mentioned, when you know which scenario can yield the wait-and-see problem with the lowest objective in advance, it can be used to derive a valid lower bound, which is weaker than the above inequality.

[1] Guo, P., & Zhu, J. (2023). Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2023.06.006

[2] Guo, C., Bodur, M., Aleman, D. M., & Urbach, D. R. (2021). Logic-based Benders decomposition and binary decision diagram based approaches for stochastic distributed operating room scheduling. INFORMS Journal on Computing, 33(4), 1551–1569. https://doi.org/10.1287/ijoc.2020.1036

[3] Mak, W.-K., Morton, D. P., & Wood, R. K. (1999). Monte Carlo bounding techniques for determining solution quality in stochastic programs. Operations Research Letters, 24(1), 47–56. https://doi.org/10.1016/S0167-6377(98)00054-6

$\endgroup$
1
$\begingroup$

It's a while since I asked this question. I have now came across the answer which is as follows:

Yes, if the stochastic problem is solved through the horizon based on the realized scenario, it provides a lower bound for (for a minimization problem). This is often called a posterior bound, which is used in papers by Warren B Powell. Indeed, it can be seen as a deterministic version of the problem. For more insights, one can look into:

  • Cheung, R.K. and Powell, W.B., 1996. An algorithm for multistage dynamic networks with random arc capacities, with an application to dynamic fleet management. Operations Research, 44(6), pp.951-963.

  • Godfrey, G.A. and Powell, W.B., 2002. An adaptive dynamic programming algorithm for dynamic fleet management, I: Single period travel times. Transportation Science, 36(1), pp.21-39.

$\endgroup$

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.