Download PDFOpen PDF in browser
EN
The title and the abstract of this preprint are also available
in English

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

EasyChair Preprint 2498

2 pagesDate: January 30, 2020

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:2498,
  author    = {Léa Blaise},
  title     = {Solution Repair by Inequality Network Propagation in LocalSolver},
  howpublished = {EasyChair Preprint 2498},
  year      = {EasyChair, 2020}}
Download PDFOpen PDF in browser