Solution Repair by Inequality Network Propagation in LocalSolver

EasyChair Preprint 2498

Abstract

This paper focuses on problems whose constraints comprise a network of two-variable linear inequalities. Among these problems are many scheduling problems, such as the Job Shop Problem, but also packing, layout, or mining problems. Alone, small neighborhood local search algorithms encounter difficulties on these problems. Indeed, the constraints being very tight in a good solution, moving from a good solution to another requires small changes on many variables.

The solution we envisioned and implemented in LocalSolver to tackle this problem is a kind of constraint propagation: a promising but infeasible solution is gradually repaired one constraint at a time.

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}}