Programación entera

La programación lineal entera mixta tiene numerosas aplicaciones en la producción industrial, incluyendo la modelización de talleres de producción. Un ejemplo importante se da en la planificación de la producción agrícola , donde se determina el rendimiento de varios cultivos que comparten recursos (por ejemplo, tierra, mano de obra, capital, semillas, fertilizantes, etc.). Un posible objetivo es maximizar la producción total sin exceder los recursos disponibles. En algunos casos, esto puede expresarse mediante un programa lineal, pero las variables deben ser enteras.

Estos problemas involucran la programación de servicios y vehículos en redes de transporte. Por ejemplo, un problema puede consistir en asignar autobuses o metros a rutas específicas para cumplir con un horario, así como en dotarlos de conductores. En este caso, las variables de decisión binarias indican si un autobús o metro se asigna a una ruta y si un conductor se asigna a un tren o metro en particular. La técnica de programación binaria se ha aplicado con éxito para resolver un problema de selección de proyectos en el que estos son mutuamente excluyentes y/o tecnológicamente interdependientes.

Los problemas de división territorial o de distritos consisten en dividir una región geográfica en distritos para planificar operaciones, considerando diferentes criterios o restricciones. Algunos requisitos para este problema son: contigüidad, compacidad, equilibrio o equidad, respeto de los límites naturales y homogeneidad socioeconómica. Algunas aplicaciones de este tipo de problema incluyen: la división política, la división escolar, la división de servicios de salud y la división de la gestión de residuos.

El objetivo de estos problemas es diseñar una red de líneas para su instalación de manera que se cumplan un conjunto predefinido de requisitos de comunicación y el costo total de la red sea mínimo. ^{[ 9 ]} Esto requiere optimizar tanto la topología de la red como la capacidad de las distintas líneas. En muchos casos, las capacidades están restringidas a valores enteros. Generalmente, según la tecnología utilizada, existen restricciones adicionales que pueden modelarse como desigualdades lineales con variables enteras o binarias.

La tarea de planificación de frecuencias en redes móviles GSM implica distribuir las frecuencias disponibles entre las antenas para que los usuarios puedan recibir servicio y se minimice la interferencia entre ellas. ^{[ 10 ]} Este problema puede formularse como un programa lineal entero en el que variables binarias indican si una frecuencia se asigna a una antena.

• Coincidencia de flujos de efectivo
• Optimización del sistema energético ^{[ 11 ] [ 12 ]}
• Guía de UAV ^{[ 13 ] [ 14 ]}
• Diseño del mapa de transporte público ^{[ 15 ]}

Si bien en general no se garantiza que la solución a la relajación LP sea integral, si el ILP tiene la forma${\displaystyle \max \mathbf {c} ^{\mathrm {T} }\mathbf {x} }$de tal manera que${\displaystyle A\mathbf {x} =\mathbf {b} }$dónde${\displaystyle A}$y${\displaystyle \mathbf {b} }$tener todas las entradas enteras y${\displaystyle A}$Si es totalmente unimodular , entonces toda solución factible básica es entera. En consecuencia, se garantiza que la solución devuelta por el algoritmo simplex es entera. Para demostrar que toda solución factible básica es entera, sea${\displaystyle \mathbf {x} }$sea ​​una solución básica factible arbitraria. Dado que${\displaystyle \mathbf {x} }$es factible, sabemos que${\displaystyle A\mathbf {x} =\mathbf {b} }$. Dejar${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$sean los elementos correspondientes a las columnas base para la solución básica.${\displaystyle \mathbf {x} }$. Por definición de una base, existe alguna submatriz cuadrada${\displaystyle B}$de ${\displaystyle A}$con columnas linealmente independientes tales que${\displaystyle B\mathbf {x} _{0}=\mathbf {b} }$.

Dado que las columnas de${\displaystyle B}$son linealmente independientes y${\displaystyle B}$es cuadrado,${\displaystyle B}$es no singular y, por lo tanto, por suposición,${\displaystyle B}$es unimodular y por lo tanto${\displaystyle \det(B)=\pm 1}$. Además, dado que${\displaystyle B}$es no singular, es invertible y por lo tanto${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$. Por definición,${\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}$. Aquí${\displaystyle B^{\mathrm {adj} }}$denota el adjugado de${\displaystyle B}$y es integral porque${\displaystyle B}$es integral. Por lo tanto, $${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{\mathrm {adj} }{\text{ is integral.}}\\&\Rightarrow \mathbf {x} _{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}}$$ Por lo tanto, si la matriz${\displaystyle A}$Si un problema de programación lineal entera (PLI) es totalmente unimodular, en lugar de utilizar un algoritmo de PLI, se puede utilizar el método simplex para resolver la relajación de PL y la solución será entera.

Cuando la matriz${\displaystyle A}$Aunque no es totalmente unimodular, existen diversos algoritmos que permiten resolver programas lineales enteros de forma exacta. Una clase de algoritmos son los métodos de planos de corte , que funcionan resolviendo la relajación del programa lineal y añadiendo restricciones lineales que conducen a que la solución sea entera sin excluir ningún punto factible entero.

Otro tipo de algoritmos son las variantes del método de ramificación y acotación . Por ejemplo, el método de ramificación y corte , que combina ambos métodos. Los algoritmos de ramificación y acotación presentan varias ventajas sobre los que solo utilizan planos de corte. Una de ellas es que pueden finalizarse prematuramente y, siempre que se haya encontrado al menos una solución integral, se puede obtener una solución factible, aunque no necesariamente óptima. Además, las soluciones de las relajaciones de programación lineal pueden utilizarse para estimar el peor caso posible de la distancia a la solución óptima. Por último, los métodos de ramificación y acotación pueden generar múltiples soluciones óptimas.

Suponer${\displaystyle A}$es una matriz entera de m por n y${\displaystyle \mathbf {b} }$es un vector entero de m por 1. Nos centramos en el problema de viabilidad, que consiste en decidir si existe un vector de n por 1.${\displaystyle \mathbf {x} }$satisfactorio${\displaystyle A\mathbf {x} \leq \mathbf {b} }$.

Sea V el valor absoluto máximo de los coeficientes en${\displaystyle A}$ y${\displaystyle \mathbf {b} }$Si n (el número de variables) es una constante fija, entonces el problema de factibilidad se puede resolver en tiempo polinomial en m y log V. Esto es trivial para el caso n = 1. El caso n = 2 fue resuelto en 1981 por Herbert Scarf . ^{[ 16 ]} El caso general fue resuelto en 1983 por Hendrik Lenstra , combinando ideas de László Lovász y Peter van Emde Boas . ^{[ 17 ]} El teorema de Doignon afirma que un programa entero es factible siempre que cada subconjunto de${\displaystyle 2^{n}}$es factible la aplicación de restricciones; se puede utilizar un método que combine este resultado con algoritmos para problemas de tipo LP para resolver programas enteros en un tiempo lineal.${\displaystyle m}$y tratable con parámetros fijos (FPT) en${\displaystyle n}$, pero posiblemente doblemente exponencial en${\displaystyle n}$, sin dependencia de${\displaystyle V}$. ^{[ 18 ]}

En el caso especial de ILP 0-1, el algoritmo de Lenstra es equivalente a la enumeración completa: el número de todas las soluciones posibles es fijo (2 ⁿ ), y la comprobación de la viabilidad de cada solución se puede realizar en tiempo polinomial( m , log V ). En el caso general, donde cada variable puede ser un entero arbitrario, la enumeración completa es imposible. Aquí, el algoritmo de Lenstra utiliza ideas de la Geometría de los números . Transforma el problema original en uno equivalente con la siguiente propiedad: o bien la existencia de una solución${\displaystyle \mathbf {x} }$es obvio, o el valor de${\displaystyle x_{n}}$(la n -ésima variable) pertenece a un intervalo cuya longitud está acotada por una función de n . En este último caso, el problema se reduce a un número acotado de problemas de menor dimensión. La complejidad temporal del algoritmo se ha mejorado en varios pasos:

• El algoritmo original de Lenstra ^{[ 17 ]} tenía tiempo de ejecución${\displaystyle 2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}}$.
• Kannan ^{[ 19 ]} presentó un algoritmo mejorado con tiempo de ejecución${\displaystyle n^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$. ^{[ 20 ]}
• Frank y Tardos ^{[ 21 ]} presentaron un algoritmo mejorado con tiempo de ejecución ${\displaystyle n^{2.5n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$. ^{[ 22 ] [ 23 ] : Prop.8}
• Dadush ^{[ 24 ]} presentó un algoritmo mejorado con tiempo de ejecución${\displaystyle n^{n}\cdot 2^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$.
• Reis y Rothvoss ^{[ 25 ]} presentaron un algoritmo mejorado con tiempo de ejecución${\displaystyle (\log n)^{O(n)}\cdot (m\cdot \log V)^{O(1)}}$.

Estos algoritmos también se pueden utilizar para programas lineales de enteros mixtos (MILP), programas en los que algunas variables son enteras y otras son reales. ^{[ 26 ]} El algoritmo original de Lenstra ^{[ 17 ] : Sec.5} tiene tiempo de ejecución${\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}$donde n es el número de variables enteras, d es el número de variables continuas y L es el tamaño de la codificación binaria del problema. Utilizando técnicas de algoritmos posteriores, el factor${\displaystyle 2^{O(n^{3})}}$puede mejorarse a${\displaystyle 2^{O(n\log n)}}$o para${\displaystyle n^{n}}$. ^{[ 26 ]}

Dado que la programación lineal entera es NP-difícil , muchas instancias del problema son intratables y, por lo tanto, deben utilizarse métodos heurísticos. Por ejemplo, la búsqueda tabú puede utilizarse para buscar soluciones a problemas de programación lineal entera (PLI). ^{[ 27 ]} Para utilizar la búsqueda tabú en la resolución de PLI, los movimientos pueden definirse como incrementar o decrementar una variable entera restringida de una solución factible, manteniendo constantes todas las demás variables enteras restringidas. A continuación, se resuelven las variables no restringidas. La memoria a corto plazo puede consistir en soluciones previamente probadas, mientras que la memoria a medio plazo puede consistir en valores para las variables enteras restringidas que han dado como resultado valores objetivo altos (suponiendo que el PLI sea un problema de maximización). Finalmente, la memoria a largo plazo puede guiar la búsqueda hacia valores enteros que no se hayan probado previamente.

Otros métodos heurísticos que se pueden aplicar a los ILP incluyen:

• Subir colinas
• Recocido simulado
• Optimización de búsqueda reactiva
• optimización de colonias de hormigas
• Redes neuronales de Hopfield

También existen diversas heurísticas específicas para cada problema, como la heurística k-opt para el problema del viajante. Una desventaja de los métodos heurísticos es que, si no encuentran una solución, no se puede determinar si se debe a que no existe una solución factible o a que el algoritmo simplemente no pudo encontrarla. Además, suele ser imposible cuantificar cuán cerca de la solución óptima se encuentra la que arrojan estos métodos.