Melhor open source Mixed Integer Otimização Solver [fechado]

Question

Eu estou usando CPLEX para resolver modelos de otimização enormes (mais de 100 mil variáveis) agora eu gostaria de ver se eu posso encontrar uma alternativa de código aberto, eu resolver problemas mistos inteiros (MILP) e CPLEX funciona muito bem, mas é muito caro, se quisermos escala então eu realmente preciso encontrar uma alternativa ou começar a escrever nossa própria biblioteca de otimização ad-hoc (que vai ser doloroso)

Qualquer sugestão / visão seria muito apreciada

Answer 1

Eu, pessoalmente, encontrou GLPK melhor (isto é, mais rápido) do que lp_solve. Ele suporta vários formatos de arquivo, e uma outra vantagem é a sua biblioteca de interface, que permite a integração harmoniosa com a sua aplicação.

Answer 2

Outro endosso para COIN-OR . Descobrimos que o componente otimizador linear (CLP) era muito forte, e o componente inteira mista (CBC) pode ser ajustado muito bem com algumas análises. Nós comparamos com LP-Solve e GLPK.

Para problemas realmente difíceis, um solver comercial é o caminho a percorrer.

Answer 3

Tente o solver SCIP. Eu usei-o para MILP problemas com mais de 300K variáveis ??com bom desempenho. Seu desempenho MILP é muito melhor do que GLPK. Gurobi também tem excelente desempenho para problemas MILP (e normalmente melhor do que SCIP (maio de 2011)), mas pode ser caro se você não for um usuário acadêmico. Gurobi usará multicores para acelerar o solver.

Answer 4

Você já tentou lp_solve ? Havia também algumas outras sugestões nas seguintes perguntas, para Java:

• para Java - livre ou recomendações de fonte aberta?
• Programação Linear Ferramenta / Bibliotecas para Java

Answer 5

Se eu fosse você, eu iria tentar usar um multi-solver interface como Osi (C ++) ou polpa (python) de modo que você pode escrever seu código uma vez, e testá-lo com muitos solucionadores.

Se os programas inteiros que você está indo para resolver são enormes, eu recomendaria python sobre C ++, porque você código será mais limpa e 99% do tempo será gasto na solver.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

Não

Se, pelo contrário, os problemas são pequenos, então o tempo para copiar os problemas da memória do python para o solver (ida e volta) está a ser negligenciado mais: nesse caso, você pode experimentar algumas melhorias de desempenho notável usando uma linguagem compilada.

Mas se os problemas são esmagadoramente enorme, línguas, em seguida, compilados estão indo para ganhar de novo, porque o consumo de memória será dividido aproximadamente por 2 (nenhuma cópia do problema em python).

Answer 6

Eu recomendo verificar o projeto COIN. moeda ou

Muitos solvers bons aqui, incluindo ipOPT para problemas não-lineares e um par agentes de resolução inteiros mistos também.

Answer 7

Scip não é mau!

Answer 8

Embora este não é talvez o que você quer ouvir, mas há anos-luz entre os solucionadores comerciais CPLEX e Gurobi sobre os solucionadores de um lado, e de fonte aberta, por outro lado.

No entanto, você pode ter sorte e seu modelo funciona bem com GLPK, Moeda ou similar, mas em soluções gerais de código aberto estão muito atrás dos solucionadores comerciais. Se fosse diferente, ninguém pagaria 12.000 $ para uma licença Gurobi e ainda mais para uma licença CPLEX.

Nos últimos anos, tenho visto muitos, muitos modelos que eram apenas para difícil para os solucionadores de código aberto. Acredite em mim ...

Não é tanto uma questão de tamanho, mas de dificuldade numérica.

Answer 9

100k variáveis ??é um problema grande. Muitas das bibliotecas de código aberto não funcionam bem com que muitas variáveis. Pelo que tenho lido lp_solve só foi testado por cerca de 30k variáveis. Usando o sistema comercial pode ser sua única opção.

Answer 10

Eu tenho usado DICOPT usando o servidor NEOS ( http: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) para resolver grandes (aproximadamente 1k variáveis ??e 1k restrições) programas de inteiros mistos não-lineares e achei excelente.

Para o meu problema DICOPT fez muito melhor do que os outros solucionadores MINLP listadas na BARON servidor neos / KNITRO / LINDO / SBB etc.

Há certas restrições ao envio de trabalhos para NEOS e é um pouco complicado, mas o livre acesso a um solver comercial poderoso mais do que compensa isso.

Answer 11

Vou acrescentar o seguinte para as já excelentes respostas.

Embora, como outros apontaram, solucionadores comerciais são muito mais rápido e mais capaz do que as alternativas livres É importante considerar o quanto de um gap optimality você pode aceitar. Para grandes problemas com muitas variáveis ??inteiras que você pode obter muito mais rápido resolver vezes se você pode aceitar 1% ou ainda maior lacuna optimality (padrões tendem a ser em torno de 0,01% ou menos).

É claro que se você está resolvendo um problema em que 1% se traduz em milhões de dólares este não é aceitável - daí o mercado para solucionadores de alto nível. (Algumas comparações de Gurobi para solucionadores gratuitos aqui )

Eu concordo com outros que usando uma plataforma que gera arquivos Problem Solver-independentes (como .mps *, arquivos .LP *) vale a pena, como você pode, então, experimentar outros solucionadores. Estou usando polpa e estou achando , eo solver COIN_CBC livre, excelente. Embora limitado para problemas com muitas variáveis ??inteiras.

Answer 12

Estou surpreso que ninguém tenha mencionado MIPCL ( http: //www.mipcl- cpp.appspot.com/index.html ). Este solver reivindicações a ser de código aberto sob a licença LGPL (fonte: http: //www.mipcl -cpp.appspot.com/licence.html ), portanto, é também adequado para ser utilizado em aplicações de origem não-abertas. Mas o que está faltando para ser realmente open source é o código-fonte do próprio solver.

Hans Mittelmann muito recentemente (10 de setembro de 2017) fez Mixed Referência de Programação Linear Inteira: http: / /plato.asu.edu/ftp/milpc.html (você também pode estar interessado em olhar para a página de visão geral http://plato.asu.edu/bench.html ou os slides de sua palestra: http://plato.asu.edu/talks/informs2017.pdf ).

No benchmark Mixed Programação Linear Inteira com 12 tópicos e um limite de tempo de 2 horas MIPCL conseguiu resolver 79 casos. Apenas os solucionadores comerciais CPLEX, Gurobi e XPRESS conseguiu resolver mais sob as restrições dadas (86 ou 87 casos, respectivamente).

Além disso, em termos de desempenho escolhido métrica (de novo usando 12 threads) MIPCL é mais rápido do que os derivados SCIP referenciados (FSCIPC, FSCIPS) eo código aberto solver CBC. Novamente, apenas os solvers comerciais CPLEX, Gurobi e XPRESS outcompete MIPCL significativamente em termos de desempenho.

Answer 13

Não open source, mas se você tiver uma licença do Microsoft Academic Alliance, o Microsoft Solver Foundation (MSF) Enterprise edition está incluído. Gurobi também é livre para fins académicos, eu usei na minha pesquisa de tese.