# Deriving a lower bound for a two-stage stochastic problem

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?

• 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. Jul 21, 2023 at 2:49

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

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.