Improving subtour constraints generation in Branch-and-Cut algorithms for TSP with Machine Learning
Thi Quynh Trang Vo  1@  , Viet Hung Nguyen  1@  , Mourad Baiou  2@  , Paul Weng@
1 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes
Ecole Nationale Supérieure des Mines de St Etienne : UMR6158, Centre National de la Recherche Scientifique : UMR6158, Université Clermont Auvergne : UMR6158, Institut national polytechnique Clermont Auvergne : UMR6158
2 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes
Ecole Nationale Supérieure des Mines de St Etienne : UMR6158, Centre National de la Recherche Scientifique : UMR6158, Université Clermont Auvergne : UMR6158, Institut national polytechnique Clermont Auvergne : UMR6158

Branch-and-Cut (B&C) is a widely-used algorithm for solving integer programming (IP) problems. In recent years, applying Machine Learning (ML) to improve fundamental decision problems of B&C algorithms is an active research domain. While much of ML research focuses on variable selection, node selection, and cut selection, less attention has been paid to the question of how to design a cutting plane generation strategy in B&C algorithms. This question is crucial since generating cutting planes might become a computational burden when the instance's size increases. In this work, we focus on improving the subtour elimination constraints (SEC) generation in B&C algorithms for Traveling Salesman Problem (TSP) by ML. SEC is a well-known constraint used to exactly solve TSP. In the IP formulations for TSP, SEC is dynamically generated as cutting planes in the course of B&C algorithms due to its exponential cardinality. Our purpose is to take advantage of ML to address two questions before launching the separation process to find violated SEC cuts on a node of the B&C search tree : 1) Does there exist violated SEC cuts ? 2) If yes, is it worth generating them ? To do this, we propose a ML-based method consisting of two parts : a cut detector to predict the cut existence and a cut decider to decide whether generate cuts. Our method not only can leverage the geometric structure of optimal solutions but it also offers the flexibility of the instance's size.


Personnes connectées : 148 Vie privée
Chargement...