OscaR.cbls

An open source local search optimization engine implementing Constraint-Based Local Search in Scala.

More information : Github.

Why local search ?

Local search is a versatile and scalable optimization technique for operations research problems. For instance, it is well suited for optimization problem 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 is also more than just local search; it 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 solution using 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 explore 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 both for 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 sparkled in 2011 and was enriched throughout research and industrial projects. The overall objective was about how 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 [Del18]
• Routing optimization based on sequences [Del18b]
• Mechanisms for developing new global constraints based on transition functions
  [Del21c]
• Distributed search [Os21, Os22]
• 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.

Constraint-based modeling

OscaR.cbls comes with three variable types: Int, IntSet and IntSequence.
IntSequence is a particular type of variable for representing vehicle routes; for more details, read the routing optimization section below.

OscaR.cbls provides a rich library of efficient constraints on these variables including:

• Arithmetic: sum, prod, sum on a selected range of elements
• Min-max: min, max, argmin, argmax
• Logic: element
• Set: intersection, union
• Routing-specific: routeLength, routeFlatMap

Check our API for the full list of supported constraints.

Combinator-based searching

Local search requires a search procedure. This procedure must consider the problem at hand.

OscaR.cbls offers a unique approach where a search procedure are crafted by combining search neighborhoods with neighborhood combinators [Del18]

• Example of search neighborhoods are:
  • Domain-independent: Assign, Swap, Roll, Shift
  • Routing: InsertPoint, 1-opt, 2-opt, 3-opt
• Combinators allow introducing various aspects into the search procedure such as:
  • Neighborhood selection: Round Robin, BestSlopeFirst (similar to hill climbing), etc.
  • Stop criterion: timeout, maxMoves
  • Metaheuristics: restart, simulated annealing, late acceptance
  • Miscellaneous: afterMove, showObjectiveFunction, etc.

OscaR.cbls also offers support for elaborating the search procedure, notably :

• Detailed Profiling information about various part of the search procedure
• Interface to iRace (to come).

Check our API for the full list of supported combinators.

Routing Optimization

Routing optimization is a common application for local search optimization.

OscaR.cbls provides specific support for routing optimization, base on our paper [Del18b] namely:

• A specific type of variable, the sequence of integer that represents a route and provides efficient data structure and symbolic delta notifications for global constraints.
• A library of constraints with global constraints algorithms that perform symbolic computations, thus routinely achieving O(log n) complexity [Del21c].
• A library of classical neighborhoods such as 1-opt, 2-opt, 3-opt, etc.
• Graphical visualization.

References

[Del18] De Landtsheer, R., Guyot, Y., Ospina, G., Ponsard, C. (2018). Combining Neighborhoods into Local Search Strategies. In: Amodeo, L., Talbi, EG., Yalaoui, F. (eds) Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 62. Springer, Cham. https://doi.org/10.1007/978-3-319-58253-5_3

[Del18b] 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 https://www.cetic.be/Reasoning-on-Sequences-in-Constraint-Based-Local-Search-Frameworks

[Del21c] De Landtsheer, R., Germeau, F., Fayolle, T., Ospina, G., Ponsard, C. (2021). Generic Support for Precomputation-Based Global Routing Constraints in Local Search Optimization. In: Yalaoui, F., Amodeo, L., Talbi, EG. (eds) Heuristics for Optimization and Learning. Studies in Computational Intelligence, vol 906. Springer, Cham. https://doi.org/10.1007/978-3-030-58930-1_10

[Os21] Ospina, Gustavo & De Landtsheer, Renaud. (2021). Towards Distributed Local Search Through Neighborhood Combinators, in Proceedings of the 10th International Conference on Operations Research and Enterprise Systems - ICORES, 248-255, 2021, https://www.cetic.be/Towards-Distributed-Local-Search-Through-Neighborhood-Combinators

[Os22] Ospina, G., De Landtsheer, R. Defining Parallel Local Search Procedures with Neighborhood Combinators. SN COMPUT. SCI. 3, 231 (2022). https://doi.org/10.1007/s42979-022-01120-1