La estructura de instancias patológicas para algoritmos simplex

17

Según tengo entendido, todos saben que las reglas de pivote deterministas para algoritmos simplex tienen entradas específicas en las que el algoritmo requiere tiempo exponencial (o al menos no polinomial) para encontrar el óptimo. Llamemos a estas instancias 'patológicas' ya que generalmente (es decir, en la mayoría de las entradas) el algoritmo simplex termina rápidamente. Recuerdo de mi curso de programación matemática que los ejemplos estándar de instancias patológicas para reglas específicas estaban altamente estructurados. Mi pregunta general es si esto es un artefacto de los ejemplos específicos, o una característica de las instancias patológicas en general.

Los resultados como el análisis suavizado y el algoritmo de tiempo polinómico que lo extiende dependen de perturbar la entrada, lo que sugiere que los ejemplos patológicos son muy especiales. Por lo tanto, la intuición de que las instancias patológicas están altamente estructuradas no parece tan descabellada.

¿Alguien tiene alguna idea específica sobre esto? ¿O algunas referencias al trabajo existente? He sido específicamente impreciso sobre lo que quiero decir con 'estructurado' para tratar de ser lo más abarcador posible, pero las sugerencias sobre cómo precisar mejor 'estructurado' también serían útiles. Cualquier consejo o referencia son muy apreciados!

Artem Kaznatcheev
fuente
1
No estoy seguro de haber entendido su pregunta, pero lo opuesto a "estructurado" parece ser "aleatorio". Si un algoritmo simplex con una determinada regla pivotante ya no es eficiente para instancias aleatorias (con alta probabilidad, de acuerdo con alguna distribución natural ), probablemente las personas no estén interesadas en construir un mal ejemplo para esa regla pivotante en particular porque esa regla pivotante en particular es en su mayoría inútil.
Tsuyoshi Ito
¿Está preguntando: para una regla pivotante fija, cuál es la probabilidad de que una instancia aleatoria sea patológica? es decir, el análisis de caso promedio del algoritmo?
Kaveh
No estoy preguntando por la probabilidad de que una instancia aleatoria sea patológica. Realmente solo estoy preguntando si las instancias patológicas tienen una estructura especial para ellas. Como Tsuyoshi señala, realmente debería restringirlo a las reglas de pivote "buenas", sea lo que sea que eso signifique. ¿Alguna sugerencia sobre cómo aclarar esto?
Artem Kaznatcheev
44
Creo que muchas instancias patológicas son cubos cuyos lados han sido perturbados maliciosamente, pero lo miré hace tanto tiempo que mi memoria podría estar completamente equivocada.
Peter Shor

Respuestas:

16

Amenta y Ziegler demostraron que todas las construcciones actualmente conocidas de instancias de tiempo exponencial para simplex siguen una estructura particular que llaman "productos deformados":

Productos deformados y sombras máximas de politopos de Amenta y Ziegler

Sin embargo, no creo que haya ninguna razón para creer que todas las instancias malas para simplex tengan esta estructura. Probablemente esto sea solo un artefacto del proceso de investigación:

  1. Klee y Minty encontraron el primer ejemplo de tiempo exponencial.
  2. Otros investigadores observaron las técnicas de Klee y Minty y las extendieron a otras reglas fundamentales. Naturalmente, tomaron el camino de menor resistencia y siguieron el cubo de Klee-Minty lo más cerca posible.
  3. Una vez que alguien encuentra un mal ejemplo para una regla pivote, no hay incentivo para que las personas busquen más. Como resultado, todos los malos ejemplos que conocemos tienen una estructura similar.
Ian
fuente
1
Siempre me encantan las respuestas sociológicas a las preguntas de matemáticas;). ¡Gracias por la respuesta! Echaré un vistazo más de cerca a AmentaZiegler1996, ¿conoce los resultados desde '96 que funcionan bien en productos deformados? Encontré un artículo de Norman Zadeh (de 1980 y 2009) que incluso en la versión de los años 80 [ stanford.edu/group/SOL/reports/OR-80-27.pdf ] menciona la superación de la construcción deformada del producto.
Artem Kaznatcheev
El "producto deformado" era claramente una noción intuitiva en la comunidad de LP décadas antes de que Nina y Gunter lo formalizaran. ¡Ciertamente esa es una descripción precisa de los cubos de Klee-Minty!
Jeffε
1
Ver también los límites inferiores exponenciales de Matoušek y Szabo para RANDOM EDGE en "cubos abstractos", que pueden verse como primos combinatorios de los productos deformados de Amenta y Ziegler: portal.acm.org/citation.cfm?id=1033164
Jeffε