La programación con restricciones o Constraint Programming es una herramienta valiosa para resolver diferentes tipos de problemas de optimización (especialmente problemas de programación industrial). Así que hoy introduciremos algunas definiciones básicas y el modelo conceptual que hay detrás.

La optimización con restricciones, o la programación de restricciones (CP), es el nombre que se le da a la identificación de soluciones factibles a partir de un conjunto muy grande de candidatos, donde el problema se puede modelar en términos de restricciones arbitrarias. CP se basa en la viabilidad en lugar de la optimización y se centra en las restricciones o dominios variables en lugar de la función objetivo.

Diseccionaremos la solución del ejemplo “4 Queens Problem”, que consiste en colocar cuatro reinas en un tablero de ajedrez de 4 x 4 para que no se puedan capturar entre sí, para demostrar los conceptos detrás de CP. Comenzamos por traducir el problema a un modelo matemático con variables y restricciones. Luego, el solver utiliza Propagación y Retroceso (o Backtracking) para llegar a la solución.

Las variables representan algunas decisiones. Pueden contener cualquier valor incluido en su rango o dominio. En nuestro problema creamos variables para cada cuadro del tablero. Cada variable toma el valor 1 si una reina está presente en el cuadro dado, de lo contrario es 0.

Las restricciones impiden que las variables tomen valores arbitrarios. No se pueden colocar dos reinas en la misma fila, la misma columna o la misma diagonal.

Propagación: las variables pueden tener valores diferentes, pero el solver debe eliminar algunos de esos valores para mantener todas las variables compatibles con el modelo.

Backtracking: de vez en cuando, el solver está bloqueado porque intenta asignar algunos valores a algunas variables que simplemente no son posibles (o deseables) porque no respetan las restricciones. Debe replantearse sus elecciones anteriores y probar otros valores. El retroceso también se produce cuando el solver encuentra una solución, pero interesa continuar la búsqueda para encontrar otras soluciones.

Veamos ahora cómo el solver de CP llega a la solución para nuestro problema:

1. Podría comenzar colocando a la Reina en la esquina superior izquierda, con lo que la variable correspondiente se asigna a 1. La propagación de las restricciones haría que las demás variables de la fila superior, la columna izquierda y la diagonal principal se asignen a 0, porque ninguna otra Reina puede ocupar ya estas posiciones.

2. Después de algunos pasos, el solver puede encontrar la siguiente situación:

No es posible colocar a la Reina en la tercera columna sin violar las restricciones. Por lo tanto, debe retroceder y revisar su decisión anterior de colocar a la Reina en la tercera fila de la segunda columna. Eso es el Backtracking.

3. Después de varios ciclos de propagación y resolución, el solver espera llegar a la solución:

Ahora veamos cómo programaríamos esta solución usando ConstraintSolver de la biblioteca de Google OR-Tools:

En este ejemplo, se han utilizado 4 variables, una por fila, que pueden adoptar valores entre 0 y 3, indicando la columna dónde se colocaría la Reina.

Y el resultado es:

Solución 1: 1 3 0 2

Solución 2: 2 0 3 1

Básicamente, eso es todo. ¡Feliz programación!