L’optimisation combinatoire est un domaine des mathématiques dans lequel un problème consiste à trouver une solution optimale dans un ensemble fini d’objets. Elle a des applications cruciales dans de nombreux domaines, notamment les mathématiques appliquées, le génie logiciel, l’informatique théorique et l’apprentissage automatique. Le branch-and-cut est l’un des algorithmes les plus utilisés pour résoudre exactement des problèmes d’optimisation combinatoire. Dans cette thèse, nous nous concentrons sur les aspects informatiques du branch and-cut et plus particulièrement, sur deux aspects importants de l’optimisation combinatoire : l’équité des solutions et l’intégration de l’apprentissage automatique.

Dans la partie I, nous étudions deux approches courantes pour traiter la question de l’équité dans l’optimisation combinatoire, qui a fait l’objet d’une attention particulière au cours des dernières décennies. La première approche est l’optimisation combinatoire équilibrée, qui trouve une solution équitable en minimisant la différence entre les plus grands et les plus petits composants utilisés. En raison des difficultés à délimiter ces composants, à notre connaissance, aucun cadre général exact basé sur la programmation linéaire en nombres entiers mixtes (MILP) n’a été proposé pour l’optimisation combinatoire équilibrée. Pour combler cette lacune, nous présentons une nouvelle classe de plans de coupe locaux adaptés aux problèmes d’optimisation combinatoire équilibrée pour l’algorithme du branch-and-cut. Nous démontrons l’efficacité de la méthode proposée dans la carde du problème du voyageur de commerce équilibré. Notamment, nous introduisons des algorithmes pour la recherche de bornes et des mécanismes pour la détermination des variables afin d’accélérer un peu plus les performances. Une deuxième approche pour traiter la question de l’équité est l’optimisation combinatoire Ordered Weighted Average (OWA), qui consiste à utiliser l’opérateur OWA dans la fonction objectif. En raison de l’opérateur d’ordonnancement, l’optimisation combinatoire OWA est non linéaire, même si ses contraintes d’origine sont linéaires. Deux formulations MILP de tailles différentes ont été introduites dans la littérature pour linéariser l’opérateur OWA. Nous fournissons des comparaisons théoriques et empiriques des deux formulations MILP pour l’optimisation combinatoire OWA. En particulier, nous prouvons que les formulations sont équivalentes en termes de relaxation de programmation linéaire. Nous montrons empiriquement que pour les problèmes d’optimisation combinatoire OWA, la formulation avec le plus de variables peut être résolue plus rapidement avec le branch-and-cut.

Dans la partie II, nous développons des méthodes d’application de l’apprentissage automatique pour améliorer les problèmes de décision fondamentaux du branch-and-cut, en mettant l’accent sur la génération de coupes. Ce dernier problème se réfère à la décision de générer des coupes ou des branches à chaque nœud de l’arbre de recherche. Nous proposons ensuite un cadre général combinant l’apprentissage supervisé et l’apprentissage par renforcement afin d’apprendre des stratégies efficaces pour générer des coupes combinatoires dans la méthode branch-and-cut. Notre cadre comporte deux composantes : un détecteur de coupes pour prédire l’existence de coupes et un évaluateur de coupes pour choisir entre la génération de coupes et le branchement. Enfin, nous fournissons des résultats expérimentaux montrant que la méthode proposée est plus performante que les stratégies couramment utilisées pour la génération de coupes, même sur des instances plus grandes que celles utilisées pour l’apprentissage.

Jury :

• Dritan NACE, Professeur à l’Université de Technologie de Compiègne (Rapporteur)
• Axel PARMENTIER, Chercheur HDR à l’Ecole Nationale des Ponts et Chaussées (Rapporteur)
• Sophie DEMASSEY, MCF HDR à Ecole de Mines de Paris (Examiantrice)
• Kim Thang NGUYEN, Professeur à l’Université Grenoble Alpes (Examinateur)
• Fatiha BENDALI, Professeure à l’Université Clermont Auvergne (Examinatrice)
• Mourad BAIOU, Directeur de recherche au CNRS, LIMOS UMR 6158 (Co-encadrant)
• Viet Hung NGUYEN, Professeur à l’Université Clermont Auvergne (Co-encadrant, directeur de thèse).