OscaR.cbls

Why local search ?

Local search is a versatile and scalable optimization technique for operations research problems. For instance, it is well suited for optimization problems with a large search space such as routing optimization problems.

It can also easily incorporate dedicated algorithms such as graph or computational geometry.

Local search also encompasses metaheuristics such as tabu search, restart, simulated annealing, destroy & rebuild, generalized local search, ejection chains, VLSN, etc.

Why OscaR.cbls ?

Developing a local search solution if often expensive because:

• Developing efficient constraint is complex as it relies on incremental constraint evaluation.
• A dedicated search procedure must be crafted and then implemented, and it must take into account the structure of the problem.

OscaR.cbls is about reducing these costs.

OscaR.cbls is a smart tool for optimization engineers. It is packaged as an open source software library (LGPL). Programming in Scala or Java is required to implement a solution using the OscaR.cbls library. A few examples are provided with the library.

To use OscaR.cbls, knowledge about local search and metaheuristics is needed for crafting and parametrizing proper models and search heuristics for specific applications.

General philosophy of OscaR.cbls

OscaR.cbls relies on the following general philosophy:

• Focus on computational complexity and provide well-though API to achieve good overall computational complexity whatever will be the application.
• Offer maximal support both for modeling and solving. Programming in Scala or Java is required to use OscaR.cbls.
• OscaR.cbls aims at focusing brain time of optimization engineers. Thanks to OscaR.cbls, an optimization engineers must only stay focused on:
  • Conceiving proper model to express business needs and constraints at a high level without wasting time in its detailed implementation.
  • Designing and rapidly exploring search procedures to find the best suited to the problem at hand and its specific constraints.

Main features of OscaR.cbls

OscaR.cbls provides advanced support for both modeling and searching:

• Constraint-based modeling
  • Incorporates very efficient algorithms to evaluate solutions based on incremental evaluation, pre-computations, caches, etc.
• Combinator-based searching
  • A local search procedure must be designed for each use case, so we made it easy to define any local search procedure and metaheuristics by assembling it from a library of standard elements.

Origin of OscaR.cbls

OscaR.cbls was sparked in 2011 and enriched throughout research and industrial projects. The overall objective was to properly package the relevant research results from academia into a clean and well-architectured solver. It evolved over years and various aspects were added including:

• Search combinators
• Routing optimization based on sequences
• Mechanisms for developing new global constraints based on transition functions
• Distributed search
• Profiling information

In 2024, we started a deep rewriting of OscaR.cbls because it has been developed as a research prototype and various modules were relying on obsolete technologies. In early 2025, we presented the first release-brade version of OscaR.cbls. It notably features a reference API that has been engineered to be stable against future evolution of OscaR.cbls.

Routing optimization

Local search excels in routing optimization. OscaR.cbls features a specific module for routing optimization. OscaR.cbls notably features specific data-structures and global constraints for routing, with specific neighborhoods 1-opt, 2-opt, 3-opt, VLSN, etc.

As usual in OscaR.cbls, it was specifically designed to accommodate additional constraints and (meta-)heuristics.

What's next ?

OscaR.cbls has a legacy of code from 2011. We are currently refactoring this whole codebase. In the coming month, we will publish more releases of OscaR.cbls with incredible features including:

• Incorporating more features from our legacy version including
  • Global constraints (100+)
  • Neighborhood combinators (simulated annealing, ejection chains, late acceptance, VLSN)
• Multi-threading and multi-node optimization

OscaR.cbls features a user API. This API will be backwards compatible, so switching to upcoming versions of OscaR.cbls will be straightforward

Stay tuned on Github !