Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Résumé Technique : Évaluation de la Performance des Formulations Directes d'Ordre Supérieur dans les Problèmes d'Optimisation Combinatoire

Énoncé du Problème
Les problèmes d'optimisation combinatoire sont fréquemment rencontrés dans des domaines tels que la logistique, la conception de matériaux et l'optimisation de portefeuille. Bien que la plupart de ces problèmes soient NP-difficiles et nécessitent des approches heuristiques, un obstacle majeur subsiste dans leur implémentation sur les « machines Ising » (incluant le matériel de recuit quantique et les solveurs inspirés de la physique). La plupart des plateformes matérielles existantes acceptent exclusivement des entrées au format QUBO (Quadratic Unconstrained Binary Optimization), ce qui restreint les fonctions d'objectif aux termes linéaires et quadratiques de variables binaires.

Cependant, de nombreux problèmes du monde réel, tels que l'échantillonnage de polymères, le repliement des protéines et certaines tâches de routage, impliquent intrinsèquement des interactions d'ordre supérieur (cubiques, quartiques, etc.). Pour résoudre ces problèmes sur le matériel standard, les chercheurs doivent appliquer des techniques de « réduction d'ordre » afin de transformer les problèmes PUBO (Polynomial Unconstrained Binary Optimization) en forme QUBO. Ce processus introduit des variables auxiliaires et des termes de pénalité pour maintenir la cohérence logique. Les auteurs postulent que cette transformation augmente inévitablement la taille du problème et la complexité structurelle, ce qui peut dégrader la qualité et la stabilité des solutions ; pourtant, l'impact spécifique de la gestion directe des termes d'ordre supérieur par rapport à leur réduction n'a pas été rigoureusement quantifié sur une plateforme unifiée pour des instances pratiques à grande échelle.

Méthodologie
Pour combler cette lacune, l'étude utilise un cadre d'évaluation comparative utilisant le Fixstars Amplify Annealing Engine (Amplify AE). Ce solveur haute performance, basé sur le recuit simulé (Simulated Annealing - SA) et une parallélisation massive sur GPU, offre deux modes distincts :

1. Solveur PUBO : Optimise directement les fonctions d'objectif contenant des termes allant jusqu'au quatrième ordre sans modification.
2. Solveur QUBO : Résout les mêmes problèmes après l'application de la méthode de substitution pour la réduction d'ordre. Cette méthode remplace les produits de variables binaires par de nouvelles variables auxiliaires et impose des contraintes via des termes de pénalité (spécifiquement, $x_1x_2 = y_{1,2}$).

L'étude compare ces deux approches sur deux problèmes de référence qui contiennent naturellement des termes d'ordre supérieur :

• Séquence Binaire à Faible Autocorrélation (LABS) : Un problème cherchant des séquences binaires avec une énergie d'autocorrélation minimale. La fonction d'énergie implique des termes d'autocorrélation au carré, ce qui résulte en des interactions de quatrième ordre ($s_i s_{i+k} s_j s_{j+k}$).
• Problème de Tournée de Véhicules (VRP) avec Équilibrage de Distance : Un problème multi-objectif minimisant la distance totale parcourue tout en minimisant simultanément la variance des distances entre les véhicules. Le terme de variance introduit des interactions de quatrième ordre lors de son développement.

Les expériences ont été menées avec des temps de calcul fixes (60 secondes) à travers diverses tailles de problèmes. Pour LABS, les longueurs de séquence ($N$) allaient de 5 à 99. Pour le VRP, le nombre d'emplacements clients ($P$) et de véhicules ($V$) a été varié. Le solveur QUBO utilisait un coefficient de pénalité fixe ($p=1$) pour la méthode de substitution, tandis que le solveur PUBO ne nécessitait aucun paramètre de réglage de ce type.

Contributions Clés et Résultats
Le document fournit une analyse quantitative des compromis entre la formulation PUBO directe et la formulation QUBO réduite :

1. Qualité et Stabilité des Solutions :

   • LABS : Le solveur PU_BO a systématiquement obtenu des valeurs d'énergie normalisées plus basses (plus proches de la solution optimale) avec des écarts-types nettement plus faibles que le solveur QUBO. L'écart de performance s'est creusé à mesure que la longueur de la séquence $N$ augmentait.
   • VRP : Dans l'analyse d'instances uniques, le solveur PUBO a produit des compromis plus stables entre la distance totale et la variance des distances. Les graphiques de dispersion ont révélé que les solutions QUBO étaient largement dispersées et ne parvenaient pas à atteindre la région de variance minimale réelle, alors que les solutions PUBO se concentraient près de la frontière de Pareto.
   • Analyse de l'Hypervolume : Sur 30 instances de VRP générées aléatoirement, le solveur PUBO a systématiquement obtenu des indicateurs d'hypervolume plus élevés (une mesure de la diversité et de la qualité de l'ensemble des solutions) que le solveur QUBO, confirmant sa supériorité en optimisation multi-objectif.

2. Expansion des Variables :

   • L'étude a quantifié l'« explosion de variables » causée par la réduction d'ordre. Pour LABS et le VRP, le nombre de variables binaires dans la formulation QUBO a augmenté rapidement avec la taille du problème, atteignant des dizaines de fois le nombre de variables de la formulation PUBO directe pour les grandes instances. Cette expansion élargit l'espace de recherche, contribuant à la dégradation observée de la stabilité des solutions.

3. Sensibilité aux Coefficients de Pénalité :

   • Les auteurs ont étudié la sensibilité de l'approche QUBO au coefficient de pénalité ($p$) utilisé dans la méthode de substitution. Une analyse par carte thermique (heatmap) pour le problème LABS a démontré que le coefficient de pénalité optimal varie considérablement selon la taille du problème ($N$). Aucune valeur unique de $p$ n'a fourni de performance constante à toutes les échelles, soulignant la difficulté de régler les formulations réduites pour une application générale.

Signification et Revendications
L'article affirme que la gestion directe des termes d'ordre supérieur via les formulations PUBO offre des avantages distincts par rapport aux méthodes traditionnelles de réduction d'ordre lors de la résolution de problèmes d'optimisation combinatoire sur le matériel de type Ising moderne. La principale signification réside dans la démonstration que :

• Intégrité Structurelle : Préserver la structure originale du problème (PUBO) évite l'expansion artificielle de l'espace de recherche causée par les variables auxiliaires.
• Robustesse : La formulation directe élimine le besoin de régler des coefficients de pénalité, qui sont sensibles à l'échelle du problème et peuvent déstabiliser le processus de recherche.
• Scalabilité : L'approche PUBO maintient une qualité de solution et une stabilité supérieures à mesure que la taille des problèmes augmente, là où l'approche QUBO souffre des effets cumulatifs de l'expansion des variables et de l'application des contraintes.

Les auteurs concluent que bien que la réduction d'ordre ait été efficace pour divers problèmes, la formulation directe PUBO représente une approche prometteuse pour les scénarios d'optimisation pratique à grande échelle, offrant à la fois simplicité structurelle et stabilité computationnelle. L'étude suggère que les développements futurs du matériel et des solveurs devraient continuer à supporter l'exécution directe d'ordres supérieurs pour pleinement exploiter ces avantages dans les applications du monde réel.