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

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.