programmazione lineare in python?

Question

Ho bisogno di creare un modello di programmazione lineare. Qui ci sono le disuguaglianze che sto usando (per esempio):

6x + 4y <= 24 
x + 2y <= 6 
-x + y <= 1 
y <= 2 

ho bisogno di trovare l'area descritta da queste disuguaglianze, e ombra in un grafico, così come tenere traccia dei vertici delle linee di delimitazione di quest'area e traccia la linea di delimitazione in un colore diverso. Vedere il grafico sottostante per un esempio di ciò che sto cercando.

.

Sto usando Python 3.2, numpy e matplotlib. Ci sono moduli migliori per la programmazione lineare in Python?

Answer 1

UPDATE: La risposta è diventata un po 'obsoleta negli ultimi 4 anni, qui è un aggiornamento. Avete molte opzioni:

• Se non devi farlo Python, allora è molto più facile da fare questo in un modellazione langage, vedere Any good tools to solve integer programs on linux?

• io personalmente utilizzare Gurobi questi giorni attraverso la sua API Python. È un prodotto commerciale, a codice chiuso ma gratuito per ricerche accademiche.

• SciPy offre programmazione lineare: scipy.optimize.linprog. (Ho mai provato questo.)

• Con PuLP è possibile creare MPS e LP files e poi risolverli con GLPK, COIN CLP/CBC, CPLEX o XPRESS attraverso la loro interfaccia della riga di comando . Questo approccio ha i suoi vantaggi e gli svantaggi .

• Apparentemente, CVXOPT offre un Python interface to GLPK, ho fatto non lo so. Sto usando GLPK per 8 anni e posso altamente raccomandato GLPK. Il examples and tutorial of CVXOPT sembra davvero carino!

• Puoi trovare altri possibilites presso nel Wikibook sotto GLPK/Python. Si noti che molti di questi non sono necessariamente soggetti a restrizione da a GLPK.

Answer 2

Vorrei raccomandare il pacchetto cvxopt per risolvere problemi di ottimizzazione convessa in Python. Un breve esempio con codice Python per un programma lineare è nella documentazione di cvxopt .

Answer 3

L'unica volta che un grafico viene utilizzato per risolvere un programma lineare è per un problema di compiti a casa. In tutti gli altri casi, i problemi di programmazione lineare vengono risolti tramite algebra lineare a matrice.

Come per Python, mentre ci sono alcune librerie pure Python, molte persone usano una libreria nativa con collegamenti Python. Esiste un'ampia varietà di librerie gratuite e commerciali per la programmazione lineare. Per un elenco dettagliato, vedere Linear Programming in Wikipedia o Linear Programming Software Survey in OR/MS oggi.

Disclaimer: Attualmente lavoro per Gurobi Optimization e in precedenza ha lavorato per ILOG, che ha fornito CPLEX.

Answer 4

Si consiglia di utilizzare il pacchetto python PuLP. Ha una bella interfaccia e puoi usare diversi tipi di algoritmi per risolvere LP.

Answer 5

lpsolve è il più facile per me. Non è necessario installare un solutore separato. Viene fornito con il pacchetto.

Answer 6

Per risolvere il problema di programmazione lineare, è possibile utilizzare il modulo scipy.optimize.linprog in SciPy, che utilizza l'algoritmo Simplex.

Answer 7

Le altre risposte hanno svolto un buon lavoro fornendo un elenco di risolutori. Tuttavia, solo il PuLP è stato menzionato come libreria Python per la formulazione di modelli LP.

Un'altra ottima opzione è Pyomo. Come PuLP, è possibile inviare il problema a qualsiasi risolutore e leggere la soluzione in Python. È anche possibile manipolare i parametri del solutore. Un compagno di classe e io abbiamo confrontato le prestazioni di PuLP e Pyomo nel 2015 e abbiamo scoperto che Pyomo poteva generare file .LP per lo stesso problema molte volte più velocemente rispetto a PuLP.