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

 (pganalyze.com)
1 puntos por GN⁺ 2024-07-05 | 1 comentarios | Compartir por WhatsApp
  • La programación con restricciones (CP) es un enfoque declarativo para problemas de optimización discreta: en vez de modelarlos con código procedural, se describen mediante variables, dominios y restricciones, y se deja que el solver encuentre una solución que cumpla las condiciones
  • El núcleo del modelo son las variables, que representan los valores a encontrar; los dominios, que son el rango de valores posibles; y las restricciones, que limitan las relaciones entre variables. Si hace falta, una función objetivo permite elegir una mejor solución
  • El ejemplo del reparto del costo de unos dulces entre Alice, Bob y Carol muestra cómo mejorar una solución válida hacia una más equilibrada usando alldifferent, maximum y minimize
  • El ejemplo práctico arma un horario semanal de trabajo para 4 empleados, durante 7 días, 3 turnos y 2 roles, usando el solver open source CP-SAT de Google OR-Tools y Python
  • Al mismo modelo se le pueden agregar condiciones de forma gradual, como un límite semanal de 40 horas, horarios de clases, combinaciones de personas que no deben trabajar juntas, reparto equitativo del trabajo de fin de semana, solicitudes de vacaciones y minimización de la diferencia en cantidad de turnos

Forma básica de pensar en la programación con restricciones

  • La programación con restricciones (CP) es un paradigma declarativo para resolver problemas de optimización discreta
  • La programación imperativa escribe, paso a paso, el procedimiento para llegar a un resultado, mientras que el enfoque declarativo describe las condiciones del resultado deseado y deja que el sistema de ejecución lo encuentre
  • En un ejemplo para obtener una lista de adultos, el código imperativo recorre la lista de personas y verifica Age >= 18, mientras que SQL declarativo expresa directamente la condición como SELECT person_name FROM people WHERE age >= 18;
  • CP también describe el resultado deseado como un modelo, cuyos componentes centrales son variables, dominios y restricciones
    • Las variables indican qué se quiere encontrar
    • Los dominios son el conjunto de valores que puede tomar una variable
    • Las restricciones limitan las relaciones entre variables

Variables, dominios, restricciones y función objetivo

  • Una solución es una asignación en la que cada variable toma un valor dentro de su dominio y cumple todas las restricciones
  • El ejemplo de los dulces plantea que Alice, Bob y Carol tienen hasta 20 dólares cada uno y juntan dinero para comprar dulces de 50 dólares
    • Las variables a, b, c son el monto que aporta cada persona
    • El dominio de las tres variables es {0, ..., 20}
    • a + b + c == 50 hace que el total coincida
    • a >= b hace que Alice aporte al menos tanto como Bob
    • c % 5 == 0 limita el monto de Carol a múltiplos de 5
    • Para que las tres personas no aporten el mismo monto, se pueden poner a != b, a != c, b != c
  • Las condiciones que abarcan varias variables pueden expresarse como restricciones globales (global constraints), y alldifferent(a, b, c) hace que las tres variables tengan valores distintos
  • El solver recibe el modelo como entrada y devuelve una solución válida
    • La solución de ejemplo a = 19, b = 11, c = 20 cumple todas las restricciones
    • Sin embargo, Carol aporta casi el doble que Bob, así que podría existir una solución más equilibrada
  • La función objetivo minimiza o maximiza una expresión específica entre las soluciones que cumplen las restricciones
    • Se define una nueva variable x como el aporte más grande y se usa maximum(x, [a, b, c])
    • Al aplicar minimize: x, se devuelve a = 18, b = 17, c = 15, x = 18
    • La diferencia entre el aporte más grande y el más pequeño baja de 9 dólares a 3 dólares

Crear un modelo de horarios con CP-SAT y Python

  • El ejemplo práctico consiste en generar el horario semanal de trabajo de una pequeña tienda
    • La tienda abre todos los días de 8 a. m. a 8 p. m.
    • Cada día tiene tres turnos: Morning, Afternoon y Evening, y cada turno dura 4 horas
    • Hay dos roles: Cashier y Restocker
    • Los empleados son Phil, Emma, David y Rebecca
  • CP-SAT es un solver CP open source incluido en Google OR-Tools
  • Un modelo vacío se crea con cp_model.CpModel() de ortools.sat.python
  • Los roles posibles por empleado son los siguientes
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • El horario se representa con variables booleanas que combinan empleado, rol, día y turno
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] vale 1 si Emma trabaja como Restocker en el turno Evening del lunes, y 0 si no
    • model.new_bool_var() crea una variable cuyo dominio es {0, 1}

Restricciones básicas del horario

  • Como se necesita exactamente un cajero en todos los horarios, la suma del rol Cashier debe ser 1 para cada día y turno
  • Para reposición se necesita solo un turno por día, así que la suma total del rol Restocker de cada día se define como 1
  • Para evitar que un turno Evening de reposición del día anterior quede seguido por un turno Morning de reposición al día siguiente, se limita la suma de ambas asignaciones a no más de 1
  • Un empleado no puede ocupar dos roles al mismo tiempo en el mismo turno, así que la suma de roles por empleado, día y turno debe ser como máximo 1
  • Para no asignar roles para los que alguien no está calificado, todas las variables de roles que ese empleado no puede hacer se fijan en 0
  • El máximo de trabajo por día es de 8 horas, es decir, 2 turnos
    • Si se asignan Morning y Evening el mismo día, queda un tiempo muerto de 4 horas durante Afternoon
    • Al limitar a 1 o menos la suma de asignaciones Morning y Evening por empleado y día, se evita tanto superar 2 turnos por día como dejar ese tiempo muerto intermedio

Ejecución del solver y resultado inicial

  • Para resolver el modelo, se crea cp_model.CpSolver() y se llama a solver.solve(model)
  • Después de obtener una solución, se leen los valores de las variables schedule con solver.value(...)
  • El horario inicial cumple todas las restricciones básicas, pero el resultado asigna a Rebecca 14 turnos en la semana
  • Para evitar horas extra, se agrega una restricción que limita el trabajo semanal de cada empleado a un máximo de 40 horas, es decir, 10 turnos
  • Phil es estudiante de tiempo completo, así que trabaja exactamente 4 turnos por semana y no puede trabajar en Morning ni Afternoon de lunes a viernes por sus clases
  • Para que Phil y Emma no trabajen en el mismo turno, se limita la suma de sus asignaciones a 1 o menos para cada día y turno
  • El trabajo de fin de semana, que a todos les disgusta, se restringe para que los 8 turnos totales de sábado y domingo se repartan entre los cuatro empleados en 2 turnos cada uno

Estados de solución: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • El solver recibe un modelo como entrada y devuelve un estado y una solución
  • OPTIMAL significa que encontró una solución para la cual no existe una mejor
    • Por ejemplo, si x + y >= 5 y se minimiza x + y, (x, y) = (5, 0) es una solución óptima
    • (x, y) = (3, 2) también tiene el mismo valor objetivo, por lo que puede ser una solución óptima
  • INFEASIBLE significa que, sin importar cómo se asignen valores a las variables, no se pueden cumplir las restricciones
    • Por ejemplo, si x ∈ {0, ..., 10} pero se exige x >= 15, es imposible
  • Si el solver se detiene por un límite de tiempo debido a un problema grande o una función objetivo compleja, pueden aparecer dos estados
    • FEASIBLE: se encontró una solución que cumple las restricciones, pero no se sabe si es óptima
    • UNKNOWN: no se encontró ninguna solución, y tampoco se sabe si existe o no una solución

Solicitudes de vacaciones y reparto justo

  • Si se agrega la restricción de que Emma quiere descansar de lunes a viernes, el estado del solver pasa a ser INFEASIBLE
    • Esto ocurre porque no se puede completar el horario sin violar otras restricciones
  • Si se cambia la condición para que Emma descanse solo de lunes a miércoles, sí se puede crear un horario
    • Phil trabaja exactamente 4 turnos, como quería
    • Emma toma 6 turnos, David 10 turnos y Rebecca 8 turnos
  • Para hacer más equitativa la cantidad de turnos entre Emma, David y Rebecca, se agrega una función objetivo
    • Se crean variables enteras total_shifts que representan el total de turnos de cada empleado
    • Con model.new_int_var(0, 10, ...) se crea una variable entera que puede tomar valores de 0 a 10
    • Como Phil es de medio tiempo, se lo excluye, y se usan model.add_min_equality(...) y model.add_max_equality(...) para rastrear el mínimo y el máximo de turnos
    • Con model.minimize(max_shifts - min_shifts) se minimiza la diferencia entre la cantidad máxima y mínima de turnos
  • El resultado final es Phil 4 turnos, Emma 6 turnos, David 9 turnos y Rebecca 9 turnos
    • Emma queda con 6 turnos porque descansa 3 días
    • David y Rebecca quedan repartidos con los mismos 9 turnos

Código de ejemplo y próximo tema

  • Este modelo genera un horario que satisface al mismo tiempo los requisitos del dueño de la tienda y los de los empleados
  • Se pueden seguir agregando restricciones al mismo modelo CP para verificar si una solicitud es posible y, entre las soluciones posibles, buscar un reparto más justo mediante una función objetivo
  • El código de ejemplo está publicado en pganalyze GitHub
  • El tema del próximo artículo es cómo usar programación con restricciones para la selección de índices en Postgres

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-05
Opiniones en Hacker News

  • Hace tiempo usé un solucionador de restricciones, y lo que podía hacer se sentía realmente como magia. El problema es que no hay mucho material apto para principiantes.
    La mayoría es resolver sudokus (el Hello World de este campo) o literatura de investigación primaria altamente técnica, solo para expertos del dominio.
    Es una lástima, porque si estas herramientas se volvieran más accesibles, parece que podrían resolver una cantidad enorme de problemas. Y con “accesibles” sigo queriendo decir que se necesita un programador; convertir un problema en una DSL de restricciones no es algo que la mayoría de la gente pueda hacer bien.

    • Creo que la razón por la que estas herramientas no son lo suficientemente accesibles es que la mayoría de los solucionadores se basan en programación entera mixta (MIP), así que hay que expresar el dominio como ecuaciones matemáticas. Para eso, el usuario debe conocer tanto el dominio como las matemáticas para escribir correctamente las restricciones.
      Pero MIP no es lo único que existe en solucionadores. También hay solucionadores de restricciones basados en búsqueda local, y este enfoque no tiene la limitación de tener que modelar todas las restricciones como relaciones o ecuaciones entre variables enteras.
      En un solucionador de búsqueda local, las restricciones generalmente se tratan como una caja negra que indica qué tan buena es una solución determinada. Por eso es difícil garantizar el óptimo a menos que se prueben todas las soluciones posibles, pero suelen encontrar soluciones subóptimas en un tiempo razonable.
      Timefold Solver es uno de esos solucionadores basados en búsqueda local. El usuario anota el dominio para que el solucionador pueda conocer las variables y sus valores posibles. Así, las restricciones trabajan con Shift y Employee en lugar de int, y también pueden acceder a sus métodos.
      Divulgación: trabajo en Timefold Solver.
    • Exactamente. La sintaxis o API real de los solucionadores de restricciones es tan simple que se puede aprender rápido. La parte que realmente requiere tiempo y experiencia es modelar el problema de esta manera, y casi no hay ejemplos con escala y complejidad reales para tomar como referencia.
      Tengo unos 5 años de experiencia resolviendo problemas de calendarización con MiniZinc, pero lamentablemente todo ese código es privado y no se publicará como open source.
      Me gustaría crear un ejemplo completo de programación con restricciones que incluya contenedorización, visualización y modelado, pero la barrera es encontrar un problema que valga la pena resolver en la práctica y que tenga datos open source utilizables.
    • Estoy de acuerdo en que la reducción (reduction) es mucho más difícil que la teoría en sí. "SAT/SMT by Example" de Dennis Yurichev (https://smt.st/) es un buen recurso sobre este tema, pero intimida bastante.
    • La frase “la mayoría de los materiales son resolver sudokus o literatura de investigación para expertos del dominio” es exacta. Intenté usar un solucionador SAT para un motor de reglas y no tenía ni idea de cómo usarlo.
      Después de bastante razonamiento, logré hacer una prueba de concepto básica, pero no pude escalarla hasta el nivel que realmente necesitaba. La brecha entre una implementación de juguete y algo más sustancial era enorme.
    • Llevo mucho tiempo programando, aunque ahora estoy algo oxidado. El año pasado hice un optimizador de equipos de fútbol con OR-Tools de Google; tenía restricciones de elección como jugar con un amigo y condiciones como equilibrar el nivel de habilidad entre equipos.
      Un LLM me ayudó a avanzar bastante rápido en una dirección aproximadamente correcta. Por ahora falla en acertar exactamente, pero ayudó lo suficiente como para que después pudiera completar el resto por mi cuenta.

  • La clave de todo esto está en aprender a modelar algo en una forma que pueda enviarse a un solucionador. Luego viene aprender a expresar la solución resultante de una manera que una persona pueda entender.
    Lo lamentable es que la mayoría de los programas intentan mantener los datos en una sola representación, y eso va en contra de esta forma de pensar. En la mayoría de los casos no es razonable hacerlo así, y se generan muchas complicaciones para adaptar los algoritmos a esa nueva representación.
    Este artículo también toca este punto al principio, cuando menciona brevemente lo declarativo. Siempre me arrepiento de que mi código no convierta entre representaciones con más frecuencia. Al hacerlo, se pueden obtener representaciones muy concisas y, gracias a esa concisión, también se obtiene el doble beneficio de mayor velocidad.
    Claro que sé que esto termina describiendo muchas pipelines de datos: estructuras que pasan la mayor parte del tiempo transformando datos y ramificándolos hacia varios lugares de cálculo.

  • En un libro que escribí hace tiempo y que ahora estoy reescribiendo, hay un capítulo breve sobre usar MiniZinc desde Python: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc es un sistema de programación con restricciones. También hay un buen curso de Coursera que usa MiniZinc.

    • Me pregunto si tienes el enlace del curso de Coursera.

  • Después de estudiar econometría, usé mucho solucionadores a principios de los 2000 durante una maestría en investigación de operaciones. Ahora trabajo en software web usando Python, y me alegra ver un artículo profundo sobre este tema.
    Me gusta este tema, y leer el artículo me trajo muchos recuerdos. También volví a darme cuenta de que trasladar las restricciones al modelo (variables, estructuras, etc.) es el 90% del trabajo y la parte más difícil.

    • En la maestría usé un programa llamado GAMS.
      La estructura de la sintaxis es completamente de formato libre.
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • Los LLM pueden ayudar bastante a trasladar restricciones a un modelo. Quería probar un adaptador que convierta desde un LLM a un modelo de restricciones.
      Parece una fruta bastante fácil de alcanzar, aunque me pregunto si otros también se beneficiarían.
    • Creo que la parte más difícil es ejecutar el problema minimizándolo en un entorno de producción. Lleva mucho tiempo escalarlo y hacerlo robusto frente a cambios en los datos.

  • Hay un cliente que opera un campamento deportivo para niños. Los niños pueden pedir qué deportes quieren practicar y con qué amigos quieren quedar en el mismo grupo.
    Por eso surgió un problema de scheduling difícil de resolver manualmente, y antes cada año se dedicaban varias semanas de trabajo de personal a esta tarea. Le construimos un sistema simple que conecta los datos del cliente con un optimizador basado en OR-Tools, y ahora el scheduling queda listo con unos cuantos clics.

    • Exacto. Si cargas bien los datos, las restricciones y la función de utilidad en el sistema, puedes encontrar muchísimas soluciones suficientemente buenas muy rápido.
      Entreno una liga de básquetbol y hay 8 periodos. Ningún jugador puede jugar 2 periodos más que otro. La cantidad de alineaciones posibles por partido, aun cumpliendo las restricciones de tiempo de juego, es astronómica.
      Encontrar un conjunto de alineaciones que cumpla las restricciones es muy fácil, pero encontrar uno óptimo o casi óptimo es muy difícil. Se vuelve más interesante si además hay que reflejar a jugadores que llegan tarde o faltan sin avisar.
      *No siempre es completamente posible.
    • Un post de blog que explique en detalle cómo hicieron esto sin duda sería muy popular.

  • Me pregunto si existe un CAD paramétrico que funcione principalmente como solucionador de restricciones.
    Me molesta que con demasiada frecuencia uno tenga que estimar a ojo valores de parámetros que al principio no le importan. Sería bueno poder dejar como restricciones los parámetros que sí interesan y optimizar el resto.

  • Me pregunto cómo se compara este enfoque con la programación entera mixta. ¿Y qué tal para problemas de física?

    • Muchos problemas pueden plantearse de ambas formas. MILP siempre tiene una función objetivo, y las restricciones siempre son combinaciones lineales de variables de decisión.
      Como Gurobi es increíblemente rápido, puede valer la pena forzar un problema para encajarlo como MILP con tal de obtener una solución.
    • CP-SAT es solo para enteros, así que no creo que sea muy bueno para física. Puedes escalar números reales, pero no es tan bueno como tratar directamente con punto flotante.
      La ventaja de CP-SAT es que maneja variables y restricciones booleanas y enteras mucho más eficientemente que un solucionador MIP, especialmente con restricciones de alto nivel como all_different.
    • En general, supongo que son parecidos. https://www.amazon.com/gp/product/1107658799/ es el último libro que leí sobre este tema, y cubre muchas de las mismas ideas.
      En particular, creo que la parte de este artículo donde se intenta minimizar algún valor está escribiendo directamente sobre lo mismo.