Y. Caseau 19/04/23 1

Challenge ROADEF: Combinaison de Propagation de Contraintes et de

Méta-Heuristiques

Yves Caseau & all

Bouygues – e-lab

Francoro III

Y. Caseau 19/04/23 2

Introduction Objectif: Instancier un patron de conception

• Auto-adaptabilité, économie de développement Application précédente: VRPTW

• CP’99, CP-AI-OR’01

• TSPTW + (LDS,LNS,Ejection)

PPCheuristiques

Push

Pull

Méta-heuristiques

Domain-dependent Domain-independent Learning Tool

LNS

LDS

E.Tree

CombinaisonDe

Méta-heuristiques

AlgorithmeHybride

Y. Caseau 19/04/23 3

Etat d’Avancement Utilisation de la PPC pour trouver une solution

• Modèle tiré de l’ordonnancement• Propagation de contraintes Ad Hoc

Application de trois méta-heuristiques• « Shaving » (consistance forte)• « Shuffling » = Large Neighborhood Search• « Limited Discrepency Search » = Introduction controlée du

Branch&Bound.

Travail en cours sur l’auto-réglage• Confirmation: le réglage représente 80% du travail• Limites de temps sur l’apprentissage• Besoin d’enrichir le modèle courant

Y. Caseau 19/04/23 4

Modèle d’Ordonnancement Le problème d’attribution de fréquence est considéré

comme un problème d’ordonnancement• (chemin, fréquence) => (tache, date)

Possibilité de réutiliser différentes techniques• Propagation (distance => contrainte classique disjonctive de

partage de ressource)• Branchement (ordre chronologique)

La notion d’intervalles de taches se retrouve avec les cliques de chemins• Possibilité d’utiliser des techniques d’edge-finding (consistance,

propagation, branchement)• Résultats décevants

Y. Caseau 19/04/23 5

Règles de Propagation Contraintes:

• Ordonnancement avec distance• Contraintes d’égalité, de différence• Sous-problème 2-SAT induit par la polarité• La distance varie suivant la polarité:

couplage dynamique 2-SAT & ORDO

Modèle classique de PPC• Fenêtre de temps + domaines exacts pour la polarité• Ordonnancement des contraintes disjonctives

Propagation des contraintes• Propagation classique (2SAT + Ordo)• Couplage 2SAT/ Ordo• Implémentation Ad Hoc vs. Choco

Y. Caseau 19/04/23 6

Consistance sur la Polarité Choix stratégique

• Contraintes globales• Consistance globale

Consistance globale (« shaving  », « singleton consistency »)• Essayer chaque valeur d’un domaine individuellement, propager et

rejeter les valeurs qui provoquent une contradiction

• Technique de choix en ordonnancement (Carlier&Pinson, Martin & Shmoys)

Utilisation systématique pour la polarité• Appelé après chaque décision d’insertion d’une tâche dans la solution

courante

• À chaque changement de la date d’insertion

• Remplace un algorithme spécialisé (marquage)

• Couplage avec le sous-problème d’ordonnancement

Y. Caseau 19/04/23 7

Consistance sur l’ordonnancement

Shaving sur un domaine intervalle• Exclusion des valeurs extrèmes• Recherche d’un point fixe• Très couteux => testé mais pas utilisé

Shaving sur un ordre• Pour chaque disjonction, on teste les deux branches de

l’alternative et on élimine les branches impossibles• Forme simplifiée de la disjonction constructive• Appliqué à chaque insertion sur les disjonctions concernées• Appliqué à chaque changement de la date d’insertion de façon

globale

L’utilisation du « shaving » est un élément clé de notre approche

Y. Caseau 19/04/23 8

Algorithme Glouton

Ordonnancement chronologique classique• Recherche d’une suite d’évènements• Pour chaque date, on calcule un ensemble de candidats• Sélection des candidats retenus en « look-ahead »

– Propagation du choix et minimisation d’une fonction globale• Résultat = solution partielle + tâches rejettées

Obtention de bornes inférieures• Pour chaque valeur de K, la propagation est appliqué au

problème initial• Lorsqu’une contradiction survient, on en déduit une borne

inférieure (cf. résultats en ordonnancement)• Sur le challenge, la borne inférieure est exacte pour tous les

problèmes => puissance de la propagation.

Y. Caseau 19/04/23 9

Algorithme de branchement LDS

L’algorithme de branchement classique consiste à énumérer les sous-ensembles de tâches affectées à une date T.

Le « Limited Discrepency Search » consiste à ne remettre en cause l’algorithme glouton que dans certains cas• Le nombre de remise en cause (discrepencies) est bornée et

faible• Excellents résultats sur de nombreux problèmes

Application:• Décider de retarder une tâche qui pourrait être affectée à T• Aucun branchement sur la polarité !

Y. Caseau 19/04/23 10

Heuristiques de LDS

Fondé sur le graphe d’exclusion local à l’intérieur de l’ensemble candidat• Branche (t reporté) => t est en conflit avec au moins 3 autres

tâches• (t reporté) => une autre tâche est placée (cut)

Poids prédominant des premiers choix• Focalise l’effort LDS sur les premiers moments

Priorité donnés aux taches les plus importantes dans l’ensemble candidat

Résultats probants (amélioration) mais décevants

Y. Caseau 19/04/23 11

Application du LNS

Large Neighborhood Search• Voisinage obtenu par reconstruction d’une solution• On enleve un fragment de la solution• On le ré-insère (par Branch&Bound = LDS)• Très bons résultats en Jobshop

Application • Variable: de la réparation jusqu’à la re-construction à partir d’un

noyau • Bien adapté à l’optimisation de solutions partielles, on essayer

de re-injecter un fragment plus grand que celui qu’on enlève• Importance de l’heuristique de sélection du « fragment »

(exemple: [Shaw98])• Meta-meta-heuristique: hill climbing

Y. Caseau 19/04/23 12

Heuristiques de LNS

Analyse des conflits entre une tâche à insérer et une solution partielle• Chaque domaine (vide) est décomposé en sous-intervalles

avec leurs causes (autres tâches)• On en déduit une liste ordonnée de voisins en conflits

Chaque fragment est construit récursivement autour d’une tâche externe (à insérer dans la solution partielle)• Les fragments font de 10 à 85% de la solution initiale• Les choix sont randomisés

Un poids est affecté aux tâches externe de façon à éviter les cycles d’éjections • Possibilité de stratégie taboue

Y. Caseau 19/04/23 13

Optimisation des Contraintes Molles

La valorisation utilisée dans l’algorithme Glouton et le LDS fait intervenir faiblement les contraintes molles

Les résultats obtenus ne sont pas bons! Nous utilisons une phase de post-optimisation avec le

LNS:• En utilisant comme source du fragment les taches impliquées

dans des contraintes molles violées• En renforçant aléatoirement le statut de certaines de ces

contraintes violées (deviennent dures)• Ce schéma donne des résultats corrects

Y. Caseau 19/04/23 14

Stratégie de Contrôle

(1) K = 0

(2) Augmenter K => la propagation ne déclenche pas de contradiction

(3) Trouver une solution avec un LDS

(4) Si le nombre de tâches externes est trop grand (> 80)augmenter K => aller à (3)

(5) Sinon appliquer LNS avec des fragments de tailles variables jusqu’à 80% du temps, ou jusqu’à l’obtention d’une solution faisable

(6) Si la solution est faisable, post-optimiser (contraintes molles), sinon relacher K (=> K + 1) et répeter (5)

Y. Caseau 19/04/23 15

Outils de développement

Utilisation de CLAIRE• Langage conçu pour le développement d’algorithmes hybrides

d’optimisation combinatoire• 500 lignes pour chaque module (propagation + greedy) et (LNS

+ LDS)• Vers la mise au point d’une librairie de classe pour les méta-

heuristiques

Mise au point = 80% de l’effort dans le réglage des paramètres

Apprentissage• L’approche utilisée pour le VRPTW nécessite 10000 fois le

temps de calcul de l’algorithme !

Y. Caseau 19/04/23 16

Conclusion Un problème très intéressant et difficile du point de vue

de la PPC. Un bon exemple d’application de notre patron de

conception• Temps de développement réduit• Résultats compétitifs

La question de l’auto-réglage reste ouverte pour des algorithmes dont le temps de calcul est long.