En optimización matemática , el algoritmo criss-cross es uno de los algoritmos de una familia de algoritmos para programación lineal . Las variantes del algoritmo criss-cross también resuelven problemas más generales con restricciones de desigualdad lineal y funciones objetivo no lineales ; existen algoritmos criss-cross 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 criss-cross no es un algoritmo de tiempo polinomial para programación lineal. Ambos algoritmos visitan las 2 D esquinas de un cubo (perturbado) de dimensión D , el cubo de Klee-Minty (según 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 criss-cross visita en promedio solo D esquinas adicionales. [6] [ 7] [8] Por lo tanto, 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 criss-cross fue publicado independientemente 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 criss-cross pivotea entre una secuencia de bases, pero difiere del algoritmo símplex . El algoritmo símplex primero encuentra una base factible (primal) resolviendo un " problema de fase uno "; en la "fase dos", el algoritmo símplex pivotea entre una secuencia de soluciones factibles básicas de modo que la función objetivo no decrezca con cada pivote, terminando con una solución óptima (también encuentra finalmente una solución "factible dual"). [3] [11]
El algoritmo criss-cross es más simple que el algoritmo simplex, porque el algoritmo criss-cross solo tiene una fase. Sus reglas de pivoteo son similares a la regla de pivoteo de índice mínimo de Bland . [12] La regla de Bland usa solo los signos de los coeficientes en lugar de su orden (en números reales) al decidir los pivotes elegibles. La regla de Bland selecciona una variable entrante comparando valores de costos reducidos, usando el orden de números reales de los pivotes elegibles. [12] [13] A diferencia de la regla de Bland, el algoritmo criss-cross es "puramente combinatorio", seleccionando una variable entrante y una variable saliente considerando solo los signos de los coeficientes en lugar de su orden de números reales. [3] [11] El algoritmo criss-cross 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 criss-cross carecen de una función de mérito monótona, lo que puede ser una desventaja en la práctica.
El algoritmo criss-cross funciona en una tabla dinámica estándar (o en partes calculadas sobre la marcha de una tabla, si se implementa como el método simplex revisado). En un paso general, si la tabla es inviable primaria o dual, selecciona una de las filas/columnas inviables como la fila/columna dinámica utilizando una regla de selección de índice. Una propiedad importante es que la selección se realiza en la unión de los índices inviables y la versión estándar del algoritmo no distingue entre índices de columna y fila (es decir, los índices de columna 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 una dinámica 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 una dinámica de tipo primaria.
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, y por eso 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 temporal polinómica. Por ejemplo, una generalización de la eliminación gaussiana llamada algoritmo de Buchberger tiene como 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 desempeño lento en problemas grandes.
Varios algoritmos de programación lineal ( el algoritmo elipsoidal de Khachiyan , el algoritmo proyectivo de Karmarkar y los algoritmos de trayectoria central ) tienen una complejidad temporal polinómica (en el peor de los casos y, por lo tanto, en promedio ). Los algoritmos elipsoidal y proyectivo se publicaron antes del algoritmo criss-cross.
Sin embargo, al igual que el algoritmo simplex de Dantzig, el algoritmo criss-cross no es un algoritmo de tiempo polinomial para programación lineal. El algoritmo criss-cross de Terlaky visita todas las 2 esquinas 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 realiza 2 pasos D. [3] [4] [5] Al igual que el algoritmo simplex, el algoritmo criss-cross visita las 8 esquinas del cubo tridimensional en el peor de los casos.
Cuando se inicializa en una esquina aleatoria del cubo, el algoritmo criss-cross visita solo D esquinas adicionales, sin embargo, 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 criss-cross visita exactamente 3 esquinas adicionales del cubo tridimensional en promedio.
El algoritmo criss-cross se ha ampliado para resolver problemas más generales que los problemas de programación lineal.
Existen variantes del algoritmo criss-cross 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 criss-cross termina finitamente solo 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 positivos. [18] [19] [20] El algoritmo criss-cross se ha adaptado también para programación lineal-fraccional . [1] [2]
El algoritmo criss-cross 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 de la envoltura convexa 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 criss-cross se estudia a menudo utilizando la teoría de matroides orientadas (OMs), que es una abstracción combinatoria de la teoría de 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 matroides orientadas. Sin embargo, la regla de Bland exhibe ciclado en algunos problemas de programación lineal de matroides orientadas. [17] El primer algoritmo puramente combinatorio para programación lineal fue ideado por Michael J. Todd. [17] [24] El algoritmo de Todd fue desarrollado no solo para programación lineal en el contexto de matroides orientadas, sino también para problemas de programación cuadrática y problemas de complementariedad lineal . [17] [24] El algoritmo de Todd es complicado incluso de enunciar, desafortunadamente, y sus pruebas de convergencia finita son algo complicadas. [17]
El algoritmo criss-cross y su prueba de terminación finita se pueden enunciar de manera sencilla y extender fácilmente el contexto de los matroides orientados. El algoritmo se puede simplificar 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 orientados. [14] El algoritmo criss-cross se ha adaptado para problemas que son más complicados que la programación lineal: también hay variantes de matroides orientados para el problema de programación cuadrática y para el problema de complementariedad lineal. [3] [16] [17]
El algoritmo criss-cross es un algoritmo de programación lineal en términos simples. Fue el segundo algoritmo completamente combinatorio para programación lineal. El algoritmo símplex parcialmente combinatorio de Bland realiza ciclos en algunos matroides orientados (no realizables). El primer algoritmo completamente combinatorio fue publicado por Todd, y también es como el algoritmo símplex en el sentido de que preserva la viabilidad después de que se genera la primera base factible; sin embargo, la regla de Todd es complicada. El algoritmo criss-cross no es un algoritmo similar al símplex, porque no necesita mantener la viabilidad. Sin embargo, el algoritmo criss-cross no tiene complejidad temporal polinómica.
Los investigadores han extendido el algoritmo criss-cross a muchos problemas de optimización, incluida la programación lineal-fraccional. El algoritmo criss-cross puede resolver problemas de programación cuadrática y problemas de complementariedad lineal, incluso en el contexto de matroides orientadas. Incluso cuando se generaliza, el algoritmo criss-cross sigue siendo simple.
Rockafellar, RT (1969). "Los vectores elementales de un subespacio de R N {\displaystyle R^{N}} (1967)" (PDF) . En RC Bose y TA Dowling (ed.). Combinatorial Mathematics and its Applications . The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, Carolina del Norte: University of North Carolina Press. págs. 104–127. MR 0278972. Reimpresión en PDF.
Rockafellar se vio 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 surgían a través de las operaciones de pivoteo del algoritmo simplex de Dantzig.