Skip to Main content Skip to Navigation
Technical Reports

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 :
Technical Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.laas.fr/hal-02866559
Contributor : Léa Blaise <>
Submitted on : Friday, June 12, 2020 - 3:38:46 PM
Last modification on : Saturday, September 5, 2020 - 3:07:44 AM

File

article_HAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02866559, version 1

Citation

Léa Blaise, Christian Artigues, Thierry Benoist. Solution Repair by Inequality Network Propagation in LocalSolver. Rapport LAAS n° 20167. 2020. ⟨hal-02866559⟩

Share

Metrics

Record views

64

Files downloads

38