1. Introduction

Constraint-based local search is a technique for solving combinatorial problems including both constraint and optimization problems. It is based on the notion of neighbourhood exploration. One has a current solution, which has some qualities. From this solution, the principle is to explore a limited set of neighbours obtained by slightly modifying the current solution. This is called neighbourhood exploration. From the explored neighbours, one selects the one that improves the most with respect to the current solution. This best neighbour becomes the new current solution. Neighbourhood exploration is repeated until no improvement can be found. This process can be enriched with various meta-heuristics such as taboo, metropolis, simulated annealing, random restart, etc.

Such approach provides very good scalability, at the cost of loosing the proof of optimality delivered by exhaustive and symbolically exhaustive approaches such as CP and MIP. For instance, a benchmark of the NQueens problem performed with the second script of the "getting started" page is given here below.

Constraints can be handled in two different ways, either as an objective function; one needs to compute the violation degree of constraints, and aims at decreasing it as if it were an objective function. The other is to consider only solutions that enforce all constraints, starting from a solution that enforces them all.

When implementing a local search approach, it is crucial to be able to quickly evaluate the objective function on neighbours. It is exactly what a CBLS framework aims at. It enables the value of objective functions to be computed incrementally. Objective functions are declared in the framework by means of so-called invariants, that implement various operators (arithmetic, min-max, set operators, logics, etc.) A CBLS framework might also come with a support for declaring constraints, and a library of standard constraints (alldiff, equalities, etc.)

The CBLS engine of Oscar is based on the reference book Constraint-based Local Search

The OscaR CBLS engine offers a powerful

• framework for invariant declaration, with an engine that is able to perform incremental update of these invariants
• library of standard invariants, which can be extended
• framework for declaring constraints
• library of standard constraints.

2. Main Features of the OscaR CBLS engine:

• Complex data types including IntVar and IntSetVar are supported by the CBLS solver. These make it possible to maintain the structure of the problem in the problem definition. Potentially, this delivers interesting efficiency gain, compared to a boolean-only approach where the problem is smashed into a large set of boolean variables. It also simplifies writing complex neighbourhood rules by making the logic of these rich variables available to the search heuristics.
• Open The OscaR CBLS engine is open, so that one can fully tailor the search heuristics to their precise problem. For instance, one can easily implement the standard meta-heuristics such as taboo, metropolis, simulated annealing, random restart, etc. Standard search procedures are also available and can be used directly on constraint problems.
• Libraries of standard invariants and constraints are proposed on integer and set of integer domains: Invariant library includes logic, numeric, min/max, and set invariants. Constraint library includes few global constraints: Alldiff, AtLeast, AtMost and equalities over integers.
• Standard domain-independent neighborhood and neighborhood combinators enable the easy development of a search procedure tailored to your model, and can easily tackle complex meta-heuristics such as tabu, or restart.
• Problem-specific solvers built on top of CBLS are available for routing (mature) and scheduling (in progress)
• The violation degree propagates upwards through the static propagation graph. Each variable has a violation degree associated with each constraint system, and this violation degree propagates upwards through invariants. Although the propagation rule might be somewhat arbitrary, it enables one to find the variable contributing the most to the overall violation.
• Propagation graph can be cyclic. Two propagation graphs are handled: a static graph that over-approximates the dependencies between variables and invariants, and a dynamic graph that represents the real dependencies given the data actually stored in the model. The static graph can include cycles. This makes it possible to implement JobShop scheduler using the standard invariants.
• Partial propagation for efficient neighborhorhood exploration. When exploring a neighborhood one generally only evaluates the objective function to decide whether or not to perform the move. Models generally include many more variables such as tabu management, violation of variables, or multiple other objective functions. Partial propagation enables a faster neighborhood exploration as it will update the smallest possible fragment of the model. Propagation is triggered when the value of a variable is queried by the search script. Deciding whether the propagation will be total or partial is done depending on the variable: if the variable is registered for partial propagation, the propagation will be partial. It will be total otherwise. Violation degrees of constraint systems are automatically registered for partial propagation.
• Lightweight The OscaR CBLS engine has been kept small and well structured to ensure that it can be easily understood and extended

3. Documentation

/!\ this documentation is partly obsolete and under reconstruction /!\

Getting Started presents an introduction on how to use Oscar.cbls

Writing Invariants presents how to enrich the library of invariants of Oscar.cbls

To know the internals of Oscar.cbls, you can start by looking at the slides.

Slides:

• General Presentation
• Extending OscaR.cbls for developers