Branch-and-Cut for Mixed-Integer Linear Decision-Dependent Robust Optimization

Decision-dependent robust optimization (DDRO) problems are usually tackled by reformulating them using a strong-duality theorem for the uncertainty set model. If the uncertainty set is, however, described by a mixed-integer linear model, dualization techniques cannot be applied and the literature on solution methods is very scarce. In this paper, we exploit the equivalence of DDRO and optimistic bilevel optimization to derive the first tailored branch-and-cut method for mixed-integer linear DDRO problems. To this end, we consider both general-purpose intersection cuts for the case of decision-dependent uncertainty sets given by general mixed-integer linear models as well as more tailored interdiction cuts for the case of downward monotone uncertainty set models. Using the special structure of robust optimization problems, we also derive a novel version of intersection cuts that are only stated in the space of the upper-level variables of the respective bilevel reformulation. We present an extensive numerical study that demonstrates the applicability of our method.

Article

Download

View PDF