Download PDFOpen PDF in browserRéparation de Solutions Par Propagation de Réseaux D'Inégalités Dans LocalSolverEasyChair Preprint 24982 pages•Date: January 30, 2020AbstractCe 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
|