La regla de Cunningham

En optimización matemática , la regla de Cunningham (también conocida como regla de los menos considerados recientemente o regla round-robin ) es un refinamiento algorítmico del método simplex para la optimización lineal .

La regla fue propuesta en 1979 por WH Cunningham para derrotar las construcciones de hipercubo deformadas de Klee y Minty et al. (véase, por ejemplo, el cubo de Klee-Minty ). ^{[ 1 ]}

La regla de Cunningham asigna un orden cíclico a las variables y recuerda la última variable que entró en la base. La siguiente variable que entra se elige como la primera candidata permitida a partir de la última variable elegida y siguiendo el orden circular dado. Las reglas basadas en el historial invalidan las construcciones de hipercubos deformados porque tienden a promediar la cantidad de veces que una variable pivota.

Recientemente, David Avis y Oliver Friedmann demostraron que existe una familia de programas lineales en los que el algoritmo simplex equipado con la regla de Cunningham requiere tiempo exponencial. ^{[ 2 ]}