KK-adaptability in two-stage distributionally robust binary programming

We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated KK-adaptability problems, which pre-select KK candidate second-stage policies here-and-now and implement the best of these policies once the uncertain parameters have been observed. We analyze the approximation quality and the computational complexity of the KK-adaptability problem, and we derive explicit mixed-integer linear programming reformulations. We also provide efficient procedures for bounding the probabilities with which each of the KK second-stage policies is selected.