Download PDFOpen PDF in browser 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 LocalSolverEasyChair Preprint no. 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, propagation de contraintes, recherche locale, Réparation de solutions, Réseaux d'inégalités, solveur
|