Come scegliere un risolutore di programmazione lineare intero?

Question

Sono novizio per la programmazione lineare intera. Ho intenzione di utilizzare un solutore di programmazione lineare intero per risolvere il mio problema di ottimizzazione combinatoria. Ho più familiarità con C++/programmazione orientata agli oggetti su un IDE. Ora sto usando NetBeans con Cygwin per scrivere le mie applicazioni la maggior parte del tempo.

Posso chiedere se è disponibile un solver ILP di facile utilizzo? Oppure dipende dal problema che voglio risolvere? Sto provando a fare un po 'di ottimizzazione della mappatura delle risorse. Per favore fatemi sapere se sono richieste ulteriori informazioni.

Grazie mille, Cassie.

Answer 1

Linear Programming da Wikipedia copre alcuni algoritmi diversi che è possibile eseguire un po 'di ricerca per vedere quale può funzionare meglio per voi. Questo aiuta o volevi qualcosa di più specifico?

Answer 2

Per problemi di grandi dimensioni, è possibile consultare AMPL, che è un interprete di ottimizzazione con molti backend solvers disponibili. Funziona come a separate process; C++ verrebbe utilizzato per scrivere i dati di input.

Quindi è possibile provare vari solutori di ultima generazione.

Answer 3

Se ciò che si desidera è una programmazione di interi misti lineare, quindi puntare a Coin-OR (e in particolare al modulo CBC). È software libero (come discorso) Puoi usarlo con un linguaggio specifico o usare C++.

Utilizzare C++ se i dati richiedono un sacco di pre-elaborazione o se si desidera mettere le mani nel risolutore (scegliendo i punti di rotazione, generazione di colonne, aggiunta di tagli e così via ...).

Utilizzare il linguaggio integrato se si desidera utilizzare il risolutore come una scatola nera (si è interessati al risultato e il problema è abbastanza semplice o classico da risolvere senza apportare modifiche).

Ma nei tag si menzionano algoritmi genetici e algoritmi di grafici. Forse si dovrebbe iniziare meglio defing tuo problema ... Per i grafici mi piace un sacco Boost :: Graph

Answer 4

ho usato lp_solve (http://lpsolve.sourceforge.net/5.5/) in un paio di occasioni con successo. È maturo, ricco di funzionalità ed estremamente ben documentato con molti buoni consigli se le tue capacità di programmazione lineare sono arrugginite. La programmazione lineare intera non è solo un'aggiunta, ma è fortemente enfatizzata con questo pacchetto.

Appena notato che dici di essere un "principiante" in questo. Bene, allora consiglio vivamente questo pacchetto poiché la documentazione è piena di esempi e tutorial gentili. Altri pacchetti che ho provato tendono ad assumere molto all'utente.

Answer 5

Cerca su GLPK. Viene fornito con alcuni esempi e funziona con un sottoinsieme di AMPL, anche se IMHO funziona meglio quando ci si attiene a C/C++ per l'impostazione del modello. Affronta anche modelli piuttosto grandi.