Learning in local branching

Defeng Liu, Andrea Lodi

Résumé (2021)

Accéder à ce document
Disponible
Libre accès au texte intégral dans PolyPublie et chez l'éditeur officiel
Version officielle de l'éditeur
Texte Texte • 393kB •

Résumé

Although state-of-the-art solvers for Mixed-Integer Programming (MIP) experienced a dramatic performance improvement over the past decades, the resolution of some MIPs is still challenging, requiring hours of computations while, in practice, high-quality solutions are often required to be computed within a very restricted time frame. In such cases, it might be preferable to provide anytime solutions, i.e., a first reasonable solution should be generated as early as possible, then better ones produced in the subsequent computation with the user deciding where to stop. In this respect, the local branching (LB) heuristic [Fischetti and Lodi, 2003] was proposed to improve an incumbent solution either at very early stages of the computation within a general MIP framework or as a stand-alone algorithmic framework. Roughly speaking, given a feasible solution, the method iterates by first defining a solution neighborhood through the so-called local branching cut, then by exploring it by calling a black-box MIP solver. In the local branching algorithm, the choice of the neighborhood size is crucial to performance. In principle, it is desirable to have neighborhoods to be relatively small for efficient computation but still large enough to contain improving solutions. In [Fischetti and Lodi, 2003], the size of the neighborhood is mostly initialized by a fixed constant value, then adjusted at run time. Nonetheless, it is reasonable to believe that there is no a priori single best neighborhood size and the choice of the value should depend on the characteristics of the problem. Furthermore, it is worth noting that, in many applications, instances of the same problem are solved repeatedly. Real-world problems have a rich structure: while more and more data points are collected, patterns and regularities appear. Therefore, problem-specific and task-specific knowledge can be learned from data and applied to adapting the corresponding optimization scenario. This motives a broader paradigm of sizing the solution neighborhoods in local branching. Following the line of work analyzed and surveyed in [Bengio et al., 2021] on the use of Machine Learning (ML) for combinatorial optimization, in this work, we aim to guide the (local) search of the local branching heuristic by ML techniques. In particular, given a problem instance and a time limit for (heuristically) solving it, we exploit ML tools to predict reasonable good values of the neighborhood size, in order to maximize the performance of the local branching algorithm. We computationally show that the neighborhood size can indeed be learnt leading to improved performances and that the overall algorithm generalizes well both with respect to the instance size and, more surprisingly, across instances.

Mots clés

Renseignements supplémentaires:
Centre de recherche : Canada Excellence Research Chair in Data Science for Real-Time Decision-Making
ISBN:
9783959772112
Adresse URL de PolyPublie:
Nom de la conférence:
27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Lieu de la conférence:
En ligne
Date(s) de la conférence:
2021-10-25 - 2021-10-29
Titre de la revue :
Leibniz International Proceedings in Informatics (LIPIcs) ( vol. 210 )
Maison d'édition:
Dagstuhl Publishing
OAI:
oai:publications.polymtl.ca:49755
ORCID
Date du dépôt:
18 avr. 2023 15:00
Dernière modification:
07 nov. 2026 06:03
Citer en APA 7:
Liu, D., & Lodi, A. (octobre 2021). Learning in local branching [Résumé]. 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), En ligne (2 pages). Publié dans Leibniz International Proceedings in Informatics (LIPIcs), 210. https://doi.org/10.4230/lipics.cp.2021.3

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Dimensions

Actions réservées au personnel

Afficher document
Afficher document