Appunti del corso Ottimizzazione Combinatoria 2, prof. Antonio Sassano

SOLUZIONI OTTIME.

Differenza con l’enumerazione completa: è come se applicassi greedy ma con la possibilità di ripensarci, si può inserire

un elemento e toglierlo successivamente.

Branch&bound

Meccanismo che consente durante la costruzione dell’albero di enumerazione di escludere a priori delle combinazioni.

In pratica posso evitare di costruire tutto l’albero che ha come radice quella in cui sto perché il bound mi permette di

dire che in tutte quelle soluzioni sotto sicuramente non c’è quella ottima.

Il bound conferisce informazioni sulla migliore soluzione che si può costruire a partire dal nodo in cui sto (quindi se nel

sottoalbero potrebbe esserci una soluzione migliore di quella che ho continuo con l’enumerazione delle diverse

combinazioni, se non può esserci una soluzione migliore posso non enumerare tutto l’albero sotto).

Ripasso di OC1

Un PL01 è un problema nel quale ho una funzione obiettivo

lineare. La differenza rispetto a c(F) che abbiamo introdotto

nelle lezioni precedenti non è grandissima:

➖ cTx è un vettore {0,1}

➖ c(F) è un insieme

Se faccio la somma dei prodotti delle componenti con lo

stesso indice alla fine rimane solo la somma delle componenti

con coefficienti 1, quindi rimane esattamente F

PL01 è un problema di ottimizzazione combinatoria perché il numero delle soluzioni ammissibili è finito.

P è un poliedro in Rn, insieme delle soluzioni che soddisfano un insieme di disequazioni lineari

P è una formulazione di S se e solo se la sua intersezione con tutti i possibili vettori n-dimensionali di componenti

{0,1} (che sono al più 2^n) è esattamente uguale all’insieme delle soluzioni ammissibili S.

Nello spazio n-dimensionale se n è uguale a 3 le soluzioni ammissibili sono i vertici di un cubo.

[0,0] è il vettore di incidenza dell’insieme vuoto.

Questa è la rappresentazione con i diagrammi di Venn del grafico nella slide. Non

abbiamo rappresentato l’insieme A e B perché non è ammissibile in quanto fuori dal

poliedro ammissibile.

Un poliedro è sempre dato dall’intersezione di semispazi lineari, cioè equazioni del tipo

1

Il poliedro verde contiene tutte le soluzioni ammissibili del problema, separa quindi i vettori di incidenza indipendenti

da quelli dipendenti (ammissibili dai non ammissibili).

Anche il triangolo nero è un poliedro che contiene esattamente tutte e sole le soluzioni del problema.

Possiamo quindi avere infinite formulazioni dello stesso problema. La formulazione interna è migliore di quella esterna

Un PL01 è un problema con funzione obiettivo lineare e

soluzioni ammissibili {0,1}^n

Un problema di programmazione lineare è un PL01 se e solo

se le soluzioni ammissibili stanno in {0,1}^n

Otteniamo un rilassamento lineare del problema se eliminiamo

la condizione che il vettore debba avere componenti 0,1. Vale il

maggiore o uguale perché così facendo otteniamo il massimo

valore della funzione obiettivo nel poliedro (non per forza a

componenti 01).

Nel caso di funzione obiettivo lineare le curve di livello sono

rette. Geometricamente potrei risolvere il problema disegnando

il poliedro e le curve di livello (punti isovalore della funzione

obiettivo).

Così facendo il minimo sarebbe il punto che tocca l’ultima curva di livello che passa per il poliedro, questo sarebbe

però l’ottimo del problema rilassato. Se non è un punto a componenti 0,1 allora ho un lower bound.

Il punto che troviamo dipende ovviamente dalla formulazione scelta. Se scegliamo la formulazione verde otteniamo

un lower bound a componenti frazionarie, se scegliamo la formulazione nera (il triangolo) il lower bound è

esattamente l’ottimo intero. Per sapere quanto è buona una eventuale soluzione trovata

posso calcolare il gap, più questo è piccolo tanto migliore è la

soluzione trovata. L’obiettivo sarebbe quello di trovare una

soluzione con gap=0.

In genere Z* è ignota, il lower bound è il punto tra gli

ammissibili per cui ottengo il più piccolo valore della funzione

obiettivo. Z0 è la soluzione di cui sono in possesso.

Le formulazioni sono infinite, il problema vero è scegliere la

formulazione migliore.

La formulazione migliore è quella possibilmente più vicina

all’insieme dei punti 0,1.

2

Esiste una formulazione ottima, è un insieme convesso, un poliedro che ha la proprietà di essere contenuto in ogni

altra formulazione possibile del problema. In genere le formulazioni ottime si trovano solo per i problemi facili.

Formulazione rango

Cerco di caratterizzare gli indipendenti con una serie di disequazioni lineari.

Il rango caratterizza l’insieme di indipendenza, quindi se abbiamo la funzione rango possiamo dire chi è un

indipendente e chi no (basta calcolare la funzione rango per l’insieme da studiare: se rango uguale alla cardinalità

dell’insieme allora questo è un indipendente). Le basi rappresentano un sistema di indipendenza, se vogliamo

verificare che un insieme è un indipendente basta controllare che appartenga ad una base.

Un insieme F appartenente ad S è un indipendente se e solo se la

cardinalità di F intersezione X è minore o uguale del rango di X

per ogni X appartenente a Γ.

Dimostrazione:

Se F appartiene ad S allora F intersezione X appartiene ad S per

ogni X appartenente a Γ. Vale l’ereditarietà, l’insieme F è anche lui

un indipendente, X potrebbe esserlo oppure no (lo è in quanto

sottoinsieme di F). Siccome è un indipendente la cardinalità di F

intersezione X è uguale al rango di F intersezione X, ma questo è

minore o uguale del rango di X per ogni X appartenente a Γ.

Il viceversa si può dimostrare così: se F non appartiene ad S

esiste una X contenuta in Γ tale che rango di F intersezione X è

strettamente maggiore del rango di X. Siccome nego entrambe le

affermazioni cambio il verso della disuguaglianza.

Se F non appartiene ad S (cioè se non è un indipendente) la sua cardinalità è maggiore del suo rango. Per X che

coincide con F abbiamo che la cardinalità dell’intersezione tra F ed F è uguale alla cardinalità di F, quindi la che è

maggiore del rango di F che però dovrebbe essere uguale al rango di X, questo è impossibile pertanto è vero il

teorema scritto sopra. La S a sinistra è un insieme di vettori, la S a destra è una

famiglia di sottoinsiemi.

A è un insieme. A è la matrice del sistema di disequazioni

La cardinalità di F intersezione A è il prodotto interno dei vettori

di incidenza di F e di A. Nell’esempio abbiamo due vettori nello

spazio n=4.

L’intersezione tra F e A vuol dire tutte le volte che compare un

uno relativo allo stesso elemento in entrambi i vettori. Se faccio

il prodotto interno calcolo la cardinalità dell’intersezione.

In pratica sommo i prodotti delle componenti con lo stesso

indice. Possiamo prendere un qualunque vettore x, esso

appartiene ad S se e solo se la sommatoria è minore del rango.

3

Nel poliedro devono starci i vettori di incidenza degli indipendenti,

tutti gli altri devono stare fuori.

Abbiamo detto che un vettore x appartiene ad A se e solo se la

sommatoria delle sue componenti è minore o uguale del rango di

A.

Il vettore di incidenza di un insieme dipendente dovrà violare

almeno una delle disequazioni.

Questa formulazione si chiama FORMULAZIONE RANGO perché

Attraverso l’eliminazione di il termine a destra di tutte le disequazioni è il rango di A.

alcuni vincoli Sappiamo che F appartiene ad S (cioè è un indipendente) se e

solo se F non contiene un circuito.

Se C è un circuito di S allora il suo rango è pari alla cardinalità

meno 1.

Il poliedro Pc lo ottengo a partire dal poliedro rango dal quale

taglio via delle disequazioni, tengo soltanto quelle che sono un

circuito. Pc è un poliedro che rispetto al poliedro precedente è

più grande (ha meno disequazioni). La formulazione rango è

contenuta nella formulazione circuiti.

Poiché abbiamo costruito Pc togliendo dei vincoli dalla

formulazione rango dobbiamo dimostrare che Pc è ancora una

formulazione.

F è un indipendente se e solo se il suo vettore di incidenza

appartiene a Pc.

Dimostrazione:

F appartiene ad S implica che Xf (vettore di incidenza) appartiene a Pr, allora a maggior ragione apparterrà a Pc

(perché Pc contiene Pr).

In ogni insieme dipendente (insieme che non appartiene ad S) esiste sicuramente un circuito quindi se F non

appartiene ad S allora F contiene sicuramente un circuito. Se esiste un circuito C contenuto in F allora Xfe=1 per ogni

e appartenente a C. Questo vuol dire che la sommatoria per e appartenente a C di Xfe è esattamente uguale alla

cardinalità del circuito. Se questo è vero allora è violato un vincolo e Xf non appartiene a Pc.

Abbiamo dimostrato che se F è un dipendente allora il suo vettore di incidenza non appartiene al poliedro, se è un

indipendente allora appartiene al poliedro, quindi Pc è una formulazione.

Gli elementi nei quadratini costituiscono un insieme stabile.

Non abbiamo una matroide perché non tutte le basi hanno la

stessa cardinalità.

I circuiti sono insiemi di coppie {u,v} tali che u,v appartengono

ad E.

Il primo vincolo dice che non possiamo scegliere

contemporaneamente sia u che v, dobbiamo eliminarne almeno

uno. 1 viene dal fatto che la sommatoria degli elementi x deve

essere minore o uguale della cardinalità meno 1.

4

Simmetrico dello stabile, insiemi di archi a coppie non incidenti

nello stesso nodo.

Gli archi rossi e quelli neri sono due matching diversi.

Due archi sono dipendenti quando incidono nello stesso nodo.

I circuiti sono cicli, quindi se ho un circuito non posso scegliere tutti i suoi

elementi, devo mollarne almeno uno.

Esempio di capital

budgeting I coefficienti devono essere positivi. I circuiti (che si chiamano

anche cover) sono insiemi di progetti non compatibili ma tali che

ogni sottoinsieme è compatibile.

Il concetto di budget è contenuto nel concetto di cover. In pratica

trovo l’insieme minimo di progetti che non posso fare.

Voglio sapere quali sono gli archi che posso buttare via lasciando

il grafo connesso.

Un insieme la cui rimozione disconnette il grafo è formato dai 3

archi rossi, quindi quelli definiscono un insieme dipendente, gli

indipendenti sono quelli che posso togliere senza sconnettere il

g