Monotonic bounds in multistage mixed-integer linear stochastic programming: theoretical and numerical results

Multistage stochastic programs bring computational complexity which may increase exponentially in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal solution are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. Numerical results on a supply real case transportation problem have been provided.


The paper is published in Computational Management Science (2016): F. Maggioni, E. Allevi, M. Bertocchi, (2016) Monotonic bounds in multistage mixed-integer stochastic programming, Computational Management Science, DOI: 10.1007/s10287-016-0254-5, First online: 06 April 2016.