Problème d’optimisation sous contraintes

Dans de nombreux cas, des relations de préférence entre les solutions d’un CSP existent eu égard aux critères fixés par le décideur. L’optimisation consiste alors rechercher des solutions optimales d’un CSP au regard des relations de préférence du décideur. Nous nous intéresserons uniquement à des problèmes d’optimisation combinatoire monocritère, c’est-à-dire lorsque l’ensemble des solutions est discret et qu’il y a un critère d’optimalité unique. Ce critère d’optimalité est généralement associé à lamaximisation/-minimisation d’une fonction objectif d’un sous-ensemble de variables vers les entiers.
Un problème d’optimisation sous contraintes (COP) est un CSP augmenté d’une fonction objectif f. Cette fonction est souvent modélisée par une variable dont le domaine est défini par les bornes supérieures et inférieures de f.

Exemple : le problème des n reines

Au cours de ce chapitre, nous illustrerons divers concepts sur le problème des n reines. Le but de ce problème, inspiré du jeu d’échec, est de placer n reines sur un échiquier de dimension n × n de manière à ce qu’aucune ne soit en prise. Deux reines sont en prises si elles sont sur la même ligne, la même colonne ou la même diagonale. Un échiquier classique comporte 8 lignes et 8 colonnes. Ce problème désormais classique est devenu une référence de mesure de performance des systèmes grâce à un énoncé simple masquant sa difficulté. Un modèle classique sans contraintes globales est défini dans la figure 2.1. En observant que deux reines ne peuvent pas être placées sur la même colonne, on peut imposer que la reine i soit sur la colonne i. Ainsi, la variable l i de domaine {1, . . . , n} représente la ligne où est placée la reine dans la colonne i. Les contraintes (2.1) imposent que les reines soient sur des lignes différentes alors que les contraintes (2.2) et (2.3) imposent que deux reines soient placées sur des diagonales différentes.

Méthodes de résolution

Les méthodes de résolution des CSPs sont génériques, c’est-à-dire qu’elles ne dépendent pas de l’instance à résoudre. Cependant, des techniques dédiées améliorent la résolution de différentes classes de problèmes. Dans le contexte d’un CSP statique et discret, nous discuterons de la réduction de l’espace de recherche par des techniques de consistance couplées si nécessaire à un algorithme de recherche arborescente.
Dans un premier temps, nous présentons deux algorithmes de recherche arborescente dont le comportement peut être amélioré par des techniques de consistance ou des contraintes globales. Ensuite, nous décrivons plusieurs algorithmes avancés, prospectifs ou rétrospectifs, dans le contexte d’une recherche complète par séparation et évaluation.

Algorithmes simples de recherche

L’algorithme generate-and-test énumère les affectations totales et vérifie leur consistance, c’est-à dire qu’aucune contrainte n’est violée. En général, les affectations sont énumérées grâce à une recherche arborescente qui instancie itérativement les variables. Cet algorithme ne réveille les contraintes que lorsqu’une affectation est totale, mais considère par contre un nombre exponentiel d’affectations le rendant impraticable même pour des problèmes de petite taille. Des résultats de complexité ont montré que prouver la satisfiabilité d’un CSP était un problème NP-complet mais qu’exhiber une solution admissible ou optimale était un problème NP-difficile.
L’algorithme simple retour arrière (backtrack ) [10] étend progressivement l’affectation vide en instanciant une nouvelle variable à chaque étape. L’algorithme vérifie alors que l’affectation partielle étendue est consistante avec les contraintes du problème. Dans le cas contraire, la dernière instanciation faite est remise en cause et l’on effectue une nouvelle instanciation. De cette manière, l’algorithme construit un arbre de recherche dont les nœuds représentent les affectations partielles testées. Cet algorithme teste l’ensemble des affectations possibles de manière implicite, c’est-à-dire sans les générer toutes. Le nombre d’affectations considéré est ainsi considérablement réduit, mais en revanche, la consistance des contraintes est vérifiée à chaque affectation partielle.
La figure 2.3 illustre la résolution du problème des 4 reines par l’algorithme backtrack qui place à chaque point de choix la première reine libre en partant de la gauche à la première position disponible en partant du haut. À chaque point de choix, l’affectation partielle courante est étendue en instanciant les variables et les valeurs selon l’ordre lexicographique. Dans ce cas précis, toutes les solutions symétriques sont éliminées en imposant que la première reine (à gauche) soit placée dans la partie haute de l’échiquier.
Remarquez que la recherche continue après la découverte de la première solution puisqu’on cherche toutes les solutions à une symétrie près. L’algorithme generate-and-test consiste à déployer l’arbre entier.
La découverte redondante d’inconsistance locale due à la perte d’information sur l’inconsistance d’affectation partielle dégrade les performances de l’algorithme backtrack . Nous discuterons donc de l’utilisation active des contraintes pour supprimer les inconsistances, des algorithmes prospectifs qui anticipent les prochaines affectations pour réduire les domaines, et rétrospectifs qui utilisent les conflits pour remettre en cause les choix antérieurs.

Stratégies de recherche

Les techniques de consistance étant incomplètes, les algorithmes de recherche résolvent les disjonctions restantes par des méthodes de séparation. Le nombre de nœuds et le temps de résolution d’un modèle peuvent varier considérablement en fonction de la méthode de séparation et des heuristiques de sélection employées.

Méthodes de séparation

À chaque création d’un nœud de l’arbre de recherche, l’algorithme crée un point de choix, c’est-à dire qu’il considère successivement la résolution de sous-problèmes disjoints dans chaque branche. Dans un point de choix binaire, on peut considérer l’ajout d’une contrainte C dans la première branche et ¬C dans la seconde grâce à la réversibilité des contraintes. Par exemple, la technique de variable ordering impose une relation d’ordre sur une paire de variables x et y : x < y ∨ x ≥ y. Cependant, on peut se limiter à considérer des points de choix opérant des restrictions sur le domaine d’une unique variable non instanciée. En effet, le mécanisme de réification d’une contrainte, c’est-à-dire l’association d’une variable booléenne indiquant la satisfaction de la contrainte, permet la transformation d’un point de choix sur des contraintes en un ou plusieurs autres portant sur des variables. De plus, la plupart des algorithmes rétrospectifs ou techniques d’apprentissage utilisent des variables car leur domaine est restauré lors d’un retour arrière alors que les contraintes sont généralement supprimées. Les techniques standards opèrent généralement une restriction sur le domaine d’une seule variable x ∈ X choisie par une heuristique de sélection de variable.
Par exemple, un point de choix appliquant le standard labeling considère l’affectation d’une valeur v ∈ D(x) à la variable ou bien sa suppression : x = v ∨ x 6 = v. De la même manière, un point de choix appliquant le domain splitting restreint la variable x à des valeurs inférieures ou supérieures à une valeur seuil v ∈ D(x) : x < v ∨ x ≥ v. La valeur v est choisie par une heuristique de sélection de valeur.
On peut définir des branchements n-aires à partir des précédents en testant une valeur différente dans chaque branche (standard labeling ) et en restreignant les valeurs de x à des intervalles disjoints dans chaque branche (domain splitting).
On appelle variables de décision, un sous-ensemble de variables dont l’instanciation provoque une affectation totale par propagation. Les méthodes de séparation peuvent limiter la profondeur de l’arbre en se restreignant à un sous-ensemble de variables de décision. Par exemple, les variables l i du modèle des n reines en figure 2.5 sont des variables de décision. Cependant, on peut leur substituer les variables auxiliaires xi et y i qui sont aussi des variables de décision. Par défaut, toutes les variables du problème sont des variables de décision.
La programmation par contraintes offre donc un cadre flexible pour la définition de méthodes de séparation de par la structure des points de choix et l’utilisation d’heuristiques de sélection évoquée ci-dessous.

Heuristiques de sélection

Les heuristiques de sélection sont des règles qui déterminent (a) l’ordre suivant lequel on va choisirles variables pour les instancier,  ainsi que (b) l’ordre suivant lequel on va choisir les valeurs pour les variables. Une bonne heuristique de sélection peut avoir un impact important sur la résolution d’un problème de décision et accélérer l’obtention de solutions (la détection d’échecs en cas de problèmes insolubles) pendant l’exploration de l’espace de recherche. Les algorithmes de résolution qui utilisent des heuristiques de sélection assurent, dans la plupart des cas, une résolution plus rapide que celle obtenue par des algorithmes sans heuristique de sélection. Une heuristique est statique si l’ordre est préalablement fixé ou dynamique s’il évolue au cours de la résolution. Les heuristiques de sélection sur des variables ensemblistes ne seront pas abordées dans le cadre de cette thèse.

Sélection de variable

Les heuristiques de sélection de variable ont souvent une influence critique sur la forme et la taille de l’arbre de recherche. Cette influence est toutefois plus restreinte lorsqu’on cherche toutes les solutions d’un CSP. De nombreuses heuristiques observent le principe first-fail énoncé par Haralick et Elliott [16] : « To succeed, try first where you are most likely to fail » (Pour réussir, essaie d’abord là où il est le plus probable d’échouer). Les heuristiques dynamiques exploitent souvent les informations sur les domaines et degrés des variables. On retrouve entre autres les heuristiques suivantes. lex ordonne les variables selon l’ordre lexicographique (statique).

Procédure bottom-up

La procédure bottom-up incrémente la borne inférieure lb de la fonction objectif lorsque le problème de satisfaction de contraintes solve(lb, lb + 1) est insatisfiable jusqu’à ce qu’une solution optimale soit trouvée. Lorsque le COP est satisfiable, la procédure résout opt − lb problèmes insatisfiables avant de résoudre un unique problème satisfiable fournissant une solution optimale. Le COP est implicitement considéré comme étant satisfiable en regard de l’efficacité amoindrie de la procédure dans le cas contraire.
En effet, lorsque le COP n’est pas satisfiable, il est plus efficace de résoudre directement le problème solve(lb, ub) plutôt que ub − lb sous-problèmes disjoints. La construction des arbres de recherche pour des problèmes voisins peut dégrader les performances à cause de la propagation redondante et de la nécessité de recréer les points de choix. En fait, L’efficacité de bottom-up dépend de la qualité de la borne inférieure initiale et de la capacité de l’algorithme de résolution à prouver l’insatisfiabilité des sous-problèmes, généralement grâce à des techniques avancées de propagation et de filtrage. Il peut être intéressant d’utiliser une borne inférieure dédiée fournissant une garantie, de relever le niveau de consistance ou de renforcer la propagation par des techniques prospectives pour réduire la taille des arbres de recherche et par conséquent les redondances. Par contre, l’algorithme dispose d’informations plus précises car la valeur de l’objectif est fortement contrainte.
Nous verrons que le nombre de sous-problèmes traités par bottom-up sur l’exemple de la figure 2.9 est plus élevé que celui des autres procédures. En pratique, la difficulté moindre des premières étapes peut compenser le nombre plus élevé de sous-problèmes.

Table des matières
Remerciements 
Table des matières 
1 Introduction 
1.1 Objectifs
1.2 Contribution
1.3 Organisation du document
1.4 Diffusion scientifique
I Contexte de l’étude
2 Programmation par contraintes 
2.1 Modélisation d’un problème par des contraintes
2.1.1 Problème de satisfaction de contraintes
2.1.2 Problème d’optimisation sous contraintes
2.1.3 Exemple : le problème des n reines
2.2 Méthodes de résolution
2.2.1 Algorithmes simples de recherche
2.2.2 Filtrage et propagation des contraintes
2.2.3 Contraintes globales
2.2.4 Algorithmes avancés de recherche
2.3 Stratégies de recherche
2.3.1 Méthodes de séparation
2.3.2 Heuristiques de sélection
2.4 Procédures d’optimisation
2.4.1 Procédure bottom-up
2.4.2 Procédure top-down
2.4.3 Procédure dichotomic-bottom-up
2.4.4 Procédures incomplètes
2.5 Solveurs de contraintes
2.6 Conclusion
3 Ordonnancement sous contraintes 
3.1 Tâches
3.2 Contraintes temporelles
3.2.1 Contraintes de précédence
3.2.2 Contraintes de disponibilité et d’échéance
3.2.3 Contraintes de disjonction
3.2.4 Problèmes temporels
3.3 Contraintes de partage de ressource
3.3.1 Contrainte disjonctive
3.3.2 Contrainte cumulative
3.4 Modèle disjonctif
3.5 Placement sous contraintes
3.5.1 Placement en une dimension
3.5.2 Placement en deux dimensions
3.6 Conclusion
4 Ordonnancement d’atelier
4.1 Définition des problèmes d’atelier
4.1.1 Définition des problèmes de base
4.1.2 Variantes et classification de Lawler
4.1.3 Applications
4.2 Résultats de complexité
4.2.1 Problèmes à deux machines
4.2.2 Problèmes à trois machines : la frontière
4.2.3 Cas général
4.2.4 Conclusion
4.3 État de l’art
4.3.1 Jeux d’instances
4.3.2 Méthodes approchées
4.3.3 Méthodes Exactes
4.4 Orientation de nos travaux
5 Ordonnancement d’une machine à traitement par fournées 
5.1 Définition des problèmes de fournées
5.1.1 Définition du problème de base
5.1.2 Variantes et classification de Lawler
5.1.3 Applications .
5.2 Résultats de complexité
5.2.1 Modèle en parallèle
5.2.2 Modèle en série
5.2.3 Conclusion
5.3 État de l’art
5.3.1 Jeu d’instances
5.3.2 Méthodes de résolution
5.4 Orientation de nos travaux
II Contribution
6 Ordonnancement d’atelier au plus tôt 
6.1 Modèle en ordonnancement sous contraintes
6.1.1 Contraintes disjonctives
6.1.2 Contraintes temporelles
6.1.3 Contraintes supplémentaires
6.1.4 Stratégie de branchement
6.2 Algorithme de résolution
6.2.1 Principe de l’algorithme
6.2.2 Solution initiale
6.2.3 Techniques de redémarrage
6.3 Évaluations expérimentales
6.3.1 Réglage des paramètres
6.3.2 Analyse de sensibilité
6.3.3 Comparaison avec d’autres approches
6.4 Conclusion
7 Heuristiques d’arbitrage dans un atelier 69
7.1 Modèles en ordonnancement sous contraintes
7.1.1 Contraintes temporelles
7.1.2 Stratégie de branchement
7.1.3 Notes sur les modèles
7.2 Algorithme de résolution
7.3 Évaluations expérimentales
7.3.1 Problèmes d’open-shop
7.3.2 Problèmes de job-shop
7.4 Conclusion
8 Minimisation du retard algébrique maximal sur une machine à traitement par fournées 
8.1 Modèle en programmation par contraintes
8.2 Description de la contrainte globale sequenceEDD
8.2.1 Relaxation du problème
8.2.2 Filtrage de la variable objectif
8.2.3 Filtrage basé sur le coût du placement d’une tâche
8.2.4 Filtrage basé sur le coût du nombre de fournées non vides
8.3 Stratégie de branchement
8.4 Éxpérimentations
8.4.1 Performance des règles de filtrage
8.4.2 Performance des heuristiques de sélection de valeur
8.4.3 Comparaison avec un modèle en programmation mathématique
8.4.4 Comparaison avec une approche par branch-and-price
8.5 Conclusion
Annexe 8.A : un algorithme quadratique pour le filtrage du placement d’une tâche
9 Implémentation dans le solveur de contraintes choco 
9.1 Le modèle
9.1.1 Variables
9.1.2 Contraintes
9.2 Le solveur
9.2.1 Lecture du modèle
9.2.2 Stratégie de branchement
9.2.3 Redémarrages
9.2.4 Résolution d’un modèle
9.3 Contraintes de choco
9.3.1 cumulative
9.3.2 disjunctive
9.3.3 use Resources (en développement)
9.3.4 precedence
9.3.5 precedence Disjoint
9.3.6 precedence Reified
9.3.7 precedence Implied
9.3.8 disjoint (décomposition)
9.3.9 pack
9.3.10 Reformulation de contraintes temporelles
9.4 Construction du modèle disjonctif
9.4.1 Traitement des contraintes temporelles
9.4.2 Traitement des contraintes de partage de ressource
9.4.3 Déduction de contraintes « coupe-cycle »
9.5 CSP Solver Competition 2009
9.5.1 Catégorie 2-ARY-INT
9.5.2 Catégorie Alldiff+Cumul+Elt+WSum
9.6 Conclusion
10 Conclusion 115
10.1 Problèmes d’atelier
10.2 Problème de fournées
10.3 Solveur choco
Annexes
A Outils choco : développement et expérimentation
A.1 Procédure générique de traitement d’une instance
A.2 Assistant à la création d’un programme en ligne de commande
A.3 Intégration dans une base de données
B Tutoriel choco : ordonnancement et placement
B.1 Gestion de projet : construction d’une maison
B.1.1 Approche déterministe
B.1.2 Approche probabiliste
B.2 Ordonnancement cumulatif
B.3 Placement à une dimension
B.3.1 Traitement d’une instance
B.3.2 Création d’une commande
B.3.3 Cas d’utilisation
C Problème de collectes et livraisons avec contraintes de chargement bidimensionnelles
D Problème d’allocation de ressources et d’ordonnancement pour la maintenance
Bibliographie 
Résumés