Lezione Cplex

Cplex
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
1
IBM ILOG Cplex:
•solver commerciale (scritto in C) dedicato alla risoluzione e
all’ottimizzazione di problemi matematici di vario tipo;
•fortemente utilizzato in ambito industriale e di ricerca;
•noto per la sua stabilità e le sue elevate prestazioni;
•risolve problemi di PLI tramite Branch&Cut; risolve rilassati
continui tramite avanzate routine riconducibili alla tecnica del
simplesso
Forum ufficiale:
http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2059
Documentazione (versione 10.1):
http://www.ieor.berkeley.edu/Labs/ilog docs/html/index.html
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
2
CPLEX come solver black-box
Problema
Modello matematico
CPLEX
Soluzione ottima
e altre info…
Soluzione ottima: ad ogni variabile del sistema viene attribuito una valore in
modo che la funzione obiettivo sia la migliore ottenibile in base ai parametri del
problema.
La soluzione potrebbe non essere ottima:
• la soluzione non esiste;
• Cplex potrebbe avere bisogno di troppe risorse (memoria o tempo).
Cplex fornisce ovviamente molte altre informazioni sulla soluzione stessa o
sulla risoluzione in sè (possono essere MOLTO utili…)
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
3
Interazione fra CPLEX e le vostre euristiche
Non vi è chiesto di risolvere il problema completo (CTQDP) tramite CPLEX!
Cplex potrebbe essere invece utile come risolutore di basso livello per
sottoproblemi del (CTQDP) o per rilassati continui. Le possibilità di interazione
sono molteplici e dipendono dalla struttura dell’euristica implementata
Problema
Problema
Rilassamento continuo
Meta-euristica
CPLEX
Individuo un
sottoproblema
CPLEX
Meta-euristica
Soluzione
Soluzione
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
4
Cplex e problemi PLI
Branch&Cut
-Costruzione di un albero decisionale in cui ogni nodo corrisponde ad un
sottoproblema (la radice è il rilassamento continuo del problema iniziale);
- Ad ogni sottoproblema risolto, se ci sono soluzioni frazionarie, vengono introdotti
tagli e il modello risultante viene risolto nuovamente (ogni nodo può prevedere più
risoluzioni);
- Se non ci sono più tagli da aggiungere, vengono generati i sottoproblemi tramite
branching su una delle variabili frazionarie;
- L’esplorazione dell’albero si continua finchè non si giunge alla soluzione ottima.
Elementi caratterizzanti del B&C di Cplex
- preprocessing (presolve + probing) nel quale vengono eliminati vincoli e variabili
inutili e analizzate le implicazioni logiche derivanti dall’assegnamento di valori interi
alle variabili intere;
- i tagli vengono introdotti nel modello in modo statico;
- procedimenti euristici eseguiti “occasionalmente” per migliorare i bound.
Risoluzioni di problemi PLI esplodono in senso combinatorio e
possono essere quindi molto difficili (o impossibili) da risolvere
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
5
Modalità d’uso
Modalità interattiva: applicazione con la quale è possibile interagire tramite
riga di comando. Si può descrivere il modello del problema (o importarlo da
un file esterno) tramite una determinata sintassi, configurare il risolutore
tramite l’impostazione di parametri opportuni e infine chiedere
l’ottimizzazione del modello specificato;
C Callable Library: libreria di funzioni C tramite le quali si può comandare
CPLEX e gestirne le funzionalità;
Concert Technology: le funzionalità di CPLEX sono disponibili
sottoforma di librerie (C++, .NET e Java) linkabili in modo dinamico.
Le ultime 2 modalità permettono di interfacciarsi col risolutore all’interno di un altro
software più ampio (embedding), lasciando ad esso il controllo del processo ed e
eliminando la necessità di una interazione realtime da parte di un utente.
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
6
Concert Technology
È necessario configurare il proprio IDE affinchè possa utilizzarla correttamente (le seguenti istruzioni
riguardano Visual Studio 2008, Cplex 10.1 e Concert Technology 2.3):
Dopo aver creato un nuovo Progetto, entrare nelle sue Proprietà e aggiungere:
C/C++ > General > Additional Include Directories:
<CPLEXDIR>\include
<CONCERTDIR>\include
C/C++ > Preprocessor > Preprocessor Definitions:
IL_STD
Linker > Input > Additional Dependencies:
wsock32.lib
<CPLEXDIR>\lib\x86_.net2005_8.0\stat_mda\cplex101.lib
<CPLEXDIR>\lib\x86_.net2005_8.0\stat_mda\ilocplex.lib
<CONCERTDIR>\lib\x86_.net2005_8.0\stat_mda\concert.lib
ATTENZIONE:
per utilizzare il risolutore
cplex101.dll deve
trovarsi nella stessa
directory dell’eseguibile
(oppure inserito nel
PATH di sistema)
Includere all’inizio del file:
#include <ilcplex/ilocplex.h>
ILOSTLBEGIN
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
7
Struttura del programma
La struttura di un’applicazione che utilizza questa tecnologia
prevede generalmente le seguenti fasi:
1. costruzione di un ambiente, ovvero un oggetto che si occuperà
in particolare della gestione ottimizzata della memoria di sistema;
2. creazione di un modello, ovvero un insieme di vincoli da
rispettare e una funzione obiettivo da ottimizzare;
3. impostazione dei parametri di controllo;
4. risoluzione del modello, ovvero il procedimento tramite il quale
CPLEX raggiunge la soluzione;
5. querying dei risultati (è possibile conoscere il valore di tutte le
variabili del modello, non solo della f.o.).
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
8
Ambiente e modello
Constructing the Environment: IloEnv
Un ambiente (un istanza di IloEnv) è il primo oggetto che viene creato. Si occupa
di gestire in maniera ottimizzata la memoria di sistema per i processi di Cplex. Si
può costruire un oggetto IloEnv dichiarando una variabile di tipo IloEnv.
IloEnv env;
L’ambiente deve essere disponibile per i costruttori di tutte le altre classi ILOG
Concert Technology!
Per distruggere l’oggetto ambiente:
env.end();
Creating a model: IloModel
È l’oggetto contenitore per tutti gli elementi del modello. Si può costruire un
oggetto IloModel dichiarando una variabile di tipo IloModel:
IloModel model(env);
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
9
È importante gestire questa eccezione!!
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
10
Elementi del modello
Dopo che un oggetto IloModel è stato costruito, può essere popolato da altri
oggetti che lo definiscono (variabili, vincoli, f.o.).
Alcune delle classi più importanti:
IloNumVar per rappresentare le variabili del modello;
IloRange per definire i vincoli (nella forma l <= expr <= u), dove expr è
un’espressione lineare;
IloObjective per rappresentare la funzione obiettivo.
Questi oggetti possono essere aggiunti al modello tramite:
model.add(object);
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
11
Variabili
Forma base più flessibile:
IloNumVar nome (env, lb, ub, type);
Es: IloNumVar x1 (env, 0.0, 40.0, ILOFLOAT);
Crea la variabile x1 con lower bound 0, upper bound 40 e di tipo ILOFLOAT
(variabile continua). Altri possibili tipi: ILOINT, ILOBOOL.
Per creare un array di variabili si usa:
IloNumVarArray xArray (env, size, lb, ub, type);
Forme più complesse (basate su composizione delle altre):
IloArray<IloNumVarArray> z_ik;
IloArray<IloArray<IloNumVarArray> > z_ikr;
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
12
Vincoli e Funzione obiettivo
Una volta create le variabili è possibile utilizzarle per costruire espressioni
lineari che identifichino i vincoli e la funzione obiettivo del problema
Vincoli:
IloRange r (env, 2, IloExpr expr, 4);
model.add(r);
IloConstraint v (x + y <= 67);
model.add(v)
IloExpr è una classe molto
utile per creare
espressioni complesse
(ad esempio quelle che
nascono da costruzioni
iterative all’interno di cicli)
Funzione obiettivo:
model.add (ObjFunc == c*x);
model.add (IloMinimize(env, ObjFunc));
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
13
Risoluzione
È necessario creare un oggetto IloCplex e estrarre il modello creato; si può fare
tutto in una sola istruzione:
IloCplex cplex(model);
È possibile settare alcuni parametri di risoluzione:
cplex.setParam(IloCplex::EpGap, 0.0);
Infine si lancia la risoluzione:
if ( !cplex.solve() ) {
env.error() << "Failed, Doh!" << endl;
throw(-1);
}
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
14
Querying dei risultati
Alcune funzioni utili per recuperare informazioni:
cplex.getStatus(); -ritorna lo stato della soluzione trovata
cplex.getObjValue(); -ritorna il valore della funzione obiettivo
cplex.getValue(IloExpr); -ritorna il valore dell’espressione in input
cplex.getValue(IloNumVar); -ritorna il valore della variabile in input
Consultare la documentazione per scoprire tutte le informazioni che può
restituire Cplex (costi ridotti delle variabili, bounds, preprocessing…)
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
15
Esempio PL:
Provare, provare subito
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
16
Esempio PLI:
x1, x2, x3 INTEGER
Provare, provare subito
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
17
Esempio
Differenze fra le due risoluzioni:
•Tempi (lo stesso problema rilassato richiede meno tempo)
•Soluzione e funzione obiettivo (le regioni di ammissibilità sono diverse)
•Metodo risolutivo (simplesso vs B&C)
Es: cerchiamo il Cutoff per il problema PLI e i costi ridotti delle variabili
per il problema PL
Manerba Daniele – Università degli Studi di Brescia – a.a. 2009-2010
18