La structure des instances pathologiques pour les algorithmes simplex

Pour autant que je sache, toutes les règles de pivot déterministes connues pour les algorithmes simplex ont des entrées spécifiques sur lesquelles l'algorithme nécessite un temps exponentiel (ou du moins pas polynomial) pour trouver l'optimum. Appelons ces instances «pathologiques» car généralement (c'est-à-dire sur la plupart des entrées) l'algorithme simplex se termine rapidement. Je me souviens de mon cours de programmation mathématique que les exemples standard d'instances pathologiques pour des règles spécifiques étaient très structurés. Ma question générale est de savoir s'il s'agit d'un artefact d'exemples spécifiques ou d'une caractéristique d'instances pathologiques en général?

Des résultats comme l' analyse lissée et l'algorithme de temps polynomial étend reposent sur la perturbation de l'entrée --- suggérant que les exemples pathologiques sont très spéciaux. Par conséquent, l'intuition selon laquelle les instances pathologiques sont hautement structurées ne semble pas si farfelue.

Quelqu'un a-t-il des idées précises à ce sujet? Ou quelques références à des travaux existants? J'ai été particulièrement vague sur ce que j'entends par «structuré» pour essayer d'être aussi englobant que possible, mais des suggestions sur la façon de mieux définir «structuré» seraient également utiles. Tous les conseils ou références sont grandement appréciés!

cc.complexity-theory reference-request linear-programming simplex Artem Kaznatcheev
la source

Je ne suis pas sûr d'avoir compris votre question, mais l'opposé de «structuré» semble être «aléatoire». Si un algorithme simplex avec une certaine règle de pivotement est déjà inefficace pour des instances aléatoires (avec une probabilité élevée, selon une distribution naturelle ), les gens ne sont probablement pas intéressés à construire un mauvais exemple pour cette règle de pivotement particulière parce que cette règle de pivotement particulière est pour la plupart inutile.

Tsuyoshi Ito

Demandez-vous: pour une règle de pivotement fixe, quelle est la probabilité qu'une instance aléatoire soit pathologique? c'est-à-dire l'analyse de cas moyen de l'algorithme?

Kaveh

Je ne demande pas la probabilité qu'un cas aléatoire soit pathologique. Je demande vraiment simplement si les instances pathologiques ont une structure spéciale. Comme Tsuyoshi le fait remarquer, je devrais vraiment le limiter aux «bonnes» règles de pivot, quoi que cela signifie. Des suggestions sur la façon de rendre cela plus clair?

Artem Kaznatcheev

Je crois que beaucoup d'instances pathologiques sont des cubes dont les côtés ont été malicieusement perturbés, mais j'ai regardé cela il y a assez longtemps pour que ma mémoire soit complètement fausse.

Peter Shor

Réponses:

Amenta et Ziegler ont prouvé que toutes les constructions actuellement connues d'instances à temps exponentiel pour simplex suivent une structure particulière qu'elles appellent des «produits déformés»:

Produits déformés et ombres maximales de polytopes par Amenta et Ziegler

Cependant, je ne pense pas qu'il y ait aucune raison de croire que toutes les mauvaises instances pour simplex ont cette structure. Ce n'est probablement qu'un artefact du processus de recherche:

Klee et Minty ont trouvé le premier exemple à temps exponentiel.
D'autres chercheurs ont examiné les techniques de Klee et Minty et les ont étendues à d'autres règles pivot. Ils ont naturellement pris le chemin de la moindre résistance et ont suivi le cube de Klee-Minty le plus près possible.
Une fois que quelqu'un trouve un mauvais exemple de règle pivot, rien n'incite les gens à en chercher plus. En conséquence, tous les mauvais exemples que nous connaissons ont une structure similaire.

Ian
la source

J'aime toujours les réponses sociologiques aux questions mathématiques;). Merci d'avoir répondu! Je vais regarder de plus près AmentaZiegler1996, connaissez-vous les résultats depuis 1996 qui fonctionnent bien sur les produits déformés? J'ai trouvé un article de Norman Zadeh (de 1980 à 2009) qui, même dans la version des années 80 [ stanford.edu/group/SOL/reports/OR-80-27.pdf ], mentionne avoir surmonté la construction du produit déformé.

Artem Kaznatcheev

«Produit déformé» était clairement une notion intuitive dans la communauté LP depuis des décennies avant que Nina et Gunter ne l'officialisent. C'est certainement une description précise des cubes Klee-Minty!

Jeffε

Voir aussi les limites inférieures exponentielles de Matoušek et Szabo pour RANDOM EDGE sur les "cubes abstraits", qui peuvent être considérés comme les cousins combinatoires des produits déformés d'Amenta et de Ziegler: portal.acm.org/citation.cfm?id=1033164

Jeffε