Séminaire de Doctorants : Paul Strang

La prochaine séance du séminaire de doctorants aura lieu mardi 11/03 à 14h00, salle 2320, et sera donnée par Paul Strang, doctorant de l'équipe OC du CEDRIC-CNAM.

Titre : Plan, branch and bound: Model-based reinforcement learning for exact combinatorial optimization

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt model-free reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, with mixed results. In fact, RL agents are frequently outperformed by human-expert branching heuristics or imitation learning agents trained to mimic these experts. However, model-based RL agents have demonstrated the ability to surpass human expertise in complex combinatorial settings, such as board games (Silver et al., 2017; Schrittwieser et al., 2020). Inspired by the success of AlphaGo and its successors, we propose adapting this framework to the problem of solving mixed-integer linear programs.