En el estudio de algoritmos , un problema de tipo LP (también llamado programa lineal generalizado ) es un problema de optimización que comparte ciertas propiedades con programas lineales de baja dimensión y que puede resolverse mediante algoritmos similares. Los problemas de tipo LP incluyen muchos problemas de optimización importantes que no son en sí mismos programas lineales, como el problema de encontrar el círculo más pequeño que contiene un conjunto dado de puntos planos. Pueden resolverse mediante una combinación de algoritmos aleatorios en un período de tiempo lineal en el número de elementos que definen el problema y subexponencial en la dimensión del problema.
Los problemas de tipo LP fueron definidos por Sharir y Welzl (1992) como problemas en los que se da como entrada un conjunto finito S de elementos y una función f que asigna subconjuntos de S a valores de un conjunto totalmente ordenado. Se requiere que la función cumpla dos propiedades clave:
Una base de un problema de tipo LP es un conjunto B ⊆ S con la propiedad de que cada subconjunto propio de B tiene un valor de f menor que el propio B , y la dimensión (o dimensión combinatoria ) de un problema de tipo LP se define como ser la cardinalidad máxima de una base.
Se supone que un algoritmo de optimización puede evaluar la función f sólo en conjuntos que son en sí mismos bases o que se forman añadiendo un solo elemento a una base. Alternativamente, el algoritmo puede restringirse a dos operaciones primitivas: una prueba de violación que determina, para una base B y un elemento x, si f ( B ) = f ( B ∪ { x } ) , y un cálculo de base que (con el mismo entradas) encuentra una base de B ∪ { x }. La tarea que debe realizar el algoritmo es evaluar f ( S ) utilizando únicamente estas evaluaciones restringidas o primitivas.
Un programa lineal puede definirse mediante un sistema de d variables reales no negativas , sujetas a n restricciones de desigualdad lineal, junto con una función objetivo lineal no negativa que debe minimizarse. Esto se puede colocar en el marco de los problemas de tipo LP dejando que S sea el conjunto de restricciones y definiendo f ( A ) (para un subconjunto A de las restricciones) como el valor mínimo de la función objetivo del programa lineal más pequeño definido por A . Con supuestos de posición generales adecuados (para evitar que múltiples puntos de solución tengan el mismo valor de función objetivo óptimo), esto satisface los requisitos de monotonicidad y localidad de un problema de tipo LP, y tiene una dimensión combinatoria igual al número d de variables. [1] De manera similar, un programa entero (que consta de una colección de restricciones lineales y una función objetivo lineal, como en un programa lineal, pero con la restricción adicional de que las variables deben tomar solo valores enteros) satisface las propiedades de monotonicidad y localidad. de un problema tipo LP, con los mismos supuestos de posición generales que para los programas lineales. Los teoremas de Bell (1977) y Bufanda (1977) muestran que, para un programa entero con d variables, la dimensión combinatoria es como máximo 2 d . [1]
Muchos problemas de optimización natural en geometría computacional son de tipo LP:
Los problemas de tipo LP también se han utilizado para determinar los resultados óptimos de ciertos juegos en la teoría algorítmica de juegos , [11] mejorar la ubicación de los vértices en mallas de métodos de elementos finitos , [12] resolver problemas de ubicación de instalaciones , [13] analizar la complejidad temporal de ciertos algoritmos de búsqueda de tiempo exponencial, [14] y reconstruir las posiciones tridimensionales de objetos a partir de sus imágenes bidimensionales. [15]
Seidel (1991) proporcionó un algoritmo para programación lineal de baja dimensión que puede adaptarse al marco de problemas de tipo LP. El algoritmo de Seidel toma como entrada el conjunto S y un conjunto separado X (inicialmente vacío) de elementos que se sabe que pertenecen a la base óptima. Luego considera los elementos restantes uno por uno en un orden aleatorio, realizando pruebas de violación para cada uno y, dependiendo del resultado, realizando una llamada recursiva al mismo algoritmo con un conjunto más grande de elementos básicos conocidos. Puede expresarse con el siguiente pseudocódigo:
la función seidel( S , f , X ) es R := conjunto vacío B := X para x en una permutación aleatoria de S : si f ( B ) ≠ f ( B ∪ { x }): B := seidel( R , f , X ∪ { x }) R := R ∪ { x } devolver BEn un problema con dimensión combinatoria d , la prueba de violación en la i -ésima iteración del algoritmo falla solo cuando x es uno de los d − | X | elementos básicos restantes, lo que ocurre con probabilidad como máximo ( d − | X |)/ i . Con base en este cálculo, se puede demostrar que, en general, el número esperado de pruebas de infracción realizadas por el algoritmo es O( d ! n) , lineal en n pero peor que exponencial en d .
Clarkson (1995) define dos algoritmos, un algoritmo recursivo y un algoritmo iterativo, para programación lineal basada en técnicas de muestreo aleatorio, y sugiere una combinación de los dos que llama al algoritmo iterativo a partir del algoritmo recursivo. El algoritmo recursivo elige repetidamente muestras aleatorias cuyo tamaño sea aproximadamente la raíz cuadrada del tamaño de entrada, resuelve el problema muestreado de forma recursiva y luego utiliza pruebas de violación para encontrar un subconjunto de los elementos restantes que deben incluir al menos un elemento base:
la función recursiva ( S , f ) es X := conjunto vacío repetir R := un subconjunto aleatorio de S con tamaño d√n B := base para R ∪ X , calculado recursivamente V := { x | f ( B ) ≠ f ( B ∪ { x })} X := X ∪ V hasta que V esté vacío, devuelve BEn cada iteración, el tamaño esperado de V es O( √ n ) , [16] y siempre que V no esté vacío incluye al menos un nuevo elemento de la base eventual de S. Por lo tanto, el algoritmo realiza como máximo iteraciones , cada una de las cuales realiza n pruebas de violación y realiza una única llamada recursiva a un subproblema de tamaño O( d √ n ) .
El algoritmo iterativo de Clarkson asigna pesos a cada elemento de S , inicialmente todos iguales. Luego elige un conjunto R de 9 d 2 elementos de S al azar y calcula los conjuntos B y V como en el algoritmo anterior. Si el peso total de V es como máximo 2/(9 d − 1) veces el peso total de S (como sucede con probabilidad constante), entonces el algoritmo duplica los pesos de cada elemento de V y, como antes, repite este proceso hasta V queda vacío. En cada iteración, se puede demostrar que el peso de la base óptima aumenta a un ritmo mayor que el peso total de S , de lo que se deduce que el algoritmo debe terminar dentro de O(log n ) iteraciones.
Al utilizar el algoritmo recursivo para resolver un problema dado, cambiar al algoritmo iterativo para sus llamadas recursivas y luego cambiar nuevamente al algoritmo de Seidel para las llamadas realizadas por el algoritmo iterativo, es posible resolver un problema de tipo LP determinado usando O( dn + d ! d O(1) log n ) pruebas de violación.
Cuando se aplica a un programa lineal, este algoritmo puede interpretarse como un método simplex dual . [17] Con ciertas primitivas computacionales adicionales más allá de la prueba de violación y las primitivas de cálculo de base, este método puede volverse determinista. [18]
Matoušek, Sharir y Welzl (1996) describen un algoritmo que utiliza una propiedad adicional de los programas lineales que no siempre se cumple en otros problemas de tipo LP: que todas las bases tienen la misma cardinalidad entre sí. Si un problema de tipo LP no tiene esta propiedad, se puede hacer que la tenga agregando d nuevos elementos ficticios y modificando la función f para que devuelva el par ordenado de su antiguo valor f ( A ) y del número min( d ,| A |) , ordenados lexicográficamente .
En lugar de agregar elementos de S uno a la vez, o encontrar muestras de los elementos, Matoušek, Sharir y Welzl (1996) describen un algoritmo que elimina elementos uno por uno. En cada paso mantiene una base C que inicialmente puede ser el conjunto de elementos ficticios. Puede describirse con el siguiente pseudocódigo:
la función msw( S , f , C ) es si S = C entonces devuelve C elige un elemento aleatorio x de S \ C B = msw( S \ x , f , C ) si f ( B ) ≠ f(B ∪ {x }) entonces B := base( B ∪ { x }) B := msw( S , f , B ) devuelve BEn la mayoría de las llamadas recursivas del algoritmo, la prueba de infracción tiene éxito y se omite la declaración if. Sin embargo, con una pequeña probabilidad la prueba de violación falla y el algoritmo realiza un cálculo de base adicional y luego una llamada recursiva adicional. Como muestran los autores, el tiempo esperado para el algoritmo es lineal en n y exponencial en la raíz cuadrada de d log n . Al combinar este método con los procedimientos recursivos e iterativos de Clarkson, estas dos formas de dependencia del tiempo se pueden separar entre sí, lo que da como resultado un algoritmo que realiza pruebas de violación O( dn ) en el algoritmo recursivo externo y un número exponencial en el raíz cuadrada de d log d en los niveles inferiores del algoritmo. [19]
Matoušek (1995) considera una variación de los problemas de optimización de tipo LP en los que se da, junto con el conjunto S y la función objetivo f , un número k ; la tarea es eliminar k elementos de S para que la función objetivo en el conjunto restante sea lo más pequeña posible. Por ejemplo, cuando se aplica al problema del círculo más pequeño, esto daría como resultado el círculo más pequeño que contiene todos menos k de un conjunto dado de puntos planos. Muestra que, para todos los problemas de tipo LP no degenerados (es decir, problemas en los que todas las bases tienen valores distintos), este problema puede resolverse en el tiempo O( nk d ) , resolviendo un conjunto de O( k d ) LP. Problemas de tipo definidos por subconjuntos de S .
Algunos problemas de optimización geométrica pueden expresarse como problemas de tipo LP en los que el número de elementos en la formulación de tipo LP es significativamente mayor que el número de valores de datos de entrada para el problema de optimización. Como ejemplo, considere un conjunto de n puntos en el plano, cada uno de los cuales se mueve con velocidad constante. En cualquier momento, el diámetro de este sistema es la distancia máxima entre dos de sus puntos. El problema de encontrar un tiempo en el que se minimiza el diámetro se puede formular como minimizar el máximo puntual de O ( n 2 ) funciones cuasiconvexas, una para cada par de puntos, midiendo la distancia euclidiana entre el par en función del tiempo. Por lo tanto, se puede resolver como un problema tipo LP de dimensión combinatoria dos en un conjunto de O( n 2 ) elementos, pero este conjunto es significativamente mayor que el número de puntos de entrada. [20]
Chan (2004) describe un algoritmo para resolver problemas de tipo LP implícitamente definidos como este en el que cada elemento de tipo LP está determinado por una k -tupla de valores de entrada, para alguna constante k . Para aplicar su enfoque, debe existir un algoritmo de decisión que pueda determinar, para una base B de tipo LP dada y un conjunto S de n valores de entrada, si B es una base para el problema de tipo LP determinado por S.
El algoritmo de Chan realiza los siguientes pasos:
Con el supuesto de que el algoritmo de decisión toma una cantidad de tiempo O( T ( n )) que crece al menos polinomialmente en función del tamaño de entrada n , Chan muestra que el umbral para cambiar a una formulación LP explícita y el número de subconjuntos en la partición se puede elegir de tal manera que el algoritmo de optimización implícito de tipo LP también se ejecute en el tiempo O( T ( n )) .
Por ejemplo, para el diámetro mínimo de puntos móviles, el algoritmo de decisión solo necesita calcular el diámetro de un conjunto de puntos en un tiempo fijo, un problema que puede resolverse en O( n log n ) tiempo utilizando la técnica de calibradores giratorios . Por lo tanto, el algoritmo de Chan para encontrar el tiempo en el que se minimiza el diámetro también requiere un tiempo O ( n log n ) . Chan usa este método para encontrar un punto de máxima profundidad de Tukey entre una colección dada de n puntos en d -espacio euclidiano dimensional, en el tiempo O( n d − 1 + n log n ) . Braß, Heinrich-Litan y Morin (2003) utilizaron una técnica similar para encontrar un punto de profundidad máxima de Tukey para la distribución uniforme en un polígono convexo.
El descubrimiento de algoritmos de tiempo lineal para programación lineal y la observación de que los mismos algoritmos podrían usarse en muchos casos para resolver problemas de optimización geométrica que no eran programas lineales se remonta al menos a Megiddo (1983, 1984), quien dio un tiempo lineal esperado. algoritmo para programas lineales de tres variables y el problema del círculo más pequeño. Sin embargo, Megiddo formuló la generalización de la programación lineal geométricamente en lugar de combinatoriamente, como un problema de optimización convexa más que como un problema abstracto sobre sistemas de conjuntos. De manera similar, Dyer (1986) y Clarkson (en la versión de la conferencia de 1988 de Clarkson 1995) observaron que sus métodos podían aplicarse tanto a programas convexos como a programas lineales. Dyer (1992) demostró que el problema del elipsoide envolvente mínimo también podría formularse como un problema de optimización convexo agregando un pequeño número de restricciones no lineales. Clarkson y Dyer & Frieze (1989) fueron pioneros en el uso de la aleatorización para mejorar los límites de tiempo para la programación lineal de baja dimensión y problemas relacionados.
La definición de problemas de tipo LP en términos de funciones que satisfacen los axiomas de localidad y monotonicidad proviene de Sharir y Welzl (1992), pero otros autores en el mismo período formularon generalizaciones combinatorias alternativas de programas lineales. Por ejemplo, en un marco desarrollado por Gärtner (1995), la función f se reemplaza por un ordenamiento total de los subconjuntos de S. Es posible romper los vínculos en un problema de tipo LP para crear un orden total, pero sólo a expensas de un aumento en la dimensión combinatoria. [21] Además, como en los problemas de tipo LP, Gärtner define ciertas primitivas para realizar cálculos en subconjuntos de elementos; sin embargo, su formalización no tiene analogía con la dimensión combinatoria.
Otra generalización abstracta tanto de los programas lineales como de los problemas de complementariedad lineal , formulada por Stickney y Watson (1978) y posteriormente estudiada por varios otros autores, se refiere a las orientaciones de los bordes de un hipercubo con la propiedad de que cada cara del hipercubo (incluido el hipercubo completo). como cara) tiene un fregadero único , un vértice sin aristas salientes. Una orientación de este tipo puede formarse a partir de un problema de tipo LP correspondiendo los subconjuntos de S con los vértices de un hipercubo de tal manera que dos subconjuntos difieran en un solo elemento si y sólo si los vértices correspondientes son adyacentes, y por orientando el borde entre conjuntos vecinos A ⊆ B hacia B si f ( A ) ≠ f ( B ) y hacia A en caso contrario. La orientación resultante tiene la propiedad adicional de que forma un gráfico acíclico dirigido , a partir del cual se puede demostrar que un algoritmo aleatorio puede encontrar el sumidero único de todo el hipercubo (la base óptima del problema de tipo LP) en varios pasos. exponencial en la raíz cuadrada de n . [22]
El marco de espacios infractores desarrollado más recientemente generaliza los problemas de tipo LP, en el sentido de que todo problema de tipo LP puede ser modelado por un espacio infractor, pero no necesariamente al revés. Los espacios violadores se definen de manera similar a los problemas de tipo LP, mediante una función f que asigna conjuntos a valores de funciones objetivas, pero los valores de f no están ordenados. A pesar de la falta de ordenamiento, cada conjunto S tiene un conjunto de bases bien definido (los conjuntos mínimos con el mismo valor que el conjunto completo) que se pueden encontrar mediante variaciones de los algoritmos de Clarkson para problemas de tipo LP. De hecho, se ha demostrado que los espacios infractores caracterizan exactamente los sistemas que pueden resolverse mediante los algoritmos de Clarkson. [23]
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ).