Résumé technique : Transformation de programmes à contraintes en entrée pour la recherche locale

Énoncé du problème

Les problèmes d'optimisation combinatoire (POC) sont omniprésents dans les sciences et l'industrie. Bien que les systèmes de programmation par contraintes (PPC) résolvent efficacement ces problèmes en utilisant des techniques de recherche complète (par exemple, arbres de recherche, propagation, résolution SAT), ces méthodes éprouvent souvent des difficultés face à l'évolutivité requise pour des problèmes très vastes. À l'inverse, les algorithmes de recherche locale et les métaheuristiques (par exemple, algorithmes génétiques, recuit simulé) sont hautement efficaces pour les problèmes à grande échelle, mais nécessitent généralement une intervention humaine significative pour définir la structure de « voisinage » — l'ensemble des mouvements valides d'une solution courante vers une solution voisine. Actuellement, il existe une rupture entre la spécification déclarative des POC et l'entrée procédurale requise par les algorithmes de recherche locale. Le problème central abordé est l'absence d'un mécanisme automatisé pour transformer une spécification de contraintes de haut niveau en les définitions de voisinage spécifiques nécessaires pour piloter un algorithme de recherche locale.

Méthodologie

Les auteurs proposent un lien théorique et pratique entre les propriétés de symétrie d'un POC et la définition des voisinages de recherche locale. La méthodologie est mise en œuvre au sein du système IDP, un système de base de connaissances fondé sur la logique FO(·) (une extension de la logique du premier ordre typée).

Cadre théorique

1. Voisinages induits par la symétrie : L'article définit un voisinage $N$ comme une application d'une affectation satisfaisante vers un ensemble d'autres affectations satisfaisantes. Les auteurs postulent qu'un ensemble de symétries $\mathcal{S}$ (permutations de l'espace d'affectation qui préservent la satisfaction des contraintes) peut induire un voisinage $N_\mathcal{S}$, où les voisins d'une affectation $\alpha$ sont les images $\{S(\alpha) \mid S \in \mathcal{S}\}$.
2. Invariance vs Variance : Une distinction critique est établie concernant la fonction objectif $O$.
   • Symétries invariantes : Symétries où $O(\alpha) = O(S(\alpha))$. Ce sont généralement de mauvais candidats pour les voisinages de recherche locale car ils n'améliorent pas la solution.
   • Symétries variantes : Symétries où $O(\alpha) \neq O(S(\alpha))$. Ce sont les cibles principales pour la génération de voisinages, car elles permettent à la recherche de se déplacer vers des solutions ayant des valeurs objectives différentes (potentiellement meilleures).
3. Symétrie d'échange d'éléments de domaine (DES) : Dans le contexte IDP, le système détecte les symétries DES. Une symétrie DES se caractérise par un triplet $(a, b, \sigma)$, où $a$ et $b$ sont des éléments de domaine du même type, et $\sigma$ est un ensemble de symboles de prédicats ou de fonctions non interprétés. La symétrie échange $a$ et $b$ au sein des interprétations des symboles dans $\sigma$.

Implémentation algorithmique dans IDP

Les auteurs ont mis en œuvre un pipeline automatisé pour générer des voisinages à partir d'une spécification FO(·) :

1. Solution initiale : Générer une affectation satisfaisante initiale en utilisant des techniques PPC standard.
2. Détection de symétrie : Détecter le groupe de symétrie $\Gamma$ du problème. Plus précisément, IDP identifie les symétries DES sur les symboles non interprétés.
3. Filtrage :
   • Identifier les symboles apparaissant dans le terme de minimisation (fonction objectif).
   • Détecter les symétries DES sur ces symboles.
   • Exclure les symétries qui sont invariantes par rapport à la fonction objectif.
4. Construction du voisinage : Convertir les symétries variantes restantes en un voisinage. Pour gérer l'explosion factorielle du groupe de symétrie complet, l'algorithme restreint l'ensemble induisant à l'ensemble de base de tous les échanges binaires possibles ($O(n^2)$), qui génère le groupe complet.

Contributions clés

• Lien théorique : L'article établit un lien formel novateur entre les propriétés de symétrie dans l'optimisation sous contraintes et la définition des voisinages de recherche locale.
• Automatisation : Il présente la première méthode automatisée pour dériver des voisinages de recherche locale directement à partir d'une spécification de contraintes déclarative (spécifiquement au sein du système IDP) sans intervention humaine.
• Robustesse : L'approche s'est révélée robuste face à différentes spécifications logiques d'un même problème (par exemple, différents codages FO(·) du problème du voyageur de commerce produisent des voisinages comparables).
• Filtrage intelligent : La méthode filtre avec succès les voisinages « inutiles » (ceux invariants par rapport à la fonction objectif), tels que les permutations globales de couleurs dans le problème du nombre chromatique, qui gaspilleraient autrement les ressources de recherche.

Résultats expérimentaux

Les auteurs ont évalué la technique sur six problèmes d'optimisation classiques :

1. Problème du voyageur de commerce (TSP) : Le système a détecté avec succès les symétries d'échange de villes et d'échange d'indices, générant des voisinages équivalents aux mouvements conçus par des humains (comme les variations 2-opt). Les résultats étaient robustes face à différentes spécifications logiques.
2. Problème du plus court chemin : L'algorithme a identifié avec succès les nœuds interchangeables (à l'exclusion du début/fin), générant un grand ensemble de voisinages induits.
3. Clique maximale : Aucune symétrie n'a été détectée car les nœuds d'un graphe ne sont généralement pas interchangeables sans violer les contraintes. Les auteurs notent que cela met en évidence une limitation : la méthode actuelle ne peut pas détecter les voisinages qui nécessitent de relâcher les contraintes (par exemple, permettre temporairement des non-cliques).
4. Problème du nombre chromatique (CNP) : Le système a correctement identifié que les permutations globales de couleurs sont invariantes par rapport à la fonction objectif (nombre de couleurs utilisées) et n'a donc pas généré de voisinage. Cela empêche l'algorithme de perdre du temps sur des mouvements non productifs.
5. Problème du sac à dos : Le système a détecté des symétries inattendues où des objets ayant des volumes identiques mais des valeurs différentes pouvaient être échangés. Cela a conduit à un voisinage valide pour explorer de petites variations dans le remplissage du sac à dos.
6. Problème d'affectation : Le système a détecté des échanges d'agents et de tâches qui étaient variantes par rapport à la fonction objectif, produisant un voisinage identique à celui qu'un expert humain aurait conçu.

Importance et affirmations

L'article affirme que les résultats expérimentaux soutiennent la faisabilité de l'utilisation de la symétrie pour générer automatiquement des voisinages de recherche locale. L'importance de ce travail réside dans :

• Rapprochement des domaines : Il rapproche la programmation par contraintes et les métaheuristiques en automatisant la traduction des contraintes déclaratives vers les entrées de recherche procédurales.
• Éviter les biais humains : Il permet la découverte de voisinages que les humains pourraient ne pas attendre (par exemple, des échanges d'objets spécifiques dans le problème du sac à dos) tout en évitant la génération de voisinages inutiles (par exemple, des échanges de couleurs invariants dans le CNP).
• Orthogonalité à la rupture de symétrie : Contrairement à la rupture de symétrie traditionnelle (qui élimine les solutions symétriques pour accélérer la recherche complète), cette approche exploite les symétries qui sont variantes par rapport à la fonction objectif pour parcourir l'espace de recherche. Les auteurs notent que briser ces symétries spécifiques risquerait d'éliminer des solutions optimales.

Les auteurs restent modestes concernant les implications futures, reconnaissant que l'approche actuelle ne gère pas encore le relâchement des contraintes (nécessaire pour des problèmes comme la clique maximale) et que le système IDP nécessite une optimisation pour des mises à jour incrémentales efficaces pendant la recherche locale. Ils suggèrent que des travaux futurs pourraient impliquer des hyperheuristiques pour sélectionner des sous-ensembles de symétries et une investigation plus approfondie de la relation entre ces symétries et les relations de dominance.