En optimización matemática , el algoritmo entrecruzado es cualquiera de una familia de algoritmos para programación lineal . Las variantes del algoritmo entrecruzado también resuelven problemas más generales con restricciones de desigualdad lineal y funciones objetivo no lineales ; existen algoritmos entrecruzados para problemas de programación lineal-fraccional , [1] [2] problemas de programación cuadrática y problemas de complementariedad lineal . [3]
Al igual que el algoritmo simplex de George B. Dantzig , el algoritmo entrecruzado no es un algoritmo de tiempo polinomial para programación lineal. Ambos algoritmos visitan todas las esquinas 2D de un cubo (perturbado) en la dimensión D , el cubo de Klee-Minty (después de Victor Klee y George J. Minty ), en el peor de los casos . [4] [5] Sin embargo, cuando se inicia en una esquina aleatoria, el algoritmo entrecruzado visita en promedio solo D esquinas adicionales. [6] [7] [8] Así, para el cubo tridimensional, el algoritmo visita las 8 esquinas en el peor de los casos y exactamente 3 esquinas adicionales en promedio.
El algoritmo entrecruzado fue publicado de forma independiente por Tamas Terlaky [9] y por Zhe-Min Wang; [10] algoritmos relacionados aparecieron en informes no publicados de otros autores. [3]
En programación lineal, el algoritmo entrecruzado pivota entre una secuencia de bases pero difiere del algoritmo simplex . El algoritmo simplex primero encuentra una base (primal) factible resolviendo un " problema de fase uno "; en la "fase dos", el algoritmo simplex pivota entre una secuencia de soluciones básicas factibles de modo que la función objetivo no decrece con cada pivote, terminando con una solución óptima (y finalmente encontrando una solución "doble factible"). [3] [11]
El algoritmo entrecruzado es más simple que el algoritmo simplex, porque el algoritmo entrecruzado solo tiene una fase. Sus reglas pivotantes son similares a la regla pivotante de índice mínimo de Bland . [12] La regla de Bland utiliza sólo signos de coeficientes en lugar de su orden (número real) al decidir los pivotes elegibles. La regla de Bland selecciona variables entrantes comparando valores de costos reducidos, utilizando el orden de números reales de los pivotes elegibles. [12] [13] A diferencia de la regla de Bland, el algoritmo entrecruzado es "puramente combinatorio", seleccionando una variable entrante y una variable saliente considerando sólo los signos de los coeficientes en lugar de su orden en números reales. [3] [11] El algoritmo entrecruzado se ha aplicado para proporcionar pruebas constructivas de resultados básicos en álgebra lineal , como el lema de Farkas . [14]
Si bien la mayoría de las variantes simplex son monótonas en el objetivo (estrictamente en el caso no degenerado), la mayoría de las variantes del algoritmo entrecruzado carecen de una función de mérito monótona, lo que puede ser una desventaja en la práctica.
El algoritmo entrecruzado funciona en un cuadro dinámico estándar (o partes calculadas sobre la marcha de un cuadro, si se implementa como el método simplex revisado). En un paso general, si el cuadro es primario o dual inviable, selecciona una de las filas/columnas inviables como fila/columna dinámica utilizando una regla de selección de índice. Una propiedad importante es que la selección se realiza sobre la unión de los índices no factibles y la versión estándar del algoritmo no distingue índices de columnas y filas (es decir, los índices de columnas básicos en las filas). Si se selecciona una fila, el algoritmo utiliza la regla de selección de índice para identificar una posición para un pivote de tipo dual, mientras que si se selecciona una columna, utiliza la regla de selección de índice para encontrar una posición de fila y realiza un pivote de tipo primario.
La complejidad temporal de un algoritmo cuenta el número de operaciones aritméticas suficientes para que el algoritmo resuelva el problema. Por ejemplo, la eliminación gaussiana requiere del orden de D 3 operaciones, por lo que se dice que tiene complejidad temporal polinómica, porque su complejidad está limitada por un polinomio cúbico . Hay ejemplos de algoritmos que no tienen complejidad de tiempo polinomial. Por ejemplo, una generalización de la eliminación gaussiana llamada algoritmo de Buchberger tiene por su complejidad una función exponencial de los datos del problema (el grado de los polinomios y el número de variables de los polinomios multivariados ). Debido a que las funciones exponenciales eventualmente crecen mucho más rápido que las funciones polinómicas, una complejidad exponencial implica que un algoritmo tiene un rendimiento lento en problemas grandes.
Varios algoritmos para programación lineal ( el algoritmo elipsoidal de Khachiyan , el algoritmo proyectivo de Karmarkar y los algoritmos de ruta central) tienen complejidad temporal polinómica (en el peor de los casos y, por tanto, en promedio ). Los algoritmos elipsoidal y proyectivo se publicaron antes que el algoritmo entrecruzado.
Sin embargo, al igual que el algoritmo simplex de Dantzig, el algoritmo entrecruzado no es un algoritmo de tiempo polinomial para programación lineal. El algoritmo entrecruzado de Terlaky visita todas las esquinas 2 D de un cubo (perturbado) en dimensión D , según un artículo de Roos; El artículo de Roos modifica la construcción de Klee -Minty de un cubo en el que el algoritmo simplex toma pasos 2 D. [3] [4] [5] Al igual que el algoritmo simplex, el algoritmo entrecruzado visita las 8 esquinas del cubo tridimensional en el peor de los casos.
Sin embargo , cuando se inicializa en una esquina aleatoria del cubo, el algoritmo entrecruzado visita sólo D esquinas adicionales, según un artículo de 1994 de Fukuda y Namiki. [6] [7] Trivialmente, el algoritmo simplex toma en promedio D pasos para un cubo. [8] [15] Al igual que el algoritmo simplex, el algoritmo entrecruzado visita exactamente 3 esquinas adicionales del cubo tridimensional en promedio.
El algoritmo entrecruzado se ha ampliado para resolver problemas más generales que los problemas de programación lineal.
Existen variantes del algoritmo entrecruzado para programación lineal, para programación cuadrática y para el problema de complementariedad lineal con "matrices suficientes"; [3] [6] [16] [17] [18] [19] por el contrario, para problemas de complementariedad lineal, el algoritmo entrecruzado termina finitamente sólo si la matriz es una matriz suficiente. [18] [19] Una matriz suficiente es una generalización tanto de una matriz definida positiva como de una matriz P , cuyos menores principales son cada uno de ellos positivos. [18] [19] [20] El algoritmo entrecruzado ha sido adaptado también para programación lineal-fraccional . [1] [2]
El algoritmo entrecruzado se utilizó en un algoritmo para enumerar todos los vértices de un politopo , que fue publicado por David Avis y Komei Fukuda en 1992. [21] Avis y Fukuda presentaron un algoritmo que encuentra los v vértices de un poliedro definido por un sistema no degenerado de n desigualdades lineales en D dimensiones (o, dualmente, las v facetas del casco convexo de n puntos en D dimensiones, donde cada faceta contiene exactamente D puntos dados) en el tiempo O ( nDv ) y el espacio O ( nD ) . [22]
El algoritmo entrecruzado a menudo se estudia utilizando la teoría de matroides orientadas (OM), que es una abstracción combinatoria de la teoría de la optimización lineal. [17] [23] De hecho, la regla de pivote de Bland se basó en sus artículos anteriores sobre la teoría de las matroides orientadas. Sin embargo, la regla de Bland muestra ciclos en algunos problemas de programación lineal matroide orientada. [17] El primer algoritmo puramente combinatorio para programación lineal fue ideado por Michael J. Todd. [17] [24] El algoritmo de Todd se desarrolló no sólo para la programación lineal en el entorno de matroides orientadas, sino también para problemas de programación cuadrática y problemas de complementariedad lineal . [17] [24] Desafortunadamente, el algoritmo de Todd es complicado incluso de enunciar, y sus pruebas de convergencia finita son algo complicadas. [17]
El algoritmo entrecruzado y su prueba de terminación finita se pueden expresar de manera simple y ampliar fácilmente la configuración de matroides orientadas. El algoritmo puede simplificarse aún más para problemas de viabilidad lineal , es decir, para sistemas lineales con variables no negativas ; Estos problemas se pueden formular para matroides orientadas. [14] El algoritmo entrecruzado se ha adaptado para problemas que son más complicados que la programación lineal: existen variantes de matroide orientada también para el problema de programación cuadrática y para el problema de complementariedad lineal. [3] [16] [17]
El algoritmo entrecruzado es un algoritmo simple para programación lineal. Fue el segundo algoritmo totalmente combinatorio para programación lineal. El algoritmo simplex parcialmente combinatorio de ciclos de Bland en algunas matroides orientadas (no realizables). Todd publicó el primer algoritmo completamente combinatorio, y también es como el algoritmo simplex en que preserva la viabilidad después de que se genera la primera base factible; sin embargo, el gobierno de Todd es complicado. El algoritmo entrecruzado no es un algoritmo simplex, porque no necesita mantener la viabilidad. Sin embargo, el algoritmo entrecruzado no tiene complejidad temporal polinomial.
Los investigadores han ampliado el algoritmo entrecruzado para muchos problemas de optimización, incluida la programación lineal-fraccional. El algoritmo entrecruzado puede resolver problemas de programación cuadrática y problemas de complementariedad lineal, incluso en el entorno de matroides orientadas. Incluso cuando se generaliza, el algoritmo entrecruzado sigue siendo simplemente enunciado.
Rockafellar, RT (1969). "Los vectores elementales de un subespacio de R N {\displaystyle R^{N}} (1967)" (PDF) . En RC Bose y TA Dowling (ed.). Matemática Combinatoria y sus Aplicaciones . Serie de monografías sobre probabilidad y estadística de la Universidad de Carolina del Norte. Chapel Hill, Carolina del Norte: Prensa de la Universidad de Carolina del Norte. págs. 104-127. SEÑOR 0278972. Reimpresión en PDF.
Rockafellar fue influenciado por los estudios anteriores de Albert W. Tucker y George J. Minty . Tucker y Minty habían estudiado los patrones de signos de las matrices que surgen a través de las operaciones de pivote del algoritmo simplex de Dantzig.