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 . Fue introducido en el contexto del problema de corte de stock . ^[1]^[2] Posteriormente, se ha aplicado al empaquetado de contenedores ^[3]^[4] y a los problemas de programación de trabajos . ^[5]^[6] En el programa lineal de configuración, 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 embalaje de contenedor

El LP integral

En el problema de empaquetado de contenedores , hay n artículos con 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 con una suma de como máximo B.

Ejemplo : ^[7] supongamos que los tamaños de los elementos 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 elementos de tamaño 3, entonces no podríamos usar la configuración 3333.

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

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

Entonces, la configuración LP del bin-packing es:

${\text{minimizar}}~~~\sum _{c\in C}x_{c}~~~{\text{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}\en \{0,\ldots ,n\}$ para todos los c en C (- hay como máximo n contenedores en total, por lo tanto, 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-hard. Además, incluso el problema en sí es generalmente muy grande: tiene C variables y S restricciones. Si el tamaño de 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 una 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 combinaciones para verificar. Para cada combinación, tenemos que verificar S restricciones, por lo que el tiempo de ejecución es , que es polinomial en n cuando S, e son constantes). ^[7] $n^{S^{1/e}}$ $S\cdot n^{S^{1/e}}$

Sin embargo, este ILP sirve como 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 es pequeña y e es grande, por lo que C es relativamente pequeña. Luego, el ILP se puede resolver ya sea mediante una búsqueda completa (si S , C son suficientemente pequeños), o relajándolo en un LP fraccionario .

El LP fraccionario

La configuración fraccionaria LP de bin-packing es la relajación de programación lineal del ILP anterior. Reemplaza la última restricción con la restricción . En otras palabras, cada configuración se puede utilizar un número fraccionario 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] $x_{c}\en \{0,\ldots ,n\}$ $estilo de visualización x_{c}\geq 0}$

Ejemplo : supongamos que hay 31 elementos de tamaño 3 y 7 elementos 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 fraccionario 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 LP fraccionario se puede escribir de la siguiente manera:

${\text{minimizar}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{st}}~~A\mathbf {x} \geq \mathbf {n} ~~~{\text{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 ).

Solución del PL fraccionario

Un programa lineal sin restricciones de integralidad se puede resolver en tiempo polinomial en el número de variables y restricciones. El problema es que el número de variables en la configuración fraccionaria LP 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 PL fraccionario:

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

Tiene S variables y ₁ ,..., y _S , y C restricciones: para cada configuración c , hay una restricción , donde 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 es como máximo 1. $A^{c}\cdot y\leq 1$ $Estilo de visualización A^{c}}$

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 LP 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 LP dual y, a partir de esto, una solución aproximada al LP primario; véase Algoritmos de empaquetamiento de contenedores de Karmarkar-Karp .

En resumen, para cualquier factor de tolerancia h , encuentra una solución factible básica de costo como máximo LOPT(I) + h , y se ejecuta en el 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 bins en el tiempo: . Una variante aleatoria de este algoritmo se ejecuta en el tiempo esperado: $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$

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

Redondeo del LP fraccionario

Karmarkar y Karp desarrollaron además una forma de redondear el LP fraccionario en una solución aproximada al LP integral; consulte los algoritmos de empaquetamiento de bins de Karmarkar-Karp . Su prueba muestra que la brecha de integralidad aditiva de este LP está en O(log ² ( n )). Más tarde, Hoberg y Rothvoss ^[10] mejoraron su resultado y demostraron que la brecha de integralidad está en O(log( n )). El límite inferior más conocido en 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 cubrimiento de contenedores , hay n elementos con diferentes tamaños. El objetivo es empacar los elementos en un número máximo de contenedores, donde cada contenedor debe contener al menos B. Una configuración natural de LP para este problema podría ser:

${\text{maximize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{s.t.}}~~A\mathbf {x} \leq \mathbf {n} ~~~{\text{and}}~~\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, el manejo de elementos pequeños es problemático, ya que los elementos pequeños pueden ser esenciales para la solución óptima. Con elementos pequeños permitidos, 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: La restricción adicional garantiza que el "espacio vacante" en los contenedores se puede llenar con los elementos pequeños. El dual de este LP es más complejo y no se puede resolver con un simple oráculo de separación 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. ${\text{maximize}}~~\mathbf {1} \cdot \mathbf {x} ~~{\text{s.t.}}$ $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$

En la programación de máquinas

En el problema de la programación de máquinas no relacionadas , hay algunas _m máquinas diferentes que deberían procesar algunos n trabajos diferentes. Cuando la máquina i procesa el trabajo j , lleva tiempo pi _{, j} . El objetivo es dividir los trabajos entre las máquinas de modo que el tiempo máximo de finalización de una máquina sea lo más pequeño posible. La versión de decisión de este problema es: dado el tiempo T , ¿existe una partición en la que el tiempo de finalización de todas las máquinas sea como máximo T ?

Para cada máquina i , hay un número finito de subconjuntos de trabajos que la máquina i puede procesar 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 que sea 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 de PL son: $x_{i,c}$

$\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 de la configuración-LP para la programación de máquinas no relacionadas es 2. ^[5]

Véase también

Empaquetado 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.
^ ab Gilmore, PC; Gomory, RE (1961). "Un enfoque de programación lineal para el problema del material de corte". Investigación de operaciones . 9 (6): 849–859. doi :10.1287/opre.9.6.849. JSTOR 167051. S2CID 8079477.
^ Karmarkar, Narendra; Karp, Richard M. (1 de noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de bins unidimensional". 23.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1982) : 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 bins 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 .
^ ab Verschae, José; Wiese, Andreas (1 de agosto de 2014). "Sobre el LP de configuración para la programació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].
^ por Claire Mathieu. "Algoritmos de aproximación, parte I, semana 3: empaquetamiento de contenedores". Coursera . Archivado desde el original el 15 de julio de 2021.
^ Rothvoß, T. (1 de octubre de 2013). "Aproximación del empaquetamiento de bins dentro de bins O(log OPT · Log Log OPT)". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . págs. 20–29. arXiv : 1301.4010 . doi :10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7.S2CID15905063 .
^ ab Karmarkar, Narendra; Karp, Richard M. (noviembre de 1982). "Un esquema de aproximación eficiente para el problema de empaquetamiento de bins unidimensional". 23.° Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1982) : 312–320. doi :10.1109/SFCS.1982.61. S2CID 18583908.
^ Hoberg, Rebecca; Rothvoss, Thomas (2017). "Una brecha de integralidad aditiva logarítmica para empaquetamiento de bins". 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.S2CID1647463 .
^ ab Csirik, Janos; Johnson, David S.; Kenyon, Claire (9 de enero de 2001). "Mejores algoritmos de aproximación para el cubrimiento de bins". 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 temporal totalmente polinomial asintótico para el cubrimiento de bins". Algoritmos y computación . Apuntes de clase en informática. Vol. 2518. Springer-Verlag. págs. 175–186. doi :10.1007/3-540-36136-7_16. ISBN . 978-3-540-00142-3.