Réparation de Solutions Par Propagation de Réseaux D'Inégalités Dans LocalSolver

EasyChair Preprint 2498

Abstract

Ce papier s’intéresse à des problèmes dont les contraintes comprennent un réseau d'inégalités linéaires à deux 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 envisagée et implémentée dans LocalSolver pour pallier ce problème consiste en une propagation des contraintes, qui permet de réparer de proche en proche, une contrainte à la fois, une solution prometteuse mais non réalisable.

Keyphrases: Ordonnancement, Réparation de solutions, Réseaux d'inégalités, propagation de contraintes, recherche locale, solveur

@booklet{EasyChair:2498,
  author    = {Léa Blaise},
  title     = {Solution Repair by Inequality Network Propagation in LocalSolver},
  howpublished = {EasyChair Preprint 2498},
  year      = {EasyChair, 2020}}