Programación entera

Programación entera (PE; del inglés integer programming, IP) es una rama de la optimización matemática en la que se investigan problemas donde algunas o todas las variables deben tomar solo valores enteros.

El caso particular más estudiado es la programación lineal entera (PLE; del inglés integer linear programming, ILP), donde la función objetivo y las restricciones son lineales. A diferencia de la programación lineal, donde las variables pueden tomar cualquier valor real, el requisito de que sean enteras hace que los problemas de PE sean significativamente más complejos de resolver.

La programación entera tiene una amplia aplicación en economía, logística, planificación de la producción y otras áreas donde las variables son discretas por naturaleza (por ejemplo, el número de unidades de un producto fabricadas o el número de empleados).

Definición y terminología

Un problema general de programación lineal entera puede formularse de la siguiente manera:

Encontrar un vector $x$ que:

maximice (o minimice) $c^{T}x$

sujeto a:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (todos los componentes del vector $x$ son números enteros)

donde $x$ es el vector de variables, $c$ y $b$ son vectores, y $A$ es la matriz de coeficientes.

Dependiendo de los requisitos sobre las variables, se distinguen los siguientes tipos de problemas:

• Programación entera pura: todas las variables deben ser enteras.
• Programación entera mixta (del inglés mixed-integer programming, MIP): solo una parte de las variables deben ser enteras.
• Programación binaria (0-1): las variables solo pueden tomar los valores 0 o 1, lo que permite modelar decisiones lógicas del tipo «sí/no».

Propiedades clave y complejidad

Complejidad computacional

El problema de programación lineal entera es, en el caso general, NP-difícil. Esto significa que no se conoce ningún algoritmo capaz de encontrar una solución óptima exacta para un problema arbitrario de PE en tiempo polinomial. La complejidad se debe a la naturaleza combinatoria del problema, ya que el número de posibles soluciones enteras puede crecer exponencialmente con el aumento del número de variables.

Relación con la programación lineal (relajación PL)

Para cualquier problema de PE, se puede formular su relajación lineal: un problema de programación lineal (PL) en el que se elimina el requisito de que las variables sean enteras. La solución de la relajación PL tiene dos propiedades importantes:

1. Se puede encontrar mucho más rápido (en tiempo polinomial).
2. El valor óptimo de la función objetivo de la relajación PL proporciona una cota (una cota superior para un problema de maximización y una cota inferior para uno de minimización) para el valor óptimo del problema entero original.

Sin embargo, el simple redondeo de la solución fraccionaria de la relajación PL a los enteros más cercanos generalmente no conduce a una solución óptima, ni siquiera factible, para el problema entero.

Propiedad de unimodularidad total

Existe una clase importante de problemas de PLE que se resuelven con la misma facilidad que sus relajaciones PL. Estos son problemas en los que la matriz de restricciones $A$ es totalmente unimodular (es decir, el determinante de cualquiera de sus submatrices cuadradas es 0, +1 o -1). Si la matriz $A$ es totalmente unimodular y el vector $b$ es entero, entonces todos los vértices del poliedro de soluciones factibles de la relajación PL serán automáticamente enteros. Por lo tanto, la solución encontrada por el método símplex será entera. Ejemplos de tales problemas son el problema del transporte y el problema de la asignación.

Métodos de solución

Para resolver problemas generales de PE que no poseen la propiedad de unimodularidad total, se han desarrollado métodos exactos basados en la idea de enumeración implícita.

• Método de ramificación y acotación (del inglés Branch and Bound) — es el principal método exacto, basado en la división sistemática del conjunto de soluciones factibles en subconjuntos (ramificación) y en la poda de aquellos subconjuntos que se garantiza que no contienen la solución óptima. Para evaluar el potencial de los subconjuntos, se utiliza la relajación PL.

• Método de los planos de corte (método de Gomory; del inglés Cutting Plane Method) — un enfoque iterativo que añade secuencialmente nuevas restricciones lineales (o «cortes») al problema. Estos cortes «recortan» las soluciones fraccionarias de la relajación PL sin eliminar ninguna solución entera factible, aproximando gradualmente la región factible de la relajación PL a la envolvente convexa de las soluciones enteras.

Los solvers modernos suelen utilizar algoritmos híbridos, como el método de ramificación y corte (del inglés Branch and Cut), que combina las ventajas de ambos enfoques.

Ejemplos y áreas de aplicación

La programación entera permite modelar una multitud de problemas clásicos de optimización combinatoria.

• Problema de la mochila: un problema clásico de programación 0-1 en el que se debe seleccionar un conjunto de artículos con el máximo valor total sin exceder una restricción de peso total.
• Problema del viajante de comercio: el problema de encontrar la ruta más corta que pasa por un conjunto determinado de ciudades. Puede formularse como un problema de programación entera, donde las variables representan la inclusión de aristas de un grafo en la ruta final.

Gracias a su flexibilidad, la PE es una de las herramientas más demandadas en la investigación de operaciones y se aplica en áreas como:

• Logística y gestión de la cadena de suministro: optimización de rutas de transporte, ubicación de almacenes, gestión de inventarios.
• Planificación de la producción: elaboración de cronogramas de producción, asignación de recursos, programación de maquinaria.
• Finanzas y economía: formación de carteras de inversión, presupuestación de capital.
• Telecomunicaciones y energía: diseño de redes de comunicación, planificación de la operación de unidades de generación de energía.

Véase también

• Programación lineal
• Método de ramificación y acotación