Por Ignacia Córdova
Un ejemplo para partir
Un problema importante en la gestión de empresas que operan en horarios continuados, como las del rubro de la producción, es la organización de los horarios de sus empleados. Esto es lo que se conoce como “Employee Scheduling” o programación de trabajadores. El desafío implica crear horarios semanales y asignar turnos a los colaboradores. Pensemos en una situación que ocurre frecuentemente en este tipo de problemas. Una empresa posee tres turnos de 8 horas cada día y asigna tres de sus cuatro trabajadores a diferentes turnos por día, mientras que el cuarto goza del día libre. Como podemos imaginar, aunque sea un problema pequeño, la cantidad de combinaciones posibles es bastante grande. Si hacemos los cálculos en un día hay 4! (24) posibles asignaciones de empleados. Pensando en una semana el número de programaciones semanales posibles es 24^7 (4500 millones). Sin embargo, si situamos este problema en la vida real, nos encontraremos con otras restricciones o limitaciones que reducen este número como, por ejemplo, las horas máximas que puede trabajar un empleado a la semana.
¿Qué es el Constraint Programming?
Una de las metodologías para resolver este tipo de problemas es el Constraint Programming. La “programación basada en restricciones” se centra en encontrar las soluciones factibles de un conjunto de soluciones posibles, modelando el problema respetando las restricciones o limitaciones que se tienen. Su principal objetivo es la viabilidad, es decir, encontrar una solución factible y no una óptima. Esto lo realiza centrándose en las restricciones del problema y no en la función objetivo. Puede suceder que un problema de Constraint Programming no posea una función objetivo. Por ejemplo, su finalidad puede ser reducir un conjunto grande de posibles soluciones a un conjunto más acotado que satisfaga ciertas restricciones.
Nace de la informática, especialmente de la teoría de grafos y los primeros intentos de inteligencia artificial. Estas características lo convierten en un método eficaz para resolver múltiples problemas del mundo real. En general, se utiliza en planificación de la producción, y en la programación de horarios y turnos de trabajo, pero puede ser aplicada en múltiples áreas. Un tipo muy común de aplicación de este método es resolver un Sudoku. Un sudoku puede ser representado con 81 variables (9 filas y 9 columnas) que toman los valores del 1 al 9 con la principal limitación de que las variables en una columna, fila o bloque nunca sean iguales.
Sus fortalezas y cuándo utilizarlo
Su principal beneficio es que puede resolver problemas complejos, que su alternativa, la programación matemática, no siempre es capaz de solucionar de forma eficiente. Nos ayuda con problemáticas que presentan restricciones de naturaleza no lineal, espacios de soluciones no convexas con muchas soluciones óptimas locales o información deficiente debido a una relajación lineal. Es decir, si contamos con un problema de lenta convergencia, podría ser mejor utilizar Constraint Programming. Podemos ver otras diferencias en la siguiente imagen:
Tipos y Tips
Existen 2 tipos de Constraint Programming. El primero es el Constraint Satisfaction Problem o CSP, que es el tipo de programación de restricciones más simple. A este se le entrega un conjunto de variables de decisión y, para cada una de ellas, un dominio con valores potenciales. También se le otorga un set de restricciones para estas variables de decisión. Su principal objetivo es encontrar una asignación de valores a las variables donde se hayan cumplido las restricciones.
En contraste, existe el Constraint Optimization Problem o COP. Es muy parecido al tipo de problema anterior, pero a este le entregamos un problema con una función objetivo que maximice o minimice alguna variable o expresión, y nos da como resultado una asignación de valores donde se optimice la función objetivo y se cumplan las restricciones.
Para modelar problemas con este método hay que tener en cuenta algunas características importantes. El Constraint Programming es declarativo, es decir, siempre se describe el resultado final deseado determinando automáticamente la vía de solución. El mayor esfuerzo al modelar se debe gastar en describir el problema, no en resolverlo. Para esto, la representación del problema puede ser tu mejor aliado. ¿Quieres saber más sobre esta herramienta o tu empresa tiene un problema que podemos resolver? Conversemos.
