Multistage problems with uncertain parameters and integer decisions variables are among the most difficult applications of robust optimization (RO). The challenge in these problems is to find optimal here-and-now decisions, taking into account that the wait-and-see decisions have to adapt to the revealed values of the uncertain parameters. An existing approach to solve these problems is to construct piecewise constant decision rules by adaptively partitioning the uncertainty set. The partitions of this set are iteratively updated by separating so-called criticial scenarios, and methods for identifying these critical scenarios are available. However, these methods are most suitable for problems with continuous decision variables and many uncertain constraints, providing no mathematically rigorous methodology for partitioning in case of integer decisions. In particular, they are not able to identify sets of critical scenarios for integer problems with uncertainty in the objective function only. In this paper, we address this shortcoming by introducing a general critical scenario detection method. The new method leverages the information embedded in the dual vectors of the LP relaxations at the nodes of the branch-and-bound tree used to solve the corresponding static problem. Numerical experiments on a route planning problem show that our general-purpose method outperforms a problem-specific approach from the literature.

We consider two types of convex approximations of two-stage totally unimodular integer recourse models. Although worst-case error bounds are available for these approximations, their actual performance has not yet been investigated, mainly because this requires solving the original recourse model. In this paper we assess the quality of the approximating solutions using Monte Carlo sampling, or more specifically, using the so-called multiple replications procedure. Based on numerical experiments for an integer newsvendor problem, a fleet allocation and routing problem, and a stochastic activity network investment problem, we conclude that the error bounds are reasonably sharp if the variability of the random parameters in the model is either small or large; otherwise, the actual error of using the convex approximations is much smaller than the error bounds suggest. Moreover, we conclude that the solutions obtained using the convex approximations are good only if the variability of the random parameters is medium to large. In case this variability is small, however, typically sampling methods perform best, even with modest sample sizes. In this sense, the convex approximations and sampling methods can be considered as complementary solution methods. Moreover, as required for our applications, we extend our approach to derive new error bounds dealing with deterministic second-stage side constraints and relatively complete recourse, and perfect dependencies in the right-hand side vector.