- Decomposition-based approaches for a class of two-stage robust binary optimization problems, by Boris Detienne, Associate Prof. at Bordeaux University
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.
- Solving a competitive facility location model with an uncertain environment scenario, by Andrey Melnikov, Assistant Prof. at Novosibirsk State University
We would consider a model of competition, where two players open their facilities aiming to maximize profit. The model is organized as a Stackelberg game, assuming that one of the players makes their decision first, while the second one observes the decision and reacts rationally. A problem to find an optimal solution of the first player could be formalized as a bi-level mixed-integer programming problem and is more difficult than NP-complete problems. In the talk, we would briefly overview key aspects of an exact branch-and-cut procedure to solve the problem without uncertainty ingredients and discuss its generalizations considering the environment’s multiple possible scenarios.