nucs es un biblioteca de pitón para la resolución de Problemas de Satisfacción y Optimización de Restricciones (CSP y COP) que estoy desarrollando como proyecto paralelo. Al estar 100% escrito en Python, NuCS es fácil de instalar y permite modelar problemas complejos en unas pocas líneas de código. El solucionador NuCS también es muy rápido porque funciona con numpy y numba.
Muchos problemas pueden formularse como CSP. Es por eso que una biblioteca de restricciones como NuCS puede beneficiar a muchos desarrolladores o científicos de datos.
Consideremos el famoso problema de N-reinas que consiste en colocar norte reinas en un NxN tablero de ajedrez de modo que las reinas no se amenacen entre sí.
El 14200 soluciones a la 12 reinas Los problemas se encuentran en menos de 2s en una MacBook Pro M2 ejecutando:
- Pitón 3.11,
- Numerosos 2.0.1,
- Número 0.60.0 y
- 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
Programación de restricciones es un paradigma para la resolución de problemas combinatorios. En la programación de restricciones, los usuarios establecen de forma declarativa las restricciones de las soluciones factibles para un conjunto de variables de decisión. Las restricciones especifican las propiedades de una solución que se va a encontrar. El solucionador combina la propagación de restricciones y el retroceso para encontrar las soluciones.
Como ejemplo, aquí hay un modelo para el Problema de secuencia mágica (encontrar una secuencia x_0,… x_n-1 tal que, para cada i en [0, n-1], x_i es el número de ocurrencias de i en la secuencia) usando 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]))
En NuCS, una restricción se denomina propagador.
El propagador (aquí ALG_COUNT_EQ) simplemente afirma que x_i es el número de ocurrencias de i en la secuencia. Los dos siguientes ALG_AFFINE_EQ Los propagadores son redundantes, lo que significa que no son necesarios para que NuCS encuentre la solución, pero aceleran el proceso de resolución.
Ver la documentacion para obtener una lista completa de propagadores compatibles con NuCS. Tenga en cuenta que la mayoría de los propagadores en NuCS son global (también conocido como norte-ario) e implementar estado del arte algoritmos de propagación.
Python es el lenguaje elegido por los científicos de datos: tiene una sintaxis simple, una comunidad en crecimiento y una gran cantidad de bibliotecas de ciencia de datos y aprendizaje automático.
Pero, por otro lado, se sabe que Python es un lenguaje lento: quizás entre 50 y 100 veces más lento que C, según los puntos de referencia.
La elección de Python para desarrollar una biblioteca de programación con restricciones de alto rendimiento no fue tan obvia, pero veremos que el uso combinado de Numpy (paquete informático de alto rendimiento) y Numba (compilación Just-In-Time para Python) ayuda mucho.
Se han hecho muchos intentos de escribir solucionadores de restricciones en Python, pero son lentos o sólo sirven. envoltorios y depender de externo solucionadores escritos en Java o C/C++.
NumPy trae el poder computacional de lenguajes como C y Fortran a Python.
En NuCS, todo es una matriz Numpy.
Esto permite aprovechar las capacidades de indexación y transmisión de Numpy y escribir propagadores compactos como 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 es un código abierto Justo a tiempo compilador que traduce un subconjunto de código Python y NumPy en código de máquina rápido.
En el siguiente ejemplo, encontramos las 14200 soluciones al 12 reinas problemas (tenga en cuenta que aquí utilizamos un solo procesador).
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
logramos un x60 acelere habilitando la compilación Just-In-Time:
NUMBA_CACHE_DIR=.numba/cache python -m nucs.examples.queens -n 12 3.03s user 0.06s system 99% cpu 3.095 total
Para permitir que Numba JIT compile su código, debe:
- evitar la programación orientada a objetos,
- utilizar tipos compatibles o matrices Numpy,
- utilizar un subconjunto del lenguaje Python,
- utilice un subconjunto de las funciones de Numpy.
En NuCS, estas directrices se han implementado con éxito para:
Gracias a Numpy y Numba, NuCS logra un rendimiento similar al de los solucionadores escritos en Java o C/C++.
Tenga en cuenta que, dado que el código Python se compila y el resultado se almacena en caché, el rendimiento siempre será significativamente mejor cuando ejecute su programa por segunda vez.
NuCS viene con muchos modelos para problemas clásicos de programación con restricciones como:
- algunos acertijos criptoaritméticos: Alfa, donald,
- el Diseño de bloques incompletos equilibrados problema,
- el gobernante golomb problema,
- el mochila problema,
- el secuencia magicael problema,
- el cuadrado magico problema,
- el cuasigrupo problema,
- el n-reinas problema,
- el Lema de Schur problema,
- el programación de torneos deportivos problema,
- el Sudokus problema.
Algunos de estos ejemplos requieren algunas técnicas avanzadas:
- restricciones redundantes,
- heurísticas personalizadas,
- algoritmos de consistencia personalizados
La mayoría de estos modelos también están disponibles en CSPLibla biblia para todo lo relacionado con CSP.
Cuando se buscan soluciones, NuCS también agrega algunas estadística:
{
'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
}
Aquí podemos ver que:
- la consistencia ligada se calculó 262006 veces,
- Se aplicaron 2268895 propagadores pero sin efecto 990435 veces mientras que se detectaron inconsistencias 116806 veces.
- eran 131000 opciones y retrocesos, con una profundidad máxima de elección de 10,
- finalmente se encontraron 14200 soluciones.
Jugar con el modelo y comprender cómo afecta a las estadísticas ha demostrado ser un ejercicio muy útil para aprovechar al máximo NuCS.
NuCS también viene con algunas capacidades de registro básicas.
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]
Finalmente, NuCS es una plataforma muy abierta donde se puede personalizar casi cualquier cosa:
- propagadores,
- algoritmos de consistencia,
- heurística,
- solucionadores.
En lo siguiente gobernante golomb Por ejemplo, un algoritmo de coherencia personalizado se registra antes de utilizarse:
consistency_alg_golomb = register_consistency_algorithm(golomb_consistency_algorithm)
solver = BacktrackSolver(problem, consistency_alg_idx=consistency_alg_golomb)
En conclusión, NuCS es una biblioteca para solucionar restricciones con muchas funciones. Aunque está escrito íntegramente en Python, es muy rápido y puede utilizarse para una amplia gama de aplicaciones: investigación, enseñanza y producción.
¡No dudes en contactarme en Github si deseas participar en el desarrollo de NuCS!
Algunos enlaces útiles para ir más allá:
Si te ha gustado este artículo sobre NuCS, aplaude 50 veces!