Programa lineal de configuración

El programa lineal de configuración ( configuration-LP ) es una técnica de programación lineal utilizada para resolver problemas de optimización combinatoria . Se introdujo en el contexto del problema de corte de materiales . ^{[ 1 ]}^{[ 2 ]} Posteriormente, se ha aplicado a los problemas de empaquetamiento de contenedores ^{[ 3 ]}^{[ 4 ]} y de programación de tareas . ^{[ 5 ]}^{[ 6 ]} En configuration-LP, hay una variable para cada configuración posible : cada posible multiconjunto de elementos que pueden caber en un solo contenedor (estas configuraciones también se conocen como patrones ). Por lo general, el número de configuraciones es exponencial en el tamaño del problema, pero en algunos casos es posible obtener soluciones aproximadas utilizando solo un número polinomial de configuraciones.

En el embalaje de contenedores

El LP integral

En el problema de empaquetado de contenedores , hay n artículos de diferentes tamaños. El objetivo es empaquetar los artículos en un número mínimo de contenedores, donde cada contenedor puede contener como máximo B. Una configuración factible es un conjunto de tamaños cuya suma es como máximo B.

Ejemplo : ^{[ 7 ]} supongamos que los tamaños de los artículos son 3,3,3,3,3,4,4,4,4,4 y B =12. Entonces las configuraciones posibles son: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Si solo tuviéramos tres artículos de tamaño 3, entonces no podríamos usar la configuración 3333.

Denotemos por S el conjunto de diferentes tamaños (y su número). Denotemos por C el conjunto de diferentes configuraciones (y su número). Para cada tamaño s en S y configuración c en C , denotemos:

n _s - el número de artículos de tamaño s .
a _s_{, c} - el número de ocurrencias de tamaño s en la configuración c .
x _c - una variable que denota el número de contenedores con configuración c .

Entonces, la configuración LP del empaquetamiento de contenedores es:

minimizar $\sum _{c\in C}x_{c}$ sujeto a
$\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ para todos los s en S (todos los n _s artículos de tamaño s están empaquetados).
$x_{c}\in \{0,\ldots ,n\}$ para todos los c en C (hay como máximo n contenedores en total, por lo que hay como máximo n de cada configuración individual).

El LP de configuración es un programa lineal entero , por lo que en general es NP-difícil. Además, incluso el problema en sí es generalmente muy grande: tiene C variables y S restricciones. Si el tamaño del elemento más pequeño es eB (para alguna fracción e en (0,1)), entonces puede haber hasta 1/ e elementos en cada contenedor, por lo que el número de configuraciones C ~ S ^{1/ e} , que puede ser muy grande si e es pequeño (si e se considera una constante, entonces el LP entero se puede resolver mediante búsqueda exhaustiva: hay como máximo S ^1/e configuraciones, y para cada configuración hay como máximo n valores posibles, por lo que hay como máximo $n^{S^{1/e}}$ combinaciones a comprobar. Para cada combinación, tenemos que comprobar las restricciones S , por lo que el tiempo de ejecución es $S\cdot n^{S^{1/e}}$ , que es polinomial en n cuando S, e son constantes). ^{[ 7 ]}

Sin embargo, este problema de programación lineal entera (PLI) sirve de base para varios algoritmos de aproximación . La idea principal de estos algoritmos es reducir la instancia original a una nueva instancia en la que S sea pequeño y e sea grande, de modo que C sea relativamente pequeño. Entonces, el PLI se puede resolver mediante una búsqueda completa (si S y C son suficientemente pequeños) o relajándolo a un problema de programación lineal fraccionaria .

El LP fraccional

La configuración fraccionaria LP de empaquetamiento de contenedores es la relajación de programación lineal del ILP anterior. Reemplaza la última restricción. $x_{c}\in \{0,\ldots ,n\}$ con la restricción $x_{c}\geq 0$ En otras palabras, cada configuración puede utilizarse un número fraccional de veces. La relajación fue presentada por primera vez por Gilmore y Gomory, ^{[ 2 ]} y a menudo se la denomina programa lineal de Gilmore-Gomory . ^{[ 8 ]}

Ejemplo : supongamos que hay 31 artículos de tamaño 3 y 7 artículos de tamaño 4, y el tamaño del contenedor es 10. Las configuraciones son: 4, 44, 34, 334, 3, 33, 333. Las restricciones son [0,0,1,2,1,2,3]* x =31 y [1,2,1,1,0,0,0]* x =7. Una solución óptima para el LP fraccional es [0,0,0,7,0,0,17/3]. Es decir: hay 7 contenedores de configuración 334 y 17/3 contenedores de configuración 333. Nótese que solo se necesitan dos configuraciones diferentes.

En resumen, el problema de programación lineal fraccionaria se puede escribir de la siguiente manera:

minimizar $~\mathbf {1} \cdot \mathbf {x} ~$ calle $~\mathbf {A} \mathbf {x} \geq \mathbf {n} ~$ y $~\mathbf {x} \geq 0~$

Donde 1 es el vector (1,...,1) de tamaño C , A es una matriz S por C en la que cada columna representa una única configuración, y n es el vector ( n ₁ ,..., n _S ).

Resolución del problema de programación lineal fraccionaria

Un programa lineal sin restricciones de integralidad puede resolverse en tiempo polinomial respecto del número de variables y restricciones. El problema radica en que el número de variables en el programa lineal de configuración fraccionaria es igual al número de configuraciones posibles, que puede ser enorme. Karmarkar y Karp ^{[ 9 ]} presentan un algoritmo que supera este problema.

Primero, construyen el programa lineal dual del LP fraccional:

maximizar $~\mathbf {n} \cdot \mathbf {y} ~$ calle $~A^{T}\mathbf {y} \leq \mathbf {1} ~$ y $~\mathbf {y} \geq 0$ .

Tiene S variables y ₁ ,..., y _S , y C restricciones: para cada configuración c , hay una restricción $A^{c}\cdot y\leq 1$ , dónde $A^{c}$ es la columna de A que representa la configuración c . 3Tiene la siguiente interpretación económica. ^{[ 9 ]} Para cada tamaño s , debemos determinar un precio no negativo y _s . Nuestra ganancia es el precio total de todos los artículos. Queremos maximizar la ganancia n y sujeta a las restricciones de que el precio total de los artículos en cada configuración sea como máximo 1.

En segundo lugar, aplican una variante del método del elipsoide , que no necesita enumerar todas las restricciones; solo necesita un oráculo de separación . Un oráculo de separación es un algoritmo que, dado un vector y , afirma que es factible o encuentra una restricción que viola. El oráculo de separación para el problema de programación lineal dual se puede implementar resolviendo el problema de la mochila con tamaños s y valores y : si la solución óptima del problema de la mochila tiene un valor total como máximo 1, entonces y es factible; si es mayor que 1, entonces y no es factible, y la solución óptima del problema de la mochila identifica una configuración para la cual se viola la restricción.

En tercer lugar, muestran que, con una solución aproximada al problema de la mochila, se puede obtener una solución aproximada al problema de programación lineal dual y, a partir de esta, una solución aproximada al problema de programación lineal primal; véase Algoritmos de empaquetamiento de contenedores de Karmarkar-Karp .

En resumen, para cualquier factor de tolerancia h , encuentra una solución básica factible con un coste máximo de LOPT(I) + h y se ejecuta en tiempo:

$O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ,

donde S es el número de tamaños diferentes, n es el número de elementos diferentes y el tamaño del elemento más pequeño es eB . En particular, si e ≥ 1/ n y h = 1, el algoritmo encuentra una solución con como máximo LOPT+1 contenedores en tiempo: $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ Una variante aleatoria de este algoritmo se ejecuta en el tiempo esperado:

$O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ .

Redondeo de la fracción LP

Karmarkar y Karp desarrollaron aún más una forma de redondear el LP fraccional a una solución aproximada del LP integral; véase Karmarkar-Karp bin packing algorithms . Su demostración muestra que la brecha de integralidad aditiva de este LP está en O(log ² ( n )). Posteriormente, Hoberg y Rothvoss ^{[ 10 ]} mejoraron su resultado y demostraron que la brecha de integralidad está en O(log( n )). La mejor cota inferior conocida para la brecha de integralidad es una constante Ω(1). Encontrar la brecha de integralidad exacta es un problema abierto .

En la cubierta del contenedor

En el problema de cubrir contenedores , hay n artículos de diferentes tamaños. El objetivo es colocar los artículos en el mayor número posible de contenedores, de manera que cada contenedor contenga al menos B artículos . Una configuración natural de programación lineal para este problema podría ser:

${\text{maximizar}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{con}}~~A\mathbf {x} \leq \mathbf {n} ~~~{\text{y}}~~\mathbf {x} \geq 0$

donde A representa todas las configuraciones de elementos con suma al menos B (solo se pueden tomar las configuraciones mínimas de inclusión). El problema con este LP es que, en el problema de cobertura de contenedores, manejar elementos pequeños es problemático, ya que los elementos pequeños pueden ser esenciales para la solución óptima. Si se permiten elementos pequeños, el número de configuraciones puede ser demasiado grande incluso para la técnica de Karmarkar y Karp. Csirik, Johnson y Kenyon ^{[ 11 ]} presentan un LP alternativo. Primero, definen un conjunto de elementos que se denominan pequeños . Sea T el tamaño total de todos los elementos pequeños. Luego, construyen una matriz A que representa todas las configuraciones con suma < 2. Luego, consideran el LP anterior con una restricción adicional: ${\text{maximizar}}~~\mathbf {1} \cdot \mathbf {x} ~~{\text{st}}$ $A\mathbf {x} \leq \mathbf {n}$ $\sum _{c\in C:sum(c)<B}(B-sum(c))\cdot x_{c}\leq T$ $\mathbf {x} \geq 0$ La restricción adicional garantiza que el "espacio vacío" en los contenedores pueda llenarse con los objetos pequeños. El dual de este LP es más complejo y no puede resolverse con un oráculo de separación simple del problema de la mochila. Csirik, Johnson y Kenyon ^{[ 11 ]} presentan un método diferente para resolverlo aproximadamente en tiempo exponencial en 1/epsilon. Jansen y Solis-Oba ^{[ 12 ]} presentan un método mejorado para resolverlo aproximadamente en tiempo exponencial en 1/epsilon.

En la programación de máquinas

En el problema de la programación de máquinas no relacionadas , existen m máquinas diferentes que deben procesar n trabajos distintos. Cuando la máquina i procesa el trabajo j , tarda un tiempo p _i_{, j} . El objetivo es distribuir los trabajos entre las máquinas de manera que el tiempo máximo de finalización de cada máquina sea lo más pequeño posible. La versión de decisión de este problema es: dado un tiempo T , ¿existe una distribución en la que el tiempo de finalización de todas las máquinas sea como máximo T ?

Para cada máquina i , existen un número finito de subconjuntos de trabajos que pueden ser procesados por la máquina i en un tiempo máximo T. Cada uno de estos subconjuntos se denomina configuración para la máquina i . Denotemos por C _i ( T ) el conjunto de todas las configuraciones para la máquina i , dado el tiempo T. Para cada máquina i y configuración c en C _i ( T ), definamos una variable $x_{i,c}$ que es igual a 1 si y solo si la configuración real utilizada en la máquina i es c , y 0 en caso contrario. Entonces, las restricciones LP son:

$\sum _{c\in C_{i}(T)}x_{i,c}=1$ para cada máquina i en 1,..., m;
$\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ para cada trabajo j en 1,..., n;
$x_{i,j}\in \{0,1\}$ para cada i , j .

Propiedades

La brecha de integralidad del LP de configuración para la programación de máquinas no relacionadas es 2. ^{[ 5 ]}

Véase también

Empaquetamiento de contenedores de alta multiplicidad

Referencias

^ Eisemann, Kurt (1 de abril de 1957). "El problema del recorte" . Ciencias de la gestión . 3 (3): 279– 284. doi : 10.1287/mnsc.3.3.279 . ISSN 0025-1909 .
1 2 Gilmore, PC; Gomory, RE (1961). "Un enfoque de programación lineal para el problema de corte de materiales". Operations Research . 9 (6): 849– 859. doi : 10.1287/opre.9.6.849 . JSTOR 167051 . S2CID 8079477 .
↑ Karmarkar, Narendra; Karp, Richard M. (1982-11-01). "Un esquema de aproximación eficiente para el problema de empaquetamiento de contenedores unidimensional". 23.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1982) . pp. 312–320 . doi : 10.1109/SFCS.1982.61 . S2CID 18583908 .
↑ Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim (1 de octubre de 2006). «Algoritmos de aproximación mejorados para problemas de empaquetamiento de contenedores multidimensionales». 47.º Simposio Anual IEEE sobre Fundamentos de la Informática (FOCS'06) de 2006. págs. 697–708 . doi : 10.1109/FOCS.2006.38 . ISBN 0-7695-2720-5. S2CID 7690347 .
1 2 Verschae, José; Wiese, Andreas (2014-08-01). "Sobre la configuración-LP para la planificación en máquinas no relacionadas" . Journal of Scheduling . 17 (4): 371– 383. arXiv : 1011.4957 . doi : 10.1007/s10951-013-0359-4 . ISSN 1099-1425 . S2CID 34229676 .
↑ Knop, Dušan; Koutecký, Martín (4 de marzo de 2020). "Programación de kernels mediante configuración LP". arXiv : 2003.02187 [ cs.DS ].
1 2 Claire Mathieu. "Algoritmos de aproximación, parte I, semana 3: empaquetamiento de contenedores" . Coursera . Archivado del original el 15 de julio de 2021.
↑ Rothvoß, T. (1 de octubre de 2013). "Aproximación del empaquetamiento de contenedores con O(log OPT · Log Log OPT) contenedores". Simposio anual IEEE 54.º sobre fundamentos de la informática de 2013. pp. 20–29 . arXiv : 1301.4010 . doi : 10.1109/FOCS.2013.11 . ISBN 978-0-7695-5135-7. S2CID 15905063 .
1 2 Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de contenedores unidimensional" . 23.º Simposio Anual sobre Fundamentos de la Informática (SFCS 1982) . págs. 312–320 . doi : 10.1109/SFCS.1982.61 . S2CID 18583908 .
↑ Hoberg, Rebecca; Rothvoss, Thomas (2017). «Una brecha de integralidad aditiva logarítmica para el problema de empaquetamiento de contenedores». Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 2616–2625 . doi : 10.1137/1.9781611974782.172 . ISBN 978-1-61197-478-2. S2CID 1647463 .
1 2 Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Mejores algoritmos de aproximación para la cobertura de contenedores" . SODA '01: Actas del duodécimo simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 557–566 . ISBN 978-0-89871-490-6.
↑ Jansen, Klaus; Solis-Oba, Roberto (21 de noviembre de 2002). "Un esquema de aproximación asintótica totalmente polinomial para la cobertura de contenedores" . Algoritmos y computación . Notas de clase en ciencias de la computación. Vol. 2518. Springer-Verlag. págs. 175–186 . doi : 10.1007/3-540-36136-7_16 . ISBN 978-3-540-00142-3.