In this talk, we study a class of two-stage robust binary optimization problems with polyhedral uncertainty set where recourse decisions are restricted to be mixed-binary and uncertainty is present only in the objective function. We present a deterministic equivalent formulation for these problems through convexification of the recourse feasible region. However, this reformulation does not directly lead to an exploitable structure in the problem. We therefore investigate a relaxation where we replace the convex hull of the recourse feasible region with an intersection of the convex hull of the pure recourse polyhedron with the linking constraints. We additionally propose “no-good” cut-type inequalities to recover the original problem from this relaxation. The resulting exact formulation can be solved with a branch-and-price-and-cut method, generating columns from the pure recourse polyhedron and introducing “no-good” cuts as needed. We additonally present necessary conditions for the relaxation to be exact without the need for additional cuts. Finally, we present various applications where these conditions are satisfied, and investigate the numerical strength of our methodology. Speicifally, we compare our methodology to a recently introduced approximation method called K-adaptability that fixes K recourse solutions in the first stage and optimizes the recourse problem over these in the second stage.< Leer menos