base más grave

En matemáticas aplicadas , las bases de Graver permiten soluciones iterativas de problemas de programación entera lineal y no lineal en tiempo polinomial . Fueron presentados por Jack E. Graver. ^[1] Bernd Sturmfels discutió su conexión con la teoría de las bases de Gröbner . ^[2] Shmuel Onn describe la teoría algorítmica de las bases de Graver y su aplicación a la programación entera . ^{[3] [4]}

Definicion formal

La base de Graver de una matriz entera de m  ×  n es el conjunto finito de elementos mínimos del conjunto ${\displaystyle A}$ ${\displaystyle G(A)}$

${\displaystyle \{x\in \mathbb {Z} ^{n}:Ax=0,\ x\neq 0\}\,}$

bajo un orden bien parcial definido por cuándo y para todos i. Por ejemplo, la base de Graver consta de los vectores (2,−1,0), (0,−1,2), (1,0,−1), (1,−1,1) y sus negaciones. ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle x\sqsubseteq y}$ ${\displaystyle x_{i}y_{i}\geq 0}$ ${\displaystyle |x_{i}|\leq |y_{i}|}$ ${\displaystyle A=(1,2,1)}$

Resolver programación entera usando bases de Graver

La programación entera es el problema de optimizar una función objetivo lineal o no lineal sobre el conjunto de puntos enteros que satisfacen un sistema de desigualdades lineales. Formalmente, se puede escribir en forma estándar de la siguiente manera:

${\displaystyle \min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .}$

Es uno de los problemas de optimización discreta más fundamentales y tiene un poder de modelado muy amplio y numerosas aplicaciones en una variedad de áreas, pero normalmente es muy difícil desde el punto de vista computacional, como se indica a continuación. Sin embargo, dada la base de Graver de , el problema con funciones objetivo lineales y varias funciones objetivo no lineales se puede resolver en tiempo polinomial como se explica a continuación. ${\displaystyle G(A)}$ ${\displaystyle A}$

Programación entera lineal

El caso más estudiado, tratado detalladamente en ^[5] , es el de la programación lineal entera ,

${\displaystyle \min\{wx\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}\ .}$

Se puede suponer que todas las variables están limitadas desde abajo y desde arriba: dichos límites aparecen naturalmente en la aplicación en cuestión o pueden imponerse sin perder ninguna solución óptima. Pero, incluso con funciones objetivo lineales, el problema es NP-difícil y, por lo tanto, presumiblemente no puede resolverse en tiempo polinomial.

Sin embargo, la base de Graver tiene la siguiente propiedad. Para cada punto factible x : ${\displaystyle G(A)}$ ${\displaystyle A}$

• O x es óptimo (es decir, se minimiza dadas las restricciones); ${\displaystyle w\cdot x}$
• O existe un vector g en , tal que x + g es factible y (es decir, x puede mejorarse añadiéndole un elemento de la base de Graver). ${\displaystyle G(A)}$ ${\displaystyle w\cdot (x+g)<w\cdot x}$

Por lo tanto, dada la base de Graver , el ILP se puede resolver en tiempo polinomial utilizando el siguiente algoritmo iterativo simple. ^{[3] [6]} Supongamos primero que se da algún punto inicial factible x . Mientras sea posible, repita la siguiente iteración: encuentre el entero positivo q y el elemento g de modo que x  +  qg no viole los límites y proporcione la mejor mejora posible; actualice x  :=  x  +  qg y continúe con la siguiente iteración. El último punto x es óptimo y el número de iteraciones es polinómico. ${\displaystyle G(A)}$ ${\displaystyle G(A)}$

Para encontrar un punto inicial factible, se puede configurar y resolver un programa auxiliar adecuado de manera similar.

Programación entera no lineal

Volviendo al caso de las funciones objetivo generales f , si las variables no están acotadas entonces el problema puede ser, de hecho, incomputable: de la solución del décimo problema de Hilbert se deduce (ver ^[7] ), que no existe ningún algoritmo que, dado un número entero polinomio f de grado 8 en 58 variables, decide si el valor mínimo de f sobre todos los vectores enteros de 58 dimensiones es 0. Sin embargo, cuando las variables están acotadas, el problema

${\displaystyle \min\{f(x)\ :\ x\in \mathbb {Z} ^{n},\ Ax=b,\ l\leq x\leq u\}}$

se puede resolver utilizando la base de Graver en tiempo polinómico para varias funciones objetivo no lineales, incluida ^{[ cita necesaria ]} : ${\displaystyle G(A)}$

• Funciones separables-convexas de la forma ; ${\displaystyle f(x)=\sum _{i=1}^{n}f_{i}(x_{i})}$
• En particular, la norma p para cada entero positivo p ; ${\displaystyle f(x)=\|x\|_{p}}$
• Funciones cóncavas compuestas f ( x ) =  g ( Wx ), donde W es una matriz entera d  ×  n con d fija, y donde g es una función cóncava d -variada;
• Ciertas funciones polinomiales de grado superior y cuadráticas (in)definidas .

Algunas aplicaciones

Tablas multidimensionales

Considere el siguiente problema de optimización sobre tablas tridimensionales con sumas de líneas prescritas,

${\displaystyle \min\{wx\ :\ x\in {\mathbb {Z} }_{+}^{l\times m\times n}\,,\ \sum _{i}x_{i,j,k}=a_{j,k}\,,\ \sum _{j}x_{i,j,k}=b_{i,k}\,,\ \sum _{k}x_{i,j,k}=c_{i,j}\}\ ,}$

con ,, enteros no negativos (cuyo valor máximo limita implícitamente todas las variables desde arriba). Denote por la matriz que define ( lm  +  ln  +  mn ) × ( lmn ) de este sistema. Tenga en cuenta que esta matriz generalmente no es totalmente unimodular . No obstante, se demostró en ^{[8] que para cada} l y m fijos , su base de Graver se puede calcular en el tiempo, que es polinomio en  n . Los resultados mencionados anteriormente permiten entonces resolver este problema en tiempo polinomial para l y m fijos y n variable . Tenga en cuenta que si sólo un lado l de la tabla es fijo (incluso con l  = 3) mientras tanto m como n son variables, entonces el problema es NP difícil, como se muestra en. ^[9] De manera más general, resultados positivos similares son válidos para niveles más altos. Problemas de tablas dimensionales (introducidos en ^{[10] ): para cada} d y fijo , la optimización (no) lineal sobre tablas con n variable y márgenes prescritos se puede realizar en tiempo polinómico. Esto tiene aplicaciones adicionales para abordar problemas de seguridad y privacidad en bases de datos estadísticas . ${\displaystyle a_{j,k}}$ ${\displaystyle b_{i,k}}$ ${\displaystyle c_{i,j}}$ ${\displaystyle A}$ ${\displaystyle G(A)}$ ${\displaystyle m_{1},\dots ,m_{d}}$ ${\displaystyle m_{1}\times \cdots \times m_{d}\times n}$

Flujos de múltiples productos básicos

Considere el problema del flujo entero de múltiples productos que consiste en encaminar k tipos de productos enteros desde m proveedores hasta n consumidores sujetos a restricciones de oferta, consumo y capacidad, de modo que se minimice la suma de los costos convexos lineales o dependientes de la congestión en los arcos. Luego, para cada k y m fijos , se puede calcular la base de Graver del sistema definitorio y minimizar en el tiempo la función objetivo convexa separable resultante, que es polinómica en el número variable n de consumidores y en el resto de los datos.

Otras aplicaciones

Las numerosas aplicaciones de la teoría algorítmica de las bases de Graver también incluyen:

• programación entera estocástica, ^[6]
• programación entera N veces,
• Programación entera descomponible de 4 bloques N veces, ^[11]
• agrupamiento,
• control de divulgación en bases de datos estadísticas,
• y asignación justa de objetos indivisibles. ^[12]

En algunas de estas aplicaciones, la base de Graver relevante no se puede calcular en tiempo polinómico, pero se puede acceder a ella de forma indirecta, lo que permite utilizarla en tiempo polinómico.

Universalidad y parametrización.

^{En [13]} se demostró que cada problema de programación entera (acotado) es precisamente equivalente al problema de tabla 3 ×  m  ×  n discutido anteriormente para algunas m y n y algunas sumas de líneas. Por tanto, estos problemas de tablas de 3 ×  m  ×  n son universales para la programación entera. Además, para cada m fijo , la clase resultante de programas enteros se puede resolver en tiempo polinómico mediante el método iterativo de base de Graver descrito anteriormente. Entonces, el ancho de la tabla m proporciona una parametrización de todos los problemas de programación entera.

Jerarquía de aproximaciones para programación entera

Denota por la base de Graver de la matriz que define el problema de tabla universal 3 ×  m  ×  n discutido anteriormente. Los elementos de son tablas de 3 ×  m  ×  n con todas las sumas de líneas iguales a 0. El tipo de dicha tabla es el número de sus  capas de 3 × m distintas de cero . Resulta que existe una función de complejidad de Graver finita g ( m ) tal que para cualquier n , el tipo de cualquier elemento de la base de Graver es como máximo g ( m ). De ello se deduce que la base Graver es la unión de las copias adecuadamente integradas de la base Graver . Para resolver aproximadamente en la práctica un problema de programación entera arbitraria, proceda de la siguiente manera. Primero incorpórelo en un problema de tabla adecuado de 3 ×  m  ×  n según lo permita la universalidad mencionada anteriormente. Ahora aplique la siguiente jerarquía de aproximaciones de . En el nivel k de esta jerarquía, sea el subconjunto que consta únicamente de aquellos elementos de tipo k como máximo ; utilizar esta aproximación en el algoritmo iterativo el mayor tiempo posible para obtener el mejor punto factible posible para el problema de programación entera incluido en el  problema de tabla 3 × m  ×  n ; si el valor de la función objetivo de este punto es satisfactorio (digamos, en comparación con el valor de la relajación de la programación lineal ), utilice este punto; de lo contrario, incremente k y pase al siguiente nivel de la jerarquía. Se puede demostrar ^[3] que para cualquier nivel fijo k , la aproximación de la base de Graver tiene cardinalidad polinómica y se puede calcular en ese tiempo. ${\displaystyle G(m,n)}$ ${\displaystyle A}$ ${\displaystyle G(m,n)}$ ${\displaystyle G(m,n)}$ ${\displaystyle G(m,n)}$ ${\displaystyle {n \choose g(m)}}$ ${\displaystyle G(m,g(m))}$ ${\displaystyle G(m,n)}$ ${\displaystyle G_{k}(m,n)}$ ${\displaystyle G(m,n)}$ ${\displaystyle G_{k}(m,n)}$ ${\displaystyle G_{k}(m,n)}$ ${\displaystyle O\left(m^{g(k)}n^{k}\right)}$

Tratabilidad de parámetros fijos: de la complejidad del tiempo polinomial a la cúbica

La complejidad temporal de resolver algunas de las aplicaciones analizadas anteriormente, como los problemas de tablas multidimensionales, los problemas de flujo de múltiples productos y los problemas de programación de números enteros N , está dominada por la cardinalidad de la base de Graver relevante, que es un polinomio con valores típicamente grandes. grado g que es una complejidad de Graver adecuada del sistema. En ^[14] se presenta un algoritmo mucho más rápido, que encuentra en cada iteración la mejor mejora x  +  qg con q entero positivo y g elemento sin construir explícitamente la base de Graver , en tiempo cúbico independientemente del sistema. En la terminología de complejidad parametrizada , esto implica que todos estos problemas adecuadamente parametrizados, y en particular l  ×  m  ×  n problemas de tablas parametrizados por l y m , son manejables con parámetros fijos . ${\displaystyle O\left(n^{g}\right)}$ ${\displaystyle G(A)}$ ${\displaystyle O\left(n^{3}\right)}$

Ver también

• El lema de Gordan : otra herramienta relacionada con conjuntos cero de matrices enteras.

Referencias

1. Jack E. Graver: Sobre los fundamentos de la programación lineal y entera, Programación matemática 9:207–226, 1975
2. Bernd Sturmfels , Bases de Gröbner y politopos convexos , Sociedad Matemática Estadounidense , xii+162 págs., 1996
3. Shmuel onn: Optimización discreta no lineal, Sociedad Matemática Europea , x+137 págs., 2010
4. Shmuel Onn: optimización de enteros lineales y no lineales, serie de conferencias en vídeo en línea, Instituto de Investigación de Ciencias Matemáticas , Berkeley, 2010
5. Alexander Schrijver : Teoría de la programación lineal y entera , Wiley, xii + 471 págs., 1986
6. Raymond Hemmecke, Shmuel Onn, Robert Weismantel: un algoritmo polinómico en tiempo de oráculo para la minimización de enteros convexos, Programación matemática 126:97–117, 2011
7. Yuri V. Matiyasevich: Décimo problema de Hilbert , MIT Press, xxiv + 264 págs., 1993
8. Jesús A. De Loera , Raymond Hemmecke, Shmuel Onn, Robert Weismantel: programación de números enteros N , optimización discreta, 5:231–241, 2008
9. Jesús A. De Loera , Shmuel Onn: La complejidad de las tablas estadísticas de tres vías, SIAM Journal on Computing, 33:819–836, 2004
10. Theodore S. Motzkin: El problema del transporte de índices múltiples, Boletín de la Sociedad Matemática Estadounidense 58:494, 1952
11. Raymond Hemmecke, Matthias Köppe, Robert Weismantel: un algoritmo de tiempo polinómico para optimizar programas enteros descomponibles de 4 bloques N , IPCO 14, 2010
12. 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 de enteros N". 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. págs. 505–523. doi :10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID  195298520.
13. Jesus A. De Loera, Shmuel Onn: Todos los programas lineales y enteros son programas delgados de transporte de 3 vías, SIAM Journal on Optimization, 17:806–821, 2006
14. Raymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: programación entera N veces en tiempo cúbico, Programación matemática, 137:325–341, 2013