...

NuCS: A Constraint Solver for Research, Teaching, and Production Applications | by Yan Georget | Nov, 2024


Photograph by Eric Prouzet on Unsplash

Blazing-fast constraint fixing in pure Python

NuCS is a Python library for fixing Constraint Satisfaction and Optimisation Issues (CSP and COP) that I’m creating as a facet challenge. As a result of it’s 100% written in Python, NuCS is straightforward to put in and permits to mannequin advanced issues in just a few strains of code. The NuCS solver can be very quick as a result of it’s powered by Numpy and Numba.

Many issues could be formulated as CSPs. For this reason a constraint library reminiscent of NuCS can profit plenty of builders or knowledge scientists.

Let’s contemplate the well-known N-queens drawback which consists in putting N queens on a N x N chessboard such that the queens do not threaten one another.

An answer to the 8-queens drawback. Supply: Yue Guo

The 14200 options to the 12-queens issues are present in lower than 2s on a MacBook Professional M2 operating:

  • Python 3.11,
  • Numpy 2.0.1,
  • Numba 0.60.0 and
  • NuCS 3.0.0.
(venv) ➜  nucs git:(important) 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 consumer 0.53s system 422% cpu 1.699 whole

Constraint programming is a paradigm for fixing combinatorial issues. In constraint programming, customers declaratively state the constraints on the possible options for a set of resolution variables. Constraints specify the properties of an answer to be discovered. The solver combines constraint propagation and backtracking to search out the options.

For instance, here’s a mannequin for the Magic Sequence Problem (discover a sequence x_0, … x_n-1 such that, for every i in [0, n-1], x_i is the variety of occurrences of i within the sequence) utilizing NuCS:

class MagicSequenceProblem(Downside):
def __init__(self, n: int):
tremendous().__init__([(0, n)] * n)
for i in vary(n):
self.add_propagator((checklist(vary(n)) + [i], ALG_COUNT_EQ, [i]))
# redundant constraints
self.add_propagator((checklist(vary(n)), ALG_AFFINE_EQ, [1] * n + [n]))
self.add_propagator((checklist(vary(n)), ALG_AFFINE_EQ, checklist(vary(n)) + [n]))

In NuCS, a constraint is called a propagator.

The propagator (right here ALG_COUNT_EQ) merely states that x_i is the variety of occurrences of i within the sequence. The next two ALG_AFFINE_EQ propagators are redundant, which means that they don’t seem to be mandatory for NuCS to search out the answer however they pace up the decision course of.

See the documentation for an entire checklist of propagator supported by NuCS. Be aware that almost all propagators in NuCS are international (aka n-ary) and implement state-of-art propagation algorithms.

Python is the language of alternative for knowledge scientists: it has a easy syntax, a rising group and a large number of knowledge science and machine studying libraries.

However however, Python is understood to be a sluggish language : perhaps 50 to 100 occasions slower than C relying on the benchmarks.

The selection of Python for creating a excessive efficiency constraint programming library was not so apparent however we are going to see that the mixed use of Numpy (excessive efficiency computing package deal) and Numba (Simply-In-Time compilation for Python) helps quite a bit.

Many makes an attempt have been made to write down constraint solvers in Python, however these are both sluggish or are solely wrappers and rely on exterior solvers written in Java or C/C++.

NumPy brings the computational energy of languages like C and Fortran to Python.

In NuCS, every thing is a Numpy array.

This permits to leverage Numpy’s indexing and broadcasting capabilities and to write down compact propagators reminiscent of 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 vary(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 an open supply Simply-In-Time compiler that interprets a subset of Python and NumPy code into quick machine code.

Within the following instance, we discover the 14200 options to the 12-queens issues (be aware that we use a single processor right here).

NUMBA_DISABLE_JIT=1 python -m nucs.examples.queens -n 12 --log_level=ERROR   179.89s consumer 0.31s system 99% cpu 3:00.57 whole

We obtain a x60 speed-up by enabling Simply-In-Time compilation:

NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12    3.03s consumer 0.06s system 99% cpu 3.095 whole

In an effort to let Numba JIT-compile your code, you need to :

  • keep away from OOP,
  • use supported sorts or Numpy arrays,
  • use a subset of the Python language,
  • use a subset of Numpy’s capabilities.

In NuCS, these pointers have been efficiently carried out for :

Because of Numpy and Numba, NuCS achieves efficiency much like that of solvers written in Java or C/C++.

Be aware that, because the Python code is compiled and the end result cached, efficiency will all the time be considerably higher once you run your program a second time.

NuCS comes with many models for traditional constraint programming issues reminiscent of:

  • some crypto-arithmetic puzzles: Alpha, Donald,
  • the Balanced Incomplete Block Design drawback,
  • the Golomb ruler drawback,
  • the knapsack drawback,
  • the magic sequence drawback,
  • the magic sq. drawback,
  • the quasigroup drawback,
  • the n-queens drawback,
  • the Schur lemma drawback,
  • the sports activities event scheduling drawback,
  • the Sudoku drawback.

A few of these examples require some superior methods:

  • redundant constraints,
  • customized heuristics,
  • customized consistency algorithms

Most of those fashions are additionally accessible in CSPLib, the bible for something CSP associated.

When options are looked for, NuCS additionally aggregates 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
}

Right here we are able to see that:

  • certain consistency was computed 262006 occasions,
  • 2268895 propagators have been utilized however with out impact 990435 occasions whereas inconsistencies have been detected 116806 occasions,
  • they have been 131000 selections and backtracks, with a most alternative depth of 10,
  • lastly, 14200 options have been discovered.

Enjoying with the mannequin and understanding the way it impacts the statistics has confirmed to be a really helpful train in getting essentially the most out of NuCS.

NuCS additionally comes with some fundamental 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 - Downside has 82 propagators
2024-11-12 17:27:45,110 - INFO - nucs.solvers.solver - Downside has 45 variables
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver makes use of variable heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver makes use of area heuristic 0
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - BacktrackSolver makes use of consistency algorithm 2
2024-11-12 17:27:45,110 - INFO - nucs.solvers.backtrack_solver - Alternative factors stack has a maximal peak 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 - Discovered a (new) resolution: 80
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 75
2024-11-12 17:27:45,677 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 73
2024-11-12 17:27:45,678 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 72
2024-11-12 17:27:45,679 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 70
2024-11-12 17:27:45,682 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 68
2024-11-12 17:27:45,687 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 66
2024-11-12 17:27:45,693 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 62
2024-11-12 17:27:45,717 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 60
2024-11-12 17:27:45,977 - INFO - nucs.solvers.backtrack_solver - Discovered a (new) resolution: 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]

Lastly, NuCS is a really open platform have been nearly something could be personalized:

  • propagators,
  • consistency algorithms,
  • heuristics,
  • solvers.

Within the following Golomb ruler instance, a customized consistency algorithm is registered earlier than getting used:

    consistency_alg_golomb = register_consistency_algorithm(golomb_consistency_algorithm)
solver = BacktrackSolver(drawback, consistency_alg_idx=consistency_alg_golomb)

In conclusion, NuCS is a constraint solver library with plenty of options. Though it’s written completely in Python, it is extremely quick and can be utilized for a variety of purposes: analysis, instructing and manufacturing.

Don’t hesitate to contact me on Github if you happen to’d like to participate in NuCS improvement!

Some helpful hyperlinks to go additional:

Should you loved this text about NuCS, please clap 50 occasions !

Source link

#NuCS #Constraint #Solver #Analysis #Instructing #Manufacturing #Purposes #Yan #Georget #Nov