CBLS in short

"Constraint-based Local Search presents a powerful new programming language paradigm for combinatorial optimization, uniting the power of local search with the declarativeness of constraint programming" Andrew J. Davenport, IBM T. J. Watson Research Center (cover of P Van Hentenryck and Laurent Michel, Constraint-Based Local Search, MIT Press 2005)
Constraint-Based Local Search allows you to declaratively model a combinatorial problem by means of constraints and invariants, and offering dedicated support for implementing efficient local search approaches


  • Declarative Models with high level vocabulary (allDifferent, argMax, union, etc)
  • Very efficient procedure for updating models, allowing for a quick evaluation of the objective function on a neighbor solution
  • Feedback mechanism from constraints to easily identify the contribution of each variable to the overall violation
  • Good scalability (50k Queens can be solved in around 20 seconds on regular PC)
  • Typical problems where CBLS is good at: scheduling, vehicle routing, very large combinatorial problems


  • Naive models are inefficient (modeling is a bit of an art)
  • Search procedure and its meta-heuristics is to be implemented by developer (although some standard ones are readily available e.g. for routing and scheduling). Some tuning is necessary for each application.
  • There is a learning curve to acquire experience with implementation of good models as well as neighborhoods and meta-heuristics

Why OscaR-CBLS

  • Very crisp and elegant models using Scala (as short as dedicated languages)
  • Full control on the search
  • Rich vocabulary for defining your models, plus handful helpers to embed custom code into models (eg: for querying dedicated estimation algorithms)
  • Reliable: nightly tested through regression tests
  • Very reactive development team (in case of question or bug fix)

Some links to learn to use OscaR and CBLS