Un problema de programación entera es un programa de optimización o viabilidad matemática en el que algunas o todas las variables están restringidas a ser números enteros . En muchos entornos, el término se refiere a la programación lineal entera (ILP), en la que la función objetivo y las restricciones (distintas de las restricciones enteras) son lineales .
La programación entera es NP-completa . En particular, el caso especial de programación lineal entera 0-1, en el que las incógnitas son binarias y sólo se deben satisfacer las restricciones, es uno de los 21 problemas NP-completos de Karp . [1]
Si algunas variables de decisión no son discretas, el problema se conoce como problema de programación entera mixta . [2]
En programación lineal entera, la forma canónica es distinta de la forma estándar . Un programa lineal entero en forma canónica se expresa así (tenga en cuenta que es el vector el que debe decidirse): [3]
y un ILP en forma estándar se expresa como
donde son vectores y es una matriz. Al igual que con los programas lineales, los ILP que no están en forma estándar se pueden convertir a la forma estándar eliminando desigualdades, introduciendo variables holgadas ( ) y reemplazando variables que no están restringidas por signos con la diferencia de dos variables restringidas por signos.
El gráfico de la derecha muestra el siguiente problema.
Los puntos enteros factibles se muestran en rojo y las líneas discontinuas rojas indican su casco convexo, que es el poliedro convexo más pequeño que contiene todos estos puntos. Las líneas azules junto con los ejes de coordenadas definen el poliedro de la relajación LP, que viene dado por las desigualdades sin la restricción de integralidad. El objetivo de la optimización es mover la línea discontinua negra lo más hacia arriba sin dejar de tocar el poliedro. Las soluciones óptimas del problema entero son los puntos y que ambos tienen un valor objetivo de 2. El único óptimo de la relajación es con valor objetivo de 2,8. Si la solución de la relajación se redondea a los números enteros más cercanos, no es factible para el ILP.
La siguiente es una reducción de la cobertura mínima de vértices a la programación entera que servirá como prueba de la dureza NP.
Sea un gráfico no dirigido. Defina un programa lineal de la siguiente manera:
Dado que las restricciones se limitan a 0 o 1, cualquier solución viable para el programa entero es un subconjunto de vértices. La primera restricción implica que al menos un punto final de cada arista está incluido en este subconjunto. Por lo tanto, la solución describe una cobertura de vértice. Además, dada cierta cobertura de vértice C, se puede establecer en 1 para cualquiera y en 0 para cualquiera, lo que nos da una solución factible para el programa entero. Así podemos concluir que si minimizamos la suma de también hemos encontrado la cobertura mínima de vértices. [4]
La programación lineal de enteros mixtos ( MILP ) implica problemas en los que solo algunas de las variables están restringidas a ser enteras, mientras que a otras variables se les permite no ser enteras.
La programación lineal cero-uno (o programación entera binaria ) implica problemas en los que las variables están restringidas a ser 0 o 1. Cualquier variable entera acotada se puede expresar como una combinación de variables binarias . [5] Por ejemplo, dada una variable entera, la variable se puede expresar usando variables binarias:
Hay dos razones principales para utilizar variables enteras al modelar problemas como un programa lineal:
Estas consideraciones ocurren con frecuencia en la práctica y, por lo tanto, la programación lineal entera se puede utilizar en muchas áreas de aplicaciones, algunas de las cuales se describen brevemente a continuación.
La programación de enteros mixtos tiene muchas aplicaciones en producciones industriales, incluido el modelado de talleres. Un ejemplo importante ocurre en la planificación de la producción agrícola e implica determinar el rendimiento de la producción para varios cultivos que pueden compartir 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 se puede expresar en términos de un programa lineal, pero las variables deben limitarse a ser enteras.
Estos problemas involucran la programación de servicios y vehículos en las redes de transporte. Un problema puede ser, por ejemplo, asignar autobuses o metros a rutas individuales para que se pueda cumplir un horario, y también equiparlos con conductores. Aquí las variables de decisión binarias indican si un autobús o metro está asignado a una ruta y si un conductor está asignado a un tren o metro en particular. La técnica de programación cero-uno se ha aplicado con éxito para resolver un problema de selección de proyectos en el que los proyectos son mutuamente excluyentes y/o tecnológicamente interdependientes. Se utiliza en un caso especial de programación entera, en el que todas las variables de decisión son números enteros. La variable sólo puede asumir los valores cero o uno.
Los problemas de partición territorial o distritación consisten en dividir una región geográfica en distritos para planificar algunas operaciones considerando diferentes criterios o limitaciones. Algunos requisitos para este problema son: contigüidad, compacidad, equilibrio o equidad, respeto de las fronteras naturales y homogeneidad socioeconómica. Algunas aplicaciones para este tipo de problema incluyen: distritación política, distritación escolar, distritación de servicios de salud y distritación de gestión de residuos.
El objetivo de estos problemas es diseñar una red de líneas a instalar de modo que se cumpla un conjunto predefinido de requisitos de comunicación y el coste total de la red sea mínimo. [6] Esto requiere optimizar tanto la topología de la red como establecer las capacidades de las distintas líneas. En muchos casos, las capacidades están restringidas a ser cantidades enteras. Generalmente existen, dependiendo de la tecnología utilizada, restricciones adicionales que pueden modelarse como desigualdades lineales con variables enteras o binarias.
La tarea de planificación de frecuencias en las redes móviles GSM implica distribuir las frecuencias disponibles entre las antenas para que se pueda atender a los usuarios y se minimice la interferencia entre las antenas. [7] Este problema se puede formular como un programa lineal entero en el que variables binarias indican si una frecuencia está asignada a una antena.
La forma ingenua de resolver un ILP es simplemente eliminar la restricción de que x es un número entero, resolver el LP correspondiente (llamado relajación LP del ILP) y luego redondear las entradas de la solución a la relajación LP. Pero esta solución no sólo puede no ser óptima, sino que incluso puede no ser factible; es decir, puede violar alguna restricción.
Si bien en general no se garantiza que la solución a la relajación LP sea integral, si el ILP tiene la forma tal que donde y tiene todas las entradas enteras y es totalmente unimodular , entonces toda solución básica factible es integral. En consecuencia, se garantiza que la solución devuelta por el algoritmo simplex será integral. Para demostrar que toda solución básica factible es integral, sea una solución básica factible arbitraria. Como es factible, lo sabemos . Sean los elementos correspondientes a las columnas base de la solución básica . Por definición de base, existe alguna submatriz cuadrada de con columnas linealmente independientes tal que .
Dado que las columnas de son linealmente independientes y son cuadradas, no son singulares y, por lo tanto, por supuesto, son unimodulares , por lo que . Además, como no es singular, es invertible y por tanto . Por definición, . Aquí denota el conjugado de y es integral porque es integral. Por tanto, si la matriz de un ILP es totalmente unimodular, en lugar de utilizar un algoritmo ILP, se puede utilizar el método simplex para resolver la relajación LP y la solución será entera.
Cuando la matriz no es totalmente unimodular, existen una variedad de algoritmos que se pueden utilizar para resolver programas lineales enteros con exactitud. Una clase de algoritmos son los métodos de plano de corte , que funcionan resolviendo la relajación LP y luego agregando restricciones lineales que hacen que la solución sea entera sin excluir ningún punto entero factible.
Otra clase de algoritmos son las variantes del método de rama y enlace . Por ejemplo, el método de rama y corte que combina los métodos de rama, unión y plano de corte. Los algoritmos de bifurcación y enlace tienen una serie de ventajas sobre los algoritmos que sólo utilizan planos de corte. Una ventaja es que los algoritmos se pueden terminar anticipadamente y siempre que se haya encontrado al menos una solución integral, se puede devolver una solución factible, aunque no necesariamente óptima. Además, las soluciones de las relajaciones de LP se pueden utilizar para proporcionar una estimación del peor de los casos de qué tan lejos de la optimización está la solución devuelta. Finalmente, los métodos de ramificación y vinculación se pueden utilizar para devolver múltiples soluciones óptimas.
Supongamos que es una matriz entera de m por n y un vector entero de m por 1. Nos centramos en el problema de viabilidad, que consiste en decidir si existe un vector n por 1 que satisfaga .
Sea V el valor absoluto máximo de los coeficientes en y . Si n (el número de variables) es una constante fija, entonces el problema de viabilidad se puede resolver en un polinomio de tiempo en my log V. Esto es trivial para el caso n =1. El caso n = 2 fue resuelto en 1981 por Herbert Bufanda . [13] El caso general fue resuelto en 1983 por Hendrik Lenstra , combinando ideas de László Lovász y Peter van Emde Boas . [14] El teorema de Doignon afirma que un programa entero es factible siempre que cada subconjunto de restricciones sea factible; Se puede utilizar un método que combina este resultado con algoritmos para problemas de tipo LP para resolver programas enteros en un tiempo lineal y manejable con parámetros fijos (FPT) en , pero posiblemente doblemente exponencial en , sin dependencia de . [15]
En el caso especial de 0-1 ILP, el algoritmo de Lenstra es equivalente a una enumeración completa: el número de todas las soluciones posibles es fijo (2 n ), y se puede verificar la viabilidad de cada solución en el tiempo poli( m , log V ) . En el caso general, donde cada variable puede ser un número entero arbitrario, la enumeración completa es imposible. Aquí, el algoritmo de Lenstra utiliza ideas de Geometría de números . Transforma el problema original en uno equivalente con la siguiente propiedad: o la existencia de una solución es obvia o el valor de (la n -ésima variable) pertenece a un intervalo cuya longitud está acotada por una función de n . En el último caso, el problema se reduce a un número acotado de problemas de dimensiones inferiores. La complejidad del tiempo de ejecución del algoritmo se ha mejorado en varios pasos:
Estos algoritmos también sirven para programas lineales enteros mixtos (MILP): programas en los que algunas variables son enteras y algunas variables son reales. [23] El algoritmo original de Lenstra [14] : la sección 5 tiene tiempo de ejecución , donde n es el número de variables enteras, d es el número de variables continuas y L es el tamaño de codificación binaria del problema. Utilizando técnicas de algoritmos posteriores, el factor se puede mejorar a o a . [23]
Dado que la programación lineal entera es NP-difícil , muchos casos de problemas son intratables y, por lo tanto, se deben utilizar métodos heurísticos. Por ejemplo, la búsqueda tabú se puede utilizar para buscar soluciones a los ILP. [24] Para utilizar la búsqueda tabú para resolver ILP, los movimientos se pueden definir como incrementar o disminuir una variable restringida por enteros de una solución factible mientras se mantienen constantes todas las demás variables restringidas por enteros. Luego se resuelven las variables no restringidas. La memoria a corto plazo puede consistir en soluciones probadas previamente, mientras que la memoria a mediano plazo puede consistir en valores de variables enteras restringidas que han resultado en valores objetivos altos (asumiendo que el ILP es un problema de maximización). Finalmente, la memoria a largo plazo puede guiar la búsqueda hacia valores enteros que no se han probado previamente.
Otros métodos heurísticos que se pueden aplicar a los ILP incluyen
También hay una variedad de otras heurísticas específicas del problema, como la heurística k-opt para el problema del viajante. Una desventaja de los métodos heurísticos es que si no logran encontrar una solución, no se puede determinar si es porque no hay una solución factible o si el algoritmo simplemente no pudo encontrarla. Además, normalmente es imposible cuantificar qué tan cerca de la solución óptima devuelta por estos métodos está.
A menudo ocurre que la matriz que define el programa entero es escasa . En particular, esto ocurre cuando la matriz tiene una estructura de bloques , como es el caso en muchas aplicaciones. La escasez de la matriz se puede medir de la siguiente manera. La gráfica de tiene vértices correspondientes a columnas de y dos columnas forman un borde si tiene una fila donde ambas columnas tienen entradas distintas de cero. De manera equivalente, los vértices corresponden a variables y dos variables forman una arista si comparten una desigualdad. La medida de escasez de es el mínimo de la profundidad del árbol del gráfico de y la profundidad del árbol del gráfico de la transpuesta de . Sea la medida numérica de definida como el valor absoluto máximo de cualquier entrada de . Sea el número de variables del programa entero. Luego se demostró en 2018 [25] que la programación entera se puede resolver en un tiempo manejable fuertemente polinómico y de parámetros fijos parametrizado por y . Es decir, para alguna función computable y alguna constante , la programación entera se puede resolver en el tiempo . En particular, el tiempo es independiente del lado derecho y de la función objetivo . Además, a diferencia del resultado clásico de Lenstra, donde el número de variables es un parámetro, aquí el número de variables es una parte variable de la entrada.