Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty

• 成果类型: Article
• 署名作者: Romeijnders, Ward; van der Laan, Niels
• 署名单位: University of Groningen
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1905
• 发表日期: 2020
• 页码: 1199-1217
• 关键词: stochastic programming; integer programming; cutting plane techniques; convex approximations

摘要

We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs with uncertainty in the right-hand side. Instead of using cutting planes that are always valid, our idea is to apply pseudo-valid cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. The advantage is that it allows us to use cutting planes that are affine in the first-stage decision variables, so that the approximation is convex and can be efficiently solved using techniques from convex optimization. We derive tight performance guarantees for using particular types of pseudo-valid cutting planes for simple integer recourse models. Moreover, we show in general that using pseudo-valid cutting planes leads to good first-stage solutions if the total variations of the one-dimensional conditional probability density functions of the random variables in the model converge to zero.