Inexact cutting planes for two-stage mixed-integer stochastic programs

We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact 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 ane in the rst-stage decision variables, so that the approximation is convex, and can be solved eciently using techniques from convex optimization. We derive performance guarantees for using particular types of inexact cutting planes for simple integer recourse models. Moreover, we show in general that using inexact cutting planes leads to good rst-stage solutions if the total variations of the probability density functions of the random variables in the model are small enough.

Citation

October 2018 Groningen: University of Groningen, SOM research school, 36 p.(SOM Research Reports; vol. 2018013-OPERA)

Article

Download

View Inexact cutting planes for two-stage mixed-integer stochastic programs