Programación de números enteros

Un problema de optimización matemática restringido a números enteros

Un problema de programación entera es un programa matemático de optimización o viabilidad 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 solo 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 un problema de programación entera mixta . ^[2]

Forma canónica y estándar para los ILP

En la 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í (nótese que es el vector el que se debe decidir): ^[3] ${\displaystyle \mathbf {x} }$

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

y un ILP en forma estándar se expresa como

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}$

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 forma estándar eliminando desigualdades, introduciendo variables de holgura ( ) y reemplazando variables que no están restringidas por signos con la diferencia de dos variables restringidas por signos. ${\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}}$ ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle \mathbf {s} }$

Ejemplo

Politopo IP con relajación LP

El gráfico de la derecha muestra el siguiente problema.

${\displaystyle {\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}}$

Los puntos enteros factibles se muestran en rojo, y las líneas discontinuas rojas indican su envoltura convexa, 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 está dado por las desigualdades sin la restricción de integralidad. El objetivo de la optimización es mover la línea discontinua negra hacia arriba lo más lejos posible sin dejar de tocar el poliedro. Las soluciones óptimas del problema entero son los puntos y 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 enteros más cercanos, no es factible para el ILP. ${\displaystyle (1,2)}$ ${\displaystyle (2,2)}$ ${\displaystyle (1.8,2.8)}$

Prueba de dureza NP

Lo que sigue 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 grafo no dirigido. Definamos un programa lineal de la siguiente manera: ${\displaystyle G=(V,E)}$

${\displaystyle {\begin{aligned}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v}&\in \mathbb {Z^{+}} &&\forall v\in V\end{aligned}}}$

Dado 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 arista está incluido en este subconjunto. Por lo tanto, la solución describe una cobertura de vértices. Además, dada una cobertura de vértices C, se puede establecer en 1 para cualquier y en 0 para cualquier, lo que nos da una solución factible para el programa entero. Por lo tanto, podemos concluir que si minimizamos la suma de , también hemos encontrado la cobertura de vértices mínima. ^[4] ${\displaystyle y_{v}}$ ${\displaystyle y_{v}}$ ${\displaystyle v\in C}$ ${\displaystyle v\not \in C}$ ${\displaystyle y_{v}}$

Variantes

La programación lineal de enteros mixtos ( MILP ) implica problemas en los que solo algunas de las variables, , están restringidas a ser números enteros, mientras que se permite que otras variables no sean números enteros. ${\displaystyle x_{i}}$

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 utilizando variables binarias: ${\displaystyle 0\leq x\leq U}$ ${\displaystyle \lfloor \log _{2}U\rfloor +1}$

$${\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.}$$

Aplicaciones

Hay dos razones principales para utilizar variables enteras al modelar problemas como un programa lineal:

1. Las variables enteras representan cantidades que solo pueden ser enteras. Por ejemplo, no es posible construir 3,7 automóviles.
2. 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 ocurren con frecuencia en la práctica, por lo que la programación lineal entera se puede utilizar en muchas áreas de aplicación, algunas de las cuales se describen brevemente a continuación.

Planificación de la producción

La programación entera mixta tiene muchas aplicaciones en la producción industrial, incluida la modelización de talleres. Un ejemplo importante se da en la planificación de la producción agrícola e implica determinar el rendimiento de la producción de 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 estar restringidas para que sean números enteros.

Programación

Estos problemas involucran la programación de servicios y vehículos en redes de transporte. Por ejemplo, un problema puede involucrar la asignación de autobuses o subterráneos a rutas individuales para que se pueda cumplir un horario, y también para equiparlos con conductores. Aquí las variables de decisión binarias indican si un autobús o subterráneo está asignado a una ruta y si un conductor está asignado a un tren o subterráneo 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. Variable puede asumir solo los valores cero o uno.

Partición territorial

Los problemas de compartimentación o deslindamiento territorial consisten en dividir una región geográfica en distritos para planificar determinadas operaciones teniendo en cuenta diferentes criterios o restricciones. Algunos requisitos de 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 problemas son: deslindamiento político, deslindamiento escolar, deslindamiento de servicios de salud y deslindamiento de gestión de residuos.

Redes de telecomunicaciones

El objetivo de estos problemas es diseñar una red de líneas para instalar de manera 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, según la tecnología utilizada, restricciones adicionales que se pueden modelar como desigualdades lineales con variables enteras o binarias.

Redes celulares

La tarea de planificación de frecuencias en redes móviles GSM implica distribuir las frecuencias disponibles entre las antenas de modo que los usuarios puedan ser atendidos y se minimice la interferencia entre las antenas. ^[7] Este problema se puede formular como un programa lineal entero en el que las variables binarias indican si una frecuencia está asignada a una antena.

Otras aplicaciones

• Coincidencia de flujo de caja
• Optimización del sistema energético ^{[8] [9]}
• Guiado por UAV ^{[10] [11]}
• Diseño de mapas de tránsito ^[12]

Algoritmos

La forma ingenua de resolver un problema de programación in vitro es simplemente eliminar la restricción de que x es un número entero, resolver el problema de programación in vitro correspondiente (llamado relajación de programación in vitro) y luego redondear las entradas de la solución a la relajación de programación in vitro. Pero, no sólo puede que esta solución no sea óptima, sino que incluso puede que no sea factible; es decir, puede violar alguna restricción.

Utilizando unimodularidad total

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

Dado que las columnas de son linealmente independientes y es cuadrada, no es singular y, por lo tanto, por suposición, es unimodular y, por lo tanto , . Además, dado que no es singular, es invertible y, por lo tanto , . Por definición, . Aquí denota el adjunto de y es integral porque es integral. Por lo tanto, Por lo 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. ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle \det(B)=\pm 1}$ ${\displaystyle B}$ ${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$ ${\displaystyle B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }}$ ${\displaystyle B^{\mathrm {adj} }}$ ${\displaystyle B}$ ${\displaystyle B}$ $${\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}}}$$ ${\displaystyle A}$

Algoritmos exactos

Cuando la matriz no es totalmente unimodular, existen diversos algoritmos que se pueden utilizar para resolver programas lineales enteros de manera exacta. Una clase de algoritmos son los métodos de plano de corte , que funcionan resolviendo la relajación de PL y luego agregando restricciones lineales que conducen la solución hacia un entero sin excluir ningún punto factible entero. ${\displaystyle A}$

Otra clase 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 los métodos de ramificación y acotación y de plano de corte. Los algoritmos de ramificación y acotación tienen una serie de ventajas sobre los algoritmos que solo utilizan planos de corte. Una ventaja es que los algoritmos pueden terminarse 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 de LP se pueden utilizar para proporcionar una estimación del peor caso posible de qué tan lejos de la optimalidad se encuentra la solución devuelta. Finalmente, los métodos de ramificación y acotación se pueden utilizar para devolver múltiples soluciones óptimas.

Algoritmos exactos para un número pequeño de variables

Supongamos que es una matriz de números enteros de m por n y es un vector de números enteros de m por 1. Nos centramos en el problema de viabilidad, que consiste en decidir si existe un vector de números enteros de n por 1 que satisfaga . ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle A\mathbf {x} \leq \mathbf {b} }$

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 puede resolverse en un polinomio de tiempo 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 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; un método que combina este resultado con algoritmos para problemas de tipo LP puede usarse para resolver programas enteros en el tiempo que son lineales en y manejables con parámetros fijos (FPT) en , pero posiblemente doblemente exponenciales en , sin dependencia de . ^[15] ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$ ${\displaystyle 2^{n}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle V}$

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 ⁿ ), y la comprobación de la viabilidad de cada solución se puede realizar en el tiempo poly( 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 es obvia, o bien 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 menor dimensión. La complejidad en tiempo de ejecución del algoritmo se ha mejorado en varios pasos: ${\displaystyle \mathbf {x} }$ ${\displaystyle x_{n}}$

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

• Dadush ^[21] 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 ^[22] 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 enteros mixtos (MILP): programas en los que algunas variables son enteras y otras son reales. ^[23] El algoritmo original de Lenstra ^{[14] : Sec.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] ${\displaystyle 2^{O(n^{3})}\cdot poly(d,L)}$ ${\displaystyle 2^{O(n^{3})}}$ ${\displaystyle 2^{O(n\log n)}}$ ${\displaystyle n^{n}}$

Métodos heurísticos

Dado que la programación lineal entera es NP-hard , muchas instancias de problemas son intratables y, por lo tanto, se deben utilizar métodos heurísticos en su lugar. 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 decrementar una variable entera restringida de una solución factible mientras se mantienen constantes todas las demás variables enteras restringidas. Luego se resuelven las variables no restringidas. La memoria de corto plazo puede consistir en soluciones previamente probadas, mientras que la memoria de mediano plazo puede consistir en valores para las variables enteras restringidas que han resultado en valores objetivos altos (asumiendo que el ILP es un problema de maximización). Finalmente, la memoria de 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:

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

También existen otras heurísticas específicas para cada problema, 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 logran encontrar una solución, no se puede determinar si es porque no existe una solución factible o si el algoritmo simplemente no pudo encontrarla. Además, suele ser imposible cuantificar cuán cerca de la solución óptima está la solución obtenida con estos métodos.

Programación de números enteros dispersos

A menudo ocurre que la matriz que define el programa entero es dispersa . 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 columnas de y dos columnas forman una arista 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 de parámetros fijos y fuertemente polinomial 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. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle d}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle f(a,d)n^{k}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle n}$

Véase también

• Mínimos cuadrados restringidos
• Ecuación diofántica  : ecuación polinómica cuyas soluciones enteras se buscan

Referencias

1. Karp, Richard M. (1972). "Reducibilidad entre problemas combinatorios" (PDF) . En RE Miller; JW Thatcher; JD Bohlinger (eds.). Complejidad de los cálculos informáticos . Nueva York: Plenum. págs. 85-103. doi :10.1007/978-1-4684-2001-2_9. ISBN. 978-1-4684-2003-6.
2. "Programación lineal entera mixta (MILP): formulación de modelos" (PDF) . Consultado el 16 de abril de 2018 .
3. Papadimitriou, CH ; Steiglitz, K. (1998). Optimización combinatoria: algoritmos y complejidad . Mineola, NY: Dover. ISBN 0486402584.
4. Erickson, J. (2015). "Reducción de programación entera" (PDF) . Archivado desde el original (PDF) el 18 de mayo de 2015.
5. Williams, HP (2009). Lógica y programación entera . Serie internacional en investigación de operaciones y ciencia de la gestión. Vol. 130. ISBN 978-0-387-92280-5.
6. Borndörfer, R.; Grötschel, M. (2012). "Diseño de redes de telecomunicaciones mediante programación entera" (PDF) .
7. Sharma, Deepak (2010). "Planificación de frecuencia".
8. 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 entera mixta". Energías Renovables . 35 (1): 151-156. Código Bib : 2010REne...35..151M. doi :10.1016/j.renene.2009.02.031. hdl : 10400.22/1585 . ISSN  0960-1481.
9. Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (1 de octubre de 2013). "Optimización de sistemas de recursos energéticos distribuidos mediante programación lineal entera mixta". Política energética . 61 : 249–266. Bibcode :2013EnPol..61..249O. doi :10.1016/j.enpol.2013.05.009. ISSN  0301-4215. S2CID  29369795.
10. Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementación y resultados de pruebas de vuelo de guía de UAV basada en MILP". Conferencia Aeroespacial IEEE de 2005. págs. 1–13. doi :10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. Número de identificación del sujeto  13447718.
11. 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 programación lineal entera mixta de dinámica rápida". Ciencia y tecnología aeroespacial . 50 : 149–160. Bibcode :2016AeST...50..149R. doi : 10.1016/j.ast.2015.12.021 . ISSN  1270-9638.
12. Bast, Hannah; Brosi, Patrick; Storandt, Sabine (5 de octubre de 2017). "Generación eficiente de mapas de tránsito geográficamente precisos". arXiv : 1710.02226 [cs.CG].
13. Scarf, Herbert E. (1981). "Conjuntos de producción con indivisibilidades, parte I: generalidades". Econometrica . 49 (1): 1–32. doi :10.2307/1911124. ISSN  0012-9682. JSTOR  1911124.
14. Lenstra, HW (1983-11-01). "Programación entera con un número fijo de variables". Matemáticas de la investigación de operaciones . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. ISSN  0364-765X. 
15. Amenta, Nina ; De Loera, Jesús A. ; Soberón, Pablo (2017). "Teorema de Helly: nuevas variaciones y aplicaciones". En Harrington, Heather A. ; Omar, Mohamed; Wright, Matthew (eds.). Actas de la Sesión Especial de la AMS sobre Métodos Algebraicos y Geométricos en Matemáticas Discretas Aplicadas celebrada en San Antonio, TX, el 11 de enero de 2015 . Matemáticas Contemporáneas. Vol. 685. Providence, Rhode Island: American Mathematical Society. pp. 55–95. arXiv : 1508.07606 . doi :10.1090/conm/685. ISBN 9781470423216.Señor 3625571  .
16. Kannan, Ravi (1 de agosto de 1987). "Teorema del cuerpo convexo de Minkowski y programación entera". Matemáticas de la investigación de operaciones . 12 (3): 415–440. doi :10.1287/moor.12.3.415. ISSN  0364-765X. S2CID  495512.
17. Goemans, Michel X. ; Rothvoss, Thomas (7 de noviembre de 2020). "Polinomialidad para empaquetamiento de contenedores con un número constante de tipos de elementos". Revista de la ACM . 67 (6): 38:1–38:21. doi : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN  0004-5411. S2CID  227154747.
18. Frank, András; Tardos, Éva (1987-03-01). "Una aplicación de la aproximación diofántica simultánea en la optimización combinatoria". Combinatorica . 7 (1): 49–65. doi :10.1007/BF02579200. ISSN  1439-6912. S2CID  45585308.
19. Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (9 de julio de 2016). "Complejidad de la asignación eficiente y sin envidia de recursos: pocos agentes, recursos o niveles de utilidad". Actas de la 25.ª Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, EE. UU.: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
20. Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (17 de junio de 2019). "Asignación justa de alta multiplicidad: Lenstra potenciada por programación entera N-fold". Actas de la Conferencia ACM de 2019 sobre economía y computación . EC '19. Phoenix, AZ, EE. UU.: Association for Computing Machinery. págs. 505–523. doi :10.1145/3328526.3329649. ISBN . 978-1-4503-6792-9.S2CID 195298520  .
21. Dadush, Daniel (14 de junio de 2012). "Programación entera, algoritmos de red y estimación de volumen determinista".
22. Reis, Victor; Rothvoss, Thomas (26 de marzo de 2023). "La conjetura de planitud del subespacio y la programación entera más rápida".
23. Hildebrand, Robert (7 de octubre de 2016). "Algoritmo FPT para programa de números enteros mixtos". Theoretical Computer Science Stack Exchange . Consultado el 21 de mayo de 2024 .
24. Glover, F. (1989). "Búsqueda tabú, parte II". ORSA Journal on Computing . 1 (3): 4–32. doi :10.1287/ijoc.2.1.4. S2CID  207225435.
25. Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Un algoritmo fuertemente polinomial parametrizado para programas enteros estructurados en bloques". En Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (eds.). 45.° Coloquio Internacional sobre Autómatas, Lenguajes y Programación, ICALP 2018, 9 al 13 de julio de 2018, Praga, República Checa . LIPIcs. Vol. 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .

Lectura adicional

• George L. Nemhauser y Laurence A. Wolsey (1988). Optimización entera y combinatoria . Wiley. ISBN 978-0-471-82819-8.
• Alexander Schrijver (1998). Teoría de la programación lineal y entera . John Wiley and Sons. ISBN 978-0-471-98232-6.
• Laurence A. Wolsey (1998). Programación entera . Wiley. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas; Robert Weismantel (2005). Optimización sobre números enteros . Ideas dinámicas. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). Programación entera: teoría y práctica . CRC Press. ISBN 978-0-8493-1914-3.
• H. Paul Williams (2009). Lógica y programación entera . Springer. 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 hasta el estado del arte . Springer. ISBN 978-3-540-68274-5.
• Der-San Chen; Robert G. Batson; Yu Dang (2010). Programación entera aplicada: modelado y solución . John Wiley and Sons. 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 entera
• Conferencia sobre Programación Entera y Optimización Combinatoria, IPCO
• Taller de optimización combinatoria de Aussois