Introducción práctica a la programación por restricciones con CP-SAT y Python

Introducción práctica a la programación por restricciones: CP-SAT y Python

Paradigma declarativo

• La programación por restricciones (CP) es un paradigma declarativo para resolver problemas de optimización discreta
• A diferencia de la programación imperativa, se describe el resultado deseado y el programa deriva por sí mismo la solución
• Por ejemplo, se explica la diferencia entre el enfoque imperativo y el declarativo al extraer una lista de personas adultas

Fundamentos de la programación por restricciones (CP)

• Modelo: describe el resultado deseado del problema
• Variables: los valores que se quieren encontrar; cada variable tiene un dominio (conjunto de valores permitidos)
• Restricciones: describen las relaciones entre las variables
• Solución: asignar valores a las variables para satisfacer las restricciones

Ejemplo práctico con Python y CP-SAT

• Problema: generar el horario semanal de trabajo de empleados
• Creación del modelo: se crea un modelo vacío usando CP-SAT
• Datos: se definen la lista de empleados y sus roles, los días de trabajo y los turnos
• Definición de variables: se crean variables booleanas que indican si cada empleado trabaja o no
• Agregar restricciones: se añaden restricciones a las variables según la descripción del problema

Resolución del modelo

• Resolución: se resuelve el modelo y se obtiene el resultado
• Restricciones adicionales: se agregan restricciones extra como evitar horas extra, limitar las horas de ciertos empleados y evitar superposición de horarios entre determinados empleados

Intermedio: estado de la solución

• Estado de la solución: devuelve estados como óptimo, factible, infactible o desconocido
• Ejemplo: se explica cada estado mediante un ejemplo sencillo

"Lo siento, Emma"

• Estado infactible: no es posible que Emma descanse 5 días entre semana
• Propuesta alternativa: se propone que Emma descanse solo 3 días entre semana

Objetivo: distribución uniforme de las horas de trabajo

• Agregar objetivo: se añade un objetivo para distribuir de forma uniforme las horas de trabajo
• Resultado: las horas de trabajo quedan repartidas equitativamente entre los empleados

Conclusión

• Introducción a los conceptos básicos: se presentan los conceptos fundamentales de la programación por restricciones y se explican con un ejemplo práctico
• Adelanto del próximo artículo: el siguiente artículo tratará sobre cómo usar programación por restricciones para la selección de índices en Postgres

Opinión de GN⁺

• Utilidad de la programación por restricciones: es muy útil para resolver problemas complejos de optimización
• Fortalezas de CP-SAT: CP-SAT, desarrollado como parte del proyecto OR-Tools de Google, ofrece un rendimiento potente
• Casos de uso reales: puede aplicarse a problemas reales como la generación de horarios laborales
• Consideraciones al adoptar la tecnología: al adoptar una nueva tecnología, hay que considerar la curva de aprendizaje y los problemas de integración con sistemas existentes
• Proyectos similares recomendados: solvers comerciales como IBM CPLEX y Gurobi también ofrecen funciones similares

[GN⁺]

Comentarios de Hacker News

• He usado solucionadores de restricciones en el pasado, y estas herramientas muestran un rendimiento realmente sorprendente

  • El problema es que casi no hay material para principiantes
  • La mayoría del material trata sobre cómo resolver Sudoku o son recursos de investigación altamente técnicos
  • Ojalá hubiera más herramientas accesibles para resolver más problemas
  • Que sean accesibles sigue significando que se necesita un programador

• Estoy reescribiendo en mi viejo libro un capítulo corto sobre el uso de MiniZinc y Python

  • MiniZinc es un sistema de programación por restricciones
  • Hay un buen curso en Coursera que usa MiniZinc

• Muchos programas intentan tener una única representación de los datos, pero eso en la mayoría de los casos no es racional

  • Se necesita mucha distorsión para hacer que un algoritmo funcione con una representación nueva
  • Siempre me ha parecido una lástima que no transformemos representaciones con más frecuencia
  • Si transformas la representación, puedes obtener una formulación muy concisa, y eso permite una ejecución más rápida

• Tengo un cliente que opera campamentos deportivos

  • Los niños pueden pedir el deporte que quieren y también a sus amigos
  • Eso crea un problema de programación que es difícil para los humanos
  • Construí un sistema simple usando una herramienta de optimización basada en OR-Tools
  • Ahora el horario queda listo con unos pocos clics

• Tengo experiencia usando muchos solucionadores desde principios de los 2000

  • Actualmente trabajo en software (web) usando Python
  • Me alegra ver una exploración profunda de este tema
  • Convertir las restricciones en un modelo es el 90% del trabajo y la parte más difícil

• Me pregunto si existe algún CAD paramétrico que funcione principalmente con un solucionador de restricciones

  • Al principio, a menudo es incómodo tener que estimar valores de parámetros que en realidad no importan
  • En su lugar, me gustaría imponer restricciones sobre los parámetros que sí me interesan y optimizar el resto

• Me pregunto cómo se comparará con la programación entera mixta