Qual é o limite superior do algoritmo simplex para encontrar uma solução para um programa linear?
Como eu iria encontrar uma prova para esse caso? Parece que o pior caso é se cada vértice tiver que ser visitado, ou seja, . No entanto, na prática, o algoritmo simplex será executado significativamente mais rápido que isso, para problemas mais comuns.
Como raciocinar sobre a complexidade média de um problema que está sendo resolvido usando esse método?
Todas as informações ou referências são muito apreciadas!
Respostas:
De fato, o algoritmo simplex visita todos os vértices no pior caso ( Klee & Minty, 1972 ), e isso se aplica a qualquer regra de pivô determinística. No entanto, em um artigo de referência usando uma análise suavizada, Spielman e Teng (2001) provaram que, quando as entradas do algoritmo são levemente perturbadas aleatoriamente, o tempo de execução esperado do algoritmo simplex é polinomial para todas as entradas - isso basicamente diz que, para qualquer problema, existe um problema "próximo" que o método simplex resolverá com eficiência e abrange praticamente todos os programas lineares do mundo real que você gostaria de resolver. Posteriormente, Kelner e Spielman (2006) introduziram2n um algoritmo simplex aleatório com tempo polinomial que funciona realmente em todas as entradas, mesmo as ruins para o algoritmo simplex original.
fonte
Como Lev disse, no pior dos casos, o algoritmo visita todos os vértices em2d onde d é o número de variáveis. No entanto, o desempenho do algoritmo simplex também pode depender muito da regra de pivô específica usada. Tanto quanto sei, ainda é uma questão em aberto se existe uma regra de pivô determinística específica com tempo de execução subexponencial no pior dos casos. Muitos candidatos foram descartados por resultados de limite inferior. Recentemente, Friedmann, Hansen e Zwick também mostraram os primeiros limites inferiores não polinomiais para algumas regras de pivô aleatórias naturais, com algumas correções fornecidas posteriormente .
No entanto, adicionando ao resultado da análise suavizada mencionado por Lev: Após o artigo seminal de Spielman e Tengs, que introduziu a análise suavizada, Vershynin melhorou ainda mais seus limites em 2006. Ele mostrou que o tempo de execução esperado em instâncias levemente perturbadas é apenas poliolarítmico no número de restriçõesn , abaixo de n86 .
fonte
Para obter informações sobre a análise de pior caso e caso médio do método simplex, leia "Análise suavizada: por que o algoritmo simplex geralmente leva tempo polinomial". por Spielman e Teng.
fonte
Uma boa referência sobre por que o simplex não está sendo executado no tempo polinomial, e não por que é exponencial é a Otimização Combinatória de Papadimitriou e Steiglitz, Seção 8.6, na qual eles demonstram que o Simplex não é um algoritmo de tempo polinomial.
fonte
Alguém pode sugerir outras maneiras de construir problemas difíceis para o método simplex, lento, mas não vinculado à memória?
Adicionado: quadrados latinos, também conhecidos como matrizes de permutação em 3D, parecem ter muitos vértices - quantos?
Teoria e prática são mais próximas na teoria do que na prática.
fonte
O algoritmo Simplex original pode divergir; ele roda em certas instâncias. Portanto, nenhum limite geral. Outras respostas fornecem respostas para as várias modificações do algoritmo Simplex.
fonte