Melhor livro sobre implementação do método Simplex?

14

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.

izhak
fonte
1
Loop: consulte en.wikipedia.org/wiki/Bland's_rule
Maverick Woo

Respostas:

13

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 .

vb le
fonte
12

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:

  • métodos simplais e duplos simplex
  • método de ponto interior duplo-primal
  • método de ramificação e corte
  • tradutor para GNU MathProg
  • API (Application Program Interface)
  • solucionador de LP / MIP independente
Massimo Cafaro
fonte
12
De fato. Eu recomendo fortemente que NÃO tente implementar o simplex sozinho, a menos que esse seja o objetivo do exercício. Se você quiser apenas usá-lo, os métodos prontos para uso são muito melhores. Além disso, o CPLEX é gratuito para uso acadêmico, se for apropriado para você.
Suresh Venkat
1
Existem implementações de código aberto distribuídas (como MPI) do LP?
Tomek Tarczynski
3
O @Tomek LP é P completo e é improvável que tenha uma paralelização eficiente.
Marcus Ritt
@Tomek: O Simphony fornece uma versão distribuída que atualmente é executada em qualquer ambiente suportado pelo protocolo de passagem de mensagens PVM (o MPI ainda não é suportado). O mesmo código fonte também pode ser compilado para arquiteturas de memória compartilhada usando qualquer compilador compatível OpenMP .. Veja branchandcut.org eo COIN-OR web site fortemente relacionado: coin-or.org
Massimo Cafaro
9
O CPLEX é provavelmente a melhor implementação de LP atualmente disponível (é por isso que as pessoas pagam muito por isso), mas praticamente todas as implementações amplamente usadas se saem substancialmente melhor do que qualquer coisa que você programa. Isso inclui os pacotes Mathematics, Maple e MATLAB. Existem muitas implementações por aí, incluindo algumas razoavelmente boas gratuitas (QSopt, por exemplo, que são gratuitas se você não planeja usá-lo para fins comerciais), portanto, programar você mesmo vale a pena pela experiência de aprendizado.
quer
9

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)

Sariel Har-Peled
fonte
6

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.

Artem Kaznatcheev
fonte
1

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.

marshallf
fonte