Saltar al contenido
Volver a los resultados

Programación con Restricciones

Propuesto por
Rossi, van Beek & Walsh
Año
2006
Tipo
Declarative combinatorial optimization
Familia
Mathematical programming

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Programación con Restricciones (CP) es un paradigma de optimización declarativo en el que un problema se formula como un conjunto de variables, dominios finitos y restricciones, y un solucionador busca sistemáticamente asignaciones que satisfagan todas las restricciones.

Formalizada de manera exhaustiva por Rossi, van Beek y Walsh en su Handbook of Constraint Programming de 2006, la CP unifica la poda basada en propagación con la búsqueda de retroceso inteligente para abordar problemas combinatorios en los dominios de planificación, programación y configuración.

La intuición detrás del método

Piense en la CP como el llenado de un complejo rompecabezas: cada casilla es una variable con un conjunto de valores legales, y cada regla del rompecabezas es una restricción. En lugar de adivinar a ciegas, la CP utiliza las reglas para eliminar inmediatamente valores imposibles de las casillas vecinas cada vez que se llena una casilla. Esta propagación reduce drásticamente el espacio de búsqueda, por lo que el solucionador explora solo combinaciones plausibles, retrocediendo y revisando solo cuando llega a un callejón sin salida.

Historia

La Programación con Restricciones surgió de la investigación en inteligencia artificial en la década de 1970 con trabajos tempranos sobre satisfacción de restricciones de Montanari y Mackworth. Maduró a lo largo de las décadas de 1980 y 1990 con el desarrollo de algoritmos de consistencia de arco, restricciones globales y solucionadores prácticos como CHIP e ILOG Solver. El campo fue consolidado autoritativamente por Rossi, van Beek y Walsh en el Handbook of Constraint Programming de 2006, que sigue siendo la referencia definitiva, cubriendo teoría, algoritmos y aplicaciones en optimización combinatoria.

Cuándo usarlo

La Programación con Restricciones se adapta mejor a problemas combinatorios con restricciones complejas y heterogéneas —planificación, horarios, configuración y enrutamiento— donde la factibilidad es tan importante como la optimalidad. Asume que los problemas pueden modelarse con dominios de variables discretos o enumerables. La CP es menos efectiva para optimización continua o programas lineales a gran escala, donde los solucionadores de Programación Lineal o Programación Entera Mixta suelen dominar. Cuando las restricciones están altamente estructuradas y la propagación puede podar grandes porciones del espacio de búsqueda, la CP supera a las metaheurísticas de propósito general.

Limitaciones y consideraciones

  • Escalabilidad: la búsqueda exponencial en el peor de los casos hace que la CP sea lenta en instancias muy grandes con propagación débil.
  • Requiere buen modelado: heurísticas deficientes de ordenación de variables/valores o la omisión de restricciones globales conducen a árboles de búsqueda innecesariamente grandes.
  • Dominios continuos: la CP está diseñada nativamente para dominios discretos; los problemas continuos requieren extensiones especializadas o enfoques híbridos.
  • Experiencia en solucionadores: el uso efectivo exige familiaridad con las técnicas de modelado de restricciones y las bibliotecas de restricciones globales específicas del solucionador.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Modelado declarativo: las reglas complejas del mundo real se expresan directamente como restricciones sin especificar el procedimiento de búsqueda.
  • Poda potente: la propagación de restricciones elimina regiones infactibles tempranamente, a menudo reduciendo la búsqueda en órdenes de magnitud.
  • Maneja restricciones heterogéneas: restricciones lógicas, aritméticas, globales y definidas por el usuario coexisten de forma natural en un único modelo.
  • Garantiza completitud: el solucionador encuentra una solución óptima o prueba la infactibilidad, a diferencia de los métodos heurísticos.

Aplicaciones

  • Programación de empleados y enfermeras: asignación de personal a turnos mientras se satisfacen las restricciones de disponibilidad, leyes laborales y habilidades.
  • Elaboración de horarios: construcción de horarios universitarios o escolares sujetos a restricciones de capacidad de aulas, disponibilidad de instructores y currículo.
  • Configuración: ensamblaje de configuraciones de productos (computadoras, vehículos) a partir de catálogos de componentes bajo restricciones de compatibilidad y recursos.
  • Enrutamiento de vehículos y logística: planificación de rutas de entrega sujetas a ventanas de tiempo, capacidades de vehículos y regulaciones de conductores.
  • Subastas combinatorias y asignación de recursos: asignación de recursos a postores o tareas bajo restricciones de exclusividad y presupuesto.

Cómo funciona

Cómo funciona

1

El problema se codifica como una tripleta de Problema de Satisfacción de Restricciones que consta de variables X, sus dominios finitos D y un conjunto de restricciones C. Cada variable x_i puede asignarse cualquier valor de su dominio D_i. Las restricciones definen combinaciones permisibles de valores en subconjuntos de variables, traduciendo reglas del mundo real —límites de capacidad, relaciones de precedencia, conflictos de recursos— en una estructura matemática sobre la cual el solucionador puede razonar.

Fórmula
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}
2

Antes y durante la búsqueda, el solucionador aplica consistencia de arco y otros algoritmos de consistencia local para podar valores de dominio que no pueden participar en ninguna solución válida. Para cada par de variables restringidas, la consistencia de arco elimina valores del dominio de una variable para los cuales no existe un valor de apoyo en la otra. Esta propagación se activa repetidamente después de cada asignación, reduciendo drásticamente el espacio de búsqueda efectivo.

Fórmula
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}
3

El solucionador selecciona una variable no asignada —típicamente usando heurísticas como valores restantes mínimos o grado— y le asigna tentativamente un valor de su dominio podado. La propagación se ejecuta de nuevo; si se detecta una contradicción (un dominio vacío), el solucionador retrocede al punto de elección más reciente y prueba un valor alternativo. El retroceso y el registro de 'nogoods' pueden acelerar aún más la recuperación de fallos.

Fórmula
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}
4

Cuando todas las variables han sido asignadas valores consistentes con cada restricción, la asignación completa S* constituye una solución. Para problemas de optimización, una función objetivo guía la búsqueda hacia la mejor solución factible, y las estrategias de ramificación y acotación refinan progresivamente la cota a medida que se encuentran mejores soluciones, hasta que se certifica el óptimo global o se alcanza un límite de tiempo.

Fórmula
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}

Errores comunes

  • La sobrecarga del modelo con restricciones redundantes o conflictivas hace que el solucionador informe incorrectamente de la infactibilidad.
  • Descuidar restricciones globales (por ejemplo, alldifferent, cumulative) pierde oportunidades de propagación que los algoritmos especializados proporcionan de forma gratuita.
  • Ignorar las heurísticas de búsqueda y depender de la ordenación predeterminada de variables/valores puede desperdiciar tiempo exponencial en ordenaciones patológicas.
  • Confundir satisfacción de restricciones con optimización: olvidar añadir una función objetivo y acotación de límites produce solo la primera solución factible, no la mejor.

Preguntas frecuentes

¿Cómo difiere la Programación con Restricciones de la Programación Lineal Entera?

Si bien ambas resuelven problemas combinatorios, la Programación Lineal Entera requiere que todas las restricciones y objetivos sean lineales, lo que permite cotas eficientes de relajación lineal. La CP no impone tal requisito de linealidad y en su lugar se basa en la propagación de restricciones y la búsqueda sistemática. La CP maneja restricciones lógicas y globales complejas de forma más natural, mientras que la Programación Lineal Entera a menudo escala mejor en problemas con una fuerte estructura lineal y un gran número de variables.

¿Qué son las restricciones globales y por qué son importantes?

Las restricciones globales son restricciones de alto nivel sobre un número arbitrario de variables —por ejemplo, alldifferent (todas las variables toman valores distintos) o cumulative (el uso de recursos en cualquier momento no excede la capacidad). Son importantes porque los solucionadores implementan algoritmos de propagación dedicados y altamente eficientes para cada una, logrando una poda mucho más fuerte que la descomposición de la misma condición en muchas restricciones binarias, lo que dejaría gran parte del espacio de búsqueda sin explorar.

¿Puede la Programación con Restricciones encontrar soluciones óptimas, o solo factibles?

La CP puede encontrar soluciones óptimas combinando la búsqueda de factibilidad con una función objetivo. El solucionador utiliza ramificación y acotación: una vez que se encuentra una solución factible, añade una restricción que exige que cualquier solución subsiguiente sea estrictamente mejor, continuando hasta que no sea posible ninguna mejora. Esto certifica la optimalidad. Si el tiempo de ejecución es limitado, se devuelve la mejor solución encontrada hasta el momento como una aproximación.

Métodos relacionados

Fuentes

  1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

    ISBN: 978-0-444-52726-4
    Copiado.