Renaud De Landtsheer, Yoann Guyot, Gustavo Ospina, Fabian Germeau, Christophe Ponsard, Reasoning on Sequences in Constraint-Based Local Search Frameworks, 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), Delft, The Netherlands, June 26-29, 2018 (accepted)
This paper explains why several global constraints for routing cannot be integrated into Constraint-Based Local Search (CBLS) frameworks. A technical reason for this is identified and defined as the \emphmulti-variable bottleneck. We solve this bottleneck by introducing a new type of variables: ``sequence of integers’’. We identify key requirements and defines a vocabulary for this variable type, through which it communicates with global constraints. Dedicated data structures are designed for efficiently representing sequences in this context. Benchmarks are presented to identify how to best parametrise those data structures and to compare our approach with other state-of-the-art local search frameworks: LocalSolver and GoogleCP. Our contribution is included in the CBLS engine of the open source OscaR framework.