Retour aux activités
Discussion DS4DM autour d'un café

Learn to Compare Nodes in Branch and Bound

iCalendar

1 août 2023   11h00 — 12h00

Abdel Ghani Labassi Johns Hopkins University, États-Unis

Abdel Ghani Labassi

Présentation sur YouTube.

The Branch and Bound method aims to find optimal solutions to NP-hard problems. It divides the search space into subproblems, which are recursively solved, while eliminating branches whose potential solution is inferior to the one already found. The choice of the exploration order of nodes is essential to the performance of this algorithm. An efficient selection strategy can speed up the solution and reduce the branching tree. We will discuss various node selection approaches, with an emphasis on data-based methods. We will also present our contribution, which uses graph neural networks to compare nodes, which are represented as bipartite graphs. Our model, capable of handling variable dimension data, has shown faster resolution and reduction of the branching tree than competitors, across three NP-hard benchmarks, while offering natural generalization to larger instances.

Federico Bobbio responsable
Defeng Liu responsable
Léa Ricard responsable

Lieu

Activité hybride au GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4
Canada

Organisme associé