¿Qué es el constraint solving?: De una necesidad puntual a una tesis completa
Todo comenzó con un problema muy concreto: una universidad muy importante, cliente de Bitlogic, necesitaba encontrar una forma eficiente de planificar las mesas de examen. La tarea no era simple: había que coordinar aulas, profesores, materias, carreras y horarios, todo bajo un conjunto de restricciones que debían cumplirse al mismo tiempo.
Este tipo de desafíos no son exclusivos del ámbito académico. En cualquier organización, asignar recursos limitados respetando condiciones específicas puede convertirse en un dolor de cabeza. Desde turnos de trabajo hasta rutas de distribución, la complejidad crece exponencialmente a medida que se agregan variables y reglas.
Frente a este escenario, Edgardo Hames, socio fundador de Bitlogic, me propuso investigar una herramienta llamada OptaPlanner con la idea de ver si podía aplicarse directamente al problema de la universidad. Eventualmente la investigación fue creciendo, y lo que empezó como una exploración aplicada terminó convirtiéndose en una especie de benchmark más amplio: un análisis comparativo entre distintas tecnologías y frameworks de Constraint Solving.
¿Qué es el Constraint Solving? Es un paradigma de programación que consiste en modelar un problema como un conjunto de restricciones que deben cumplirse simultáneamente. A diferencia de los enfoques tradicionales de programación, donde solemos dar una secuencia de pasos para llegar a una solución, aquí lo que hacemos es describir el problema y las condiciones que limitan sus posibles soluciones. El trabajo del algoritmo es, justamente, encontrar una combinación de asignaciones que satisfaga esas condiciones.
Estas restricciones suelen dividirse en dos tipos:
- Restricciones duras (hard constraints): son inquebrantables. Si se violan, la solución directamente no es válida.
- Restricciones blandas (soft constraints): son deseables pero no obligatorias. Se pueden relajar si es necesario, aunque cada vez que se incumplen generan un “costo” que el algoritmo intentará minimizar.
Ejemplo simple: imaginemos que debemos organizar exámenes en una universidad.
- Una restricción dura podría ser: “dos exámenes de la misma carrera no pueden programarse a la misma hora”.
- Otra restricción dura sería: “un aula no puede asignarse a dos materias al mismo tiempo”.
- En cambio, una restricción blanda podría ser: “tratar que un profesor no tenga exámenes en días consecutivos” o “evitar que los estudiantes tengan más de dos exámenes el mismo día”.
Si solo consideramos las restricciones duras, cualquier solución que las cumpla sería técnicamente válida. Pero al incluir también las blandas, podemos buscar no solo soluciones factibles, sino soluciones óptimas: aquellas que además de ser posibles, minimizan los conflictos y maximizan la comodidad de profesores y estudiantes.
Esto mismo se aplica a muchos otros dominios, por ejemplo:
- En logística, que un camión deba visitar todas las ciudades (restricción dura), pero que se intente minimizar el consumo de combustible o el tiempo de viaje (restricción blanda).
- En asignación de turnos, que un médico no pueda estar en dos guardias al mismo tiempo (dura), pero que se intente distribuir las horas de forma equitativa (blanda).
En definitiva, el poder del Constraint Solving está en transformar problemas muy complejos en modelos declarativos que un algoritmo puede procesar. El desafío está en diseñar este modelo de forma precisa y en elegir el algoritmo y la herramienta adecuada para encontrar soluciones dentro de un espacio de búsqueda que en muchos casos, es tan grande que sería imposible recorrerlo a mano o con métodos ingenuos.
En la práctica, esto significa poder buscar soluciones óptimas o casi óptimas a problemas donde la cantidad de combinaciones posibles es inmanejable para un enfoque tradicional. Este tipo de problemas suelen ser NP-hard, lo que implica que incluso con instancias pequeñas el espacio de búsqueda crece de manera exponencial.
Para hacer frente a esta complejidad, en la tesis me concentré en el algoritmo Local Search y en algunas de sus variantes más utilizadas:
- Hill Climbing, que mejora progresivamente la solución actual evaluando sus vecinos más cercanos.
- Tabu Search, que evita caer en ciclos o soluciones locales poco deseables manteniendo una “lista tabú” de estados ya explorados.
- Simulated Annealing, inspirado en procesos de la metalurgia, que permite aceptar soluciones peores con cierta probabilidad al inicio de la búsqueda, para luego ir afinando hacia la convergencia global.
Estos enfoques no garantizan siempre encontrar la solución perfecta, pero sí permiten obtener resultados de alta calidad en tiempos razonables, lo cual es fundamental cuando hablamos de problemas reales de planificación, logística o asignación de recursos.
Con ese marco, seleccioné tres de los frameworks de código abierto más utilizados en Java para llevar la investigación a un plano práctico:
Para evaluarlos, los puse a prueba en distintos casos de estudio representativos:
- Las N reinas: un clásico de la teoría computacional. Sirvió como punto de partida para comparar la facilidad de modelado y la rapidez de resolución de cada herramienta.
- Sudoku “Everest”: considerado el más difícil del mundo. Este reto fue clave para testear la robustez de los frameworks en un problema altamente combinatorio. No todos los solvers pudieron resolverlo en tiempos aceptables, lo que mostró diferencias claras en sus enfoques.
- Asignación de cuadernos: un caso original inspirado en la vida cotidiana: minimizar la cantidad de cuadernos que una estudiante necesita llevar según su horario. Este ejemplo puso a prueba la capacidad de modelar situaciones más cercanas al mundo real, donde conviven restricciones duras (como materias en un mismo día) y blandas (como la comodidad de no sobrecargar la mochila). Para mas detalles del problema referirse al documento de la tesis adjunto al final.
De los resultados obtenidos surgieron varias conclusiones interesantes:
- Choco-solver: Se destacó por su eficiencia y un modelado muy compacto. Resultó ser el más rápido en varios experimentos, especialmente en problemas combinatorios. Óptimo para enfrentar problemas clásicos y bien estructurados.
- OptaPlanner: Mostró su fuerza en escenarios de planificación más realistas, donde la flexibilidad y la capacidad de configurar heurísticas fueron decisivas. Ofreció una gran expresividad en el modelado,aunque requirió un esfuerzo de implementación mayor. Este framework es ideal para problemas complejos de planificación.
- JaCoP: Presenta limitaciones importantes para trabajar con restricciones blandas, lo que impacta en la capacidad de optimización en escenarios más realistas. Aunque más limitado, es simple y accesible para quienes recién empiezan en el campo. Se mantiene como una buena puerta de entrada para aprender sobre programación con restricciones.
En definitiva, la comparación dejó en claro que no existe un “solver perfecto” para todos los casos. La elección depende del tipo de problema, la complejidad del modelo y las necesidades prácticas.
Más allá de lo académico, la conclusión fue clara: este enfoque tiene un enorme potencial para resolver problemas reales de planificación y optimización. Desde organizar horarios en instituciones educativas, hasta optimizar rutas de entrega, asignar turnos de trabajo o gestionar recursos en empresas industriales.
Lo que comenzó con la necesidad puntual de un cliente se transformó en una tesis que no sólo exploró el estado del arte en herramientas de Constraint Solving, sino que también dejó abierta la puerta a múltiples aplicaciones prácticas que hoy son cada vez más relevantes en organizaciones que buscan eficiencia y flexibilidad.
Este artículo resume los puntos principales de la investigación, pero la tesis completa incluye un análisis más detallado de algoritmos, experimentos y resultados. Se puede acceder al documento completo acá: Constraint solving y su aplicación práctica a problemas con restricciones.
Si estás evaluando tus opciones y quieres compartirlas con nosotros para conocer nuestra mirada, agendemos una charla ☕ ¡el café corre por nuestra cuenta!
