Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Résumé Technique : Recherche de Voisinage Large assistée par Machine Ising avec Taille de Sous-problème Ajustable de Manière Flexible

Énoncé du Problème
Les machines Ising servent de solveurs heuristiques pour l'optimisation combinatoire en recherchant des états de basse énergie de modèles d'Ising ou d'Optimisation Binaire Quadratique Sans Contrainte (QUBO). Cependant, l'application directe d'Ising aux problèmes contraints à grande échelle (la « méthode naïve ») se heurte à deux difficultés principales :

1. Scalabilité : Le nombre de variables binaires dans la formulation QUBO dépasse souvent la capacité matérielle des machines Ising actuelles.
2. Faisabilité : Les contraintes sont généralement incorporées sous forme de termes de pénalité. Par conséquent, l'espace de recherche inclut des solutions infaisables, et les états de basse énergie ne correspondent pas nécessairement à des solutions faisables de haute qualité du problème original.

Bien que les approches existantes comme la fixation de variables ou le principe de "diviser pour régner" tentent de réduire la taille du problème, elles peinent souvent à équilibrer la taille du sous-problème avec la capacité de reconstruire des solutions faisables pour le problème original. La Recherche de Voisinage Large (LNS) offre un cadre où une solution initiale faisable est améliorée de manière itérative en ré-optimisant un sous-problème (un « voisinage »). Bien que la LNS préserve la faisabilité si la méthode de génération du sous-problème est conçue correctement, la performance de la LNS assistée par machine Ising est très sensible à la taille du sous-problème. Si le sous-problème est trop petit, l'amélioration potentielle par itération est limitée ; s'il est trop grand, la qualité de la solution de la machine Ising se dégrade en raison de l'expansion de l'espace de recherche.

Méthodologie
L'article se concentre sur deux problèmes : le Problème de Tournées de Véhicules (VRP) et le Problème de Sac à Dos Quadratique Multiple (QMKP).

• Méthode Existante (LNS-V) : Pour le VRP, les auteurs analysent une méthode précédente (LNS-V) qui sélectionne un sous-ensemble de véhicules et ré-optimise l'intégralité de leurs itinéraires. Bien que cela préserve la faisabilité, la taille du sous-problème est contrôlée uniquement par le nombre de véhicules sélectionnés ($V'$). Comme l'itinéraire complet d'un véhicule sélectionné est ré-optimisé, le nombre de variables évolue selon $(V')^2(T-2)^2$ (où $T$ est le nombre total d'étapes). Cela entraîne une granularité grossière ; changer $V'$ d'une unité peut provoquer un saut massif dans le nombre de variables, rendant difficile l'ajustement de la taille du sous-problème vers la plage optimale pour la machine Ising.

• Méthode Proposée (LNS-VT) : Pour remédier au problème de granularité, les auteurs proposent LNS-VT. En plus de sélectionner $V'$ véhicules, LNS-VT introduit un nouveau paramètre : le nombre d'étapes consécutives ($T'$) à ré-optimiser pour chaque véhicule sélectionné.

  • Mécanisme : Pour chaque véhicule sélectionné, un segment contigu de l'itinéraire (de longueur $T_{seg} = \min(T', \text{étapes valides réelles})$) est extrait. Le sous-problème ré-optimise l'assignation et l'ordre des sites au sein de ces segments spécifiques tout en maintenant le reste de l'itinéraire fixe.
  • Faisabilité : En fixant les sites en dehors des intervalles d'extraction et en s'assurant que les segments extraits ne concernent que des sites non-dépôt, la méthode garantit que la réinsertion de toute solution de sous-problème faisable produit une solution faisable pour le VRP original.
  • Contrôle des Variables : Le nombre de variables libres dans LNS-VT est approximativement $(V'T')^2$. Cela permet un contrôle précis de la taille du sous-problème, indépendamment du nombre total d'étapes $T$ du problème.

• Extension au QMKP : Les auteurs appliquent le même principe de conception au QMKP. Ils construisent une méthode de génération de sous-problème qui sélectionne un sous-ensemble de sacs à dos ($K'$) et un sous-ensemble d'articles ($N'$) à ré-optimiser. Cette méthode préserve également la faisabilité en fixant les articles ne faisant pas partie de l'ensemble sélectionné et en ajustant les contraintes de capacité pour la capacité résiduelle des sacs à dos sélectionnés.

Résultats Clés
Des expériences numériques ont été menées sur un VRP de 300 sites et 5 véhicules, et un QMKP de 200 articles et 5 sacs à dos, en utilisant la machine Ising Fixstars Amplify AE.

• Performance du VRP :

  • LNS-VT a surpassé à la fois la méthode naïve et l'existante LNS-V.
  • Le meilleur réglage de LNS-VT (spécifiquement $V'=2, T'=40$) a réduit la valeur de l'objectif d'environ 10 % par rapport à LNS-V après 100 itérations.
  • LNS-VT a atteint la qualité de solution finale de LNS-V en utilisant seulement environ 30 % des itérations.
  • Sensibilité des Variables : La taille optimale du sous-problème (en termes de variables d'assignation de sites non-dépôt) s'est avérée être comprise entre 6 000 et 10 000. L'existante LNS-V ne pouvait pas atteindre cette plage avec $V' \ge 2$ (son minimum était d'environ 14 400 variables), ce qui explique sa performance inférieure.
  • Besoins Dynamiques : La taille appropriée du sous-problème changeait au cours du processus de recherche. Des sous-problèmes plus larges étaient plus efficaces lors des premières itérations (valeurs d'objectif élevées), tandis que des sous-problèmes plus petits étaient plus efficaces dans les phases ultérieures (affinement des solutions de haute qualité).

• Performance du QMKP :

  • La LNS appliquée au QMKP a également surpassé la méthode naïve.
  • La taille optimale du sous-problème pour le QMKP s'est avérée nettement plus petite, environ 100 à 150 variables.
  • Cette différence marquée avec le VRP (6 000–10 000) indique que la taille optimale du sous-problème dépend de la classe spécifique de problème et de la formulation QUBO, et non seulement des capacités de la machine Ising.

Signification et Revendications
L'article affirme que pour que la LNS assistée par machine Ising soit efficace pour les problèmes contraints à grande échelle, la préservation de la faisabilité seule est insuffisante. La capacité de régler de manière flexible la taille du sous-problème pour correspondre au point idéal de performance de la machine Ising est un facteur de conception critique.

L'étude démontre que :

1. L'introduction d'un paramètre de contrôle supplémentaire (étapes consécutives pour le VRP, ou nombre d'articles/sacs à dos pour le QMKP) permet un ajustement précis de la taille du sous-problème, ce qui est impossible avec les méthodes qui ne varient que le nombre d'entités sélectionnées.
2. Il existe une plage optimale de variables pour le sous-problème qui maximise la qualité de la solution, et cette plage varie considérablement entre les différentes classes de problèmes (VRP vs QMKP).
3. La taille optimale du sous-problème peut également dépendre de la qualité de la solution actuelle, suggérant que les réglages de paramètres statiques peuvent ne pas être optimaux tout au long du processus de recherche.

Les auteurs concluent que bien que leurs résultats soient spécifiques aux instances et aux réglages de machine testés, le principe de génération de sous-problèmes structurés et de réglage flexible est une direction prometteuse pour l'optimisation combinatoire contrainte. Ils notent que les travaux futurs devraient se concentrer sur le développement de stratégies adaptatives pour sélectionner automatiquement les paramètres du sous-problème en fonction de l'étape de recherche et de la structure du problème.