Saltar al contenido
Volver a los resultados

Programación Entera — PE y Programación Entera Mixta (PEM)

Propuesto por
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
Año
1958
Tipo
Mathematical optimisation — exact combinatorial method

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 entera (PE), también llamada programación entera mixta (PEM) cuando solo algunas variables están restringidas a números enteros, es una rama de la optimización matemática en la que algunas o todas las variables de decisión deben tomar valores enteros o binarios.

Basándose en la programación lineal, se formalizó a través del método de planos de corte de Ralph Gomory (1958) y el algoritmo de ramificación y acotación de Land y Doig (1960), y desde entonces se ha convertido en el marco exacto estándar para problemas de planificación, asignación, enrutamiento y asignación de recursos.

La intuición detrás del método

La programación lineal ordinaria encuentra el mejor punto en una región factible continua. Pero muchas decisiones reales son discretas: no se puede tener 2.7 enfermeras o abrir medio almacén. La programación entera añade la restricción de que algunas o todas las variables deben ser números enteros (o elecciones binarias 0/1). El precio de esa restricción es computacional: el conjunto factible ya no es una superficie lisa sino un conjunto disperso de puntos, y encontrar el mejor puede requerir examinar un número enorme de soluciones candidatas. Los solucionadores gestionan esto dividiendo inteligentemente el problema en subproblemas más pequeños (ramificación) y podando ramas que no pueden superar la mejor solución encontrada hasta el momento (acotación), al mismo tiempo que ajustan la aproximación continua mediante desigualdades añadidas (planos de corte).

Historia

La programación entera surgió a finales de la década de 1950 cuando los investigadores buscaron extender la programación lineal a decisiones discretas. Ralph Gomory introdujo el método sistemático de planos de corte en 1958, demostrando que cualquier programa entero podía en principio resolverse añadiendo un número finito de cortes. Land y Doig (1960) formalizaron la ramificación y acotación, que se convirtió en el algoritmo exacto dominante. Wolsey (1998) y Nemhauser y Wolsey (1988) proporcionaron los tratamientos de libros de texto canónicos en los que el campo todavía se basa. La revolución práctica llegó con el desarrollo de solucionadores de ramificación y corte en la década de 1990, que combinaban ambas técnicas con heurísticas avanzadas, y más tarde con la explosión del rendimiento de los solucionadores comerciales y de código abierto que permiten aplicaciones del mundo real a gran escala hoy en día.

Cuándo usarlo

Utilice la programación entera cuando las decisiones sean inherentemente discretas —elecciones binarias de sí/no, cantidades enteras o restricciones lógicas de encendido/apagado— y cuando necesite una solución óptima exacta o casi exacta con una cota de calidad demostrable. Es adecuada para problemas de planificación, asignación de personal y recursos, enrutamiento de vehículos, localización de instalaciones, presupuestación de capital y selección de carteras. No hay requisito de tamaño mínimo de muestra porque la PE es un marco de optimización determinista en lugar de un procedimiento de inferencia estadística. Los tipos de variables pueden ser binarios, categóricos (codificados como binarios) o continuos (en el caso mixto entero). El requisito práctico clave es que el problema pueda modelarse con un objetivo lineal y restricciones lineales; si el objetivo o las restricciones son no lineales, se necesitan extensiones de programación no lineal entera mixta (PNEM).

Limitaciones y consideraciones

  • La programación entera es NP-difícil en general; el tiempo de resolución puede crecer exponencialmente con el tamaño del problema y una formulación deficiente.
  • Una relajación de PL débil (gran brecha de integralidad) conduce a árboles de búsqueda profundos y costosos y a largos tiempos de ejecución.
  • La expansión binaria de variables categóricas de alta cardinalidad puede disparar el tamaño del modelo.
  • Para instancias muy grandes, los solucionadores pueden necesitar ser terminados anticipadamente con una tolerancia de brecha en lugar de lograr una brecha cero.

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

Fortalezas

  • Produce soluciones óptimas exactas con una brecha de optimalidad certificada, a diferencia de las heurísticas que no ofrecen garantía de calidad.
  • Maneja variables binarias y enteras generales de forma nativa, lo que lo convierte en el marco natural para decisiones combinatorias.
  • Aplicable a una amplia gama de problemas de dominio —planificación, enrutamiento, asignación, mochila— con la misma maquinaria matemática.
  • Los solucionadores modernos de ramificación y corte pueden resolver problemas con millones de variables y restricciones que habrían sido intratables hace décadas.

Aplicaciones

  • Planificación de personal y enfermería — asignación de turnos para cumplir con los requisitos de cobertura respetando las regulaciones de horas de trabajo.
  • Enrutamiento de vehículos y logística — encontrar rutas de entrega de costo mínimo bajo restricciones de capacidad y ventanas de tiempo.
  • Localización de instalaciones — decidir qué almacenes o plantas abrir para minimizar el costo total de distribución.
  • Presupuestación de capital — seleccionar una cartera de proyectos de inversión dentro de un presupuesto para maximizar el retorno total.
  • Planificación de producción — determinar tamaños de lote enteros a lo largo de períodos de tiempo para equilibrar costos de configuración y costos de mantenimiento.
  • Diseño de redes — elegir qué enlaces instalar en una red de comunicación o transporte.

Cómo funciona

Cómo funciona

1

El problema se plantea como un programa matemático: definir variables de decisión (que deben declararse como enteras o binarias donde el problema lo requiera), escribir una función objetivo lineal para minimizar o maximizar, y listar todas las restricciones lineales. Una formulación ajustada —una cuya relajación continua (PL) esté lo más cerca posible del óptimo entero verdadero— reduce drásticamente el tiempo de resolución.

2

Las restricciones de integralidad se eliminan temporalmente para obtener la relajación de PL. Resolver esta relajación es rápido y produce una cota: su valor óptimo es siempre al menos tan bueno como el óptimo entero verdadero (una cota inferior para minimización). Si la solución de la relajación resulta ser completamente entera, el problema está resuelto. De lo contrario, la brecha entre la relajación y la integralidad guía la búsqueda.

3

Se selecciona una variable fraccionaria en la solución de la relajación y el problema se divide en dos subproblemas: uno que requiere que esa variable se redondee hacia abajo, otro redondeada hacia arriba. Cada subproblema se relaja y resuelve, creando un árbol de búsqueda. Las ramas cuya cota de relajación sea peor que la mejor solución entera encontrada hasta el momento se podan sin exploración adicional.

4

Los planos de corte son desigualdades lineales válidas que cortan parte de la región factible de la relajación de PL sin eliminar ningún punto entero factible. Añadir cortes fuertes (cortes de Gomory, desigualdades de cobertura, cortes de clique) ajusta la cota de PL y reduce el número de nodos que el solucionador debe explorar.

5

La mejor solución entera factible encontrada en todos los nodos explorados se devuelve como el óptimo. Se informa la brecha de optimalidad —la diferencia porcentual entre la mejor solución entera y la mejor cota restante; una brecha de cero certifica la optimalidad global. Para instancias NP-difíciles grandes, el solucionador puede terminar anticipadamente con una tolerancia de brecha especificada por el usuario, devolviendo una solución casi óptima con una cota demostrable.

Errores comunes

  • Declarar variables como continuas cuando deberían ser enteras —o viceversa— produce silenciosamente soluciones incorrectas; siempre verifique que los tipos de variables coincidan con la realidad física del problema.
  • Una formulación laxa con una gran brecha de relajación de PL causa ramificación excesiva; invierta tiempo en ajustar la formulación (desigualdades fuertes, ruptura de simetría) antes de resolver.
  • Ignorar la brecha de integralidad en la salida del solucionador: un valor objetivo reportado es solo la mejor solución entera encontrada, no necesariamente el óptimo global a menos que la brecha sea cero.
  • Aplicar PE a problemas cuyos objetivos o restricciones son no lineales sin el tratamiento adecuado de PNEM producirá modelos incorrectos.
  • Para problemas de planificación o enrutamiento, no añadir desigualdades válidas (como cortes de clique o de cobertura) deja importantes ganancias de rendimiento sin aprovechar.

Preguntas frecuentes

¿Cuál es la diferencia entre PE y PEM?

En la programación entera pura (PE) cada variable de decisión debe ser un entero. En la programación entera mixta (PEM), algunas variables son enteras o binarias mientras que otras pueden ser continuas. La PEM es el marco más general y más comúnmente utilizado en la práctica, porque la mayoría de los problemas reales mezclan opciones discretas con cantidades continuas.

¿Por qué la programación entera es NP-difícil si la programación lineal es polinomial?

La programación lineal optimiza sobre un politopo convexo y puede resolverse en tiempo polinomial por los métodos simplex o de puntos interiores. Añadir restricciones de integralidad rompe esta convexidad: el conjunto factible se convierte en un conjunto finito pero potencialmente astronómicamente grande de puntos enteros, y no se conoce ningún algoritmo de tiempo polinomial para encontrar el mejor en general. La relajación de PL proporciona una cota pero no una solución directa.

¿Cómo sé si mi solución es óptima?

El solucionador informa una brecha de optimalidad —la diferencia porcentual entre la mejor solución entera encontrada y la mejor cota inferior restante. Una brecha del 0% certifica la optimalidad global. Para problemas grandes puede establecer una tolerancia de brecha (por ejemplo, 1%) y aceptar una solución casi óptima; la cota aún garantiza que el óptimo verdadero no puede ser mejor que ese porcentaje.

¿Qué hace que una formulación sea 'ajustada' y por qué importa?

Una formulación ajustada es aquella cuya relajación de PL da una cota cercana al óptimo entero, dejando una pequeña brecha de integralidad. Cuando la brecha es pequeña, la ramificación y acotación necesita explorar menos nodos y termina más rápido. Añadir desigualdades válidas como cortes de Gomory, desigualdades de cobertura o cortes de clique ajusta la formulación y a menudo es la forma más impactante de acelerar un solucionador.

Métodos relacionados

Fuentes

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    Copiado.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    Copiado.