Appunti Ottimizzazione combinatoria

Come ottenere vari possibili lower bounds

• Rilassamento lineare
• Rilassamento lagrangiano
• Programmazione semi definita
• Metodi combinatorici e “ad hoc”

Il rilassamento lineare si ottiene tramite la formulazione lineare e la teoria della dualità. Per passare da PLI a PL si rilassano i vincoli di interezza delle variabili. Il rilassamento lineare per un problema di PL01 si ottiene rilassando i vincoli booleani delle variabili.

Formulazione lineare

13" SP140P è una formulazione di S (S è l’insieme delle soluzioni ammissibili) se e solo se =,

Un poliedro P è una formulazione se e solo se:

• Contiene tutti i vettori di S 1340 S
• Non contiene alcun vettore di -.

Osservazione: Posso avere infinite formulazioni di un problema di PL011ynyP140minheix xeS]=mimhcX ** *Cx: = =: ,LB(P)= XEP3mim[CTX =: VALORE OTIMO DELLAA SOLUZIONE DEL PL01problema di PL (rilassamento lineare)LB(P)

Allora: LB(P) è un lower bound per z*z

Criteri di qualità della formulazione lineare

P1 migliore di P2 se e solo se LB(P1)>LB(P2)

Criterio 1

Il problema di questo criterio è la dipendenza dalla funzione obiettivo, che a priori non può essere prevedibile, pertanto introduciamo il criterio 2 VceRm

Criterio 2

P1 migliore di P2 se e solo se LB(P1)>LB(P2)

Ciò è equivalente al criterio 3, il quale enuncia:

P1 migliore di P2 se e solo se P1 C P2

Criterio 3

Pertanto possiamo dire che esiste una formulazione che è contenuta in ogni altra cioè la formulazione ottima PS=Conv(s)IP PDISAFORMULAZIONECome verificare che una formulazione è ottima:

1. Ogni disequazione del sistema Ax<b è implicata nel sistema Dx<d
2. Oppure che argmin{ c x: x P} S per ogni c R=/mT EE
3. Oppure che ogni vertice di P ha componenti 0-1 (noi analizzeremo questa)

Relazione di connessione

u connesso a v se e solo se esiste un cammino con estremi u e v

“Connesso a”:

Relazione di equivalenza R per rendere simmetrica la relazione è

Proprietà: necessaria la contemporanea esistenza di un

1. Transitiva: uRv vRt ==> uRt cammino orientato da u a v e di uno da v ad u
2. Riflessiva: uRu
3. Simmetrica: uRv se e solo se vRu (questa proprietà non vale per cammini orientati)

Relazioni di connessione forte

uR v se e solo se u fortemente connesso a v quindi se e solo se esiste un cammino orientato da u

(R è una relazione di equivalenza)

a v e uno da v a u

Proprietà:

1. Transitiva: uRv vRt ==> uRt
2. Riflessiva: uRu
3. Simmetrica: uRv se e solo se vRu

Complessità

Il tempo di esecuzione di un algoritmo è dato dal numero di passi necessari per determinare la soluzione associata ad un’istanza. Definiamo per prima cosa che cos’è un algoritmo: una procedura in grado di individuare in passi successivi una soluzione per una generica istanza di un problema.

Definiamo l’istanza cioè l’insieme delle informazioni in ingresso (dati); definiamo anche la soluzione cioè una particolare “proprietà” F(I) dell’istanza I. È necessario che un algoritmo sia corretto, cioè che produca sempre F(I) ed efficiente in termini di spazio e tempo.

La complessità di un algoritmo è data dal numero di passi necessari per determinare la soluzione di una generica istanza di dimensione size(I); quindi ci serve una funzione della sola dimensione: c(size(I)).

Dimensione size(I)= numero di celle necessarie a rappresentare i dati in ingresso.

Complessità c(size(I))= media tra caso peggiore e caso migliore

Modello di calcolo e classi di complessità

Una Macchina di Turing (MdT) è un meccanismo calcolatore astratto formato da:

• Nastro (infinito, ogni cella contiene un simbolo)
• Testina (legge o scrive il nastro e si sposta rispetto a lui)
• Programma (per ogni stato e simbolo in input, una regola che dice cosa fare)
• Stato (appartiene ad un insieme di possibili stati)

La macchina ha uno stato iniziale, e dato un input, effettua una serie di operazioni producendo l’output (che potrebbe richiedere tempo infinito).

La tesi di Church postula che tutte le funzioni effettivamente calcolabili siano esprimibili con una Macchina di Turing.

• MdT deterministica: dato uno stato e un input, esegue una determinata operazione
• MdT non deterministica: dato uno stato e un input, può eseguire una tra varie determinate operazioni

Classi di complessità: a seconda dell’andamento di complessità, usando il modello di MdT si definiscono le classi di complessità: Classe P: problemi risolubili in tempo polinomiale su MdT deterministica) ;Classe NP:problemi risolubili in t