Programación en enteros

La PLEM tiene muchas aplicaciones en la producción industrial, incluyendo modelado trabajo-tienda. El plan de producción en la agricultura implica determinar el rendimiento de la producción para varios cultivos que pueden compartir recursos (e.g., tierra, labor, fondo para fertilizador de semillas, etc.). Un objetivo posible es maximizar la producción total, sin exceder los recursos disponibles. En algunos casos, esto puede ser expresado en términos de un programa lineal, pero las variables deben ser restringidas a los enteros.

Estos problemas involucran planificación de vehículos y servicios en redes de transportación. Por ejemplo, un problema puede implicar asignar autobuses o metros a rutas individuales para que un horario sea cumplido, y también equiparlos con chóferes. Aquí las variables de decisión binarias indican dónde un autobús o metro es asignado a una ruta y dónde un chófer es asignado a un tren o metro en particular.

El objetivo de estos problemas es diseñar una red de líneas para instalar por lo que un conjunto predefinido de requerimientos de comunicación es conocido y el costo total de la red es minimal.[3] Esto requiere optimizar la topología de la red junto con la configuración de capacidades de las diferentes líneas. En muchos casos, las capacidades están restringidas a cantidades enteras. Usualmente existen, dependiendo de la tecnología usada, restricciones adicionales que pueden ser modeladas como desigualdades lineales con variables enteras o binarias.

La tarea de planificar frecuentemente en redes de teléfonos GSM implica distribuir frecuencias disponibles a través de las antenas para que los usuarios puedan ser servidos y la interferencia sea minimizada entre las antenas.[4] Este problema puede ser formulado como un programa lineal en enteros en el cual las variables binarias indican donde una frecuencia es asignada a una antena.

Mientras que en general la solución del problema relajado no se garantizará que sea óptima, si el PLE tiene la forma ${\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }$ tal que ${\displaystyle A\mathbf {x} =\mathbf {b} }$ donde ${\displaystyle A,\mathbf {b} ,}$ y ${\displaystyle \mathbf {c} }$ son todos enteros y ${\displaystyle A}$ es totalmente unimodular, entonces toda solución factible básica es entera. Consecuentemente, la solución retornada por el algoritmo símplex se garantiza que es entera. Para demostrar que cada solución factible básica es entera, sea ${\displaystyle \mathbf {x} }$ una solución factible básica cualquiera. Puesto que ${\displaystyle \mathbf {x} }$ es factible, sabemos que ${\displaystyle A\mathbf {x} =\mathbf {b} }$. Sea ${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$ los elementos correspondientes a las columnas básicas para la solución básica ${\displaystyle \mathbf {x} }$. Por definición de una base, existe una submatriz cuadrada ${\displaystyle B}$ de ${\displaystyle A}$ con columnas linealmente independientes tales que ${\displaystyle B\mathbf {x} _{0}=\mathbf {b} }$.

Puesto que las columnas de ${\displaystyle B}$ son linealmente independientes y ${\displaystyle B}$ es cuadrada, ${\displaystyle B}$ es no singular, y por consiguiente, ${\displaystyle B}$ es unimodular y así ${\displaystyle \det(B)=\pm 1}$. También, debido a que ${\displaystyle B}$ es no singular, es inversible y por consiguiente ${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$. Por definición, ${\displaystyle B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}}$. Note que ${\displaystyle B^{adj}}$ denota la conjugada de ${\displaystyle B}$ y es entera porque ${\displaystyle B}$ es entera. Por consiguiente,

${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ es entera.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ es entero.}}\\&\Rightarrow {\text{Cada solución factible básica es entera.}}\end{aligned}}}$

De esta forma, si la matriz ${\displaystyle A}$ de un PLE es totalmente unimodular, en vez de usar un algoritmo de PLE, el algoritmo símplex puede ser usado para resolver la relajación de PL y la solución será entera

Cuando la matriz ${\displaystyle A}$ no es totalmente unimodular, existen una variedad de algoritmos que pueden ser usados para resolver los programas lineales en enteros exactamente. Una clase de estos algoritmos son los métodos de planos cortantes los cuales funcionan resolviendo la relajación de PL y entonces añadir restricciones lineales que lleve la solución a ser entera sin excluir algún punto entero factible.

Otra clase de algoritmos son las variantes de los métodos de ramificación y acotación Por ejemplo, el método ramificación y corte que combina los métodos de ramificación y acotación y planos cortantes. Los algoritmos de ramificación y acotación poseen un gran número de ventajas sobre algoritmos que solo usan planos cortantes. Una ventaja es que los algoritmos pueden ser tempranamente terminados y siempre y cuando al menos una solución entera ha sido encontrada, una factible, aunque no necesariamente óptima, ésta puede ser retornada. Además, las soluciones de los PL relajados pueden ser usadas para proveer un estimado del caso peor de cuán lejos de la optimalidad está la solución retornada. Finalmente, los métodos de ramificación y acotación pueden ser usados para retornar múltiples soluciones óptimas.

Lenstra en 1983 demostró,[5] que cuando el número de variables es fijo, los problemas de programación en enteros pueden ser resueltos en un tiempo polinomial.

Puesto que la programación lineal en enteros es NP-completo, muchas instancias de problemas son intratables, por lo que métodos heurísticos deben ser usados en su lugar. Por ejemplo, búsqueda tabú puede ser usada para buscar soluciones de PLEs.[6] Para usar búsqueda tabú para resolver PLEs, los movimientos pueden ser definidos como incrementar o decrementar una variable entera de una solución factible, mientras que todas las demás variables enteras se mantienen constantes. Las variables irrestrictas pueden entonces ser resueltas. Memoria de término corto puede consistir de soluciones previamente intentadas mientras que memoria de término medio puede consistir de valores para las variables enteras que han resultado en valores altos de la función objetivo (asumiendo que el PLE es un problema de maximización). Finalmente, memoria de término largo puede guiar la búsqueda hacia los valores enteros que no han sido previamente intentados.

Otros métodos heurísticos que pueden ser usados para resolver PLEs incluye

• Hill climbing
• Simulated annealing
• Optimización de búsqueda reactiva
• Algoritmo de la colonia de hormigas
• Red neuronal Hopfield

Existen también una variedad de otras heurísticas de problemas específicos, tales como heurísitica k-opt para el TSP. Note que una desventaja de los métodos heurísticos es que si fallan en encontrar una solución, no puede ser determinado donde es porque no hay solución factible, o donde el algoritmo simplemente no pudo encontrar una solución. Además, es usualmente imposible cuantificar cuán cerca de la solución óptima está una solución retornada por estos métodos.