Soutenance mémoire
Programmation par contraintes
Nous nous int´ eressons dans cette section ` a la r´ esolution des probl` emes de satisfaction de contraintes (CSP) en domaines finis (1.1.1). Plus particuli` erement, nous abordons les m´ ethodes syst´ ematiques de r´ esolution, par opposition aux strat´ egies heuristiques comme la recherche locale.
Ces m´ ethodes sont bas´ ees sur deux principes, la d´ eduction (1.1.2) ou renforcement de la consistance, pour rendre plus explicite, voire totalement explicite, la formulation d’un probl` eme, et la r echerche (1.1.3), essentiellement par backtracking, qui m` ene ` a une solution par tentatives successives. Les m´ ethodes combinant ces deux principes (1.1.4) sont souvent les plus efficaces : les techniques de consistance servent ` a r´ eduire l’espace de recherche des solutions par pr´ ediction des tentatives infructueuses. Les backtracking intel ligents (1.1.5) pr´ esentent une autre fa¸ con de r´ eduire la recherche, en sachant identifier et exploiter la cause d’un ´ echec. Plus r´ecemment encore, des proc´ edures hybridant backtracking intelligent et techniques de d´ eduction ont ´ et´ e appliqu´ ees avec succ` es. On verra pourtant (1.1.6) qu’il est primordial de trouver une bonne combinaison de ces m´ ethodes, l’efficacit´ e de l’une pouvant ˆ etre annul´ ee par une autre. Nous terminerons par les mani` eres de prendre en compte un crit` ere d’optimisation au moyen de ces techniques de satisfaction de contraintes (1.1.7).
Deduction et filtrage
Propagation de contraintes
La premiere approche pour resoudre un CSP est de proceder par raisonnement logique. Cette approche est appel´ ee propagation de contraintes ou r enforcement de la consistance. Pour reprendre l’exemple de la section pr´ ec´ edente avec trois variables et la contrainte X1 + X2 = X3, si une autre contrainte X1 + X2 = 0 entre dans la d´ efinition du probl` eme, on en d´ eduit que X3 = 0 puis que (0, 0, 0) est l’unique solution du probl` eme. Le raisonnement consiste ainsi ` a inf´ erer d’un ensemble de contraintes, d’autres contraintes plus explicites, voire totalement explicites sur les solutions du probl` eme. Les contraintes unaires ou contraintes de domaines sont parmi les plus explicites puisqu’elles restreignent (ou filtrent ) le domaine de la variable associ´ ee. Autrement dit, elles ´ eliminent des instanciations possibles de la variable. Elles se pr´ esentent le plus souvent comme des contraintes nogoods, Xi 6∈ D 0 i (plutˆ ot que Xi ∈ Di \ D 0 i ) et sont directement traduites par l’ajustement de domaines des variables, Di ← Di \ D 0 i . Supprimer les valeurs des domaines incompatibles avec les contraintes unaires se dit : effectuer la consistance de noeuds. Le probl` eme est r´ esolu en particulier dans deux cas : soit quand le domaine d’au moins une variable est vide (le CSP est insatisfiable), soit quand le domaine de toutes les variables est r´ eduit ` a un singleton. k-consistance
On consid` ere ici un CSP binaire. Une contrainte binaire, liant deux variables Xi et Xj , est dite consistante d’arc si pour toute valeur d i de Xi, il existe une valeur d j dans le domaine de Xj telle que l’instantiation partielle (d i , d j ) satisfait la contrainte, et de mˆ eme en interchangeant Xi et Xj . Par exemple, la contrainte X1 > X2 avec les domaines D1 = D2 = {0, 1, 2} est rendue consistante d’arc en supprimant les valeurs 0 de D1 et 2 de D2. De nombreux algorithmes (AC-1, AC-3,…) effectuent la consistance d’arc d’un CSP binaire. Ils diff` erent sur la mani` ere de propager
la r´ eduction de domaine, dˆ ue ` a la consistance d’une contrainte, aux autres contraintes du probleme.
Dans un CSP consistant d’arcs, toutes les instanciations partielles de deux variables sont des solutions partielles, mais une instanciation compl` ete quelconque n’est pas une solution. Dans l’exemple pr´ ec´ edent, si on consid` ere une troisi` eme variable X3 de domaine {0, 1} et les contraintes X1 + X3 = 2 et X2 + X3 = 1, le probl` eme est toujours consistant d’arc, mais la solution partielle (X1 = 2, X2 = 0) ne peut pas ˆ etre ´ etendue ` a X3. On peut ainsi a jouter une nouvelle contrainte liant X1 et X2, plus forte, X1 = X2 + 1. Pour renforcer la consistance du probl` eme, il faut consid´ erer les instanciations possibles de k variables simultan´ ement. La consistance d’arc se g´ en´ eralise ainsi ` a la k-consistance. Un probl` eme est dit k-c onsistant si toute solution partielle de k − 1 variables peut ˆ etre ´ etendue ` a une solution partielle de k variables en choisissant n’importe quelle valeur dans le domaine de la k-` eme variable. Un probl` eme est fortement k-consistant s’il est consistant pour tout k 0 ≤ k. k = 2 correspond bien ` a la consistance d’arc, tandis que pour k = 3, le probl` eme est dit consistant de chemin. Complexite Maintenir la k-consistance forte d’un CSP binaire est une m´ ethode de r´ esolution compl` ete, dans le sens o` u, si le probl` eme est fortement consistant pour un degr´ e k suffisamment ´ elev´ e, alors on peut facilement d´ eterminer un ordre d’instanciation des variables, et une instanciation progressive des variables dans cet ordre qui m` ene ` a une solution compl` ete [F reuder 1982]. Malheureusement, en g´ en´ eral, mˆ eme la 3-consistance a joute tant de contraintes au probl` eme, que le nouveau degr´ e de consistance ` a atteindre pour r´ esoudre le nouveau r´ eseau de contraintes augmente en proportion.
PROGRAMMATION P AR CONTRAINTES
Pour certaines classes de CSP cependant, la seule consistance d’arc est compl`ete. C’est le cas en particulier des CSP modelisant des problemes d’ordonnancement avec simplement des contraintes de precedence entre les tˆ aches de type Sj − Si ≥ p i (la variable Si designant la date de d´ ebut de la tˆ ache i et la donn´ ee p i , sa dur´ ee). Le graphe des contraintes, sans cycle, peut en effet se d´ ecomposer en niveaux indiquant un ordre sur les arcs pour effectuer la consistance, qui se traduit alors par le calcul de plus long chemins dans le graphe (p. ex. , par l’algorithme de Bellman en O(m)). Plus g´ en´ eralement, dans les CSP temp orels simples o` u les contraintes s’´ ecrivent sous la forme Xj − Xi ≥ d ij , et o` u les domaines sont approxim´ es par des interv alles, si la consistance n’est maintenue qu’aux bornes des domaines (seules les valeurs des extr´ emit´ es des interv alles sont consid´ er´ ees), alors la consistance de chemin aux bornes est compl` ete et peut s’effectuer en O(n 3 ) par l’algorithme de Floyd-W arshall (voir section 2.2.1).
CSP n-aires et contraintes globales
La notion de consistance d’arc s’´ etend aux CSP n-aires de deux mani` eres, ` a la consistance d’arc g´ en´ eralis´ ee (pour une contrainte, toute valeur dans le domaine d’une variable est compatible avec au moins une instanciation des autres variables de la contrainte), et ` a la condition plus forte d’inter consistance (les contraintes sont rendues compatibles deux ` a deux). Ces deux techniques sont g´ en´ eralement tr` es lourdes.
Pour certaines contraintes d’arit´ e superieure, des tests de consistance sp´ ecifiques ont ´ et´ e d´ evelopp´ es, souvent issus de la recherche op´ erationnelle. Ils pr´ esentent l’avantage d’ˆ etre plutˆ ot rapides mais aussi plus efficaces que la consistance d’arc sur les contraintes binarisees. La consistance de la contrainte all-different [Regin 1994], par exemple, est assuree par la recherche d’un couplage maximal dans un graphe. Les techniques de consistance de la contrainte cumulative sont incompletes mais elles permettent d’inferer de nouvelles contraintes unaires (filtrage) et binaires, redondantes mais plus facilement traitees. Ces techniques sont presentees dans le cadre du RCPSP au chapitre suivant.
Backjumping
backjumping rem´ edie ` a ce cas de figure en effectuant directement un backtrack sur une variable dont l’instanciation, en mˆ eme temps que les instanciations pr´ ec´ edentes, cause le conflit (ici on passe directement du noeud (0, 2, 0, ∗) au noeud (1, ∗, ∗, ∗), sans visiter (0, 2, 1, ∗) et (0, 2, 2, ∗)).
Les algorithmes de backjumping [Gaschnig 1979, Prosser 1993] diff` erent entre eux sur leur mani` ere d’identifier la variable la plus haute ` a laquelle on peut directement remonter sans oublier de solution. Il s’agit en particulier de caract´ eriser un conflict-set, un sous-ensemble de variables dont l’instanciation pr´ esente est interdite, le plus petit possible. Quand un ´ echec intervient au moment d’instancier une nouvelle variable Xi , le conflict-set peut ˆ etre, par exemple, l’ensemble des variables li´ ees ` a Xi dans le graphe de contraintes ou bien l’ensemble des variables (d´ ej` a instanci´ ees) qui interviennent dans au moins une contrainte viol´ ee par une instanciation de Xi . Pour assurer la convergence de l’algorithme, le backtrack s’effectue sur la variable du conflict-set la plus recemment instanciee.
Learning
Le backjumping est plus efficace que le backtracking, cependant il n’empˆ eche pas la redondance de la recherche. Dans notre exemple, une partie du travail qui avait ´ et´ e fait sur les variables X2 et X3 pour l’instanciation X1 = 0 sera reproduite pour X1 = 1. La solution consiste ` a « apprendre » de la recherche pass´ ee, c’est ` a dire, ` a enregistrer les informations d´ eduites des branchements d´ ej` a effectu´ es, branchements qui ont donc abouti ` a un ´ echec. Les approches bas´ ees sur ce principe sont regroup´ ees sous la d´ enomination le arning algorithms (ou constraint r ecording,…). Dependency directed backtracking [Stallman 1977], ddb, est le premier algorithme ` a avoir adopt´ e ce principe.
Comme le backjumping, il agit en identifiant, ` a chaque ´ echec rencontr´ e, la cause de l’´ echec, autrement dit un conflict-set pour la derni` ere variable instanci´ ee. En ce sens, backjumping, mais aussi d’autres strat´ egies de backtracking modifi´ e (backmarking, backchecking,… non d´ eveloppees ici) sont des cas particuliers de ddb : la raison de l’´ echec provient des variables dont « d´ epend » la derni` ere variable consid´ er´ ee. Seulement, ddb va en plus m´ emoriser cette cause sous la forme d’une contrainte nogood.
Optimisation
Toutes les m´ ethodes expos´ ees ci-dessus pour la recherche d’une solution d’un CSP s’appliquent ´ egalement ` a la r´ esolution des CSOP constraint satisfaction optimisation problem, quant il s’agit de rechercher une solution satisfaisant toutes les contraintes du probl` eme et qui, de plus, minimise ou maximise un crit` ere donn´ e. Pour prendre l’exemple d’un probl` eme de minimisation, il existe plusieurs fa¸ cons de prendre en compte un crit` ere min f (φ(X)), o` u l’objectif f est fonction de l’instanciation totale φ des variables du probl` eme, et prend ses valeurs dans un ensemble ordonne. Soit f ∗ la valeur minimale de f sur l’ensemble des solutions du probl` eme.
L’approche la plus intuitive consiste ` a r´ esoudre une succession de probl` emes de d´ ecision P .
Le probl` eme de d´ ecision P est initialis´ e avec les contraintes du probl` eme, sans tenir compte du crit` ere d’optimisation, puis r´ esolu. Si P est insatisfiable, alors le probl` eme d’optimisation n’a pas de solution, sinon, tant que P possede une solution φ ∗ (X), on a joute la contrainte f (φ(X)) < f (φ ∗ (X)), pour toute solution φ de P . La derni` ere solution trouv´ ee est une solution optimale du probl` eme. Les contraintes redondantes qui ont ´ eventuellement ´ et´ e g´ en´ er´ ees lors d’une ´ etape de r´ esolution demeurent ´ evidemment valides ` a l’´ etape suiv ante. Les d´ eductions faites ` a une ´ etape peuvent donc ˆ etre conserv´ ees dans P ou pas. Dans une recherche arborescente, cela revient, soit ` a repartir de la racine de l’arbre ` a chaque nouvelle r´ esolution, soit ` a modifier le probl` eme de d´ ecision en cours de recherche, en ajoutant la nouvelle contrainte d` es lors qu’une feuille de l’arbre est atteinte.
Methodes de resolution
Cette int´ egration est facilit´ ee par le fait que les schemas de resolution des deux approches sont similaires. T ous deux sont en effet bas´ es sur trois principes : le partitionnement de l’espace de recherche, l’´ etude de relaxations et l’inf´ erence de nouvelles contraintes.
Le partitionnement de l’espace de recherche est le point de d´ epart de la strat´ egie « diviser et conqu´ erir », la plus employ´ ee ` a la fois en PPC (backtracking) et en PLNE (PSE). T out l’espace est bien sˆ ur consid´ er´ e, mais ` a chaque moment, seule une fraction est ´ etudi´ ee, ` a la recherche d’une solution strictement meilleure que celles trouv´ ees dans les sous-espaces pr´ ec´ edement ´ etudi´ es. Les m´ ethodes arborescentes s´ eparent ainsi progressivement l’espace en parties de plus en plus fines jusqu’` a ce que, soit une solution optimale dans le sous-espace courant est exhib´ ee, soit on prouve qu’aucune meilleure solution n’est contenue dans ce sous-espace.
A l’oppos´ e du partitionnement o` u le probl` eme est simplifi´ e en ´ etant sur-contraint, une relaxation consid` ere le probl` eme sans tenir compte des contraintes les plus dures, ´ elargissant ainsi la recherche, pour la faciliter, ` a des solutions non-r´ ealisables. Si le terme « relaxation » est clairement d´ efini en PLNE, avec en premier lieu la relaxation continue, il est sous-jacent au maintien de la consistance en PPC o` u il d´ esigne simplement l’ensemble des contraintes de domaines (constraint stor e ). Une solution de la relaxation en PPC consiste en une instanciation des variables ` a une valeur quelconque de leurs domaines, mais, ` a moins que l’espace ne soit r´ eduit ` a cette solution uniquement, elle n’est pas explicit´ ee, contrairement ` a la PLNE o` u la relaxation est effectivement r´ esolue. Dans les deux approches, on cherche ` a prouver que la relaxation (et donc le probl` eme original) ne contient pas de (meilleure) solution : en PPC, si le domaine d’une variable est vide ; en PLNE, si la solution optimale de la relaxation est moins bonne que la solution courante du probl` eme.
Enfin, pour resserrer la formulation de la relaxation, de nouvelles contraintes peuvent ˆ etre inf´ er´ ees des contraintes initiales du probl` eme et a jout´ ees ` a la relaxation. Cela se traduit, en PLNE, par la g´ en´ eration de coupes pour le programme lin´ eaire relˆ ach´ e, et en PPC, par les techniques de filtrage et la propagation de contraintes induisant une r´ eduction des domaines des variables.
Ce sch´ ema modulaire commun pr´ esente une voie d’unification des deux approches puisque, par exemple, dans une m´ ethode arborescente, la relaxation ` a chaque noeud peut ˆ etre r´ esolue alternativement ou simultan´ ement par propagation de contraintes ou par programmation lin´ eaire. De mˆ eme, les contraintes inf´ er´ ees par l’une des deux m´ ethodes peuvent ´ eventuellement ˆ etre traduites puis utilis´ ees par l’autre. Ainsi, la plupart des m´ ethodes coop´ eratives emploient le pouvoir d’inf´ erence de la PPC pour d´ eduire les coupes d’une relaxation formul´ ee par un programme lin´ eaire.
A son tour, le programme lin´ eaire renvoie alors une instanciation compl` ete des variables proche d’une solution optimale, permettant de guider la recherche mais aussi de supprimer le noeud s’il est sub-optimal.
|
Table des matières
Introduction
1 Interactions entre programmation lineaire et programmation par contraintes
1.1 Programmation par contraintes
1.1.1 Problemes de satisfaction de contraintes
1.1.2 Deduction et filtrage
1.1.3 Recherche syst´ ematique
1.1.4 Evitement des conflits
1.1.5 R´ eparation des conflits
1.1.6 Am´ elioration du backtracking ?
1.1.7 Optimisation
1.2 Programmation lin´ eaire en nombres entiers
1.2.1 Programmation lin´ eaire
1.2.2 Contraintes d’int´ egralit´ e
1.2.3 Relaxations et d´ ecompositions
1.3 Approches Hybrides PPC-PLNE
1.3.1 Comparaison des approches
1.3.2 Modes d’int´ egration
1.3.3 Sch´ emas de coop´ eration
1.3.4 Backtracking intelligent, principe de r´ esolution et programmation lin´ eair
2 Le probleme d’ordonnancement de projet a contraintes de ressources
2.1 Description du RCPSP
2.1.1 D´efinition
2.1.2 Complexite
2.1.3 Exemple
2.1.4 Applications et cas particuliers
2.1.5 V ariantes et extensions du mod` ele classique
2.2 R` egles d’ajustement
2.2.1 Contraintes temporelles et propagation
2.2.2 Ensembles disjonctifs
2.2.3 Contraintes cumulatives
2.2.4 Raisonnement energetique
2.2.5 T riplets symetriques
2.2.6 Shaving
2.3 Formulations lineaires
2.3.1 Temps continu
2.3.2 Temps discretise
2.4 Revue de la litt´erature
2.4.1 Benchmarks
2.4.2 Sch´ emas de branchement
2.4.3 Evaluation par propagation de contraintes
2.4.4 Bornes inf´ erieures issues de la programmation lineaire
3 Calcul de Bornes Inf´ erieures par Relaxation Lagrangienne
3.1 Relaxation lagrangienne du mod` ele des ensembles admissibles
3.1.1 Problemes de sac a-dos multidimensionnels
3.1.2 Ordonnancement de projet avec couts dependant des dates de debut
3.1.3 Saut de dualite
3.2 Relaxation lagrangienne du mod` ele pr´ eemptif
3.2.1 F ormulation pr´ eemptive
3.2.2 G´ en´ eration de colonnes
3.2.3 Relaxation lagrangienne
3.3 D´ etails d’impl´ ementation
3.3.1 Bornes constructives et destructives .
3.3.2 Algorithme de filtrage et pretraitement
3.3.3 Resolution du dual lagrangien
3.4 Resultats exp´ erimentaux
4 Calcul de Bornes Inf´ erieures par G´ en´ eration de Coupes
4.1 G´ en´ eration d’in´ egalit´ es valides par lifting
4.2 Coupes pour le mod` ele disjonctif en temps continu
4.2.1 F ormulation lin´ eaire et relaxation
4.2.2 Pr´ etraitement par PPC
4.2.3 Coupes de s´ equencement issues du shaving
4.2.4 Coupes de distance issues du shaving
4.2.5 Coupes de chemin issues du shaving
4.2.6 Coupes de clique et edge-finding
4.3 Coupes pour le mod` ele en temps discr´ etis´ e
4.3.1 F ormulation lin´ eaire et relaxation
4.3.2 Pr´ etraitement par PPC
4.3.3 Coupes de cliques
4.3.4 Coupes de distance issue du shaving
4.4 Coupes pour le mod` ele pr´ eemptif sur les ensembles admissibles
4.4.1 Coupes ´ energ´ etiques
4.4.2 Coupes non-pr´ eemptives
4.4.3 Coupes de precedence
4.5 Resultats experimentaux
4.5.1 Modeles en temps continu et en temps discretise
4.5.2 Bornes inf´ erieures constructives
4.5.3 Bornes inf´ erieures destructives
4.5.4 Mod` ele pr´ eemptif sur les ensembles admissibles
4.5.5 Comparaison des bornes destructives
5 Resolution optimale du RCPSP par resolution search
5.1 Resolution search
5.1.1 Notations et Preliminaires
5.1.2 Preuve par résolution en logique propositionnelle
5.1.3 Principe de resolution et methodes d’enumeration implicite
5.1.4 Premier exemple
5.1.5 Gestion de la famille des nogoods
5.1.6 Preuve de convergence
5.2 Application basique ` a la formulation du RCPSP en temps discretise
5.2.1 Schema d’application
5.2.2 R´ esultats exp´ erimentaux
5.3 Proposition d’application avanc´ ee au RCPSP
5.3.1 Branchement bas´ e sur les sch´ emas d’ordonnancement
5.3.2 Am´ eliorations de resolution search
5.4 Discussion autour de resolution search
5.4.1 Avantages et Inconvenients
5.4.2 Perspectives
Conclusion
Liste des algorithmes
T able des figures
Liste des tableaux
Bibliographie
