Nucs it's a python library for the resolution of Constraint Satisfaction and Optimization Problems (CSP and COP) that I am developing as a parallel project. Being 100% written in Python, NuCS is easy to install and allows you to model complex problems in a few lines of code. The NuCS solver is also very fast because it works with numpy and numba.
Many problems can be formulated as CSP. This is why a constraints library like NuCS can benefit many developers or data scientists.
Let us consider the famous N-queens problem which consists of placing north queens in a NxN chessboard so that the queens do not threaten each other.
He 14200 solutions to the 12 queens The problems are found in less than 2s on a MacBook Pro M2 running:
- Python 3.11,
- Numerous 2.0.1,
- Number 0.60.0 and
- NuCS 3.0.0.
(venv) ➜ nucs git:(main) time NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 --log_level=ERROR --processors=6
{
'ALG_BC_NB': 262006,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 0,
'PROPAGATOR_FILTER_NB': 2269965,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 990435,
'PROPAGATOR_INCONSISTENCY_NB': 116806,
'SOLVER_BACKTRACK_NB': 131000,
'SOLVER_CHOICE_NB': 131000,
'SOLVER_CHOICE_DEPTH': 10,
'SOLVER_SOLUTION_NB': 14200
}
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 6.65s user 0.53s system 422% cpu 1.699 total
Restriction programming It is a paradigm for solving combinatorial problems. In constraint programming, users declaratively set constraints on feasible solutions for a set of decision variables. Constraints specify the properties of a solution to be found. The solver combines constraint propagation and backtracking to find the solutions.
As an example, here is a model for the Magic sequence problem (find a sequence x_0,… x_n-1 such that, for each Yo in (0, n-1), x_i is the number of occurrences of Yo in the sequence) using NuCS:
class MagicSequenceProblem(Problem):
def __init__(self, n: int):
super().__init__(((0, n)) * n)
for i in range(n):
self.add_propagator((list(range(n)) + (i), ALG_COUNT_EQ, (i)))
# redundant constraints
self.add_propagator((list(range(n)), ALG_AFFINE_EQ, (1) * n + (n)))
self.add_propagator((list(range(n)), ALG_AFFINE_EQ, list(range(n)) + (n)))
In NuCS, a constraint is called a propagator.
The propagator (here ALG_COUNT_EQ) simply states that x_i is the number of occurrences of Yo in the sequence. The next two ALG_AFFINE_EQ The propagators are redundant, meaning they are not necessary for NuCS to find the solution, but they speed up the solving process.
See the documentation for a complete list of NuCS-compatible propagators. Note that most propagators in NuCS are global (also known as north-ary) and implement state of the art propagation algorithms.
Python is the language of choice for data scientists: it has simple syntax, a growing community, and a wealth of data science and machine learning libraries.
But on the other hand, Python is known to be a slow language: perhaps 50 to 100 times slower than C, depending on benchmarks.
The choice of Python to develop a high-performance constrained programming library was not so obvious, but we will see that the combined use of Numpy (high-performance computing package) and Numba (Just-In-Time compilation for Python) helps a lot.
Many attempts have been made to write constraint solvers in Python, but they are either slow or useless. wrappers and depend on external solvers written in Java or C/C++.
NumPy brings the computational power of languages like C and Fortran to Python.
In NuCS, everything is a Numpy array.
This allows you to take advantage of Numpy's indexing and streaming capabilities and write compact propagators like Max_i x_i <= y
def compute_domains_max_leq(domains: NDArray, parameters: NDArray) -> int:
x = domains(:-1)
y = domains(-1)
if np.max(x(:, MAX)) <= y(MIN):
return PROP_ENTAILMENT
y(MIN) = max(y(MIN), np.max(x(:, MIN)))
if y(MIN) > y(MAX):
return PROP_INCONSISTENCY
for i in range(len(x)):
x(i, MAX) = min(x(i, MAX), y(MAX))
if x(i, MAX) < x(i, MIN):
return PROP_INCONSISTENCY
return PROP_CONSISTENCY
Numba is open source Just in time compiler that translates a subset of Python and NumPy code into fast machine code.
In the following example, we find the 14200 solutions to 12 queens problems (note that we use a single processor here).
NUMBA_DISABLE_JIT=1 python -m nucs.examples.queens -n 12 --log_level=ERROR 179.89s user 0.31s system 99% cpu 3:00.57 total
we achieved a x60 Speed up by enabling Just-In-Time compilation:
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 3.03s user 0.06s system 99% cpu 3.095 total
To allow Numba JIT to compile your code, you must:
- avoid object-oriented programming,
- use compatible types or Numpy arrays,
- use a subset of the Python language,
- use a subset of Numpy's functions.
At NuCS, these guidelines have been successfully implemented to:
Thanks to Numpy and Numba, NuCS achieves similar performance to solvers written in Java or C/C++.
Note that since Python code is compiled and the result is cached, performance will always be significantly better when you run your program a second time.
NuCS comes with many models for classic programming problems with constraints such as:
- some cryptoarithmetic puzzles: Alpha, donald,
- he Balanced Incomplete Block Design problem,
- he ruler golomb problem,
- he backpack problem,
- he magic sequencethe problem,
- he magic square problem,
- he quasigroup problem,
- he n-queens problem,
- he Schur's motto problem,
- he sports tournament programming problem,
- he Sudoku problem.
Some of these examples require some advanced techniques:
- redundant constraints,
- custom heuristics,
- custom consistency algorithms
Most of these models are also available in CSPLibthe bible for everything related to CSP.
When looking for solutions, NuCS also adds some statistics:
{
'ALG_BC_NB': 262006,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 0,
'PROPAGATOR_FILTER_NB': 2269965,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 990435,
'PROPAGATOR_INCONSISTENCY_NB': 116806,
'SOLVER_BACKTRACK_NB': 131000,
'SOLVER_CHOICE_NB': 131000,
'SOLVER_CHOICE_DEPTH': 10,
'SOLVER_SOLUTION_NB': 14200
}
Here we can see that:
- the bound consistency was calculated 262006 times,
- 2268895 propagators were applied but without effect 990435 times while inconsistencies were detected 116806 times.
- There were 131,000 options and setbacks, with a maximum choice depth of 10,
- finally 14200 solutions were found.
Playing with the model and understanding how it affects statistics has proven to be a very useful exercise in getting the most out of NuCS.
NuCS also comes with some basic logging capabilities.
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.golomb -n 10 --symmetry_breaking --log_level=INFO
2024-11-12 17:27:45,110 - INFO - nucs.solvers.solver - Problem has 82 propagators
2024-11-12 17:27:45,110 - INFO - nucs.solvers.solver - Problem has 45 variables
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses variable heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses domain heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver uses consistency algorithm 2
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - Choice points stack has a maximal height of 128
2024-11-12 17:27:45,172 - INFO - nucs.solvers.backtrack_solver - Minimizing variable 8
2024-11-12 17:27:45,644 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 80
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 75
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 73
2024-11-12 17:27:45,678 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 72
2024-11-12 17:27:45,679 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 70
2024-11-12 17:27:45,682 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 68
2024-11-12 17:27:45,687 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 66
2024-11-12 17:27:45,693 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 62
2024-11-12 17:27:45,717 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 60
2024-11-12 17:27:45,977 - INFO - nucs.solvers.backtrack_solver - Found a (new) solution: 55
{
'ALG_BC_NB': 22652,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 107911,
'PROPAGATOR_FILTER_NB': 2813035,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 1745836,
'PROPAGATOR_INCONSISTENCY_NB': 11289,
'SOLVER_BACKTRACK_NB': 11288,
'SOLVER_CHOICE_NB': 11353,
'SOLVER_CHOICE_DEPTH': 9,
'SOLVER_SOLUTION_NB': 10
}
( 1 6 10 23 26 34 41 53 55)
Finally, NuCS is a very open platform where you can customize almost anything:
- propagators,
- consistency algorithms,
- heuristics,
- solvers.
In the following ruler golomb For example, a custom consistency algorithm is registered before being used:
consistency_alg_golomb = register_consistency_algorithm(golomb_consistency_algorithm)
solver = BacktrackSolver(problem, consistency_alg_idx=consistency_alg_golomb)
In conclusion, NuCS is a feature-rich constraint solving library. Although it is written entirely in Python, it is very fast and can be used for a wide range of applications: research, teaching, and production.
Feel free to contact me on Github if you want to get involved in NuCS development!
Some useful links to go further:
If you liked this article about NuCS, clap 50 times!
