Programación Entera Determinista — Optimización Exacta con Variables de Decisión Enteras
- Propuesto por
- Ralph E. Gomory
- Año
- 1958
- Tipo
- Exact combinatorial 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
¿Qué hace?
La Programación Entera Determinista (DIP) es un enfoque de optimización matemática que encuentra la mejor solución a problemas donde algunas o todas las variables de decisión deben tomar valores enteros, dados datos de objetivo y restricciones completamente conocidos (deterministas).
Es la forma clásica y no estocástica de programación entera, fundamental para la investigación de operaciones y la optimización combinatoria desde finales de la década de 1950.
La intuición detrás del método
Muchas decisiones del mundo real son inherentemente discretas: se abre una instalación o no; se asigna un trabajador a un turno o no. Los métodos de optimización continua no pueden imponer estos requisitos de números enteros. La Programación Entera Determinista maneja esto restringiendo las variables a enteros, mientras que todos los parámetros del problema —costos, capacidades, demandas— se conocen con certeza. El resultado es una solución exacta y demostrablemente óptima bajo ese supuesto de certeza, lo que la convierte en la formulación de referencia contra la cual se comparan las variantes estocásticas y robustas.
Historia
La programación entera surgió de la programación lineal a finales de la década de 1950. El algoritmo de planos de corte de Ralph Gomory de 1958 fue el primer método exacto sistemático. Junto con la ramificación y acotación (Land y Doig, 1960), estos enfoques definieron el campo. El adjetivo 'determinista' distingue la formulación clásica de la programación entera estocástica (Birge y Louveaux, 1997) y se convirtió en terminología estándar a medida que proliferaron las variantes conscientes de la incertidumbre.
Cuándo usarlo
Utilice la Programación Entera Determinista cuando: (1) las variables de decisión son inherentemente discretas (asignación, programación, localización de instalaciones, empaquetamiento de contenedores, diseño de redes); (2) todos los parámetros del problema se conocen con certeza o pueden estimarse de manera confiable como valores puntuales; (3) se requiere una solución óptima exacta en lugar de una aproximación heurística. NO la utilice cuando: los parámetros son inciertos o dependen del escenario (use programación entera estocástica o robusta en su lugar); la escala del problema es tan grande que la ramificación y acotación es computacionalmente intratable y las heurísticas son aceptables; las variables son verdaderamente continuas (use LP); o múltiples objetivos en conflicto deben equilibrarse simultáneamente (use programación entera multiobjetivo).
Limitaciones y consideraciones
- Asume que todos los parámetros del problema se conocen exactamente; la incertidumbre del mundo real se ignora por diseño.
- NP-difícil en general; el tiempo de resolución en el peor de los casos crece exponencialmente con el tamaño del problema.
- Los problemas combinatorios grandes pueden requerir horas o días de cálculo incluso con solucionadores modernos.
- La calidad de la formulación del modelo (rigidez de las restricciones, ruptura de simetría) afecta en gran medida el tiempo de resolución.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Garantiza una solución demostrablemente óptima dentro de los supuestos del modelo determinista.
- Maneja naturalmente estructuras de decisión discretas y combinatorias que los métodos continuos no pueden.
- Respaldado por solucionadores comerciales y de código abierto maduros y altamente eficientes (CPLEX, Gurobi, SCIP).
- Proporciona un certificado de brecha de optimalidad, lo que permite una terminación temprana fundamentada para instancias grandes.
- Sirve como la formulación de referencia estándar de oro para comparar variantes heurísticas y estocásticas.
Aplicaciones
- Planificación y programación de la producción con recursos discretos de máquinas o mano de obra
- Localización de instalaciones: decidir qué almacenes o plantas abrir
- Enrutamiento de vehículos y programación de tripulaciones en transporte y logística
- Presupuesto de capital: selección de una cartera de proyectos de inversión indivisibles
- Diseño de redes de telecomunicaciones con costos fijos de establecimiento de enlaces
- Programación de personal sanitario y de quirófanos
Cómo funciona
Cómo funciona
Defina el modelo de optimización: una función objetivo a minimizar (o maximizar) como una combinación lineal de variables de decisión enteras, sujeta a un conjunto de restricciones lineales de desigualdad o igualdad. Todos los coeficientes (c, A, b) son fijos y conocidos; esto es lo que hace que la formulación sea determinista. Las variables binarias (0/1) son un caso especial para decisiones de sí/no.
Fórmula
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nResuelva la relajación LP, que permite temporalmente que las variables tomen valores continuos. Esto proporciona una cota inferior para el objetivo entero óptimo. Si la solución de la relajación LP ya tiene valores enteros, es óptima para la IP; de lo contrario, comienza la ramificación.
Fórmula
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0Elija una variable fraccionaria de la solución de la relajación LP y divida la región factible añadiendo una restricción de piso (x_j <= floor value) en una rama y una restricción de techo (x_j >= ceil value) en la otra, generando dos subproblemas para ser resueltos recursivamente.
Fórmula
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilResuelva la relajación LP de cada subproblema para obtener una cota. Si la cota de un nodo es peor que la mejor solución entera conocida (incumbente), púrguelo. Si el subproblema produce una solución factible entera mejor que la incumbente, actualice la incumbente. El proceso forma un árbol de búsqueda de ramificación y acotación.
Fórmula
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}Los métodos de planos de corte —notablemente los cortes de Gomory— derivan desigualdades lineales adicionales del tableau LP que son satisfechas por todas las soluciones enteras pero violadas por la solución LP fraccionaria actual. La adición de estos cortes ajusta la relajación LP y reduce la ramificación. Los solucionadores modernos combinan la ramificación y acotación con cortes en un marco de ramificación y corte.
Fórmula
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}El algoritmo termina cuando todos los nodos abiertos son purgados o producen soluciones enteras. La incumbente al finalizar es la solución entera demostrablemente óptima. Los solucionadores también informan una brecha entre la mejor cota y la incumbente, que puede usarse como criterio de parada para problemas grandes.
Fórmula
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*Errores comunes
- Tratar los parámetros inciertos como estimaciones puntuales deterministas puede producir soluciones que funcionan mal en la práctica; valide esta suposición antes de aplicar DIP.
- Las relajaciones LP débiles (grandes brechas de integralidad) conducen a árboles de ramificación y acotación enormes; invierta en desigualdades válidas y reformulación antes de escalar.
- La explosión de variables binarias de las formulaciones big-M puede desestabilizar numéricamente la relajación LP; prefiera reformulaciones de restricciones más ajustadas.
- Confundir la factibilidad con la optimalidad al usar una tolerancia de brecha no nula; siempre informe la brecha junto con el valor objetivo.
- Ignorar la simetría en los modelos (por ejemplo, máquinas o trabajadores idénticos) provoca una ramificación redundante; añada restricciones de ruptura de simetría.
Preguntas frecuentes
¿Qué distingue la programación entera determinista de la programación entera estocástica?
En la IP determinista, todos los parámetros del objetivo y las restricciones son fijos y conocidos. La IP estocástica modela explícitamente los parámetros inciertos mediante distribuciones de probabilidad o escenarios, produciendo soluciones que son robustas u óptimas en expectativa a través de esos escenarios. La IP determinista es más simple y rápida de resolver, pero ignora la incertidumbre.
¿Es la programación binaria un caso especial de programación entera?
Sí. La programación binaria (0-1) restringe cada variable de decisión a {0, 1}. Es el caso especial más común, utilizado para decisiones de sí/no, como si abrir una instalación, seleccionar un proyecto o asignar un trabajador. La programación entera general permite cualquier valor entero no negativo.
¿Cuándo debo cambiar de IP determinista a un método heurístico?
Cuando el árbol de ramificación y acotación es demasiado grande para explorar dentro de un límite de tiempo aceptable y la brecha de optimalidad de una buena heurística (algoritmo genético, recocido simulado, búsqueda de vecindad grande) es tolerable para la aplicación. Informe y justifique la brecha al desviarse de la optimización exacta.
¿Puede la IP determinista manejar objetivos o restricciones no lineales?
La IP determinista clásica asume linealidad (programación lineal entera). La programación entera no lineal existe, pero es sustancialmente más difícil; muchas formas no lineales pueden linealizarse mediante variables binarias auxiliares y reformulaciones big-M. La programación entera cuadrática (QIP) es directamente compatible con algunos solucionadores modernos.
¿Qué solucionador debo usar para la IP determinista en la práctica?
Comerciales: Gurobi o IBM CPLEX para el mejor rendimiento. Académicos/código abierto: SCIP, CBC (a través de COIN-OR) o HiGHS. Todos implementan ramificación y corte con preprocesamiento automático. Para usuarios de Python, PuLP, Pyomo o scipy.optimize.milp proporcionan interfaces de modelado convenientes.
Métodos relacionados
Fuentes
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
Abrir referencia DOICopiado.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Copiado.