Séminaire

Date : 26 juin 2026 14:00 - Salle :Salle A104 Robust Optimization and Learning for Branch-and-Bound Zacharie Alès - CEDRIC – ENSTA Paris

Part 1. Minimizing recovery cost: a robust framework

We propose a two-stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty ξ is revealed, it can be more important to recover a solution x(ξ) that remains as close as possible to the nominal solution x than to minimize the objective value of x(ξ). This situation arises, for example, when the nominal solution is implemented regularly or when uncertainty is revealed only at a late stage.

We define a proactive problem that minimizes weighted recovery costs over a discrete set of scenarios while preserving the optimality of the nominal objective value. We study the complexity of several network problems within this framework and highlight the benefits of the proactive approach through a case study on a railroad planning problem.

Part 2. Learning Branch-and-Bound branching heuristics through reinforcement learning

Recent work has focused on learning branching rules for Branch-and-Bound (B&B) directly from data, with policies optimized for specific MILP distributions. This talk presents two contributions in that direction.

First, we introduce BBMDP, a principled formulation of branching as a standard Markov Decision Process, enabling the direct application of a wide range of reinforcement learning algorithms. Second, we present PlanB&B, a model-based reinforcement learning approach that learns an internal model of B&B dynamics and uses planning to discover improved branching strategies.

Across four standard MILP benchmarks, both approaches outperform previous state-of-the-art RL-based branching methods, illustrating how modern reinforcement learning and planning techniques can be systematically integrated into Branch-and-Bound.