Miglior risolutore di ottimizzazione di numeri interi misti open source [chiuso]

Question

Sto usando CPLEX per risolvere enormi modelli di ottimizzazione (più di 100k variabili) ora mi piacerebbe vedere se riesco a trovare un'alternativa open source, risolvo problemi con numeri interi misti (MILP) e CPLEX funziona benissimo ma è molto costoso se lo facciamo voglio scalare, quindi ho davvero bisogno di trovare un'alternativa o iniziare a scrivere la nostra libreria di ottimizzazione ad hoc (il che sarà doloroso)

Qualsiasi suggerimento/intuizione sarebbe molto apprezzato

Answer 1

Personalmente ho trovato GLPK migliore (ovvero più veloce) di LP_SOLVE. Supporta vari formati di file e un ulteriore vantaggio è la sua interfaccia di libreria, che consente una perfetta integrazione con la tua applicazione.

Answer 2

Un'altra approvazione per COIN-OR . Abbiamo scoperto che il componente dell'ottimizzatore lineare (Clp) era molto forte e che il componente intero misto (Cbc) poteva essere sintonizzato abbastanza bene con alcune analisi. Abbiamo confrontato con LP-Solve e GLPK.

Per problemi davvero difficili, un risolutore commerciale è la strada da percorrere.

Answer 3

Prova il risolutore SCIP. L'ho usato per problemi MILP con oltre 300K variabili con buone prestazioni. Le sue prestazioni MILP sono molto migliori di GLPK. Gurobi ha anche prestazioni eccellenti per i problemi MILP (e in genere migliori di SCIP (maggio 2011)), ma potrebbe essere costoso se non sei un utente accademico. Gurobi utilizzerà i multicore per accelerare il risolutore.

Answer 4

Hai provato lp_solve ? Ci sono stati anche altri suggerimenti nelle seguenti domande, per Java:

• libreria di ottimizzazione matematica per Java & # 8212; - raccomandazioni gratuite o open source?
• Strumento di programmazione lineare / Librerie per Java

Answer 5

Se fossi in te, proverei a utilizzare un'interfaccia multi-solver come Osi (C ++) o PuLP (python) in modo da poter scrivere il codice una volta e testarlo con molti solutori.

Se i programmi interi che stai per risolvere sono enormi, consiglierei Python su C ++, perché il tuo codice apparirà più pulito e il 99% del tempo sarà impiegato nel solutore.

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

Se, al contrario, i problemi sono piccoli, allora il tempo per copiarli dalla memoria di Python al solutore (avanti e indietro) non deve più essere trascurato: in tal caso è possibile sperimentare alcuni notevoli miglioramenti delle prestazioni usando una lingua compilata.

Ma se i problemi sono enormemente enormi, allora i linguaggi compilati vinceranno di nuovo, perché l'impronta della memoria sarà approssimativamente divisa per 2 (nessuna copia del problema in Python).

Answer 6

Consiglio di dare un'occhiata al progetto COIN. COIN OR

Molti bravi solutori qui, incluso ipOPT per problemi non lineari e una coppia risolutori interi misti pure.

Answer 7

Scip non è male!

Answer 8

Anche se questo non è forse quello che vuoi sentire, ma ci sono anni luce tra i risolutori commerciali CPLEX e Gurobi da un lato e i risolutori open source dall'altro.

Tuttavia puoi essere fortunato e il tuo modello funziona bene con GLPK, Coin o simili, ma in generale le soluzioni open source sono molto indietro rispetto ai solutori commerciali. Se fosse diverso, nessuno pagherebbe 12.000 $ per una licenza Gurobi e ancora di più per una licenza CPLEX.

Negli ultimi anni ho visto molti, molti modelli che erano troppo difficili per i risolutori open source. Credimi ...

Non è tanto una questione di dimensioni, ma di difficoltà numeriche.

Answer 9

100k variabili sono un grosso problema. Molte delle librerie open source non funzionano bene con così tante variabili. Da quello che ho letto lp_solve è stato testato solo per circa 30k variabili. L'uso del sistema commerciale potrebbe essere la tua unica scelta.

Answer 10

Ho usato DICOPT usando il server NEOS ( http: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) per risolvere grossi (non 1k variabili e 1k vincoli) programmi non lineari misti interi non-lineari e lo ha trovato eccellente.

Per il mio problema DICOPT ha fatto molto meglio degli altri solutori MINLP elencati sul server neos BARON / KNITRO / LINDO / SBB ecc.

Vi sono alcuni vincoli nell'invio di lavori a NEOS ed è leggermente complicato, ma l'accesso gratuito a un potente risolutore commerciale è più che compensato.

Answer 11

Aggiungerò quanto segue alle risposte già eccellenti.

Mentre, come altri hanno sottolineato, i risolutori commerciali sono molto più veloci e più capaci delle alternative gratuite, è importante considerare quanto di un gap di ottimalità puoi accettare. Per problemi di grandi dimensioni con molte variabili intere, è possibile ottenere tempi di risoluzione molto più rapidi se si accetta il divario di ottimalità dell'1% o addirittura maggiore (i valori predefiniti tendono a essere intorno allo 0,01% o meno).

Naturalmente, se si sta risolvendo un problema in cui l'1% si traduce in milioni di dollari, questo non è accettabile, da cui il mercato dei solutori di prim'ordine. (Alcuni confronti di Gurobi con solutori liberi qui )

Concordo con gli altri sul fatto che utilizzare una piattaforma che genera file di problemi indipendenti dal solutore (come file * .mps, * .lp) sia utile in quanto è quindi possibile provare altri solutori. Sto usando PuLP e lo sto trovando e il risolutore COIN_CBC gratuito, eccellente. Sebbene limitato per problemi con molte variabili intere.

Answer 12

Sono sorpreso che nessuno abbia menzionato MIPCL (http://www.mipcl-cpp.appspot.com/index.html).Questo risolutore dichiara di essere open source con licenza LGPL (fonte: http://www.mipcl-cpp.appspot.com/licence.html), quindi è adatto anche per essere utilizzato in applicazioni non open source.Ma quello che manca per essere davvero open source è il codice sorgente del solutore stesso.

Hans Mittelmann molto recentemente (10 settembre 2017) ha eseguito il benchmark della programmazione lineare intera mista: http://plato.asu.edu/ftp/milpc.html (potresti anche essere interessato a guardare la pagina di panoramica http://plato.asu.edu/bench.html o le slide del suo intervento: http://plato.asu.edu/talks/informs2017.pdf).

Nel Mixed Integer Linear Programming Benchmark con 12 thread e un limite di tempo di 2 ore MIPCL è riuscito a risolvere 79 istanze.Solo i solutori commerciali CPLEX, Gurobi e XPRESS sono riusciti a risolverne di più entro i limiti indicati (rispettivamente 86 o 87 istanze).

Anche in termini di metrica prestazionale scelta (sempre utilizzando 12 thread) MIPCL è più veloce dei derivati ​​SCIP di riferimento (FSCIPC, FSCIPS) e del solutore open source CBC.Anche in questo caso solo i solutori commerciali CPLEX, Gurobi e XPRESS superano significativamente MIPCL in termini di prestazioni.

Answer 13

Non open source, ma se si dispone di una licenza Microsoft Academic Alliance, la Microsoft Solver Foundation (MSF) Enterprise Edition è inclusa. Gurobi è anche gratuito per scopi accademici, l'ho usato nella mia ricerca di tesi.