Un problema de programación de enteros es una optimización matemática o un programa de viabilidad en el que algunas o todas las variables están restringidas a números enteros . En muchos entornos, el término se refiere a la programación lineal de enteros (ILP), en la que la función objetivo y las restricciones (distintas de las restricciones de enteros) son lineales .
La programación de enteros es NP-completa . En particular, el caso especial de la programación lineal de enteros 0-1, en el que las incógnitas son binarias y solo deben satisfacerse las restricciones, es uno de los 21 problemas NP-completos de Karp .
Si algunas variables de decisión no son discretas, el problema se conoce como un problema de programación de enteros mixtos . [1]
Forma canónica y estándar para ILP
En la programación lineal de enteros, 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 elvector que tiene que ser decidido): [2]
y un ILP en forma estándar se expresa como
dónde son vectores y es una matriz, donde todas las entradas son números enteros. Al igual que con los programas lineales, ILPs no en forma estándar pueden ser convertidas a forma estándar mediante la eliminación de las desigualdades, la introducción de variables de holgura () y reemplazando las variables que no están restringidas por el signo con la diferencia de dos variables restringidas por el signo
Ejemplo
El gráfico de la derecha muestra el siguiente problema.
Los puntos enteros factibles se muestran en rojo, y las líneas de trazos rojos indican su casco convexo, que es el más pequeño convexo poliedro 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 dada por las desigualdades sin la restricción de integralidad. El objetivo de la optimización es mover la línea punteada negra hacia arriba sin dejar de tocar el poliedro. Las soluciones óptimas del problema de números enteros son los puntos y los cuales ambos tienen un valor objetivo de 2. El óptimo único 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.
Prueba de dureza NP
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.
Dejar ser un gráfico no dirigido. Defina un programa lineal de la siguiente manera:
Teniendo en cuenta que las restricciones limitan a 0 o 1, cualquier solución factible para el programa entero es un subconjunto de vértices. La primera restricción implica que al menos un punto final de cada borde se incluye en este subgrupo. Por lo tanto, la solución describe una cobertura de vértice. Además, dada alguna cobertura de vértice C, se puede establecer en 1 para cualquier y a 0 para cualquier dándonos así una solución factible para el programa de enteros. Por tanto, podemos concluir que si minimizamos la suma detambién hemos encontrado la cobertura mínima de vértices. [3]
Variantes
La programación lineal de enteros mixtos ( MILP ) implica problemas en los que solo algunas de las variables,, están restringidos a ser enteros, mientras que otras variables pueden ser no enteros.
La programación lineal cero-uno (o programación de enteros binarios ) implica problemas en los que las variables están restringidas a 0 o 1. Cualquier variable de entero acotado se puede expresar como una combinación de variables binarias. [4] Por ejemplo, dada una variable entera,, la variable se puede expresar usando variables binarias:
Aplicaciones
Hay dos razones principales para usar variables enteras al modelar problemas como un programa lineal:
- Las variables enteras representan cantidades que solo pueden ser enteras. Por ejemplo, no es posible construir 3.7 autos.
- Las variables enteras representan decisiones (por ejemplo, si incluir un borde en un gráfico ) y, por lo tanto, solo deben tomar el valor 0 o 1.
Estas consideraciones se producen con frecuencia en la práctica y por lo número entero de programación lineal se pueden utilizar en muchos campos de aplicación, algunos de los cuales son brevemente descrito a continuación.
Planeación de producción
La programación de enteros mixtos tiene muchas aplicaciones en las producciones industriales, incluido el modelado de talleres. Un ejemplo importante que ocurre en la planificación de la producción agrícola 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 restringirse para que sean enteras.
Planificación
Estos problemas involucran la programación de servicios y vehículos en las redes de transporte. Por ejemplo, un problema puede implicar la asignación de autobuses o subterráneos a rutas individuales para que se pueda cumplir con un horario y también para 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. El cero-uno técnica de programación se ha aplicado con éxito para resolver un problema de selección de proyectos en los que los proyectos son mutuamente excluyentes y / o tecnológicamente interdependientes. Se utiliza en un caso especial de programación de enteros, en el que todas las variables de decisión son enteros. Puede asumir los valores como cero o uno.
Partición territorial
El problema de la partición territorial o distrital consiste 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 los límites naturales y homogeneidad socioeconómica. Algunas aplicaciones para este tipo de problema incluyen: distritos políticos, distritos escolares, distritos de servicios de salud y distritos de gestión de residuos. [5]
Redes de telecomunicaciones
El objetivo de estos problemas es diseñar una red de líneas para instalar de modo que se cumpla un conjunto predefinido de requisitos de comunicación y el costo total de la red sea mínimo. [6] Esto requiere optimizar tanto la topología de la red como la configuración de las capacidades de las distintas líneas. En muchos casos, las capacidades están limitadas a cantidades enteras. Por lo general, existen, dependiendo de la tecnología utilizada, restricciones adicionales que pueden modelarse como desigualdades lineales con variables enteras o binarias.
Redes celulares
La tarea de la planificación de frecuencias de GSM redes móviles implica la distribución de frecuencias disponibles a través de las antenas de modo que los usuarios pueden ser servidos y se minimiza la interferencia entre las antenas. [7] Este problema se puede formular como un entero lineal programa en el que las variables binarias indican si una frecuencia se asigna a una antena.
Otras aplicaciones
- Gestión de residuos sólidos urbanos [8]
- Coincidencia de flujo de caja
- Optimización del sistema energético [9] [10]
- Orientación UAV [11] [12]
Algoritmos
La forma ingenua para resolver una ILP es simplemente eliminar la restricción de que x es número entero, resolver el LP correspondiente (llamada la relajación LP de la ILP), y luego alrededor de las entradas de la solución a la relajación LP. Pero, no sólo puede esta solución no es óptima, puede incluso no ser factible; es decir, puede violar alguna restricción.
Usando unimodularidad total
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 dónde y tener todas las entradas enteras y es totalmente unimodular , entonces cada solución básica factible es integral. En consecuencia, la solución devuelto por el algoritmo simplex se garantiza que sea integral. Para mostrar que toda solución básica factible es integral, seaser una solución factible básica arbitraria. Desde es factible, sabemos que . Dejar Ser los elementos correspondientes a las columnas base para la solución básica. . Por definición de una base, hay alguna submatriz cuadrada de con columnas linealmente independientes tales que .
Dado que las columnas de son linealmente independientes y es cuadrado, no es singular y, por tanto, por supuesto, es unimodular y así. Además, desde no es singular, es invertible y por lo tanto . Por definición,. Aquídenota el adyuvante de y es integral porque es integral. Por lo tanto,
Por tanto, si la matriz de un ILP es totalmente unimodular, en lugar de utilizar un algoritmo ILP, el método simplex se puede utilizar para resolver la relajación LP y la solución será un número entero.
Algoritmos exactos
Cuando la matriz no es totalmente unimodular, hay una variedad de algoritmos que se pueden usar para resolver programas lineales enteros de manera exacta. Una clase de algoritmos son método de planos de corte que trabajan mediante la resolución de la relajación LP y después añadiendo restricciones lineales que impulsan la solución hacia ser un entero sin exclusión de cualquier puntos factibles enteros.
Otra clase de algoritmos son variantes de la rama y atado método. Por ejemplo, la rama y corte método que combina tanto la rama y métodos avión con destino y de corte. Branch y algoritmos encuadernados tienen un número de ventajas sobre los algoritmos que sólo utilizan planos de corte. Una ventaja es que los algoritmos se pueden terminar antes 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 LP se pueden utilizar para proporcionar una estimación del peor de los casos de qué tan lejos de la optimización se encuentra la solución devuelta. Por último, los métodos de bifurcación y vinculación se pueden utilizar para devolver múltiples soluciones óptimas.
Algoritmos exactos para una pequeña cantidad de variables
Suponer es una matriz entera m- por- n yes un m vector entero -por-1. Nos centramos en el problema de viabilidad, que es decidir si existe un n vectores -by-1 satisfactorio .
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 de polinomio vez en m y log V . Esto es trivial para el caso n = 1. El caso n = 2 fue resuelto en 1981 por Herbert Scarf . [13] El caso general fue resuelto en 1983 por Hendrik Lenstra , combinando ideas de Laszlo Lovasz y Peter van Emde Boas . [14]
En el caso especial de 0-1 ILP, el algoritmo de Lenstra es equivalente a enumeración completa: el número de todas las soluciones posibles es fijo (2 n ), y la comprobación de la viabilidad de cada solución se puede hacer de poli tiempo ( 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 geometría de números . Transforma el problema original en uno equivalente con la siguiente propiedad: o la existencia de una solución es obvio, o el valor de (la n -ésima variable) pertenece a un intervalo cuya longitud está limitada por una función de n . En el último caso, el problema se reduce a un número limitado de problemas de dimensiones inferiores.
El algoritmo de Lenstra implica que ILP se puede resolver en tiempo polinómico también en el caso dual, en el que n es variable pero m (el número de restricciones) es constante.
El algoritmo de Lenstra fue posteriormente mejorado por Kannan [15] y Frank y Tardos. [16] El tiempo de ejecución mejorado es , dónde es el número de bits de entrada, [17] que está en. [18] : Prop.8
Métodos heurísticos
Desde número entero lineal de programación es NP-duro , muchos casos de problemas son intratables y así métodos heurísticos deben ser utilizados en su lugar. Por ejemplo, la búsqueda tabú se puede utilizar para buscar soluciones a los programas de vida independiente. [19] búsqueda uso en Tabu para resolver ILPs, mueve pueden definirse como aumentar o disminuir una variable limitado número entero de una solución factible mientras se mantiene todo otro número entero con limitaciones de variables constantes. 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 mediano plazo puede consistir en valores para las variables con restricciones enteras que han resultado en valores objetivos altos (asumiendo que el ILP es un problema de maximización). Finalmente, la memoria a largo plazo puede orientar 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
- Montañismo
- Recocido simulado
- Optimización de búsqueda reactiva
- Optimización de colonias de hormigas
- Redes neuronales de Hopfield
También hay una variedad de otras heurísticas de problemas específicos, tales como la heurística k-opt para el problema del viajante de comercio. Una desventaja de los métodos heurísticos es que si no encuentran una solución, no se puede determinar si es porque no hay una solución factible o si el algoritmo simplemente no pudo encontrar una. Además, generalmente es imposible cuantificar qué tan cerca de la solución óptima devuelta por estos métodos está.
Programación de enteros dispersos
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, que es el caso en muchas aplicaciones. La escasez de la matriz se puede medir de la siguiente manera. El gráfico de tiene vértices correspondientes a las 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 las variables, y dos variables forman un borde si comparten una desigualdad. La medida de la escasez de es el mínimo entre la profundidad del árbol del gráfico dey la profundidad del árbol del gráfico de la transposición de. Dejarser la medida numérica de definido como el valor absoluto máximo de cualquier entrada de . Dejarser el número de variables del programa entero. Luego se demostró en 2018 [20] que la programación de enteros se puede resolver en un tiempo manejable fuertemente polinomial y de parámetro fijo parametrizado por y . Es decir, para alguna función computable y algo constante , la programación de enteros se puede resolver a tiempo . En particular, el tiempo es independiente del lado derecho y función objetiva . Además, en contraste con el 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.
Ver también
- Mínimos cuadrados restringidos
Referencias
- ^ "Programación lineal de enteros mixtos (MILP): Formulación del modelo" (PDF) . Consultado el 16 de abril de 2018 .
- ^ Papadimitriou, CH ; Steiglitz, K. (1998). Optimización combinatoria: algoritmos y complejidad . Mineola, Nueva York: Dover. ISBN 0486402584.
- ^ Erickson, J. (2015). "Reducción de programación de enteros" (PDF) . Archivado desde el original (PDF) el 18 de mayo de 2015.
- ^ Williams, HP (2009). Programación lógica y entera . Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión. 130 . ISBN 978-0-387-92280-5.
- ^ Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización de la partición vertido de residuos en el estado de Paraná, Brasil". Revista de producción más limpia . 283 : 125353. doi : 10.1016 / j.jclepro.2020.125353 .
- ^ Borndörfer, R .; Grötschel, M. (2012). "Diseño de redes de telecomunicaciones de programación entera" (PDF) .
- ^ Sharma, Deepak (2010). "Frecuencia de Planificación" .
- ^ Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización de la partición vertido de residuos en el estado de Paraná, Brasil". Revista de producción más limpia . 283 : 125353. doi : 10.1016 / j.jclepro.2020.125353 .
- ^ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A .; Khodr, HM (1 de enero de 2010). "Programación óptima de una microrred renovable en un área de carga aislada mediante programación lineal de enteros mixtos" . Energía renovable . 35 (1): 151-156. doi : 10.1016 / j.renene.2009.02.031 . hdl : 10400,22 / 1585 . ISSN 0960-1481 .
- ^ Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (1 de octubre de 2013). "Optimización del sistema de recursos energéticos distribuidos mediante programación lineal de enteros mixtos" . Política energética . 61 : 249-266. doi : 10.1016 / j.enpol.2013.05.009 . ISSN 0301-4215 .
- ^ Schouwenaars, T .; Valenti, M .; Feron, E .; Cómo, J. (2005). "Implementación y resultados de prueba de vuelo de la guía UAV basada en MILP". 2005 Conferencia IEEE Aeroespacial : 1-13. doi : 10.1109 / AERO.2005.1559600 . ISBN 0-7803-8870-4. S2CID 13447718 .
- ^ Radmanesh, Mohammadreza; Kumar, Manish (1 de marzo de 2016). "Formación de vuelo de vehículos aéreos no tripulados en presencia de obstáculos en movimiento utilizando entera mixta rápido-dinámico lineal de programación" . Ciencia y tecnología aeroespacial . 50 : 149-160. doi : 10.1016 / j.ast.2015.12.021 . ISSN 1270-9638 .
- ^ Bufanda, Herbert E. (1981). "Conjuntos de producción con indivisibilidades, Parte I: Generalidades" . Econometrica . 49 (1): 1-32. doi : 10.2307 / 1911124 . ISSN 0012 a 9682 . JSTOR 1.911.124 .
- ^ Lenstra, HW (1 de noviembre de 1983). "Programación de enteros con un número fijo de variables" . Matemáticas de la investigación operativa . 8 (4): 538–548. doi : 10.1287 / moor.8.4.538 . ISSN 0364-765X .
- ^ Kannan, Ravi (1 de agosto de 1987). "Teorema del cuerpo convexo de Minkowski y programación de enteros" . Matemáticas de la investigación operativa . 12 (3): 415–440. doi : 10.1287 / moor.12.3.415 . ISSN 0364-765X .
- ^ Frank, András; Tardos, Éva (1 de marzo de 1987). "Una aplicación de aproximación diofántica simultánea en optimización combinatoria" . Combinatorica . 7 (1): 49–65. doi : 10.1007 / BF02579200 . ISSN 1439-6912 . S2CID 45585308 .
- ^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (9 de julio de 2016). "La complejidad de la asignación eficiente y libre de envidias de recursos: unos agentes, recursos, o los niveles de utilidad" . Actas de la XXV Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, EE.UU.: AAAI Press: 102-108. ISBN 978-1-57735-770-4.
- ^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (17 de junio de 2019). "Asignación justa de alta multiplicidad: Lenstra potenciado por programación de números enteros N-veces" . Actas de la Conferencia ACM de 2019 sobre economía y computación . CE '19. Phoenix, AZ, EE. UU.: Asociación de Maquinaria de Computación: 505–523. doi : 10.1145 / 3328526.3329649 . ISBN 978-1-4503-6792-9. S2CID 195298520 .
- ^ Glover, F. (1989). "Búsqueda Tabu-Parte II" . ORSA Diario de Computación . 1 (3): 4-32. doi : 10.1287 / ijoc.2.1.4 . S2CID 207225435 .
- ^ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Un parametrizado Fuertemente polinómica Algoritmo para estructurado en bloques Programas entero" . Michael Wagner: 14 páginas. arXiv : 1802.05859 . doi : 10.4230 / LIPICS.ICALP.2018.85 . S2CID 3.336.201 . Cite journal requiere
|journal=
( ayuda )
Otras lecturas
- George L. Nemhauser ; Laurence A. Wolsey (1988). Entero y optimización combinatoria . Wiley. ISBN 978-0-471-82819-8.
- Alexander Schrijver (1998). Teoría de la programación lineal y entera . John Wiley e hijos. ISBN 978-0-471-98232-6.
- Laurence A. Wolsey (1998). Programación de enteros . Wiley. ISBN 978-0-471-28366-9.
- Dimitris Bertsimas; Robert Weismantel (2005). Optimización sobre enteros . Ideas dinámicas. ISBN 978-0-9759146-2-5.
- John K. Karlof (2006). Programación entera: teoría y práctica . Prensa CRC. ISBN 978-0-8493-1914-3.
- H. Paul Williams (2009). Programación lógica y entera . Saltador. ISBN 978-0-387-92279-9.
- Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser ; William R. Pulleyblank ; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 Años de Programación Entera 1958-2008: Desde los primeros años al Estado-of-the-art . Saltador. ISBN 978-3-540-68274-5.
- Der-San Chen; Robert G. Batson; Yu Dang (2010). Aplicada Programación Entera: Modelado y solución . John Wiley e hijos. ISBN 978-0-470-37306-4.
- Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica . Prensa CRC. ISBN 978-1-498-71016-9.
enlaces externos
- Un tutorial sobre programación de enteros
- Programación de enteros de conferencias y optimización combinatoria, IPCO
- El taller de optimización combinatoria de Aussois