Saltar al contenido
Volver a los resultados

Programación Entera Mixta — Optimización exacta sobre decisiones continuas y enteras

Propuesto por
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
Año
1958–1960
Tipo
Mathematical optimization
Familia
Simulation / optimization

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 Mixta (MIP, por sus siglas en inglés) es un marco de optimización matemática en el que algunas variables de decisión deben tomar valores enteros mientras que otras pueden ser continuas.

Generaliza la programación lineal y se utiliza ampliamente en investigación de operaciones, logística, planificación, asignación de recursos y diseño de ingeniería, donde surgen de forma natural restricciones de indivisibilidad — como decisiones de sí/no o cantidades de unidades completas.

La intuición detrás del método

Muchos problemas de optimización reales implican decisiones que no se pueden dividir: o se abre una instalación o no, se asigna exactamente un trabajador a un turno, se piden unidades completas. La programación lineal continua ignora estas realidades y puede producir respuestas fraccionarias no implementables. La MIP impone la integralidad directamente en el modelo. El solucionador explora sistemáticamente el espacio de soluciones enteras factibles mediante ramificación y acotación (branch-and-bound): resuelve subproblemas continuos relajados para acotar la mejor solución posible en cada región, descarta regiones que no pueden mejorar la mejor solución entera encontrada hasta el momento y añade planos de corte para refinar la búsqueda. El resultado es un plan demostrablemente óptimo o casi óptimo.

Historia

Los cimientos de la programación entera fueron sentados por Ralph Gomory, quien introdujo el método de planos de corte en 1958, y por Land y Doig, quienes formalizaron la ramificación y acotación en 1960. Las décadas siguientes vieron el desarrollo de la teoría de relajación LP, la combinatoria poliédrica (Edmonds, Padberg, Grötschel) y, para la década de 1990, los solucionadores comerciales hicieron práctica la MIP a gran escala. El campo se trata de manera exhaustiva en Nemhauser y Wolsey (1988) y Wolsey (1998).

Cuándo usarlo

Utilizar MIP cuando su problema tenga un objetivo y restricciones lineales o linealizables e incluya decisiones que deban ser de valor entero (localización de instalaciones, planificación de personal, presupuestación de capital, diseño de redes, problemas de corte). Es el método de elección cuando se necesita una solución demostrablemente óptima o con brecha acotada y el tamaño del problema es manejable (miles de variables con solucionadores modernos). NO utilizar MIP cuando el objetivo o las restricciones sean altamente no lineales (utilizar programación no lineal o de enteros mixtos no lineal en su lugar), cuando el problema sea tan grande que los métodos exactos sean prohibitivos (considerar heurísticas o metaheurísticas), o cuando las aproximaciones continuas sean suficientemente precisas (utilizar LP por velocidad).

Limitaciones y consideraciones

  • La complejidad en el peor de los casos es NP-difícil; el tiempo de resolución puede crecer exponencialmente con el número de variables enteras.
  • Requiere una formulación matemática precisa; los modelos mal formulados pueden ser intratables incluso cuando el problema subyacente es manejable.
  • Los elementos no convexos o no lineales requieren linealización adicional o solucionadores especializados, lo que aumenta la complejidad del modelo.
  • Los costos de licencia de los solucionadores pueden ser significativos para herramientas comerciales, aunque existen alternativas de código abierto de alta calidad.
  • Los resultados solo son tan buenos como el modelo: una especificación incorrecta de las restricciones conduce a óptimos sin sentido.

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 demostrablemente óptimas con una brecha de optimalidad cuantificable, lo que permite una justificación rigurosa de las decisiones.
  • Maneja variables binarias y enteras generales de forma nativa, capturando restricciones de indivisibilidad y lógicas del mundo real.
  • Los solucionadores modernos (Gurobi, CPLEX, SCIP) explotan la ramificación y acotación avanzada, los planos de corte y el preprocesamiento (presolve) para manejar instancias grandes de manera eficiente.
  • La formulación transparente del modelo hace explícitas las suposiciones y es auditable por expertos del dominio.
  • Soporta análisis de sensibilidad y estudios paramétricos para comprender cómo las soluciones cambian con los datos de entrada.
  • Ampliamente soportado por lenguajes de modelado (AMPL, GAMS, Pyomo, JuMP) que permiten la creación rápida de prototipos.

Aplicaciones

  • Cadena de suministro y logística: enrutamiento de vehículos, localización de instalaciones y optimización de inventario con cantidades enteras de envío.
  • Planificación de la fuerza laboral: asignación de enfermeras, asignación de personal y planificación de turnos con variables de asignación binarias.
  • Presupuestación de capital: selección de una cartera de proyectos de inversión indivisibles sujetos a restricciones presupuestarias.
  • Diseño de redes y telecomunicaciones: expansión de capacidad y enrutamiento con decisiones binarias de activación de enlaces.
  • Sistemas de energía: compromiso de unidades (unit commitment) en redes eléctricas decidiendo qué generadores encender o apagar cada hora.
  • Fabricación: determinación de lotes de producción, planificación de máquinas y problemas de corte con tamaños de lote enteros.

Cómo funciona

Cómo funciona

1

Definir el modelo de optimización: una función objetivo (combinación lineal de variables de decisión a minimizar o maximizar), restricciones lineales de desigualdad y igualdad, y requisitos de integralidad. Las variables continuas manejan cantidades que pueden ser fraccionarias; las variables binarias (0/1) o enteras generales manejan decisiones discretas.

Fórmula
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

Resolver la relajación lineal (LP) omitiendo temporalmente las restricciones de integralidad. Esto proporciona una cota inferior (para minimización) del objetivo óptimo de la MIP y una solución candidata que puede ser fraccionaria.

Fórmula
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

Seleccionar una variable entera fraccionaria de la solución de la relajación LP. Crear dos subproblemas hijos añadiendo una restricción de suelo (floor) en uno y una restricción de techo (ceiling) en el otro, particionando el espacio factible sin perder ningún punto factible entero.

Fórmula
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

Resolver la relajación LP de cada subproblema. Si la cota es peor que la mejor solución entera encontrada hasta el momento (el actual), podar esa rama. Si la solución LP resulta ser factible entera, actualizar el actual si mejora el objetivo.

Fórmula
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

Opcionalmente, añadir planos de corte — desigualdades válidas que cortan la solución LP fraccionaria sin eliminar ningún punto factible entero. Los cortes de Gomory son el enfoque clásico; los cortes específicos del problema (p. ej., cortes de clique, cortes de flujo) pueden reducir drásticamente el tamaño del árbol.

Fórmula
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

Detenerse cuando el árbol de ramificación y acotación se haya explorado por completo o cuando la brecha entre la mejor solución entera y la cota inferior global caiga dentro de una tolerancia especificada por el usuario (p. ej., 0.01%). Devolver la solución actual con su certificado de optimalidad.

Fórmula
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

Errores comunes

  • Elegir una tolerancia de brecha de optimalidad demasiado ajustada puede hacer que el solucionador se ejecute indefinidamente; siempre establezca una brecha práctica (p. ej., 1%) para instancias grandes.
  • La simetría en el modelo (p. ej., instalaciones intercambiables) crea ramas redundantes y aumenta el árbol de búsqueda; utilice restricciones de ruptura de simetría.
  • Las relajaciones LP débiles (gran brecha de integralidad) conducen a árboles de ramificación y acotación muy grandes; invierta tiempo en añadir desigualdades válidas o refinar la formulación.
  • Tratar todas las variables como enteras cuando solo algunas lo necesitan es innecesariamente costoso; utilice variables binarias solo donde las restricciones lógicas lo exijan.
  • Ignorar el arranque en caliente (warm-starting) con una buena solución factible inicial desperdicia tiempo del solucionador en encontrar el primer actual.

Preguntas frecuentes

¿Cómo se diferencia la MIP de la programación lineal (LP)?

La LP requiere que todas las variables de decisión sean continuas (de valor real), lo que puede producir soluciones fraccionarias que son físicamente inviables (p. ej., 2.7 camiones). La MIP añade restricciones de integralidad a algunas o todas las variables, imponiendo soluciones de números enteros o binarias a costa de una mayor complejidad computacional.

¿Cuándo debo usar una heurística en lugar de MIP?

Cuando el problema tiene millones de variables, una estructura altamente no lineal, o requiere una solución casi en tiempo real, la MIP exacta puede ser demasiado lenta. Las metaheurísticas (algoritmos genéticos, recocido simulado) pueden producir buenas soluciones rápidamente, pero sin garantías de optimalidad. Se prefiere la MIP cuando la certificación de la calidad de la solución es importante.

¿Qué es la brecha de optimalidad y cuán pequeña debe ser?

La brecha es (objetivo actual - cota LP) / cota LP, expresada como porcentaje. Certifica cuán lejos puede estar la mejor solución entera conocida del óptimo verdadero. Para la mayoría de las aplicaciones prácticas, una brecha del 0.1-1% es suficiente; brechas más ajustadas requieren exponencialmente más tiempo de resolución.

¿Puede la MIP manejar objetivos o restricciones no lineales?

La MIP estándar asume linealidad. Las relaciones no lineales deben linealizarse (p. ej., aproximación por tramos lineales, expansión binaria de productos) o manejarse con solucionadores de programación no lineal de enteros mixtos (MINLP), que son significativamente más difíciles de resolver.

¿Qué solucionadores se recomiendan para MIP?

Comerciales: Gurobi y CPLEX son los puntos de referencia de la industria. Código abierto: SCIP, CBC (a través de COIN-OR) y HiGHS son competitivos para problemas de tamaño moderado. Todos soportan interfaces de modelado estándar como AMPL, Pyomo y JuMP.

Métodos relacionados

Fuentes

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    ISBN: 9780471359432
    Copiado.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Copiado.