Optimización de restricciones, o programación de restricciones (CP), es el nombre que se le da a la identificación de soluciones posibles a partir de un conjunto muy grande de candidatos, en la que el problema se puede modelar en términos de restricciones arbitrarias. Hay problemas en la CP en muchas disciplinas científicas y de ingeniería. (La palabra “programación” es un término inadecuado, similar a lo que alguna vez “computadora” significaba “una persona que calcula”). Aquí, "programación" se refiere a la disposición de un plan, en lugar de programar en un lenguaje de programación).
La CP se basa en la viabilidad (buscar una solución factible) en lugar de la optimización (en la búsqueda de una solución óptima) y se centra en las restricciones y las variables, en lugar de la función objetiva. De hecho, es posible que un problema de PC ni siquiera tenga una función objetiva. El objetivo puede ser reducir un conjunto muy grande de soluciones posibles a un subconjunto más manejable agregando restricciones al problema.
Un ejemplo de un problema que es adecuado para CP es la programación de empleados.
El problema surge cuando las empresas que funcionan de forma continua, como las fábricas, necesitan crear horarios semanales para sus empleados. Este es un ejemplo muy simplificado: una empresa ejecuta tres turnos de 8 horas por día y asigna tres de sus cuatro empleados a diferentes turnos cada día, mientras da el cuarto día libre. Incluso en un caso tan pequeño, la cantidad de programas posibles es enorme: cada día, hay 4! = 4 * 3 * 2 * 1 = 24 asignaciones de empleados posibles, por lo que la cantidad de programas semanales posibles es 247, que es más de 24,000 millones.
Por lo general, habrá otras restricciones que reduzcan la cantidad de soluciones posibles; por ejemplo, que cada empleado trabaje al menos una cantidad mínima de días por semana. El método de CP hace un seguimiento de qué soluciones siguen siendo viables cuando agregas restricciones nuevas, lo que la convierte en una herramienta potente para resolver problemas de programación grandes y reales.
CP cuenta con una comunidad amplia y muy activa en todo el mundo, con revistas científicas dedicadas y conferencias y un arsenal de diferentes técnicas de resolución. La CP se aplicó correctamente en la planificación, la programación y muchos otros dominios con restricciones heterogéneas.
Herramientas
Google ofrece algunas maneras de resolver los problemas de CP:
- Resolución de CP-SAT: Es un agente de programación de restricciones que usa métodos de SAT (satisfacción).
- Resolución de CP original: Es un solucionador de programación de restricciones que se usa en la biblioteca de enrutamiento.
Si tu problema se puede modelar con un objetivo y restricciones lineales, entonces tienes un problema de programación lineal y deberías considerar MPSolver. (Sin embargo, los problemas de ruta generalmente se resuelven mejor con nuestra biblioteca de enrutamiento de vehículos incluso si se pueden representar con un modelo lineal).
Ejemplos
En la siguiente sección, se describe el solucionador de problemas CP-SAT, el solucionador de herramientas del OR principal para la programación de restricciones. (SAT significa satisfabilidad: la resolución utiliza técnicas para resolver problemas de SAT junto con los métodos de CP).
Estos son algunos ejemplos de problemas de programación que son adecuados para el solucionador de problemas del CP-SAT:
Dos problemas clásicos de CP son el problema de N-queens y los acertijos criptoaritméticos.