2021-07-28 –, Red
The freshly born JuliaConstraints GitHub organization provides a combination of packages around the theme of Constraint Programming and Combinatorial Optimization.
This talk introduces the whole ecosystem of JuliaConstraints packages and its main dependencies. It focuses on the LocalSearchSolvers.jl framework (and CBLS.jl, its interface with JuMP) for Constraint-Based Local Search. We also cover the utility packages that we hope to share with the Julia and Constraint Programming communities.
Problem-solving often consists in two actions: model and solve. The holy grail of Constraint Programming is to have the human (user) model the problem and have the machine (solver) solve it. All the smartness should be in the solver.
JuliaConstraints, a freshly hatched GitHub organization, is a first attempt to provide common grounds to the growing Constraint Programming community in Julia while tackling that holy grail.
We will approach the different blocks of the ecosystem through the lens of shared interfaces, shared instances and models, and shared internals. We will illustrate the use, pros and cons of problem-solving through Constraint Programming with different solvers and frameworks such as ConstraintSolver.jl and LocalSearchSolvers.jl.
A possible common interface, building on the popular JuMP.jl, is already available for some solvers. An attempt to write shared models in JuMP syntax as just started as ConstraintModels.jl. Various problems have been modeled such as:
- sudoku
- n-queens
- magic square
- chemical equilibrium
- quadratic assignment
- golomb ruler
- minimum and maximum cuts in networks
- traveler salesman problem
- scheduling
A store of instances, generators and global information combinatorial optimization problems is also available as COPInstances.jl (tentative name, WIP). This package aims for a larger audience than simply CP solvers, and we would be glad to see it grows for other optimization packages.
Finally, JuliaConstraints hosts also some internal packages, mainly used within the LocalSearchSolvers.jl framework, but with the hope, that some parts can be shared with other solvers:
- Constraints.jl: a store of usual constraints in CP
- ConstraintDomains.jl: structures and methods for the domain of variables
- CompositionalNetworks.jl: a glass-box neural networks for scalable compositions of functions
- A very nice logo with chains and Julia (in)famous colored dots
There is an extensive list of incredible Julia packages and internal methods that provide all the computational power and the expressive syntax of the Constraint Programming ecosystem in Julia. We will also highlight the key external dependencies such as JuMP, Evolutionary, Dictionaries, Base.Threads, and more!
Incidentally, we will try to have some fun with an interactive model session (if interactivity is allowed in the COVID-19 context) for LocalSearchSolvers.jl. Did we mention that the solving speed scale super linearly with the number of thread/process?
Jean-François Baffier is an academic researcher at the RIKEN Center for Advanced Intelligence Project (AIP), and a consultant in Artificial Intelligence, Big Data Science, Data Structures, and Algorithms. As an academic, he gives back to society through fundamental research in computer science supplemented by open source libraries and softwares.
His current research project involves the study of the “Analysis of information networks,” the “Smart compression for high-scalability of data structures,” and “Explainable Artificial Intelligence.” Other topic of interest covers modeling of failures and routing in Networks, Game Analysis, and AI for Games.