Ottimizzazione Combinatoria
Argomento tesina
A.A. 2009-2010
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Corso di Laurea in “Ingegneria Gestionale”
1
Informazioni
Tutte le informazioni relative alla tesina si trovano nella sezione tesina
della pagina del corso
http://www.dis.uniroma1.it/~or/gestionale/OC
Le tesine si svolgono a gruppi al più di tre persone.
Il tema della tesina verrà illustrato a lezione. Per lo svolgimento della
tesina ciascun gruppo potrà far uso di tutte le metodologie e gli algoritmi
illustrati nell’arco del corso.
L’implementazione della strategia di soluzione per il tema assegnato
dovrà essere necessariamente nel linguaggio AMPL, che verrà
interpretato dall’interprete AMPL.
L’unico solutore che può essere impiegato nell’implementazione della
strategia di soluzione è CPLEX.
2
Assegnazione tesina
Per l’assegnazione della tesina, ciascun gruppo deve inviare un’e-mail di
richiesta contenente:
- nome, matricola, corso di laurea e indirizzo e-mail dei membri del
gruppo;
- il nome e l’indirizzo e-mail di un membro del gruppo indicato come
referente.
Per finalizzare l’assegnazione, ciascun gruppo riceverà un’e-mail di
assegnazione contenente:
- istanza di problema (dati) da risolvere
- il formato dei dati
Al momento della ricezione dell’e-mail di assegnazione, la tesina sarà
considerata assegnata al gruppo.
Ogni studente può far parte di un solo gruppo e ogni gruppo lavora su
una sola istanza di problema.
3
Presentazione tesina
Per presentare la tesina, ciascun gruppo deve inviare un’e-mail di
presentazione della tesina contenente:
- documento (minimo 2 pagine, massimo 8 pagine) o presentazione
(minimo 3 slide, massimo 12 slide) che descriva:
 algoritmo di soluzione
 dettagli implementativi
 risultati ottenuti per l’istanza di problema assegnata.
- file di codice (.mod, .run, … ) dell’algoritmo di soluzione e file di dati
(.dat, .txt, … ) dei dati in input e in output per l’istanza di problema
assegnata.
I file di codice e di dati devono essere corretti e coerenti tra loro.
4
Valutazione tesina
La valutazione della tesina si baserà fondamentalmente su:
- analisi di tutto il materiale inviato nell’e-mail di presentazione
- colloquio (durata massima 30 minuti) con il docente, cui devono
necessariamente partecipare tutti i membri del gruppo;
I criteri di valutazione saranno:
- valutazione dell’approccio di soluzione ( 40% )
- valutazione dell’implementazione ( 30% )
- valutazione dei risultati ( 20% )
- valutazione della presentazione ( 10% )
Il risultato della valutazione verrà comunicato tramite e-mail a tutti i
membri del gruppo e i risultati verranno pubblicati sulla pagina del corso.
La valutazione della tesina è condizione necessaria per sostenere l’esame
di Ottimizzazione Combinatoria.
5
Tema della tesina
Una grande azienda di produzione ha diverse sedi sul territorio nazionale.
A fronte dell’esigenza di collegare
rapidamente e in maniera sicura le
diverse sedi, l’azienda ha deciso di
realizzare una rete privata virtuale
sulla rete Telecom (già esistente).
Una rete privata virtuale
garantisce una connessione sicura
tra due siti della rete ed è una
soluzione molto adottata in campo
business.
Una rete virtuale presenta diversi
vantaggi ma ha un costo.
6
Tema della tesina
Ogni collegamento punto-punto è caratterizzato da:
- una capacità trasmissiva
espressa in Mbit/s
- un costo
L’azienda ha un budget massimo B
da spendere per la realizzazione
della rete privata virtuale
L’obiettivo dell’azienda è quello di
realizzare una rete privata virtuale
- rispettando il vincolo di budget
- massimizzando la capacità
trasmissiva della rete virtuale.
La capacità trasmissiva della rete
virtuale è definita come somma
delle capacità trasmissive dei
collegamenti che la compongono.
(1.1,1.5)
(3.1,1.7)
(2.6,3.4)
(2.6,2.4)(2.1,0.8)
(1.6,4.6)
(2.6,4.4) (2.7,1.1)
(2.7,2.1)
(2.3,1.3)
(1.6,6.4)
(2.1,5.9)
(2.2,1.6)
(2.2,3.4)
(2.2,3.4)
(2.6,2.4)
(3.5,1.7)
(1.5,1.6)
(2,5.2)
(2.8,2)
(2.1,1.2)
(3.6,2.4)
(0.6,0.4)
7
Tema della tesina
Rappresentiamo la rete come un grafo G(N,A) connesso in cui ciascun
arco ij A è caratterizzato dalla capacità trasmissiva cij e dal costo wij
Vogliamo determinare il sottografo connesso il cui costo totale non superi
il budget B e tale che la capacità trasmissima totale sia massima.
costo totale = somma del costo degli archi
capacità trasmissiva totale =
somma delle capacità trasmissive degli archi
Sia S l’insieme dei sottografi connessi ricoprenti
di G.
S = { x  {0,1}
: x vettore di incidenza di un
sottografo connesso ricoprente di G}
|A|
8
Tema della tesina
Il problema si può formulare come un problema di ottimizzazione
combinatoria.
vincolo di budget
(knapsack)
T
max c x
wT x  B
xS
qual è la
formulazione di
S?
S = { x  {0,1}
: x vettore di incidenza di un
sottografo connesso ricoprente di G}
|A|
9
“Grafo connesso ricoprente”
Grafo connesso G(N,A)
S = { insiemi di archi la cui rimozione non
disconnette il grafo G(N,A) }
v3
v8
v2
v1
v6
v4
v9
v5
G(N,A)
TS  H ( N ,T ) connesso
Circuiti = Tagli minimali
v7
Formulazione circuiti:
  y e  | K | 1, K taglio
eK
PC  
y e  0 , e  E
10
“Grafo connesso ricoprente” (II)
Grafo connesso G(N,A)
TS  H ( N ,T ) connesso ricoprente
v3
v8
v2
v1
v6
v4
v9
v5
  y e  | K | 1, K taglio
eK
PC  
y e  0 , e  E
v7
G(N,A)
y  PC  0 ,1
|E |
 x  ( 1|E|  y )
x vettore di incidenza degli archi di un
sottografo connesso ricoprente
  xe  1 K taglio
P   eK
0  xe  1
eE
Formulazione (“tagli” ) di :
 x : x  1|E|  y , 
S
|E |  11
y  PC  0 ,1 