Estou interessado em implementar o SM para tarefas de LP, no entanto, ouvi falar de possíveis armadilhas: o livro de Cormen diz que é possível ter dados de entrada que farão com que a implementação ingênua se comporte em tempo exponencial. Também ouvi dizer que a implementação ingênua pode fazer um loop para algum tipo de dados.
Existe um livro / artigo / fonte que explique as nuances da implementação prática do SM?
Desde já, obrigado.
Respostas:
Eu recomendo fortemente o artigo de Bixby, o "pai" do CPLEX, que examina não apenas aspectos de implementação do algoritmo simplex (revisado): Robert E. Bixby , Resolvendo programas lineares do mundo real: uma década e mais progresso , operações Research (50) 2002, 3-15 .
fonte
O algoritmo simplex não está em P. CLRS, portanto, afirma que, embora na prática funcione "bem", há algumas entradas que fazem com que o algoritmo seja executado em tempo exponencial. Isso está estritamente relacionado ao algoritmo, não à sua implementação: você enfrentará isso independentemente de como exatamente implementa o algoritmo. No entanto, LP está em P. Isso foi provado por Khachian em 1979, porém seu algoritmo elipsóide não é prático. Hoje, os métodos de pontos interiores são amplamente utilizados. O primeiro foi descoberto por Karmarkar em 1984.
Se você estiver interessado em implementações práticas, dê uma olhada em:
O GUROBI, gratuito para uso acadêmico, é atualmente o melhor otimizador disponível (nas versões paralela e sequencial de memória compartilhada):
http://www.gurobi.com
a biblioteca GLPK:
http://www.gnu.org/software/glpk/
este é um projeto de código aberto, fornecendo implementações para:
fonte
O livro de programação linear de Vanderbei aborda muitos dos detalhes de baixo nível ... Mas, como as outras respostas / comentários sugeriram, implementar o solver de LP é uma tarefa difícil e ingrata. O solucionador de prateleira provavelmente é o caminho a percorrer ... (Existem também alguns solucionadores de código-fonte aberto LP)
fonte
Não são apenas as implementações ingênuas que às vezes se comportam em tempo exponencial. De fato, acho que todas as regras determinísticas e aleatórias conhecidas têm entradas super-polinomiais para os piores casos. A maioria das entradas conhecidas que produzem esse pior comportamento é altamente estruturada, uma questão relacionada:
A estrutura de instâncias patológicas para algoritmos simplex
No entanto, na prática, o SM funciona bem. Isso foi formalizado pela introdução de uma análise suavizada, que é basicamente a análise do pior caso, com entradas levemente perturbadas. Sob essa análise, SM é polytime, ou seja, para cada entrada (mesmo as patológicas), há uma leve perturbação que permite que o algoritmo tenha um bom desempenho. Esse insight foi transformado em um algoritmo aleatório que executa em polytime. No entanto, tanto quanto eu entendo, ainda há algum debate sobre se esse algoritmo se qualifica como um algoritmo simplex 'verdadeiro'. Também não sei se os pacotes padrão implementam algo nesse sentido, mas você deve encontrar alguma implementação se pesquisar, por conta do resultado ter mais de 5 anos.
fonte
Você pode verificar Luenberger, Ye, Linear and Nonlinear Programming, 3rd ed. Isso parece bastante abrangente, mas ainda não cheguei longe o suficiente para dizer se ela responde completamente à sua pergunta.
fonte