Résumé technique : QAOA respectant les contraintes pour la planification du personnel

Énoncé du problème

La planification du personnel est un problème d'optimisation combinatoire caractérisé par des contraintes opérationnelles strictes, telles que les exigences de couverture quotidienne et les restrictions sur les jours de travail consécutifs. Bien que les méthodes classiques (programmation entière, métaheuristiques) aient connu un certain succès, la croissance exponentielle de l'espace de recherche avec la taille du système motive l'utilisation d'algorithmes quantiques, spécifiquement l'algorithme d'optimisation approximative quantique (QAOA).

Les formulations QAOA standard pour les problèmes contraints reposent généralement sur des approches basées sur les pénalités. Dans ce cadre, les contraintes strictes sont imposées en ajoutant des termes de pénalité énergétique au hamiltonien de phase. Cette approche présente des inconvénients significatifs :

1. Sensibilité au calibrage : La performance dépend fortement du choix des coefficients de pénalité.
2. Distorsion du paysage : Des pénalités élevées peuvent distordre le paysage d'optimisation.
3. Accessibilité de l'infaisabilité : Les configurations infaisables restent dynamiquement accessibles pendant l'évolution variationnelle, permettant à l'amplitude quantique de s'accumuler dans des régions qui devraient être interdites, même si elles sont énergétiquement pénalisées.

L'article répond au besoin d'un cadre QAOA respectant les contraintes où les contraintes strictes sont intégrées directement dans le hamiltonien de mélange (mixer), confinant l'évolution quantique strictement au sous-espace faisable.

Méthodologie

1. Formulation mathématique

Les auteurs formulent un problème de planification de personnel binaire avec $N$ travailleurs sur $D$ jours. L'état est représenté par une matrice binaire $q \in \{0,1\}^{N \times D}$, où $q_{n,d}=1$ indique qu'un travailleur $n$ est assigné le jour $d$.
Le problème consiste à minimiser un coût d'assignation $C(q)$ soumis à deux contraintes strictes :

• Couverture quotidienne : $\sum_{n} q_{n,d} = W_d$ (effectif fixe par jour).
• Pas de service consécutif : $q_{n,d} q_{n,d+1} = 0$ (aucun travailleur ne travaille deux jours de suite).

L'espace de configuration est structuré de manière hiérarchique :

• $\mathcal{H}$ : L'espace de Hilbert binaire complet.
• $\mathcal{F}_{cov}$ : Le sous-espace satisfaisant uniquement la contrainte de couverture.
• $\mathcal{F}_{full}$ : Le sous-espace satisfaisant les deux contraintes (la variété pleinement faisable).

2. Constructions de mélangeurs (Mixers)

L'article propose une hiérarchie de hamiltoniens de mélange correspondant aux secteurs faisables :

• Penalty-X (Référence) : Utilise un mélangeur de champ transverse standard ($\sum X_{n,d}$) et impose les deux contraintes via des termes de pénalité énergétique dans le hamiltonien de phase.
• Coverage-XY : Utilise un mélangeur XY qui conserve le nombre d'excitations (nombre de travailleurs) pour chaque jour. Cela préserve $\mathcal{F}_{cov}$ dynamiquement mais nécessite toujours un terme de pénalité pour la contrainte de non-consecutivité.
• Guarded-XY (Proposé) : Introduit un opérateur de transition gardé qui intègre les deux contraintes directement dans le mélangeur.
  • Mécanisme de garde : Pour un échange proposé entre deux travailleurs $u$ et $v$ au jour $d$, l'opérateur inclut un "projecteur de garde" $\hat{G}$. Ce projecteur évalue l'état des jours voisins ($d-1, d+1$) et s'annule si l'échange créerait une violation de service consécutif.
  • Résultat : Le mélangeur $\hat{H}_{M}^{guard}$ génère des transitions uniquement au sein de $\mathcal{F}_{full}$. Par conséquent, le hamiltonien de phase se réduit à la fonction objectif seule ($\hat{H}_C = \hat{H}_{obj}$), éliminant ainsi le besoin de calibrage des pénalités de contraintes strictes.

3. Accessibilité et extension de type "Tight-Pattern"

Les auteurs identifient que la préservation exacte de la faisabilité ne garantit pas l'accessibilité (connectivité du graphe faisable). Dans les segments de charge de travail "saturés" où $W_d + W_{d+1} = N$, la contrainte de non-service consécutif force des assignations complémentaires, pouvant fragmenter le graphe faisable en composantes déconnectées.

• Solution : Une extension de type "tight-pattern" est introduite. Elle ajoute des opérateurs d'échange collectifs qui échangent des motifs d'assignation alternés entiers à travers les segments saturés, restaurant la connectivité au sein de $\mathcal{F}_{full}$ sans violer les contraintes.

4. Protocole de simulation

L'étude utilise des simulations exactes de l'état vectoriel sur une instance de référence ($N=4, D=4$, charge de travail $W=[2,1,2,1]$).

• Comparaisons : Penalty-X, Coverage-XY, et Guarded-XY (avec et sans extension tight-pattern).
• Optimisation : Évaluée sous les objectifs de Valeur d'Espérance et de Valeur à Risque Conditionnelle (CVaR, $\alpha=0.2$).
• Calibrage : Les coefficients de pénalité pour les méthodes de référence ont été rigoureusement calibrés pour assurer une comparaison équitable, tandis que Guarded-XY ne nécessitait aucun calibrage.
• Initialisation : Les tests comprenaient des superpositions uniformes sur les secteurs faisables et des états faisables localisés.

Résultats clés

1. Élimination du calibrage des pénalités

L'approche Guarded-XY élimine avec succès la nécessité de régler les coefficients de pénalité des contraintes strictes. Le hamiltonien de phase ne contient que le coût d'assignation, simplifiant le paysage variationnel.

2. Qualité supérieure de la distribution de sortie

• Faisabilité : Guarded-XY maintient $P_{full} = 1$ (100 % de probabilité d'états faisables) par construction. En revanche, Coverage-XY et Penalty-X présentent des fuites dans les régions infaisables ($P_{full} < 1$), même avec des pénalités optimisées.
• Concentration de l'optimal : Sous optimisation CVaR, Guarded-XY produit systématiquement la plus haute probabilité d'échantillonner le planning exact optimal ($P_{opt}$) par rapport aux autres méthodes.
• Qualité de la solution : Guarded-XY atteint le ratio d'approximation moyen ($\langle r \rangle$) le plus élevé. L'article note que les méthodes de préservation partielle des contraintes (Coverage-XY) attribuent souvent une probabilité significative à des calendriers infaisables qui possèdent des coûts bruts artificiellement bas, ce qui détourne l'optimisation des vrais optima faisables.

3. Sensibilité structurelle et initialisation

• Charges de travail saturées : L'extension tight-pattern s'avère nécessaire pour maintenir la connectivité dans les scénarios de charge de travail hautement saturés, empêchant la fragmentation du graphe faisable.
• Initialisation : Le cadre reste efficace lorsqu'il est initialisé à partir d'un seul planning faisable localisé (plutôt qu'une superposition uniforme), à condition d'appliquer quelques couches de mélangeur de "propagation". Cela suggère une stratégie d'initialisation compatible avec le matériel.
• Scalabilité : Les tests sur des instances avec des nombres de qubits variables (12, 16, 20) montrent que, bien que la probabilité optimale brute diminue avec la taille (en raison de l'expansion de l'espace de recherche), l'enrichissement de l'état optimal ($\eta_{opt}$) reste élevé, indiquant que l'algorithme amplifie systématiquement la solution optimale par rapport à un échantillonnage uniforme.

Signification et revendications

L'article affirme présenter la première formulation QAOA respectant les contraintes pour la planification du personnel où les deux contraintes de planification strictes sont intégrées directement dans le hamiltonien de mélange.

Les principales contributions incluent :

1. Changement de gestion des contraintes : Déplacement de l'application des contraintes du hamiltonien de phase énergétique vers le mélangeur dynamique, garantissant que l'évolution est confinée à la variété faisable par construction.
2. Séparation des principes de conception : Distinction entre la préservation de la faisabilité (garantir que le mélangeur reste dans l'ensemble faisable) et la conception de l'accessibilité (garantir que l'ensemble faisable est connecté). Le mélangeur Guarded-XY gère la première, tandis que l'extension tight-pattern gère la seconde.
3. Généralisabilité : Les auteurs affirment que le cadre de graphe de transition et le principe de transition gardée sont applicables à une large classe de problèmes d'optimisation quantique contraints (planification, routage, allocation de ressources) où la faisabilité peut être caractérisée par des règles de transition locales.

Ce travail démontre que les mélangeurs respectant les contraintes peuvent produire des distributions de sortie de meilleure qualité et une plus forte concentration sur les solutions optimales par rapport aux méthodes basées sur les pénalités, sans la sensibilité au calibrage des coefficients de pénalité.