Como implementar ramo e preço?
Ouvi uma vez que o algoritmo branch and price (B&P) está entre os mais difíceis em OR, mas se for bem implementado, pode ser muito eficiente. Existem outros algoritmos que também são tão complicados?
Quero implementar o B&P em um problema. Então, como escolho um problema que não seja muito complexo? Sinta-se à vontade para sugerir mais de um problema se você acha que isso tem um impacto na maneira como o algoritmo é implementado, ou seja, se vou aprender princípios diferentes de problemas diferentes.
Eu também preciso de alguma orientação. Como começar? Quais são as armadilhas a evitar? Qualquer recurso que tenha um código-fonte aberto bem documentado também será apreciado. Eu quero escolher python ou C ++.
Respostas
Antes de iniciar a implementação, gostaria de me certificar de que estou confortável com todos os aspectos teóricos, que também são um pouco complicados. Este é um tópico bastante avançado em OR e requer alguma experiência. Você está confortável com branch-and-bound, com o algoritmo simplex, com decomposição de Dantzig-Wolfe, geração de coluna, etc?
Você está hesitando entre Python e C ++. Existe uma razão para isso ? Python é muito mais simples, mas C ++ será mais rápido. Isso é para a academia ou para a indústria?
Você também pode check-out Dippy , que é uma extensão da polpa (pelo que a sua Python) que permite que os usuários especifiquem decomposições e personalizar a ramificação, a geração de corte e geração de colunas de DIP , a partir de um modelo de polpa. Tudo é open source.
Usar uma estrutura como o SCIP pode ser uma boa ideia para começar. Fazendo isso, você pode implementar rapidamente sua formulação. Possui interfaces em C ++ e Python. A documentação contém exemplos de branch-and-price, sugiro que você dê uma olhada neles. Para qualquer problema em mãos, você pode usar o método de decomposição de Dantzig-Wolfe para gerar o esquema de ramificação e preço.
Nah. Construir uma interface ASL é difícil , BnP está OK. Supondo que você esteja familiarizado com seus blocos de construção (assim como com qualquer outro algoritmo), o desafio está nos detalhes de implementação.
Existem algumas coisas a serem observadas para o BnB em geral, e para o BnP especificamente:
BnB
- Heurísticas de aceleração: os algoritmos BnB só funcionam bem se combinados com certas heurísticas de aceleração, como redução de domínio (por exemplo, propagação de restrição) ou boas estratégias de ramificação (por exemplo, pseudococos).
- Para grandes problemas, você precisa de estruturas de dados boas e escalonáveis para evitar que o algoritmo fique lento para um rastreamento, especialmente se seus problemas forem grandes o suficiente para exigir a geração de colunas.
- Python puro será 1.000-10.000 vezes mais lento que C ++ para qualquer problema de tamanho decente. A maneira adequada de fazer isso é codificar bibliotecas C ++ para cálculos de alto desempenho e importá-las como objetos Python usando APIs Python-> C ++, como boost Python. Isso pode deixar você 100x mais lento do que C ++.
- Pelas duas razões acima, o Python tem seus limites devido à largura de banda limitada na transferência de dados entre diferentes partes do seu código. Em particular, muitas APIs Python-> C ++ inevitavelmente acionam construtores de cópia C ++, o que pode ser um grande problema se suas estruturas de dados forem grandes. A memória também pode se tornar um problema.
- Já que estamos no assunto, mesmo que você realmente saiba o que está fazendo em C ++, o melhor que você pode fazer com código híbrido é 100x mais lento do que C ++. No entanto, se você está nesse nível de saber o que está fazendo, é melhor fazer tudo em C ++.
- MINOTAUR é o código BnB de código aberto C ++ mais bem escrito que vi até agora (embora não muito bem documentado há alguns anos).
- Uma coisa que a maioria das pessoas negligencia no início é que você precisa de uma maneira de incluir a matemática em seu código. Pense em como você fará isso desde o início, pois afetará muitas de suas decisões de arquitetura.
BnP
- Uma consideração importante de implementação aqui é que você deve adicionar colunas ao relaxamento à medida que o procedimento de solução avança. Esta pode ser uma operação muito cara, especialmente com matrizes grandes, portanto, você precisará pesquisar a maneira mais rápida que o solucionador linear oferece suporte para adicionar novas colunas. Reconstruir a matriz é a maneira mais simples e, na verdade, é ok para muitos algoritmos, mas é um não-não para a geração de colunas.
Pela sua descrição, parece que seu objetivo é aprender coisas novas, portanto, Python ou C ++ são adequados para esse propósito. Se você quiser usar seu código para algo "real", usar C ++ até certo ponto será inevitável, então cabe a você decidir o que deseja aprender em termos de programação. Porém, esteja ciente de que a migração de código híbrido para C ++ pode ser bem doloroso, portanto, se você perceber que terá que usar C ++, é melhor fazê-lo no início do desenvolvimento.
De qualquer forma, prepare-se mentalmente para um grande investimento de tempo e divirta-se!
Se você quiser examinar o código-fonte C ++, existem alguns projetos COIN-OR que fornecem estruturas para "preço e corte de ramo" ou "corte e preço de ramo", como às vezes é conhecido. Dois que vêm à mente são o BCP e o Symphony .
Uma das principais ideias por trás de nosso solucionador de decomposição GCG (gcg.or.rwth-aachen.de/dev) é economizar seu tempo experimentando seu próprio código B&P apenas para descobrir que B&P não é a abordagem certa para o seu problema. Uma outra ideia principal do nosso solucionador é que, depois de descobrir que o B&P é uma boa abordagem, você pode simplesmente usar o GCG para fazer o trabalho por você. Experimente, espero que poupe algumas horas. Baixe com SCIP em scipopt.org.