Generic Support for Global Routing Constraint in Constraint-Based Local Search Frameworks

The OscaR.cbls framework supports a declarative constraint-based local search language for declaring optimization problems [1]. It features a new variable of type sequence of integers [2]. This variable was designed to embed global constraints into the framework. A classic example is a global constraint that maintains the length of the route in routing optimization. It inputs a distance matrix specifying the distance between each pair of nodes of the routing problem and the current route. When flipping a portion of route (a,b,c,d become d,c,b,a), and if the distance matrix is symmetric, smart algorithms are able to update the route length in O(1)-time [3].
The sequence variable of OscaR.cbls communicate their update in a symbolic way, even for complex structured moves such as flips or moving some subsequences. The sequence variable also features a checkpoint mechanism through which global constraints are notified that a neighbourhood exploration will start exploring around the current value of the variable. The proper time for global constraint to perform some pre-computation is when they receive a message notifying them about the definition of such a checkpoint. The goal of the presented contribution is to make the development of global constraint easier.

Voir en ligne : https://www.orbel.be/orbel32