Skip to Main content Skip to Navigation
Conference papers

Solution Repair by Inequality Network Propagation in LocalSolver

Léa Blaise 1, 2 Christian Artigues 2 Thierry Benoist 1
1 Innovation 24 & LocalSolver
Innovation 24 & LocalSolver
2 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : This paper focuses on optimization problems whose constraints comprise a network of binary and ternary linear inequalities. These constraints are often encountered in the fields of scheduling, packing, layout, and mining. Alone, small-neighborhood local search algorithms encounter difficulties on these problems. Indeed, moving from a good solution to another requires small changes on many variables, due to the tight satisfaction of the constraints. The solution we implemented in LocalSolver is a kind of constraint propagation: when the solution obtained after a local transformation is infeasible, we gradually repair it, one constraint at a time. In order to extend the local transformation rather than cancel it, we impose never to go back on the decision to increase or decrease the value of a variable. We show that the success of this repair procedure is guaranteed for a large class of constraints. We apply this method to several scheduling problems, characterized by precedences and disjunctive resource constraints. We give numerical results on the Job Shop, Open Shop and Unit Commitment Problems, and show that our repair algorithm dramatically improves the performance of our local search algorithms.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Léa Blaise <>
Submitted on : Friday, June 12, 2020 - 3:38:46 PM
Last modification on : Thursday, June 10, 2021 - 3:02:01 AM


Files produced by the author(s)



Léa Blaise, Christian Artigues, Thierry Benoist. Solution Repair by Inequality Network Propagation in LocalSolver. 16th International Conference on Parallel Problem Solving from Nature (PPSN 2020), Sep 2020, Leiden, Netherlands. ⟨10.1007/978-3-030-58112-1_23⟩. ⟨hal-02866559⟩



Record views


Files downloads