🔢 mathematics

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

Cet article présente un algorithme de branchement-prix-et-coupe numériquement sûr avec une stratégie de tarification par programmation dynamique efficace qui surpasse de manière significative les méthodes existantes pour le problème de la partition de cycles à contrainte de longueur, résolvant des instances plus grandes et fermant des cas auparavant non résolus.

Auteurs originaux : Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Publié 2026-07-20✓ Author reviewed ⓘ

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez le gestionnaire d'une flotte de drones de livraison. Chacun de vos arrêts de livraison (vos destinations) doit être visité régulièrement et possède une règle très spécifique et non négociable : une limite de temps critique. Certains lieux sont extrêmement urgents et exigent une visite très rapide, tandis que d'autres sont moins pressants et peuvent attendre plus longtemps. Votre travail consiste à déterminer la manière la plus efficace de regrouper tous vos arrêts de livraison en boucles. Vous voulez utiliser le moins de drones possible, mais chaque boucle que vous créez doit être assez courte pour respecter la contrainte du lieu le plus exigeant visité : la durée totale de la boucle ne peut pas dépasser le temps critique le plus court parmi tous les points qu'elle dessert. C'est un puzzle de géométrie et de temporalité, un problème que les mathématiciens appellent le « Problème de partition de cycles à longueur contrainte ». C'est le genre de défi qui se présente dans la vie réelle, comme la planification de patrouilles de sécurité pour une ville ou l'organisation d'échanges de reins, mais résoudre cela parfaitement est notoirement difficile. C'est comme essayer de résoudre un puzzle géant dont les pièces changent de forme selon la façon dont vous essayez de les assembler.

Cet article présente une nouvelle méthode, extrêmement intelligente, pour résoudre ce puzzle, qui est non seulement plus rapide mais aussi incroyablement rigoureuse sur le plan mathématique. Les auteurs, une équipe de chercheurs venus d'Allemagne et d'Australie, ont conçu un algorithme de type « branch-price-and-cut » (séparation par branchement, prix et coupe). Considérez cela comme un détective qui ne se contente pas de deviner où se trouvent les indices, mais qui construit systématiquement une carte de toutes les solutions possibles, éliminant les impossibles et « évaluant le prix » des plus prometteuses pour trouver la meilleure route absolue. Leur arme secrète est une technique appelée « génération de colonnes », qui revient à construire une maison en ne commandant que les briques spécifiques dont on a besoin à l'instant présent, plutôt que d'essayer de transporter toute une montagne de briques sur le chantier à la fois. Ils ont également ajouté une fonctionnalité de « sécurité numérique », qui est comme un système de double vérification garantissant que l'ordinateur ne commette pas de petites erreurs d'arrondi qui pourraient conduire à une mauvaise réponse.

Les résultats sont impressionnants. L'équipe a testé leur méthode sur 84 instances de puzzles différentes, allant de petites configurations de 14 nœuds à des structures massives de 100 nœuds. Leur nouvel algorithme a réussi à résoudre 52 de ces instances avec une perfection prouvée, incluant une instance de 76 nœuds — une taille qui n'avait jamais été résolue auparavant (le record précédent était de 52 nœuds). Ils ont également résolu 14 instances qui étaient auparavant insolubles. En termes de vitesse, leur méthode est, en moyenne, 14,7 fois plus rapide que la meilleure approche précédente. Ils ont découvert que les astuces les plus importantes étaient la « rupture de symétrie » (dire à l'ordinateur de ne pas perdre de temps à vérifier deux fois la même boucle simplement parce qu'elle commence par un point différent) et la « recherche bidirectionnelle » (construire la boucle à partir des deux extrémités en même temps pour qu'elles se rejoignent au milieu). Bien qu'ils aient tenté d'ajouter des « plans de coupe » supplémentaires (des règles mathématiques pour élaguer les mauvaises options), ils ont constaté que, pour la plupart des cas, le puzzle était déjà si serré que ces règles supplémentaires n'apportaient pas grand-chose et ralentissaient parfois le processus. L'article conclut que, bien qu'ils aient déchiffré le code pour jusqu'à 76 nœuds, le véritable goulot d'étranglement est désormais la vitesse de la routine de tarification, et que la résolution de puzzles encore plus grands nécessitera probablement des astuces informatiques encore plus puissantes.

Résumé Technique : Un algorithme de Branch-Price-and-Cut numériquement sûr pour le problème de la partition de cycles à contrainte de longueur

1. Définition du Problème

Le problème de la partition de cycles à contrainte de longueur (LCCP - Length-Constrained Cycle Partition) est un problème d'optimisation de graphe défini sur un graphe non orienté $G=(V, E)$ . L'objectif est de partitionner l'ensemble des nœuds $V$ en le nombre minimum de cycles disjoints tels que chaque nœud $i$ soit couvert exactement une fois.

Chaque nœud $i$ est associé à un temps critique $q_i > 0$ , et chaque arête $\{i, j\}$ possède un temps de trajet $t_{i,j} \ge 0$ . Un cycle $C$ est dit de longueur admissible si son temps de trajet total ne dépasse pas le temps critique de n'importe quel nœud qu'il contient :
$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$
Le problème est connu pour être NP-difficile (réductible au problème du voyageur de commerce) et ne possède aucun algorithme d'approximation en temps polynomial. Les approches de l'état de l'art précédent utilisaient des formulations de programmation mixte en nombres entiers (MIP) compactes (basées sur les contraintes de type Miller-Tucker-Zemlin ou d'élimination de sous-tours) qui pouvaient résoudre des instances allant jusqu'à 52 nœuds.

2. Méthodologie

Les auteurs proposent un algorithme exact de Branch-Price-and-Cut (BPC) basé sur une formulation de Partition de l'Ensemble (Set Partitioning - SP).

2.1 Formulation de Partition de l'Ensemble

Au lieu de formulations compactes, le problème est modélisé comme un problème de partition d'ensemble où les variables représentent des cycles entiers de longueur admissible. La formulation minimise $\sum_{C \in \Omega} \lambda_C$ sous réserve de contraintes de couverture $\sum_{C \in \Omega} a^C_i \lambda_C = 1$ pour tout $i \in V$ . En raison de la taille exponentielle de $\Omega$ , les auteurs emploient la Génération de Colonnes pour résoudre dynamiquement la relaxation de programmation linéaire (LP).

2.2 Le Problème de Prix (LCPCCP)

La tâche de calcul centrale est le Problème de Cycle avec Récompense à Contrainte de Longueur (LCPCCP - Length-Constrained Prize-Collecting Cycle Problem), qui cherche un cycle avec un coût réduit négatif. Ce problème est fortement NP-difficile. Les auteurs le résolvent en utilisant :

Programmation Dynamique (DP) : Un algorithme de marquage par étiquettes (label-setting) où les étiquettes suivent les nœuds visités, le coût réduit, le temps de trajet total et le temps critique minimum du chemin.
Recherche Bidirectionnelle : Exploitant la nature non orientée du graphe, l'algorithme étend les étiquettes à partir d'un nœud de départ $s$ uniquement jusqu'à ce que $t(\ell) < q(\ell)/2$ . Des étiquettes non dominées issues de recherches directes et inverses sont ensuite fusionnées pour former des cycles complets. Cela réduit considérablement l'espace de recherche par rapport à une recherche monodirectionnelle.
Règles de Dominance : Les étiquettes sont élaguées si une autre étiquette au même nœud possède un coût réduit inférieur ou égal, un temps de trajet inférieur ou égal, et un sous-ensemble de nœuds visités.
Relaxation ng : Pour gérer les cycles non élémentaires (revisite de nœuds), les auteurs utilisent une relaxation de chemin ng avec une expansion dynamique du voisinage. Cela fournit des bornes inférieures valides tout en évitant la complexité de l'imposition stricte de l'élémentarité lors des phases de recherche initiales.
Heuristique Gloutonne : Une heuristique rapide est exécutée en premier pour trouver des cycles améliorants en supprimant des nœuds duaux négatifs ou en insérant des nœuds duaux positifs, réduisant ainsi le besoin d'itérations de DP coûteuses.

2.3 Exploitation de la Structure

Inégalité Triangulaire : Pour les nœuds où l'inégalité triangulaire est respectée localement, les auteurs passent à des contraintes de couverture d'ensemble (set covering). Cela restreint les variables duales à être non négatives, permettant la suppression des nœuds aux duaux nuls et permettant un élagage préemptif.
Rupture de Symétrie : Pour éviter de générer le même cycle à partir de différents nœuds de départ, la recherche est restreinte pour ne visiter que des nœuds dont les temps critiques sont supérieurs ou égaux au nœud de départ (avec une règle de départage par indice).

2.4 Plans de Coupe (Cutting Planes)

L'algorithme intègre deux familles de coupes :

Coupes de Lignes de Sous-ensembles (SRC - Subset Row Cuts) : Appliquées à des sous-ensembles de nœuds pour limiter le nombre de cycles les couvrant.
Coupes de Cliques (CC - Clique Cuts) : Basées sur le graphe de conflit des cycles.
Les auteurs étudient le respect de ces coupes dans le problème de prix. Ils constatent que si les coupes de cliques sont ignorées dans le prix pour éviter la complexité, les coupes de lignes de sous-ensembles sont respectées en augmentant les étiquettes avec des ressources supplémentaires, ce qui améliore la convergence sur certaines instances difficiles.

2.5 Sécurité Numérique

Une contribution clé est l'implémentation de bornes numériquement sûres. L'arithmétique en virgule flottante peut conduire à des solutions duales infaisables en raison d'erreurs d'arrondi. Les auteurs proposent un mécanisme de réparation duale :

Passer les duaux en virgule flottante à des entiers de grande taille.
Vérifier la faisabilité duale exactement en utilisant l'arithmétique entière.
Si infaisable, réduire le facteur d'échelle et réessayer.
Cela garantit que les bornes inférieures utilisées pour la ramification sont mathématiquement rigoureuses, empêissant l'algorithme de prétendre à l'optimalité sur la base d'artefacts numériques.

2.6 Ramification et Heuristiques

Ramification (Branching) : Utilise principalement la ramification sur les arêtes (fixer les arêtes pour qu'elles soient présentes ou absentes de la solution). La ramification de Ryan-Foster (sur les paires de nœuds) a été testée mais jugée moins robuste pour cette structure de problème spécifique.
Heuristiques : Une variante de branch-and-price heuristique relâche les règles de dominance pour trouver rapidement des solutions primales de haute qualité, qui servent ensuite de points de départ (warm starts) pour le solveur exact.

3. Contributions Clés

Formulation de Partition d'Ensemble : Démontre qu'une approche basée sur la partition d'ensemble produit des relaxations LP nettement plus serrées (écart moyen de 0,4 %) par rapport aux formulations compactes précédentes (écart de 30,3 %).
Prix par DP Bidirectionnelle : Introduit une recherche bidirectionnelle efficace pour le problème de prix LCPCCP, exploitant la symétrie des graphes non orientés pour réduire l'espace de recherche.
Sécurité Numérique : Fournit un cadre pour obtenir des bornes inférieures prouvables dans un contexte de branch-and-price en combinant des solveurs en virgule flottante avec une vérification duale par calcul entier exact.
Intégration Algorithmique : Combine le prix glouton, la relaxation ng, la rupture de symétrie et la gestion spécifique des coupes en un solveur cohérent.

4. Résultats Computationnels

L'algorithme a été testé sur 84 instances de référence (14 à 100 nœuds) contre la méthode précédente de l'état de l'art (branch-and-cut, bnc-sec).

Performance : L'algorithme de Branch-Price-and-Cut proposé (spécifiquement la configuration withsrc+pricing) a résolu 52 instances avec une optimalité prouvée, contre 40 pour la méthode précédente la plus performante.
Échelle : Il a résolu avec succès des instances allant jusqu'à 76 nœuds, comblant 14 instances auparavant non résolues. La limite précédente était de 52 nœuds.
Vitesse : Le cœur de branch-and-price est en moyenne 14,7 fois plus rapide que l'approche précédente la plus performante.
Efficacité du Nœud Racine : 49 des 52 instances résolues l'ont été au nœud racine sans ramification, soulignant la force de la relaxation LP.
Surcoût de Sécurité Numérique : La version numériquement sûre a résolu le même nombre d'instances que la version non sûre, mais est environ 40 % plus lente (moyenne géométrique de 7,6s contre 4,5s). Cependant, aucun résultat incorrect n'a été détecté dans la version non sûre, et le surcoût est considéré comme modéré compte tenu de la garantie de correction.

5. Signification et Revendications

L'article affirme que la formulation de partition d'ensemble est le principal moteur de performance, fournissant des bornes serrées qui permettent de résoudre la plupart des instances au nœud racine. La recherche bidirectionnelle et la rupture de symétrie sont identifiées comme les composants algorithmiques les plus impactants pour réduire le temps d'exécution.

Les auteurs notent modestement que bien que la méthode améliore significativement l'état de l'art, les instances dépassant 76 nœuds restent non résolues, et la routine de prix demeure le goulot d'étranglement computationnel. Ils suggèrent que les améliorations futures pourraient nécessiter des bornes duales plus fortes ou des algorithmes de prix plus scalables (par exemple, l'accélération par GPU). Ce travail établit un nouveau standard pour la résolution du LCCP, prouvant que des méthodes exactes peuvent traiter des instances plus grandes et plus complexes lorsqu'elles sont combinées à des techniques de gestion de structure et de sécurité numérique.