Che materia stai cercando?

Appunti del corso di Ottimizzazione Combinatoria 2 prof Antonio Sassano

Il file contiene gli appunti di tutte le lezioni di Ottimizzazione Combinatoria II del professor Antonio Sassano da marzo a maggio 2018. Consiglio (se possibile) di stampare il file a colori. Appunti basati su appunti personali del publisher presi alle lezioni del prof.

Esame di Ottimizzazione combinatoria II docente Prof. A. Sassano

Anteprima

ESTRATTO DOCUMENTO

Sistemi di indipendenza

Rango, Matroidi e Greedy

Proprietà dei sistema di indipendenza: il poliedro contiene

tutte le soluzioni ammissibili e non contiene quelle non

ammissibili.

Il sistema rango è una famiglia di sottoinsiemi che deve avere la proprietà di essere ereditaria. Il rango di una matrice

è la dimensione della più grande sottomatrice quadrata non singolare.

Quindi il rango è il massimo numero di righe e di colonne che formano una sottomatrice il cui determinante è diverso

da 0.

Il rango è il numero massimo di colonne linearmente indipendenti.

Il rango di X, dove X è un qualunque insieme appartenente a Γ, è la massima cardinalità di un insieme indipendente

contenuto in X. X infatti potrebbe non essere indipendente, col rango prendiamo il più grande indipendente contenuto

in esso, la sua cardinalità definisce il rango di X.

Proprietà del rango: (possibile domanda di esame) ➖ Il rango dell’insieme vuoto è 0, per ogni X,Y contenuto in Γ

sono valide le seguenti proprietà:

➡ Il rango d X è minore o uguale del rango di Y se X è

contenuto in Y (rango non decrescente)

➡ Il rango di un insieme X è uguale alla cardinalità di X se e

solo se X è appartenente ad S. Se X è un indipendente allora

il rango corrisponde alla sua cardinalità. Se il rango è diverso

allora X è un dipendente, quindi il rango sarà strettamente

minore della cardinalità.

➡ I circuiti sono dipendenti, il loro rango deve essere minore della cardinalità. Se tolgo un solo elemento dal circuito

deve essere un indipendente, quindi il rango di X è cardinalità meno 1. Le due equazioni caratterizzano i circuiti, se X

è un circuito allora valgono entrambe. Solo la prima non bastava perché se vale rango = card -1 non

necessariamente X è un circuito. Infatti devo poter togliere un qualunque elemento, non uno in particolare. Solo la

seconda non bastava perché non esclude il fatto che il rango possa essere uguale alla cardinalità, quindi X potrebbe

essere un indipendente e non un circuito. Il lower rank è applicabile ad un qualunque insieme X

appartenente a Γ. Mi dice come sono fatti gli insiemi che non

appartengono ad S.

Prendiamo qualunque sottoinsieme X appartenente a Γ, il

lower rank è la minima cardinalità di un insieme T contenuto

in X e appartenente ad S, ma deve avere la proprietà che se

lo estendo a T unione e per qualunque e appartenente ad X

ma non a T, allora questo non appartiene ad S.

In pratica è la minima cardinalità contenuta in X tale che

appena gli aggiungo un elemento (che appartiene ad X ma

non a T) non appartiene più ad S.

Per ogni X lower rank minore o uguale al rango.

Il lower rank è il minimo insieme indipendente massimale di X.

In A il lower rank è 1 perché c’è il pallino verde col cerchio continuo intorno.

MATROIDE: per definizione l’insieme dei sistemi di indipendenza nei quali il lower rank è uguale al rango per ogni

insieme X è una matroide.

L’algoritmo Greedy nel caso in cui l’insieme delle soluzioni ammissibili è una matroide trova sempre la soluzione

ottima. 1

Dato il grafo un insieme stabile è dato da tutti i singoli nodi

cerchiati a tratto continuo.

I due sottoinsiemi tratteggiati non sono insiemi stabili, uno dei

due è un ciclo.

α di un sottoinsieme è il più grande indipendente che posso

trovare

Lower rank è minore del rango, se fosse 0 e la cardinalità

dell’insieme vuoto non potrei aggiungergli elementi di H e

lasciarlo indipendente.

Che archi dovrei aggiungere ad H per far sì che il rango

rimanga 2 ma il lower rank diventi 1?

Il secondo esempio di Matching number, il simbolo è η. Si tratta di insiemi

di archi non di nodi come prima. Il matching di massima cardinalità in K è

1. In H è 2 perché posso trovare due archi che non vanno nello stesso

nodo. Foreste: insiemi di archi che non contengono un ciclo

(sottografi aciclici).

Il rango di A è il numero di archi in una foresta massimale F

contenuta in A.

A1 insieme di archi in rosso non definiscono cicli, allora A1 è

una foresta, un albero ricoprente.

A2 non è una foresta perché c’è un ciclo. Se tolgo l’arco a-b

diventa una foresta, due alberi ricoprenti uno per ciascuna

componente connessa.

Il rango è pari alla cardinalità dell’insieme se quest’ultimo è

una foresta.

Gli indipendenti sono insiemi di progetti compatibili col

budget.

Se 8 progetti hanno rango 3 vuol dire che al massimo posso

fare 3 progetti altrimenti vado fuori budget.

È un circuito perché comunque tolgo uno tra a,b,c trovo un

indipendente. 2

Sistemi di indipendenza: S = { {1,2},{1,5},{1},φ... }

Potrei scriverli anche come vettori

Per capire se sono basi devo essere sicuro che non sono contenuti in altri

sottoinsiemi di Γ

Un circuito è un indipendente minimale, deve essere un sottoinsieme di Γ: {5,4} non è

un circuito perché 4 non è un indipendente, {2,5} è un circuito

L’insieme X={1,3,4} è un dipendente, non è un circuito. La cardinalità del più grande

indipendente contenuto in X è r(X)=1. Lower rank: cerco un indipendente massimale

in X, lr(X)=1, l’insieme vuoto non è un indipendente massimale infatti può crescere se

ci aggiungo 1

{3} è un circuito, il suo unico sottoinsieme è l’insieme vuoto

Se all’insieme X aggiungessimo anche l’insieme {3,4} (quindi anche {3},{4} in S)

r(X)=2, lr(X)=1 ({3,4} è un indipendente ma non di cardinalità minima, quindi lr=1)

Esercizio d’esame

Costruire un grafo e mostrare un sottoinsieme tale che il rango è 2 ed il lower rank 1.

S = { φ,{1},{2},{3},{4},{5} }

Stabili: {2,5} {1} {1,4} {3,5} {1,3} {2,4} (tutte le coppie che non hanno archi che li collegano

X è un indipendente

{1,2} è un circuito (tutte le coppie collegate da un arco)

r(X)=2 lr(X)=2 (indipendente massimale di cardinalità min in X)

Devo quindi trasformare, aggiungo l’arco 1-4 che abbassa il lower rank, ora 1 è un indipendente massimale quindi

r(X)=2 e lr(X)=1 c è un vettore che ha tante componenti quanti sono gli

elementi del sistema di indipendenza per Γ=1,...,m

Il vettore c associa un valore a ciascun elemento del sistema

di indipendenza, quindi pesa gli elementi (costi o vantaggi a

seconda se minimizzo o massimizzo)

Sfruttiamo la proprietà di linearità (funzione obiettivo

lineare quindi vale la sovrapposizione degli effetti):

Se ho dei vantaggi per ciascun elemento che scelgo posso

fare la somma sei vantaggi

Uno stabile è ottimo quando la sua funzione c è la migliore tra

quelle di tutti gli altri stabili.

Massimo sottoinsieme indipendente è un problema di

ottimizzazione combinatoria con funzione obiettivo lineare, questi

problemi hanno soluzioni ammissibili in numero finito (2^n)

Se stiamo massimizzando e abbiamo degli elementi con peso negativo posso toglierli e risolvere il problema senza

perché in ogni caso la soluzione ottima F* non conterrà quegli elementi. Potrei eliminare anche gli elementi con peso 0.

Se Ch fosse minore di 0 potrei prendere la soluzione c(F*-h), questa è una nuova soluzione, il peso di quest’ultima è il

peso della vecchia meno h, che quindi è maggiore di c(F*). Ecco quindi la dimostrazione del fatto che possiamo

togliere gli elementi di peso negativo e risolvere il problema. Dal punto di vista della dimostrazione dimostriamo che

possiamo togliere solo gli elementi con peso negativo, non diciamo nulla su quelli con peso uguale a 0.

3

Dobbiamo risolvere il problema quindi trovare il massimo

sottoinsieme indipendente che massimizza la funzione

obiettivo. Questo in generale è un problema difficile in quanto

non esiste un polinomio che limita il numero di passi da fare

per trovare la soluzione ottima.

Si dice che tutti gli algoritmi noti per questo problema siano

esponenziali, quindi non riusciamo a dire che il numero di

passi è limitato.

Dobbiamo accontentarci di soluzioni accettabili date dalle

euristiche senza avere la certezza che quelle siano

effettivamente le migliori.

Greedy al primo passo ordina gli elementi di Γ per pesi decrescenti e inizializza l’insieme T come insieme vuoto.

Poi inizia col ciclo for: fa n passi dove n è il numero degli elementi. Se T(i-1) unione ei appartiene ad S allora

aggiunge ei a T(i-1).

In pratica se ei è un indipendente allora lo aggiunge a T altrimenti lascia invariato T per il passo successivo. È molto

importante avere un sistema di indipendenza per poter avere Tn soluzione greedy.

Tn è una base di S, cioè Tn è un insieme tale che se ci aggiungo uno qualsiasi degli elementi che greedy non ha

aggiunto trovo un dipendente. Non c’è una dimostrazione formale di questo.

Tutte le volte che un elemento viene aggiunto a T quell’elemento rimane nella soluzione, non viene tolto nei passi

successivi.

Greedy è una soluzione euristica, potremmo aver trovato la soluzione ottima oppure no, ma è una soluzione

soddisfacente. Ogni nodo ha un suo valore (potrebbe essere l’insieme delle

offerte in un’asta combinatoria, ognuno dei nodi rappresenta

un’offerta, ovviamente non posso soddisfare

contemporaneamente due nodi collegati da un arco).

Applico greedy:

➖ Ordino i nodi per pesi decrescenti (a parità di pesi scelgo

arbitrariamente prima uno poi l’altro)

➖ Inizializzo T0 come insieme vuoto

➖ per T1 mi devo chiedere: se aggiungo v1 ottengo un

indipendente (ovvero un insieme stabile)? Se sì (cioè se non ci

sono archi con gli elementi già presenti in T) aggiungo v1, quindi

T1 è composto da v1

➖ T2: se aggiungo v2 a T1 è un indipendente? Se sì aggiorno T altrimenti lascio così

➖ Procedo fino alla fine degli elementi 4 La soluzione ottima nella maggior parte dei casi non la

conosciamo, vogliamo limitare inferiormente e

superiormente il valore del rapporto tra le soluzioni.

Il rapporto tra lower rank e rango di X è lo stesso

rapporto che c’è tra le due soluzioni (greedy e soluzione

ottima). Quindi il rapporto tra greedy e la soluzione

ottima è sempre minore o uguale ad 1, ovvero la

soluzione ottima ha sempre un peso maggiore o uguale

di quella greedy.

Nel caso di una matroide l’algoritmo greedy trova

sempre la soluzione ottima in quanto il rapporto tra Tn

ed F* è compreso tra 1 e 1.

Un sistema di indipendenza è una matroide se e solo se

con greedy si trova l’ottimo per ogni funzione obiettivo.

Nella dimostrazione i rettangoli verdi rappresentano i Γi in ordine crescente di peso per indici crescenti.

Prendiamo l’i-esimo dei Γi, l’intersezione di Γi con la soluzione ottima F* è Fi, ovvero l’insieme che l’algoritmo greedy

ha costruito al passo i.

Poiché Fi è un indipendente (appartiene ad S, è un indipendente perché è un sottoinsieme della soluzione ottima)

abbiamo che la sua cardinalità è minore o uguale del rango di un insieme che lo contiene. Sappiamo che e è un

indipendente quindi il rango è uguale alla cardinalità, qui diciamo che la cardinalità è minore o uguale del rango

perché Fi è contenuto in Γi. Inoltre per costruzione abbiamo detto che Ti è contenuto in Γi (Ti è fatto dagli elementi

aggiunti fino al passo i), poiché ogni elemento che appartiene a Γi ma non a Ti ha la proprietà che Ti unione e non

appartiene ad S, ovvero Ti massimale. Se è un indipendente massimale in Γi allora il suo lower rank è maggiore o

uguale della sua cardinalità. Un elemento ek appartiene alla soluzione greedy se e

solo se l’insieme degli elementi di Tk che non

appartengono a T(k-1) è diverso dall’insieme vuoto,

quindi solo se T(k-1) è cresciuto di esattamente un

elemento.

La funzione obietto calcolata in Tn è la somma di tutti i

pesi degli ek appartenenti a Tn (sovrapposizione degli

effetti, funzione obiettivo lineare). Nella seconda parte

dell’uguaglianza vengono sommati tutti i pesi degli ek

se la differenza è uguale ad 1 (quindi vengono sommati

solo i pesi degli elementi che appartengono alla

soluzione ottima, per gli elementi non appartenenti la

differenza vale 0).

È una SOMMATORIA TELESCOPICA:

Un elemento compare 2 volte ma con segni discordi

(una volta come k e una come k-1), gli unici elementi

che compaiono una sola volta sono il primo e l’ultimo.

➖ Il peso di en non è accoppiato con nessun altro

elemento quindi nel primo passaggio lo mettiamo fuori

dalla sommatoria.

➖ Sostituisco la cardinalità col lower rank perché

quest’ultimo è minore o uguale, quindi otteniamo

un’espressione minore o uguale della precedente

(questa affermazione è vera solo se tutti i coefficienti

sono positivi, in questo caso lo sono perché quelli

negativi li abbiamo eliminati all’inizio, nelle sottrazioni i

valori sono tutti positivi perché gli ek sono ordinati in

maniera decrescente.

5

➖ se q(S) è pari al minimo del rapporto lower rank / rango allora q(S) è minore o uguale di ciascun rapporto per ogni

X contenuto in Γ. Possiamo quindi sostituire al lower rank q(S)*r(Γn). Siccome q(S) è uguale per tutti lo metto in

evidenza. ➖ Ora sostituiamo il rango con la cardinalità

➖ Facciamo i passaggi analoghi a quelli di prima ma al

contrario

F0 non è definito, è l’insieme vuoto

La sommatoria finale è uguale al valore della soluzione

ottima pur non conoscendo quest’ultima, dunque vale la

disuguaglianza.

Questo teorema stabilisce quanto è buona la soluzione

greedy rispetto a quella ottima.

Il problema di matching non è una matroide, q(S) vale 1/2, è

un numero piccolo, quindi al più troviamo la metà della

soluzione ottima, a seconda della situazione questo potrebbe

andare bene.

Teorema di Edmonds

Se siamo in grado di verificare che ogni vettore c messo

come funzione obiettivo di un sistema di indipendenza

l’algoritmo greedy dà la soluzione ottima allora siamo in

presenza di una matroide.

In una matroide tutte le basi hanno la stessa cardinalità.

Potrebbe essere vero che prendo un sistema di indipendenza

che non è una matroide, prendo una funzione c, applico

greedy e trovo la soluzione ottima.

Se non è una matroide deve esistere almeno un insieme X per

cui il lower rank è minore del rango.

Se è vero che lower rank minore del rango allora esistono due

insiemi massimali indipendenti contenuti in X, uno che mi

determina lower rank (il più piccolo indipendente massimale)

e uno che mi determina r.

Abbiamo quindi questi due insiemi e vogliamo costruire una

funzione obiettivo.

La soluzione ottima del greedy Tn è B1 mentre la soluzione

ottima del problema è diversa da B1, cerchiamo quindi di

dimostrare che esiste una soluzione migliore di B1.

Assegniamo a tutti gli elementi di B1 peso 1+δ, agli elementi

che appartengono a B2 ma non a B1 mettiamo peso 1, a tutti

gli altri elementi che non appartengono né a B1 né a B2

assegniamo peso 0.

Se applichiamo greedy a questo punto esso rimane bloccato

in B1, quindi Tn=B.

Posso aggiungere un elemento qualunque (in o fuori da X) a

B1 e ottenere ancora un indipendente. Il peso di Tn quindi

Dimostriamo che rimane uguale a quello di B1 ma il peso di B2 è maggiore,

il peso di B1 è

minore del peso di quindi la soluzione greedy non è la soluzione ottima perché

B2. ne abbiamo trovata una che ha peso maggiore.

6

Sistemi di indipendenza

Formulazioni

Un problema di ottimizzazione combinatoria potrebbe essere risolto ad esempio per ENUMERAZIONE COMPLETA.

Dovremmo prendere tutte le soluzioni, guardarle una per una e scegliere la soluzione ottima. Questo sistema funziona

solo se le soluzioni ammissibili sono in numero limitato. Per un problema di matching ad esempio le soluzioni

ammissibili sono in numero esponenziale, quindi in questo caso l’enumerazione completa è inefficiente.

Se il problema è illimitato inferiormente o superiormente non c’è possibilità di trovare una soluzione ottima.

Nel caso in cui un problema sia illimitato diciamo allora che il problema non ha soluzione.

Un problema di ottimizzazione combinatoria si risolve così:

➖ si crea un albero di enumerazione in cui si fissano le variabili 0 e 1. Le variabili sono ovviamente gli elementi degli

insiemi

➖ parto con una prima ipotesi: la soluzione ottima contiene l’elemento 1

➖ seconda ipotesi la soluzione ottima contiene l’elemento 2

➖ così via, provo con tutti gli elementi in tutte le combinazioni, costruisco quindi un ALBERO CON TUTTE LE

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

grafo.

L’insieme di archi T che se rimosso lascia T barrato che definisce

ancora un grafo connesso. T unione T barrato è l’insieme A, T

intersezione T barrato è l’insieme vuoto.

I circuiti sono tagli minimali.

5

Possono contenere cicli ma non cicli con costi negativi.

Il sistema della formulazione circuiti è uguale a quello delle

foreste solo che invece di ciclo c’è scritto ciclo negativo.

Pr è un circuito? No perché dovrebbe valere 3. Il più grande

indipendente vale 2, appena ne troviamo 3 andiamo fuori budget.

Le disequazioni 4,5 sono disequazioni rango.

Quella minore o uguale di 4 non è sicuramente una disequazione

rango perché ha dei coefficienti diversi da 1.

Prendiamo l’insieme A=1,2,3 e determiniamo il rango, troviamo quindi il più grande indipendente all’interno:

1,2 e 1,3 sono entrambi non compatibili con il budget ma 2,3 sì quindi il rango è 2.

La disequazione y1+y2+y3<=2 non c’è perché è implicata dalle altre, sarebbe ridondante. In questo caso è implicata

dalla 4 e dalla 5. È implicata perché la posso ottenere con questa operazione, abbiamo così dimostrato

che l’equazione sotto è ridondante. Ripasso

Nello spazio bidimensionale l’insieme dei vettori ottenuti per

combinazioni convesse sono i segmenti che uniscono due

punti, in questo caso il triangolo e tutti i punti interni, combino

quindi in modo convesso 3 vettori.

Teorema:

Per ottenere tutte le combinazioni convesse basta che

considero un poliedro, ha tutte le caratteristiche per essere

una formulazione, in particolare è la combinazione migliore che

si può trovare (i vertici sono esattamente i punti di S).

S è dato, prendo il suo involucro convesso che è unicamente

definito: i vertici del poliedro sono dati dall’insieme S, cioè

nessun elemento di S cade all’interno di questo o sulla

congiungente.

La soluzione ottima è data dalla minimizzazione cTx, potrei però scrivere l’insieme dei vertici di Ps (cioè Ext(Ps)).

Possiamo ancora cambiare (parte in rosso) per il teorema che dice che quando abbiamo funzione obiettivo lineare e

poliedro limitato allora esiste una soluzione ottima (TEOREMA FONDAMENTALE DELLA PROGRAMMAZIONE

LINEARE) allora esiste una soluzione che sta su un vertice (quindi non può esistere una soluzione ottima all’interno del

poliedro). Posso quindi scrivere che posso applicare il metodo del simplesso. La soluzione che troviamo è una

soluzione ottima del rilassamento lineare. 6

D è il rilassamento di una formulazione ottima

Torniamo a noi

➖ La formulazione ottima per il problema del matching con grafo

bipartito è la formulazione circuiti.

➖ la formulazione ottima per il massimo sistema indipendente

quando abbiamo una matroide è la formulazione rango.

Dimostrare che la formulazione è ottima:

Voglio massimizzare una funzione obiettivo e trovare z*. P è una

Combinazione formulazione di S, la proprietà di P è che la sua intersezione con

coninca (coeff >=0) l’insieme {0,1}^n mi dà vettori 0,1.

Ps è un poliedro identificato da disequazioni, ho quindi 2 poliedri

e mi chiedo se questi sono uguali tra loro. Posso dimostrarlo in

vari modi.

In generale le funzioni obiettivo non le diamo mai per certe quando costruiamo il poliedro, dobbiamo essere sicuri che

il problema che abbiamo costruito troverà soluzioni 0,1 per qualunque funzione obiettivo.

Primale e duale di un problema di programmazione lineare: coppia

di due problemi legati tra loro.

In blu il primale, in rosso il duale.

Un problema di programmazione lineare è fatto da una funzione

obiettivo lineare, vincoli lineari, termini noti ecc

Il suo duale è definito così:

➖ Se il primale è un problema di massimo il duale è di minimo, se

il primale è di minimo il duale di massimo

➖ I vincoli sotto sono RESTRIZIONI IN SEGNO, non sono veri

vincoli, sia il primale che il duale hanno queste restrizioni.

➖ C’è una variabile del duale per ogni vincolo del primale (per

ogni A contenuto in Γ). Il vettore y avrà dimensione 2^n. Per

simmetria avremo una variabile del primale per ogni vincolo del

duale.

➖ Il numero di vincoli duali è limitato mentre il primale ha un numero limitato di variabili ma tanti vincoli.

➖ I coefficienti del duale diventano i termini noti del primale.

➖ Se i vincoli del primale sono di minore o uguale quelli del duale sono di maggiore o uguale.

➖ D è una matrice 0,1, ogni riga corrisponde ad un A perché ogni a è un vincolo. Per costruire la matrice duale si fa la

matrice trasposta di D.

Primale e duale sono molto importanti per il teorema della DUALITÀ DEBOLE (il minimo della funzione obiettivo duale

è sempre maggiore o uguale del massimo della funzione obiettivo del primale, quindi il minimo del duale è sempre un

ulteriore bound del massimo del primale).

Quindi ogni soluzione ammissibile del primale è sempre minore o uguale di ogni soluzione del duale, allora: ogni

soluzione del duale sarà un upper bound della soluzione del primale, ogni soluzione del primale sarà un lower bound

della soluzione del duale. 7

In pratica primale e duale sono due generatori infiniti di bound.

Teorema della DUALITÀ FORTE: il minimo del duale è uguale al massimo del primale, questo succede all’ottimo.

Quindi se troviamo una soluzione del primale che ha valore uguale al minimo del duale allora quella soluzione è ottima.

Il simplesso utilizza questo teorema, si ferma quando ha costruito una soluzione del primale che ha valore uguale al

minimo del duale. Costruiamo una soluzione ottima del duale e la utilizziamo per

dimostrare l’ottimalità.

Una soluzione del duale è un vettore che ha componenti in

corrispondenza di ogni insieme A contenuto in Γ.

Assegniamo a ciascun y un valore pari alla differenza tra i due

valori adiacenti, il risultato è sempre maggiore o uguale a 0

perché c(i) è sempre maggiore o uguale di c(i+1) in quanto

abbiamo ordinato per pesi decrescenti.

Si concentra su quelli che hanno indice maggiore o uguale di i, solo per quelli infatti ei appartiene ad A.

Proprietà della soluzione:

c(i) maggiore o uguale a 0 per i che va da q ad n-1 perché c(n+1) non è definito, quindi yA maggiore o uguale a 0 per

ogni A.

Controlliamo ora se sono soddisfatti i vincoli del duale: scriviamo il vincolo duale come sommatoria degli yA dove A è

tale che ei appartiene ad A. Vogliamo dimostrare che questa sommatoria per tutte le A che contengono e deve essere

maggiore o uguale di ci. Questa sommatoria vale ci perché è una sommatoria telescopica, restano quindi soltanto il

primo e l’ultimo termine perché gli altri si semplificano. Allora y è una soluzione ammissibile.

Vogliamo dimostrare che la soluzione duale ha il valore della

soluzione greedy, allora avremo dimostrato che esiste una

soluzione duale esattamente uguale ad una soluzione del

primale quindi questa è una coppia della dualità forte.

Possiamo dire che se il vettore di incidenza del greedy in

posizione i vale 1 allora il rango di Ai meno il rango di A(i-1)

vale 1. Tutte le volte che il vettore di incidenza vale 0 allora

l’elemento non appartiene alla soluzione greedy.

8

Approfondimenti dualità

9

Separazione, Metodo del Simplesso

Dinamico e Lower Bound da soluzioni 0-1

Siamo in grado di risolvere il problema di PL01

Invece di sapere tutti i vincoli del poliedro dobbiamo saper

costruire l’oracolo.

L’oracolo è come se fosse una scatola nera, in ingresso entra

un qualunque vettore, l’oracolo risponde in due modi:

! xcappello appartiene a P

" xcappello non appartiene a P, in questo caso deve dire il

vincolo che viene violato

Prendiamo un grafo connesso in cui il sistema di indipendenza

è fatto dagli insiemi di archi la cui rimozione disconnette il

grafo.

Se eliminassimo tutti gli archi neri rimarrebbe un albero

ricoprente (potrei quindi non pagare queste connessioni ed

avere comunque un grafo con tutti i nodi collegati). Questo

insieme di archi si chiama CO-ALBERO, ovvero il

complemento di un albero.

Potrei cercare il CO-ALBERO di massimo peso.

I circuiti sono tagli minimali: se rimuovo un arco qualsiasi sconnetto il grafo. Potrei voler cercare il più piccolo insieme

di archi che non posso eliminare. La formulazione circuiti contiene tutti i possibili tagli.

Se un taglio contiene un taglio minimale allora i vincoli che definiscono il taglio più grande sono ridondanti.

T appartiene ad S se e solo se T è il complemento dell’insieme

degli archi di un sottografo connesso ricoprente: X vettore di

incidenza degli archi di un sottografo connesso.

A questo punto invece di costruire questo poliedro avente

come soluzioni ammissibili le soluzioni in y posso prendere un

nuovo poliedro avente come soluzioni i vettori di incidenza dei

complementi.

A questo punto posso scrivere il nuovo poliedro facendo la trasformazione.

1

Per ogni taglio conserva almeno un arco, quindi almeno uno

degli archi deve far parte del sottografo ricoprente.

È un formulazione che può avere tantissimi vincoli.

Per ogni prova dovrò avere un diverso oracolo di separazione.

I due problemi sono equivalenti ma il secondo è più facile.

Abbiamo il vettore in ingresso, dentro l’oracolo di separazione

facciamo subito: se una componente è maggiore di 1 o minore

di 0 per qualche e (verifica per ispezione) allora rispondiamo

subito che il punto non appartiene a P. Se la somma delle

xcappello è minore di 1 allora x non appartiene al poliedro (il

vincolo di taglio è violato). Se per tutti i tagli abbiamo che la

somma è maggiore o uguale a 1 allora x appartiene a P.

Il flusso massimo che posso mandare da un nodo ad un altro è

uguale al taglio minimo che li separa. Non posso quindi inviare

un flusso superiore al taglio minimo.

Posso mettere in relazione i tagli di G con i tagli di W. W è

l’insieme che viene separato quando tolgo tutti gli archi

uscenti.

Il taglio uscente da W in H è uguale a 2,6,5,4.

Risolvo il problema del massimo flusso per ogni coppia s,t,

trovo il taglio di capacità minima da un qualunque taglio

uscente da W.

Minimum minimorum: il minimo dei minimi, faccio tutte le

possibili combinazioni s-t con i relativi minimi tagli e prendo il

taglio più piccolo di tutto il grafo.

Se W* (taglio minimo) ha una capacità maggiore o uguale di 1

posso dire che la sommatoria è maggiore o uguale di 1 per

ogni taglio più grande di W*.

Risolve un problema di programmazione lineare non un PL01.

Ha bisogno del l’oracolo di separazione e del metodo del

simplesso.

Problema illimitato non esiste perché siamo in un cubo

limitato, prima o poi sbatte in un lato del cubo unitario, non

può andare all’infinito. Risponde quindi solo con soluzione

ottima oppure con nessuna soluzione.

2

Problema core: prendo un sottoinsieme di vincoli.

➖ Parto assegnando la matrice D, sottovettore D0. Non metto

quindi A e B intere ma soltanto un sottoinsieme.

➖ Applico il metodo del simplesso il quale risponde in due

modi possibili:

! l’insieme delle soluzioni ammissibili è vuoto, ma allora Q è

vuoto, anche P vuoto perché Q è un suo rilassamento

" potrebbe rispondere con la soluzione ottima del problema

➖ chiamo l’oracolo di separazione, questo mi dice se a soluzione appartiene al poliedro oppure no:

! se appartiene allora quella è la soluzione ottima dell’intero problema (perché ho risolto su un insieme più grande)

" se non appartiene non posso dire di aver trovato la soluzione ottima, prendo il vincolo violato lo aggiungo a D,

faccio quindi crescere la matrice corrente e e risolvo di nuovo il problema.

➖ ripeto la procedura finché non trovo una soluzione che appartiene a P. Può quindi risolvere il problema senza mai

risolvere su tutto A. 3

Metodo di Approssimazione Primale-Duale

Algoritmi di approssimazione: algoritmi che non trovano la soluzione ottima ma trovano una soluzione ammissibile di

buona qualità (esempi: greedy, algoritmi di ricerca locale, algoritmi euristici).

Il metodo primale duale è un algoritmo euristico, uno tra i più

utilizzati perché è efficiente e dice anche l’entità

dell’approssimazione alla soluzione ottima, ci dice quindi

quanto siamo lontani dalla soluzione ottima.

La prima volta è stato introdotto negli anni 70.

Il metodo primale-duale serviva per risolvere un problema di

programmazione lineare.

È alternativo al metodo del simplesso: è più efficiente e più intuitivo ma il simplesso è più semplice. Il simplesso è

basato sulla dualità forte, cerca di dimostrare con una serie di passaggi che ad un certo punto al vertice ottimo è

associata una soluzione del duale con lo stesso valore, quindi quello è il punto di ottimo.

Il metodo primale-duale usa invece la condizione di scarto complementare.

Abbiamo nella slide una coppia primale-duale, P e Q sono i poliedri, tutte le x ammissibili per i rispettivi problemi.

Aj è una riga di A trasposto (una colonna di A), abbiamo la matrice A per il primale, A trasposto per il duale.

Numero dei vincoli del duale è uguale al numero delle variabili del primale e viceversa.

La coppia primale-duale si chiama COPPIA SIMMETRICA.

Le soluzioni del duale sono sempre lower bound per le soluzioni primali, le soluzioni primali sono sempre upper bound

per le soluzioni duali.

Condizioni di scarto complementare: Non esiste gap di dualità

x è l’ottimo primale e y è l’ottimo duale (le due soluzioni sono ottime per i rispettivi problemi) se e solo se queste due

condizioni sono verificate:

! Quando ho una componente positiva nel primale il corrispondente vincolo duale è soddisfatto dalla soluzione duale

all’uguaglianza.

" Tutte le volte che prendo una soluzione duale il rispettivo vincolo del primale è soddisfatto con l’uguaglianza.

Se sono vere queste condizioni allora la soluzione è ottima, se la soluzione è ottima sono valide queste.

Se queste due condizioni non sono verificate continua a cambiare. L’algoritmo si ferma quando sono verificate le due

condizioni. Abbiamo un problema per cui vogliamo trovare il minimo della

funzione obiettivo lineare in cui x appartiene all’insieme dei vettori

di incidenza di un sistema di indipendenza.

Conto quindi i costi degli archi che ho scelto, non conto quelli per

cui la componente di x vale 0.

Poliedro: posso riscrivere S come intersezione delle x che stanno

nel poliedro e che hanno componenti 0,1. Allora questo poliedro è

una formulazione.

Rilassamento lineare: elimino i vincoli 0,1 lasciando quindi solo il

poliedro.

Si è aggiunto l’1 nei vincoli per limitare il poliedro ad un cubo di

lato 1.

Una qualunque soluzione x barrato in S è una soluzione α-approssimata se vale il rapporto.

Devo trovare un α che è un upper bound di quel rapporto. Se conoscessi x* potrei scriverci direttamente il valore, ma

siccome non lo conosco devo trovare il modo di calcolare α senza conoscere la soluzione.

Più è grande α meno è interessante la soluzione che ho trovato perché è lontana dall’ottimo. α quindi deve essere il

minimo possibile: più si avvicina ad 1 più la soluzione che ho è di qualità. α è un up per bound.

1

α certifica la qualità della soluzione trovata.

Esiste un altro meccanismo di approssimazione relativo al rilassamento lineare.

Qual è la relazione tra la funzione obiettivo calcolata col rilassamento ed il valore della funzione obiettivo all’ottimo?

In questo caso valore ottimo e valore trovato si sono invertiti, il rapporto è sempre maggiore o uguale a 1 perché la

soluzione ottima è sempre minore o uguale di quella che ho trovato.

Anche l’α che indica l’integrality gap è molto importante, tanto minore è α tanto migliore è la formulazione.

C è la funzione obiettivo che dipende dal cliente

π è il problema, ogni istanza del problema la chiamiamo (S,c)

S viene dato dall’esterno (grafo) ogni arco ha un peso dato da c,

possiamo avere quindi infinite istanze.

π potrebbe essere il problema del massimo insieme stabile, minimo o massimo indipendente di un sistema di

indipendenza

π: Base di peso minimo in un sistema di indipendenza, minima rispetto ad un peso c qualunque, è un obiettivo

generale, non specifica l’istanza, quando specifico S e c allora è un problema specifico.

Il problema viene impostato prima di sapere su quali istanze sarà applicato. Le istanze sono infinite.

Chiamo un algoritmo α-approssimato quando per qualsiasi istanza (S,c) di π mi restituisce una soluzione α-

approssimata.

Una famiglia di formulazioni si dice α-approssimata quando produce un integrality gap di valore α (quindi ogni volta

che risolvo il problema per un certa istanza produco una soluzione vicino alla ottima). Questa definizione non la

useremo mai, useremo solo algoritmi α-approssimati non anche formulazioni.

È un problema di massimo, il rapporto qui deve essere minore o

uguale di 1 e non maggiore o uguale come prima perché prima

stavamo minimizzando.

Cerchiamo di avere α più vicino possibile ad 1.

Tn è la soluzione ottima del greedy, F* è la soluzione ottima del

problema. Il rapporto è sempre minore o uguale di 1

Il teorema di Hausman ci calcola α tra la soluzione greedy e quella

ottima.

Vogliamo sapere quale sarà il peggior valore di α che avremo

applicando greedy ad un qualunque sistema di indipendenza.

Il caso peggiore si ha quando il rapporto diventa molto piccolo, cioè quando il rango tende a diventare più grande

possibile ed il lower rank più piccolo possibile. Il rango è la cardinalità di un indipendente contenuto in quell’insieme,

siccome Γ contiene n elementi il rango al massimo può essere n, il lower rank non può essere 0 (insieme massimale

indipendente) deve esserci almeno un elemento quindi vale 1. Possiamo dire quindi che questo rapporto 1/n è

effettivamente il più piccolo valore che α potrebbe assumere.

Esempio

Massimo insieme indipendente, disegno un grafo 2

In realtà α minimo potrebbe essere 1/(n-1) ma va bene anche scrivere 1/n perché quello che mi interessa è l’ordine di

grandezza.

Se ho una matroide al contrario α vale sempre 1, ma questo lo sapevamo già, lo avevamo dimostrato.

Per calcolare α useremo la teoria della dualità.

Nell’asse reale l’ottimo del rilassamento lineare è minore

dell’ottimo del problema 0,1, quindi ho un lower bound.

X barrato è una soluzione ammissibile 0,1 del problema primale

(non di quello rilassato).

Y barrato è l’ottimo del duale, è minore o uguale dell’ottimo del

problema rilassato per via della dualità debole.

In generale cerco di costruire la coppia X barrato y barrato che mi

dà il gap più piccolo, quando nullo ho la soluzione ottima.

Preferisco α1 ma in molti casi potrebbe essere difficile da

calcolare allora α2 va bene lo stesso.

La soluzione x barrato è una soluzione ammissibile qualsiasi, quindi facile da calcolare.

Potrei arrotondare e ottenere una soluzione non

ammissibile, quindi l’affermazione non è vera sempre.

Euristica giusta: genera una coppia di soluzioni (una per il

primale una per il duale) che soddisfa le condizioni

rilassate di scarto complementare.

Cioè invece di trovarne una che soddisfa lo scarto

complementare ne trovo 2 accoppiate.

Se la coppia soddisfa le condizioni di scarto

complementare allora ho trovato la soluzione ottima del

problema.

L’idea euristica è: se prendo una coppia X barrato appartenente ad S (soluzione 0,1), y barrato appartenente a Q è

una coppia primale-duale, se scopro che la coppia soddisfa le condizioni di scarto complementare allora la coppia è

ottima per il rilassamento lineare (ognuno è sempre ottimo per il rispettivo problema).

Poiché ho scelto X barrato appartenente ad S (non è un rilassamento) , allora X barrato è proprio l’ottimo quindi il

rapporto è uguale ad 1.

y barrato appartiene a Q, quanto è difficile trovarla? Potrei non essere sicuro dell’esistenza di y barrato, ne sono

sicuro quando X barrato è l’ottimo del problema di programmazione lineare allora potrei dire che effettivamente esiste

una y barrato. 3

y posso dire che certamente esiste quando il poliedro primale ha un vertice del poliedro in S.

Allora facciamo il rilassamento, chiediamo di soddisfare le condizioni di complementarietà approssimate, rilassate.

Calcolo quindi un valore che non è esattamente 1 ma ci sta vicino.

bi maggiore o uguale di 0: perdo generalità o posso fare questa

cosa tranquillamente? Devo modificare il problema in modo tale

da mettermi in una situazione in cui bi è maggiore o uguale di 0, la

risposta è sì data la generalità con cui scrivo le disequazioni.

Ipotesi: bi maggiore o uguale di 0.

Teorema che ci dice come calcolare α, ha una caratteristica: α

deve essere calcolato senza conoscere l’ottimo.

Dimostriamo in 2 fasi:

Dati X barrato appartenente ad S e α>=1 se esiste una y che

soddisfa le seguenti condizioni di scarto complementare allora

sbarrato è una soluzione α-approssimata.

Le condizioni sono scritte in modo rilassato perché abbiamo

scritto α maggiore o uguale di 1, se avessi scritto α uguale 1 non

avrei potuto.

Faccio l’ipotesi che esista.

Prodotto interno quindi la somma dei prodotti delle componenti

con lo stesso indice. X barrato è una variabile 0,1 quindi mi

interesso soltanto delle componenti che valgono 1. Al posto di cj

sostituisco la sua espressione perché faccio la sommatoria solo

per le j tali che le componenti siano maggiori di 0.

Inverto le due sommatorie, dentro rimane la stessa cosa,

La seconda condizione di scarto complementare è inclusa.

4

Il problema del Set-Covering

T è un cover se la sua intersezione con ogni insieme della

famiglia è non vuota.

Si tratta di una famiglia di sottoinsiemi qualsiasi non

necessariamente un sistema di indipendenza.

Punti 3,6,10 è un cover se c’è un elemento del cover in ogni

insieme della famiglia.

Prendere la slide formulazione set covering

Cardinalità dell’intersezione almeno 1, non può essere 0.

Vettore di incidenza del cover T è un vettore 0,1. Tante

componenti quanti sono gli elementi di J. Ogni volta che c’è un

1 vuol dire che l’elemento appartiene a J.

Sono vettori 0,1 sia il vettore T che il vettore di incidenza F, la

cardinalità dell’intersezione è uguale al prodotto interno dei due

vettori. Se il prodotto interno viene 0 allora non hanno elementi

in comune.

Ogni vettore di incidenza di un cover soddisfa queste disequazioni, quindi appartiene al poliedro.

Potrebbe stare nel poliedro un vettore 0,1 che non è un cover? No perché allora non sarebbe una formulazione.

S è sempre la famiglia dei vettori 0,1 ammissibili

Prendiamo un insieme A che non è un cover, non appartiene ad

S il suo vettore di incidenza.

Non è un cover cioè non interseca almeno uno degli insiemi

della famiglia.

Il vettore di incidenza di A sostituito nel sistema scopro che da

qualche parte non è maggiore o uguale a 1.

Infiniti vettori potrebbero soddisfare il sistema ma non

appartengono ad S.

Si associa a ciascun elemento un costo, si sommano gli

elementi che stanno in c col vincolo che T è un insieme

ammissibile, per essere ammissibile è un cover.

Si cerca il cover di peso minimo.

Il poliedro rappresenta tutti i vettori di incidenza di un cover.

Deve avere almeno un 1 in ciascuno dei termini a sinistra.

È la formulazione naturale, si chiama naturale perché la

descrizione del problema ci porta direttamente alla formulazione.

Se X appartiene al poliedro e ha componenti 0,1

allora è il vettore di incidenza di un cover. RSC è

una formulazione

Voglio trovare un grafo st orientato connesso di peso minimo

(non cerco il cammino tra s e t), voglio trovare un grafo in cui s e

t siano collegati da un cammino. Diventa il problema di cammino

minimo quando si hanno tutti costi positivi degli archi. Voglio

mettere in evidenza il ruolo dei vincoli di covering.

Insieme J sono gli archi. La famiglia è costituita da tutti i tagli st

(tagli che separano s da t).

Ogni taglio deve contenere almeno un arco di un cammino st.

Voglio che tutto il grafo sia connesso, quindi che ci sia un albero

ricoprente di peso minimo, voglio sapere quanti archi mi servono

per avere l’intero grafo connesso.

Uno dei possibili esercizi che potremmo trovare all’esame

Problema dei turni del personale

Dobbiamo in questo caso definire chi sono i piloti, le hostess di

uno specifico volo. Definire il modo in cui veste un certo

aeroplano.

Una generica azienda ha dei servizi da svolgere (compagnia

aerea: volare da una città ad un’altra).

Nella gestione dell’equipaggio per le linee aeree ci potrebbero

essere i segmenti di volo (tratte) che sono da un decollo ad un

successivo atterraggio (l’equipaggio potrebbe ripartire subito

dopo e fare un altro volo).

Sequenze di servizi : accompagnamenti, sequenze compatibili

La sequenza di servizi tende a tornare al punto di partenza.

Questo è solo un esempio, non va studiato

Problema: sequenziare i turni del personale per minimizzare i

costi. 25000 piloti nel 2001 e personale di bordo, spendevano

1,5 miliardi l’anno di stipendi. Il loro algoritmo di ottimizzazione

fa l’ipotesi che i loro voli siano già fissati.

Il metodo usato è TRIP. Ottimizzazione locale, euristica locale

che riaggiusta l’orario a partire dagli orari degli anni precedenti.

Nel 92 hanno cambiato radicalmente il loro algoritmo. C’è un

punto interrogativo perché non si è sicuri che quello sia

effettivamente il metodo usato.

FAA si preoccupa di rispettare tutta una serie di regole per il

personale impiegato.

I vincoli sono internazionali per quanto riguarda le regole sul

personale manutenzione ecc.

Per quanto riguarda il personale ci sono tante regole, esempio:

- almeno 8 ore di lavoro in servizio

- Massimo tempo 12 ore in servizio

- Minimo tempo di sosta che dipende da quante ore ha volato

nel periodo precedente (quanto si devo fermare dipende da

quanto uno ha lavorato prima, se la tratta è più lunga il periodo

di sosta deve essere maggiore).

- ci vuole un minimo tempo tra un volo ed un altro

Quelli nella slide sono diversi percorsi degli equipaggi, percorsi come questi possono essere costruiti in tantissimi

modi diversi. Questo è un esempio di crew pairing di un equipaggio fatto in

due giorni diversi.

Fare sempre attenzione agli eventi elementari: cose che

possono accadere o non accadere, eventi a cui possiamo

assegnare 0,1. Elementi dell’insieme Γ che poi vengono messi

insieme come soluzioni. Evento elementare singola

componente di un vettore.

Il percorso della slide è sbagliato. Un servizio assegnato ad un

pairing, l’evento elementare è il servizio. A questo punto

definisco una variabile xij 0,1 che corrisponde all’evento

elementare. Ovviamente non tutti vengono attivati (il pairing è il

grafico di prima, le sequenze). Questo problema posto così

potrebbe essere visto come un problema di localizzazione degli

impianti.

Affrontare questo problema così non va bene.

Tutti i clienti afferiscono ovunque, non c’è un problema di appartenenza (un cliente di Palermo può usufruire

dell’impianto di Milano ma il costo è altissimo quindi comunque nella soluzione questo collegamento non verrà

incluso). Il ragionamento fatto così è sbagliato in questo caso perché vengono presi in considerazione anche i casi in

cui i costi siano molto molto elevati. Gli accordi sindacali vanno messi nell’appartenenza.

Il costo nel caso della localizzazione di impianti (costo fisso di costruzione e di afferenza) qui invece i costi dipendono

dal servizio, quindi dalle persone che ne usufruiscono. Questo modello non funziona perché non riesco a costruirlo.

Gli eventi elementari sono i pairing, le sequenze di servizio che

coprono tutti i servizi.

Invece di vedere come evento elementare il singolo volo

guardiamo come evento elementare una possibile sequenza di

servizi.

L’insieme J degli oggetti singoli, eventi elementari, è dato dalle

sequenze ammissibili, tutte le possibili sequenze di servizi

ammissibili.

Esempio di prima: 5 pairings fatti con i servizi elementari.

Abbiamo 5 delle possibili sequenze. I numeri sono quelli dei

servizi originari nelle slide precedenti.

Posso costruire un certo insieme di pairings dato un certo

insieme di servizi.

Quando abbiamo i pairings dobbiamo riconoscere quali sono i

servizi. (Questo succede in esercizi come questo, può darsi che

all’esame ci dia direttamente i numeri dei servizi).

Gli eventi elementari in questo esempio sono i 5 scritti nella

slide.

Gli Fk sono gli insiemi di pairing che contengono lo stesso servizio k

Cover: Ogni servizio è contenuto in qualche pairing di T. Vorrei il cover di costo minore nel rispetto dei limiti sindacali.

Pairing: accoppiamento di voli, ogni pairing copre una serie di voli, cioè una serie di servizi.

Si cerca di minimizzare i costi dei pairing che coprano tutti i voli. Immaginiamo che la soluzione sia pairing 1,2,3,4,

quindi 4 pairing, 4 equipaggi coprono 8 voli.

Se due pairing diversi coprono lo stesso servizio, lo stesso volo, quando risolvo un problema di covering e decido

quanti equipaggi utilizzare ci saranno due equipaggi che coprono lo stesso volo. HEAD DEADING: c’è un equipaggio

a bordo che però non guida, fa solo il viaggio di spostamento per andare poi a fare altri servizi. È uno spreco, c’è un

equipaggio che vola su un aereo in cui c’è già un altro equipaggio. Il problema si potrebbe risolvere così: invece di

maggiore o uguale di 1 potremmo scrivere = 1. PROBLEMA DI SET PARTITIONING (problema in cui non diremmo

ogni servizio deve essere incluso in ALMENO UN PAIRING, diremmo ogni volo deve essere in un solo pairing). È un

problema molto più difficile

Il set covering è molto più semplice da risolvere.

I limiti sindacali potrebbero essere stati già rispettati nelle sequenze che ho scelto.

Principio di sovrapposizione degli effetti

Non fa parte del corso

Cosa facevano alla fine degli anni 90 nelle ferrovie dello stato:

Si faceva una modifica del mese precedente, si sceglieva un

piccolo insieme di equipaggi che facevano un certo giro e si

mettevano a zero (5-10 pairing locali), a quel punto generati tutti

i pairing per quella zona si ottimizzava, la soluzione non si

spostava molto rispetto a quella vecchia. L’ottimizzazione locale

cambia di poco la globale.

Genera un elenco di pairing da 6 milioni, c’è un grafo di

generazione (grafo temporale, vertici tempo e aeroporti), trova 6

milioni di cammini minimi nel grafo con partenza e ritorno nello

stesso punto,in pratica trova 6 milioni di cicli. Genera a priori

una valanga di oggetti che possono essere utilizzati nella

soluzione.

Su questo insieme poi risolve un problema di ottimizzazione

Quando genero 6 milioni di pairing ho generato tutti i possibili? No, probabilmente sono miliardi. Se risolvessi un

problema di set partition sceglierei magari 5 milioni, la soluzione allora potrebbe essere ancora peggiore.

Algoritmo Primale-Duale per il Set Covering

Scriviamo primale duale e rilassamento del problema di set

covering.

Problema di minimo, il duale è di massimo. La funzione obiettivo

la prendo dai termini noti del problema primale.

1 trasposto per y è un vettore di tutti 1, la sommatoria di tutte le

y con coefficienti tutti uguali a 1.

I vincoli duali sono tanti quante le variabili del primale.

J è l’insieme dei pairings.

Voglio scegliere in ogni insieme F almeno un pairing.

F è l’insieme di tuti i pairing che contengono il servizio i, ogni

volta che ne scelgo uno ho coperto il servizio corrispondente ad

F. Ogni pairing copre un volo quando e appartiene ad F

Coprire un volo significa piazzare un volo in F

Gli e sono i pairing f sono i voli.

Le variabili duali sono tante quanti sono i voli.

I è un vettore di zeri che ha tanti elementi quanti i voli.

I vincoli duali sono tanti quanti i pairing. Quindi o ho 6 milioni di variabili o 6 milioni di vincoli, dipende quello che voglio

risolvere.

Ogni vincolo duale è abbinato ad un pairing.

Primale e duale: il primo è il problema originario rilassato, rilassamento del problema intero (ho eliminato il vincolo di

0,1). Dopo aver costruito il poliedro mi dimentico delle soluzioni 0,1, le ho usate solo per costruire la formulazione, poi

non mi servono più (usate solo quando ho detto che il poliedro contiene tutti vettori di incidenza 0,1). Le soluzioni 0,1

in qualche modo ora sono scomparse, tutti i vettori 0,1 nel poliedro sono vettori di incidenza di cover.

Esempio:

Il vettore c dei costi, 5 elementi, elementi base sui quali costruisco i miei insiemi. 5 pairings, troviamo l’insieme di 8

corrispondenti agli 8 voli della lezione precedente (cioè il diagramma di venn con l’esempio dei voli delle slide

precedenti, dobbiamo trovare 5 pairings e 8 insiemi).

A è coperto dai pairing 2,5,4 il b da 1,4 c da 3,5.

Abc sono i voli (le F). Gli elementi sono le e, cioè i pairing. L’equipaggio 4 vola su a e su b. 5 vola a e c. 3 vola solo c.

Il problema per esteso: vincolo per ogni F, cioè a b c, poi avremo una variabile per ciascun pairing e una sommatoria

maggiore o uguale di 1. O il pairing 1 o il 4 se voglio che qualcuno piloti il volo B.

Se avessi un vincolo tipo x3 maggiore o uguale 1 allora quello dovrebbe essere preso per forza (l’equipaggio associato

al pairing 3 deve essere per forza scelto, allora posso eventualmente eliminare alcuni degli altri vincoli perché

soddisfatti visto che 3 è sempre maggiore o uguale di 1). Si cerca spesso di avere vincoli con una sola variabile per

poterne ridurre il numero.

Nel primale dell’esempio ci sono 5 variabili quindi nel duale mi aspetto 5 vincoli, ho 3 vincoli nel primale quindi mi

aspetto 3 variabili nel duale. I termini noti del duale (minore o uguale) sono i coefficienti delle rispettive variabili nella

funzione obiettivo del primale.

Per costruire il duale si prende la matrice dei coefficienti del poliedro del primale e si fa la trasposta, quella diventa la

matrice 3x5 dei vincoli del duale.

La soluzione duale la trovo col metodo del simplesso.

Soluzione ottima intera di questo problema è: posso scegliere ad esempio 4,5 costo complessivo 2 e copro tutto, 1 e

5 potrebbe essere un’altra soluzione ottima intera. Ho due soluzioni ottime entrambe uguali. Una soluzione ottima per

il duale? Prendiamo una soluzione a caso del duale, ad esempio la soluzione 0, ammissibile, però è sempre più

piccola di qualsiasi soluzione ammissibile del primale.

Cerchiamo un certificato di qualità della soluzione trovata prima: la soluzione 4,5 è ottima, soddisfa i vincoli ma questo

non basta. Potrei dire ya =2, non è ammissibile. Se trovo una soluzione del duale che vale 2 allora entrambe sono

soluzioni ottime per i rispettivi problemi, ho usato la dualità forte. Se la soluzione trovata è 0,1 allora ho trovato la

soluzione del set covering non una qualsiasi soluzione del problema rilassato.

Nel duale la funzione obiettivo è la somma di yn yc, devo trovare quindi la massima somma, potrei ad esempio

prenderli tutti e 3 però non è ammissibile. Scelgo ad esempio yb e yc uguali ad 1 e ya zero allora è ammissibile, la

funzione obiettivo vale 2 come nella soluzione del primale, allora ho dimostrato che entrambe sono soluzioni ottime

per i rispettivi problemi. Se quella è la soluzione del problema rilassato lo è anche per l’intero problema, se è una

soluzione 0,1 allora è la soluzione del problema del set covering.

Domanda di esame: dimostrare il teorema nel caso speciale del

set covering: invece di dire se esiste y barrato tale che valga

quell’uguaglianza la scriviamo nel caso particolare del set

covering.

Nel caso del set covering abbiamo: X barrato appartenente ad

S se e solo se X barrato è vettore di incidenza (vettore 0,1) di un

cover T. Ovvero: il cover T è un cover perché la sua intersezione

con Fi (quindi e appartenente ad F) ha cardinalità maggiore o

uguale di 1 per ogni Fi. Inoltre x barrato con e maggiore di 0

posso scrivere e appartiene a T.

La condizione del teorema diviene (ecco la risposta alla

domanda di esame): e appartenente a T se l’elemento e

appartiene al cover T, allora per la riga del problema duale

(scritta in modo specifico per il set covering) sommo tutte le xf

corrispondenti agli insiemi e.

In pratica tutti i pairings in cui è contenuto il volo.

Se il vincolo duale non è soddisfatto all’uguaglianza allora l’elemento non appartiene a T.

La cardinalità dell’intersezione si ottiene sommando su tutti gli elementi il vettore di incidenza degli elementi che

appartengono ad entrambi. Questo è ancora un caso particolare del teorema di sopra.

Partiamo da un cover, troviamo una soluzione X barrato,

vediamo se è soddisfatta questa condizione, troviamo α in

questo modo.

Allora quella soluzione è α approssimata dove α ha il valore del

massimo della cardinalità dell’intersezione

Immaginiamo che sia data una soluzione y barrato appartenente

a Q.

Parto da una soluzione y barrato (posso partire da una soluzione

tutta 0, potrebbe essere un buon inizio, in alcuni casi potrebbe

essere conveniente partire da una soluzione diversa per fare

meno passi).

Verifico che la soluzione sia ammissibile per il duale, quindi

verifico che ogni vincolo sia soddisfatto (non necessariamente

all’uguaglianza).

Per gli elementi 1 e 3 i vincoli sono soddisfatti all’uguaglianza.

Quindi abbiamo 2 elementi che soddisfano i vincoli

all’uguaglianza, allora abbiamo J={1,3}.

Vedi se esiste un cover contenuto in J=. Esiste un cover in J=? Comunque ci mettiamo anche se prendiamo tutto J

non copriamo l’insieme A quindi la risposta è no, non esiste un cover in J=, allora questa y non va bene va aggiornata.

Devo coprire i tre insiemi col costo minimo. 4,3 pesa 3, 5,1 pesa 3, 5,4 pesa 4, troppo, comunque abbiamo più

soluzioni che pesano 3. La soluzione duale vale invece (funzione obiettivo = sommatoria delle y) la soluzione ottima del

duale vale 2. L’algoritmo dice cerca un cover in J=, non ci sono quindi devo aggiornare la soluzione.

Come trovo un cover in J= o come faccio a dire che non esiste? Questo è un problema difficile. Ma non chiede

necessariamente l’ottimo, ne basta uno.

Dovrei trovare un cover con due proprietà: T cover e T contenuto in J=.

Questa operazione prende il nome generale di primale ristretto: è un problema uguale all’originario (trova un cover di

minimo peso) ma qui è ristretto: non lo voglio in tutto J ma solo in J= (quindi ho ristretto la ricerca), secondo vantaggio

nessuno chiede il cover minimo, ne viene chiesto uno qualsiasi.

Quello che posso fare è verificare se J= è un cover, se lui è un cover va bene così. Se J= non è un cover allora non può

esserci un cover in J=. Il valore di α cambia con gli insiemi F.

Prendo la variabile duale associata all’insieme che non è coperto

e la incremento Nessun elemento di F barrato ha il vincolo duale soddisfatto

all’uguaglianza perché se ci fosse uno così allora quell’elemento

sarebbe anche in J= e quindi l’intersezione sarebbe diversa da

zero.

Per ogni e appartenente quindi ad F barrato il vincolo del duale

(i vincoli) sono soddisfatti tutti col minore e nessuno con l’=.

Gli si somma la minima slack

C’è almeno un vincolo che dopo la modifica verrà soddisfatto

all’uguaglianza.

L’algoritmo completo è contenuto in questo scatolone.

Ad ogni passo la soluzione cresce, ad un certo punto si fermerà

perché arriverà ad essere uguale a J. Quindi il numero di passi

massimo è m perché al massimo prenderò tutto J.

L’obiettivo è trovare un sottoinsieme di j che ci darà una soluzione α-approssimata. Gli elementi devono intersecare

tutti gli elementi F di una certa famiglia.

Abbiamo una famiglia F, abbiamo gli elementi, vogliamo trovare il sottoinsieme più piccolo possibile che interseca ogni

insieme F appartenente alla famiglia F.

Trovare la soluzione è difficile, ci accontentiamo di una α-approssimata. (2-approssimata, cioè al massimo due volte la

soluzione ottima).

Si cercherà di trovare la soluzione con l’α più piccolo possibile, quindi più vicino possibile ad 1.

Si parte con una soluzione ammissibile per il duale, potrei ad esempio prendere la soluzione tutta zero che è sempre

ammissibile. Costruisco un insieme J= che è fatto da elementi di J (sottoinsieme di J) con la proprietà che il vincolo di

ciascun elemento appartenente a J= sono soddisfatti all’uguaglianza dalla soluzione corrente. Potrebbe non esistere

neanche un vincolo soddisfatto all’uguaglianza. L’insieme che ho appena costruito interseca tutti gli F? Se li interseca

tuti allora lui è una soluzione α approssimata dove α lo posso calcolare col massimo della cardinalità dell’intersezione

di J= e ogni insieme F. Può darsi che α venga con valore alto, può anche darsi che togliendo alcuni elementi dalla

soluzione finale rimane comunque ammissibile, allora posso toglierli. Se però non è vero che l’insieme trovato

interseca tutti gli insiemi allora esiste qualche insieme per cui l’intersezione con qualche insieme di F è 0. Posso allora

incrementare la variabile duale corrispondente ad Fsegnato. Incremento liberamente ybarrato di Fbarrato della

quantità min(...).

Incremento ogni volta, entra in J= almeno uno degli elementi di e contenuti in Fbarrato.

I vincoli del duale soddisfatti all’uguaglianza sono sempre di più.

Applichiamo l’algoritmo ad un problema di set covering.

Applicare al problema di crew scheduling l’algoritmo appena

visto per il set covering, questo potrebbe essere un esercizio di

esame.

Il node cover è un problema di set covering.

Immaginiamo di avere un grafo, potrebbe essere una città, gli

archi sono strade, i nodi incroci, immaginiamo di avere sotto

controllo le strade, dobbiamo decidere dove mettere i carrarmati

per controllare l’intera città. Problema di node covering.

Controllare una strada vuol dire essere piazzati in uno dei due nodi agli estremi della strada. Voglio coprire archi, cioè

coprire coppie di nodi, ogni insieme è una coppia di nodi.

Se prendo un insieme vuoto non copro niente, se prendo tutti i nodi controllo tutto ma mi costa troppo. Voglio sapere

qual è il minimo insieme di nodi che copre tutti gli archi (oppure insieme di minimo peso che copre tutti gli archi).

Ogni insieme F della famiglia di archi deve avere uno dei due elementi scelti nel cover.

Problema difficile. Problema di set covering, tutti gli insiemi della famiglia hanno cardinalità 2.

Nel primale ogni variabile è associata ad un nodo, nel duale ogni variabile è associata ad un arco. Posso associare

una variabile duale a ciascun arco. Fissando uno dei due estremi (u) scelgo un vincolo corrispondente e prendo tutti

gli archi.

A una variabile del duale corrisponde un vincolo del duale.

Packing e covering: packing quando la somma a sinistra può crescere ma ad un certo punto sarà limitata da un certo

valore (vincoli duali), covering invece vuol dire che il valore a sinistra deve essere almeno il valore a destra (primale).

Packing: Assegna numeri agli archi in modo tale che la somma dei valori sia minore o uguale di un numero associato

al nodo (nel nostro caso il peso del nodo). Esercitazione: prendo il grafo e associo a ciascun nodo un

peso. In nero ci sono i costi dell’installare i carrarmati in

ciascun nodo.

Ybarrato è la soluzione in rosso. V= è l’insieme vuoto. Come

trovo una soluzione duale ammissibile? Qualcuno potrebbe

non partire da una soluzione tutta 0, potrei mettere quello zero

pari ad 1, è ancora ammissibile.

Partire da una soluzione o dall’altra potrebbe portarci ad una

euristica diversa.

Siccome i costi sono positivi la soluzione di ybarrato è 0, allora la soluzione vuota è ammissibile. Se avessimo dei pesi

negativi allora sarebbe come se ci pagassero per mettere un carrarmato in quella zona, allora quelli sicuramente li

prenderemmo tutti perché ci pagano.

Posso sempre immaginare quindi che tutti i costi siano positivi, dimentichiamo che la soluzione tutta 0 funziona solo

se i costi sono tutti positivi.

Ora costruiamo l’insieme J= cioè l’insieme dei vincoli duali soddisfatti all’uguaglianza. Come riconosco i vincoli

soddisfatti con l’uguale senza scrivere tutti i vincoli duali? Il modo è: guardo il nodo, guardo gli archi che incidono in

quel nodo, verifico se la somma degli archi che incidono in quel nodo è esattamente uguali al peso.

L’insieme dei nodi i cui vincoli duali sono soddisfatti all’uguaglianza è vuoto perché sto considerando l’insieme vuoto,

ho tutti i costi dei nodi maggiori di zero quindi nessun vincolo soddisfatto con l’=.

L’insieme V= copre tutti gli archi? No, non ne copre neanche uno. Allora ci deve essere almeno un insieme Fbarrato

che non è coperto dall’insieme V=. Gli insiemi questa volta sono gli archi, c’è almeno un arco che non è coperto da V=.

Scelgo un arco (coppia di nodi) che non interseca V=. Prendiamo ad esempio l’arco b-c. Incrementiamo, aggiorniamo

ybarrato.

L’insieme può crescere fino a quando uno dei due estremi soddisfa il vincolo.

B e c ora sono soddisfatti all’uguaglianza. I vincoli corrispondenti (sia b che c) sono soddisfatti all’uguaglianza.

B,c non è un cover, c’è ancora un arco che non è coperto da

questa soluzione.

La scelta degli archi è casuale, potrei sceglierne diversi, scelgo

l’arco e-f.

L’algoritmo si ripete uguale a prima.

I due estremi della e-f dell’arco hanno costi diversi, uno ha

costo 3 uno 1. Di quanto posso far crescere gli archi entranti in

e? Fino a 3. In particolare l’arco rosso può crescere fino a 3 ma

il nodo F pesa 1, quindi la differenza peso - archi entranti vale 1

devo scegliere il minimo, non devo violare il vincolo.

Stavolta non entrano entrambi gli elementi, f è soddisfatto all’uguaglianza, e no. Entra solo

l’elemento il

cui vincolo è

soddisfatto

all’uguaglianza

La soluzione è α-approssimata.

Devo vedere l’intersezione massima dell’insieme con quelli della

famiglia.

Sarebbe stato 1 solo se V avesse intersecato ogni arco in un

solo estremo.

Se questa soluzione vale 10 (2-approssimata) allora la soluzione

ottima vale almeno 5.

L’intersezione non può valere più di 2 perché gli insiemi sono

fatti tutti da 2 elementi.

In generale prendo l’algoritmo, lo applico alle generiche istanze

del problema, quanto vale l’approssimazione?

Nel caso del node cover è sempre 2 perché per tutte le possibili

istanze male che va la cardinalità dell’intersezione è 2.

Questa è una cosa buona.

Se avessi insiemi più grandi allora la soluzione α approssimata

potrebbe avere α più grande di 2.

Nel caso peggiore potrei trovare una soluzione in cui α è

dell’ordine della cardinalità di J.

α cresce al crescere di J.

L’approssimazione è tanto migliore quanto minore è la

cardinalità di J.

Esiste un algoritmo α approssimato con α minore di 2? Finora non ci è riuscito nessuno in maniera significativa.

Rilassamento Lagrangiano e metodo Subgradiente

Problema del cammino minimo del commesso viaggiatore.

In questo caso abbiamo un vincolo in più di budget.

Scriviamo il problema di ottimizzazione come:

P è il problema che vogliamo risolvere, trovare il minimo di una

funzione obiettivo lineare, w è il peso, X sono le variabili, col

vincolo che Ax maggiore o uguale di b (un poliedro), fino a qui il

problema è di programmazione lineare. Oltre a questi x deve

appartenere a Q, cioè ad un certo insieme contenuto in Rn,

potrebbe essere ad esempio l’insieme dei vettori 0,1.

Se Q fosse un poliedro allora avremmo l’intersezione di due

poliedri, cioè un poliedro, di nuovo un problema di

programmazione lineare.

Noi vogliamo rilassare una parte di questi vincoli.

Vogliamo costruire un problema che chiameremo rilassamento lagrangiano che è funzione di un vettore di

moltiplicatori non negativi u maggiori o uguali di 0. Hanno quindi la dimensione delle righe della matrice A.

b-Ax è un prodotto interno, diventa positivo quando b è maggiore strettamente di Ax componente per componente.

b è maggiore di Ax quando il vincolo è violato.

Controllo componente per componente.

Il problema si chiama R(u), dato u consiste nel calcolare il minimo di quella funzione. È rimasta solo una parte dei

vincoli di origine.

Esempio:

Funzione obiettivo lineare, abbiamo m=2 (due vincoli) nel poliedro Ax maggiore o uguale b.

Sotto abbiamo i vincoli di box: le variabili sono entrambe comprese tra 0 e 2, cioè i valori delle X stanno nel cubo di

lato 2. Q anche qui indica un poliedro, poteva essere una sfera o qualsiasi altra cosa.

Problema di programmazione lineare, la x deve appartenere ad entrambi i poliedri, quindi nell’intersezione di questi

due oggetti nello spazio 2-dimensionale.

Prendo i vincoli di Ax e li metto nella funzione obiettivo, mi tengo quindi soltanto i vincoli più facili.

Alla fine troverò un vettore di incidenza di un matching o di una foresta.

Come rilassiamo:

Prendiamo qualunque vettore a componenti non negative e costruiamo il lagrangiano. U trasposto per b-Ax, quindi

vettore riga per vettore colonna.

Moltiplico la prima riga per 2 e la sommo alla seconda riga moltiplicata per 1.

U in questo caso lo consideriamo dato. Dato u costruisco R(u).

R(u) si costruisce con la vecchia funzione obiettivo più u trasposto(u-Ax). I vincoli sono quelli che abbiamo deciso di

lasciare.

R(u) allora è quello nel riquadro rosso, 3 è una costante quindi lo possiamo mettere prima del minimo perché tanto in

ogni caso lo pagheremmo, raccolgo gli altri termini. Quindi minimizzo e quando ho minimizzato sommo la costante 3.

Vogliamo utilizzare il rilassamento lagrangiano per calcolare un

lower bound per il problema originario.

È molto difficile trovare la soluzione ottima, proviamo con una

soluzione generica, mi interessa trovare un gap, quindi un lower

bound.

Quando Q diventa 0,1 è una metodologia per trovare un lower

bound del problema originario.

Guardo il problema, vedo i vincoli difficili, li elimino mettendoli

nella funzione obiettivo.

L(u) può generare un lower bound, prendiamo il vettore u tutto

zero, calcolare L(0) vuol dire tenersi solo i vincoli X appartenenti

a Q, è come se eliminassi tutti gli altri vincoli.

1

Questo è un rilassamento perché ho eliminato una parte dei vincoli.

Per il vettore u tutto nullo L(u) calcola un lower bound.

Dimostrazione del teorema:

Prendi una soluzione ottima x barrato per R(u) (problema rilassato) se è ottima allora L(u) è esattamente quanto scritto

nella slide, è la funzione obiettivo calcolata nel punto xbarrato. Prendiamo una soluzione ottima x* per il problema

originario P, sappiamo che è ammissibile, tutti i vincoli devono essere soddisfatti, x* deve appartenere a Q.

Il fatto che x* appartenga a Q ci dice che oltre ad essere ammissibile per P lo è anche per R(u).

Xbarrato è l’ottimo di R(u), quindi il valore di R(u) calcolato in una generica altra soluzione ammissibile x* allora il valore

della funzione obiettivo ha un valore maggiore o uguale.

Che tipo di lower bound vogliamo quando abbiamo un

problema di minimo? Noi vorremmo trovare il valore più alto

possibile. Allora vogliamo poter lavorare sulla funzione L(u)

intesa come la funzione in cui u varia in tutti i modi possibili,

quindi non più u fisso.

Vogliamo trovare la u che massimizza L(u).

x(u) è l’argomento del minimo, cioè il valore in corrispondenza

del quale troviamo il minimo. Al cambiare di u cambia

ovviamente anche x.

➡ vincoli difficili vuol dire che ci sono dei vincoli che potrebbero

portarmi lontano dalla risoluzione efficiente.

➡ Nel problema del multi commodity abbiamo tanti problemi di flusso tenuti insieme dal fatto di dover rispettare un

vincolo di capacità cumulativo. I vincoli di accoppiamento sono fastidiosi, se li potessi eliminare sarebbe meglio. I

vincoli di accoppiamento sono quelli che elimino e metto nella funzione obiettivo.

➡ penalità: non dico che il vincolo deve essere soddisfatto ma scrivo nella funzione obiettivo che se viene violato

pago una penalità, quindi cerco di non violarlo. Si sceglie un coefficiente di penalità e si mette nella funzione obiettivo.

➡ Cerco di trovare L* cioè il massimo degli L(u). Il vero obiettivo è individuare L*, il lower bound migliore possibile.

DL= duale lagrangiano. È il più grande di tutti i lower bound che posso trovare, è un problema di max min.

Vedremo due metodi per risolvere problemi del genere, metodo del subgradiente e metodo simile al simplesso.

Problema di programmazione lineare.

Decidiamo di rilassare le equazioni. Invece di scegliere la u la

lasciamo indicata come u trasposto. Facciamo il prodotto

interno tra la riga ed il vettore, otteniamo il risultato cerchiato

nella slide

La funzione trovata non è una funzione lineare, abbiamo il

prodotto di due variabili, quindi abbiamo dei termini quadratici.

Se fisso i valori di u1 e u2 allora diventa lineare. Fissando a X ad

un valore costante diventa lineare.

Questa funzione si chiama anche bilineare: compaiono solo

prodotti tra variabili diverse.

A questo punto costruisco R(u), minimizzo rispetto a X.

Scrivo la funzione obiettivo più il termine di penalità

R(u) è il nome del problema, L(u) è un numero, è il minimo, il risultato dell’ottimizzazione fissato u (cioè il valore della

funzione obiettivo)

Per fissato u ottengo un problema di programmazione lineare minimo al variare di X.

Chiamo c1 e c2 in funzione di u, sono due termini che quando fisso u diventano due coefficienti. La soluzione ottima

del problema si trova facilmente. Si guarda il coefficiente, se è positivo c1>0 quanto dovrebbe essere x1? Potendo

scegliere scelgo x1=0, questo perché sto minimizzando. Se avessi coefficiente negativo allora prenderei xi=2.

Il problema R(u) si risolve facilmente per una fissata u perché u fissato mi dà le c.

2

Abbiamo il problema originario, PL01, è un problema di

knapsack a coefficienti positivi, è un sistema di

indipendenza.

Lo scrivo come problema di minimo e scrivo che X

appartiene a Q dove Q è l’insieme dei vettori a componenti

0,1. Q è l’insieme di 4 vettori. La definizione di Q può

essere scritta in diversi modi.

Il knapsack è rappresentato geometricamente dalla retta,

gli insiemi dei vettori che lo soddisfano sono quelli

dell’iperpiano.

La soluzione ottima è (0,1), l’ottimo è -2.

L’elemento complicato è il vincolo di knapsack.

Eliminiamo questo vincolo, prendiamo un moltiplicatore u (uno scalare, non un vettore in questo caso) e lo mettiamo

nella funzione obiettivo.

La soluzione ottima del problema si trova facilmente: tutte le volte che il coefficiente 2u è maggiore o uguale di 0 devo

mettere la variabile x1 a 0, tutte le volte che è minore di 0 scrivo x1 =1. Quindi guardo sempre il coefficiente della xi

nella funzione obiettivo e quindi poi scelgo il valore più grande o più piccolo che posso mettere per la variabile x,

analogo a prima.

Avendo scelto u=1/2 mi viene che il lower bound viene = -2

Potrebbe capitare che si accetti l’idea che si possano

teoricamente pagare delle penali nel caso in cui ci fosse un

vincolo non soddisfatto. Potrebbe esserci ad esempio un volo

senza equipaggio.

Il termine di penalità è ciò che pago.

Costruisco un problema rilassato nel quale alcuni vincoli non

sono più tali ma posso pagare per violarli.

Abbiamo un poliedro e un secondo poliedro Q contenuto in

{0,1}^n. Nel caso avremo un poliedro identico da Ax maggiore o

uguale b e un secondo poliedro X appartenente a Q. Ogni

poliedro è un’intersezione di poliedri, x deve essere 0,1.

Problema con funzione obiettivo lineare, problema di PL01. Il poliedro intersezione tra i due poliedri è una formulazione

di un problema di ottimizzazione combinatoria. Scrivo i due poliedri perché voglio distinguere tra alcune disequazioni

che complicano il problema e altre che sono semplici. Ax >=b sono i vincoli difficili (budget) q sono il resto dei vincoli

che giudico facili.

Problema di PL01 in cui il poliedro è l’intersezione di due poliedri uno facile e uno difficile che complica il problema.

Devo risolvere il problema del duale lagrangiano.

Definizioni:

L(u) è il valore del rilassamento lagrangiano (valore della soluzione ottima del problema R(u)).

(DL) è il duale lagrangiano, il nostro vero obiettivo è trovare il massimo di L(u) nell’insieme dei vettori m-dimensionali

positivi o nulli. Il duale lagrangiano è il massimo di questi valori che massimizzano L(u).

Il modo in cui voglio risolvere è questo: studio l’andamento di L(u) al variare di u. Faccio uno studio di funzione

Sfruttiamo la discretizzazione del rilassamento lagrangiano.

Q intersezione 0,1 alla n sono tutte le soluzioni che cadono in Q e hanno componenti 0,1, sono tutti vettori. P è

dell’ordine di 2^n. Potrebbero essere anche tutti i vettori 0,1. In generale Q potrebbe essere un poliedro diverso,

contenere solo vettori di incidenza di cammini.

Scrivo L(u) in funzione dei vettori sopra, sostituisco uno dopo l’altro i valori, calcolo i valori della funzione obiettivo in

tutti quei vettori u e scelgo il minimo (enumerazione completa), nella pratica però è impensabile fare così perché P

potrebbe essere un numero gigantesco. 3

U è uno scalare (cioè ha una sola componente) quando Ax maggiore o uguale b è fatto da un solo vincolo, allora u è

uno scalare, a+ub è una retta. In generale non è una retta ma un iperpiano.

Una retta è un iperpiano in R2.

Se u è uno scalare succede che abbiamo un iperpiano in R2 (m=1) cioè una retta.

Queste rette non sono spazi lineari a meno che non passino per l’origine. Se il poliedro contiene quindi l’origine allora

è uno spazio lineare, se non contenesse l’origine sarebbe uno spazio affine.

B-Axk è il coefficiente angolare, quando è minore di 0 retta decrescente, quando è maggiore di 0 retta crescente.

Vincolo di knapsack, un solo vincolo, poi la condizione poi tutte

le possibili coppie 0,1.

{0,1}^2 sono tutti i punti coppie ammissibili di soli 0,1

L’insieme dei vincoli che voglio eliminare è l’unico vicolo, allora

u è uno scalare, moltiplico la slack di questo vincolo e la sommo

alla funzione obiettivo, il risultato finale è L(u).

L(u) corrisponde perfettamente all’espressione di L(u) che

avevamo trovato nella slide precedente.

Per trovare Lk(u) sostituisco in L(u) tutti i vettori 0,1 scritti sopra.

Il pedice indica la componente di un vettore mentre l’apice

indica il vettore

Il minimo delle 4 rette è L’INVILUPPO INFERIORE, cioè l’ultima

che incontro passo passo. Rimango sempre sulla retta minima.

Questa in rosso è la retta su cui vogliamo trovare L(u).

Se quella rossa è L(u) quanti sono i vincoli che ho rilassato?

Cioè qual è la dimensione del vettore u? Siamo in uno spazio di

dimensione 2, allora u aveva dimensione 2, ho tolto un solo

vincolo. Allora il numero di vettori 0,1 che sono in L(u) sono tanti

quanti sono gli iperpiani, avrò una retta per ogni X 0,1

appartenente a Q.

Abbiamo scritto il valore della nostra funzione come il minimo di una serie di funzioni k appartenente a K dove K è un

insieme di vettori 0,1 ammissibili per il problema. Siamo interessati a calcolare un lower bound, un’approssimazione.

Abbiamo dimostrato un teorema che dice che L(u) per ogni u maggiore o uguale di 0 definisce un lower bound. Le

soluzioni ammissibili non le possiamo elencare tutte. Abbiamo tante funzioni, un insieme di funzioni Lk(u). Nello spazio

a due dimensioni sono rette, nello spazio a 3 dimensioni sono piani ecc.

Da u1 a u2 cambio retta. Comunque scegliamo u abbiamo un lower bound, più sono alti più sono buoni. Il lower

bound nella posizione più alta è il migliore di tutti.

L’obiettivo è sempre quello di trovare il lower bound più alto in un problema di min.

4

In pratica si scende finché non si arriva all’iperpiano.

Quello che ci interessa è la dimensione di k. P è ciò che rende difficile il problema perché potrebbe essere molto

grande, potrei anche in uno spazio bidimensionale avere tantissime rette che definiscono l’iperpiano.

P corrisponde ai vettori 0,1 ammissibili del nostro problema originario.

U* è il punto ottimo, ho le coordinate sul piano. V* è l’altezza

massima

Questo è il problema scritto per esteso al variare di u. Quindi non

ho più un modo banale di trovare solo un minimo di n numeri,

perché ora u può variare in tutti i modi possibili, sto cercando il

valore più alto possibile.

È un problema di programmazione lineare, vincoli lineari.

Dobbiamo controllare i coefficienti di u e di v che in questo caso

sono costanti, ho un iperpiano.

Per risolvere questo problema si usa il simplesso, il simplesso

però non lo risolve perché ci sono troppi vincoli, allora si usa il

simplesso dinamico.

Metodo del simplesso dinamico risolve il problema non

utilizzando tutti i vincoli ma solo quelli indispensabili.

Vediamo come troviamo il max min di una funzione che a sua

volta è definita come un minimo.

Immaginiamo di fissare ubarrato, vediamo come calcoliamo

L(ubarrato).

Enumerazione totale per trovare il minimo, sostituisco nella R(u)

al posto della x (variabile) x1, x2, ...

Ho tutti numeri, il problema è che sono tanti.

Se la volessi risolvere come un problema di ottimizzazione

invece di scrivere trova il minimo scrivo trovo il massimo valore

della variabile v se si mantiene minore o uguale di tutti quei

numeri.

Al secondo passaggio (quello intermedio), u anche senza barra è un valore specificato, calcolo per ogni fissato u allo

stesso modo di prima, cerco il massimo possibile.

In pratica per la ricerca del massimo minimo prendo un valore e salgo salgo finché non si sbatto contro uno dei

vincoli, allora ho trovato il min (tutti i vincoli devono essere soddisfatti quindi appena ne tocco uno mi devo fermare). U

può assumere infiniti valori, ho quindi un iperpiano nello spazio n+1 dimensionale quando faccio variare u in tutti i

modi possibili.

U diventa a questo punto una variabile come X. U è la pozione v è l’altezza, ho quindi due parametri secondo cui mi

sposto.

Il problema allora diventa massimizza al variare di u in tutti i modi possibili con tutti i coefficienti positivi, dimmi quanto

vale il massimo valore che assume quello che avevamo calcolato prima per un particolare u.

Il valore massimo della funzione lo trovo così: v indica la posizione massima, u il punto orizzontale dove mi trovo, solo

in un punto avrò una v che arriva all’altezza più alta, in tutti gli altri avrò una v più bassa. Questo ora è un problema di

programmazione lineare 5

Non tengo tutti i vincoli, ne tengo soltanto un numero limitato,

problema CORE, che faremo crescere passo passo sperando di

non doverli aggiungere tutti.

Il metodo del simplesso dinamico funziona bene perché

abbiamo un sacco di vincoli ridondanti, i vincoli che definiscono

l’iperpiano sono pochissimi quindi non arriveremo ad

aggiungere al core tutti i vincoli ma solo una piccola parte.

B è un sottoinsieme dei valori k, la cardinalità di B è un numero

limitato. B lo si sceglie eliminando vincoli dall’iperpiano.

Invece di dire k appartiene a K scrivo k appartiene a B,

problema ridotto.

Quello che dobbiamo assicurarci è che il problema con pochi vincoli non sia illimitato superiormente.

V(B) è l’ottimo quando scelgo l’insieme B come iperpiano.

Ho un upper bound perché sto massimizzando.

V(B) maggiore di L* vuol dire che la soluzione è strettamente maggiore della soluzione ottima del problema originario,

allora questa soluzione non è ammissibile per il problema originario, ovvero viola qualche vincolo.

Possiamo risolvere il problema su un sottoinsieme dei vincoli degli iperpiani, trovare la soluzione ottima, calcolare per

un u(B) dato per il problema originario, alla base di questo ragionamento c’è il fatto che calcolare la funzione L (quindi

con tutti i vincoli) per un particolare u non è difficile, quello che è difficile è trovare il minimo con tutti i vincoli.

L’oracolo ci permette di dire se dobbiamo aggiungere un altro

vincolo oppure no. L’oracolo dice che se v(B) è una soluzione

ammissibile per il problema originario allora è la soluzione

ottima.

Quindi ho il lower bound ottimo.

Se invece la soluzione non è ammissibile per il problema

completo allora c’è un vincolo che non avevo messo in B e che

ho violato.

Quindi:

Scelgo un sottoinsieme di vincoli B contenuto in K

Risolvo il problema ridotto di programmazione lineare e trovo

v(B), un valore che è maggiore o uguale di L* (un upper bound

del valore che devo calcolare). Sono arrivato a v(B) come altezza

perché ho eliminato il vincolo rappresentato in blu. Ora calcolo

L(u(B)) quindi il valore della funzione obiettivo originaria con un u

fissato. Questa operazione di calcolo è facile. La facilità viene

dal fatto che non è fatta al variare di u ma per uno specifico u, in

particolare per L’u(B) trovato per il problema ridotto.

Se v(B)=L(u(B)) allora la soluzione è ottima. Cioè se l’altezza tra

problema ridotto e problema originario è la stessa allora la

soluzione è ammissibile.

Se non lo è allora si aggiunge un iperpiano, quello contro cui si è andati a sbattere nel momento in cui si è calcolato L

Risolvo di nuovo.

Questo metodo lo applichiamo al cammino minimo con budget.

Tutto questo metodo serve solo a trovare un lower bound, poi per trovare la soluzione ottima del problema originario si

dovrà usare un metodo di branch and bound. 6


PAGINE

87

PESO

97.43 MB

AUTORE

CSY

PUBBLICATO

5 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria gestionale
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher CSY di informazioni apprese con la frequenza delle lezioni di Ottimizzazione combinatoria II e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Sassano Antonio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ottimizzazione combinatoria ii

Risposte alle domande di esame Ottimizzazione Combinatoria 2 - Sassano
Appunto
Appunti del corso Ottimizzazione Combinatoria 2, prof. Antonio Sassano
Appunto
Appunti Ottimizzazione Combinatoria 2 prof. Sassano
Appunto
Appunti del corso Sistemi di servizio e simulazione Massimo Roma
Appunto