Réparation de Solutions par Propagation de Réseaux d'Inégalités dans LocalSolver

International audienceThis paper focuses on optimization problems whose constraints comprise a network of binary and ternary linear inequalities. These constraints are often encountered in the fields of scheduling, packing, layout, and mining. Alone, small-neighborhood local search algorithms encounter difficulties on these problems. Indeed, moving from a good solution to another requires small changes on many variables, due to the tight satisfaction of the constraints.The solution we implemented in LocalSolver is a kind of constraint propagation: when the solution obtained after a local transformation is infeasible, we gradually repair it, one constraint at a time. In order to extend the local transformation rather than cancel it, we impose never to go back on the decision to increase or decrease the value of a variable. We show that the success of this repair procedure is guaranteed for a large class of constraints.We apply this method to several scheduling problems, characterized by precedences and disjunctive resource constraints. We give numerical results on the Job Shop, Open Shop and Unit Commitment Problems, and show that our repair algorithm dramatically improves the performance of our local search algorithms.Ce papier s’intéresse à des problèmes d'optimisation dont les contraintes comprennent un réseau d'inégalités linéaires à deux ou trois variables. Parmi ces problèmes, on peut trouver de nombreux problèmes d’ordonnancement, comme celui du Job Shop, mais aussi des problèmes de packing, de layout, ou de mining. Seuls, les algorithmes de recherche locale à petits voisinages se retrouvent en difficulté face à ces problèmes. En effet, les contraintes étant très serrées dans une bonne solution, le passage d’une bonne solution à une autre nécessite de faire de petits changements sur de nombreuses variables.La solution que nous avons implémentée dans LocalSolver pour pallier ce problème consiste en une propagation des contraintes : lorsque la solution obtenue après une transformation locale est non réalisable, celle-ci est réparée de proche en proche, une contrainte à la fois. Afin d'étendre la transformation locale, plutôt que de l'annuler, nous imposons de ne jamais revenir en arrière sur la décision d'augmenter ou de diminuer la valeur d'une variable. Nous montrons que le succès de ce mécanisme de réparation est garanti pour une large classe de contraintes.Nous appliquons cette méthode à plusieurs problèmes d'ordonnancement, caractérisés par des précédences et des contraintes de ressource disjonctive. Des résultats numériques sont donnés sur les problèmes du Job Shop, de l'Open Shop, et du Unit Commitment, et montrent que notre algorithme de réparation améliore significativement les performances de nos algorithmes de recherche locale