Ottimizzazione combinatoria 2 appunti

Ottimizzazione combinatoria 2

Antonio Sassano

Esame: risposte scritte a 3 domande teoriche ed esercizi

Ricevimento: venerdì 29 maggio

Preappello: due gruppi uno dalle 14-16, l’altro dalle 16.15-18-18.15

Presentazione

Prerequisiti

Teoria dei grafi:

• Definizione di base
• Teoria della dualità -> pdf libro
• Complessità computazionale
• Ricerca in profondità e larghezza su un grafo BFS, DFS (non è indispensabile)
• Cammino minimo e albero ricoprente
• Proprietà matrice di incidenza di un grafo: totalmente unimodulare

Ottimizzazione combinatoria:

• PL01, lower bound
• Algoritmo di Branch&Bound
• Algoritmo Greedy, ricerca locale

Sistemi d'indipendenza

Sono dei speciali problemi di ottimizzazione combinatoria: guardando un problema reale si deve valutare se si è in grado di ricondurlo a un problema di sistema d'indipendenza. Esempi di problemi di questo tipo sono:

• Matching
• Albero ricoprente
• Pianificazione degli investimenti
• Massimo sottoinsieme di disequazioni ammissibili (trovare una soluzione che soddisfa tutte le disequazioni coincide con la fase 1 del metodo del simplesso).

Si concentra l'analisi sui sistemi di indipendenza poiché:

• La forma astratta è standard
• Le proprietà teoriche sono comuni
• Le euristiche (algoritmo che non permette di arrivare all'ottimo ma termina restituendo la migliore soluzione trovata in modo intelligente) studiate per un problema, possono essere utilizzate per altri problemi.

Per poter parlare di SI occorre prima richiamare cosa si intende per problema di PL01. Un problema di programmazione lineare 01 è un problema di ottimizzazione in cui si ha una funzione obiettivo lineare, (es. prodotto dei costi per le variabili) con le x, soluzioni ammissibili, che variano in un insieme di soluzioni ammissibili S finito di componenti (0,1) n dimensionale, cioè n componenti che possono assumere valore 0 o 1:

* (01) = min ∈ ⊆ {0,1}²

Si hanno quindi possibili vettori costruibili. S ha un numero finito di elementi. Lo stesso problema può essere riscritto utilizzando la formulazione e riportandosi ad un poliedro:

* (01) = ( ≥ ∈ ) {0,1} ∈

Sistema di disequazioni, che nello spazio rappresentano un poliedro, devono essere tutte soddisfatte.

Per rilassamento lineare si intende sostituire il problema che era in origine di PL01, con un problema più semplice, dove x non è un vettore che ha tutte componenti pari a 0 e 1 ma componenti comprese tra 0 e 1:

min (: ≥ ∈ ) 1 ≥ ≥ 0 ∈

Con ovviamente la soluzione ottima, necessaria, è che sia ammissibile cioè deve appartenere ad S cioè:

* * {0,1} ∈ , è ∈

La soluzione ottima ha la proprietà che: * ≤ ̅ ̅ ∈ cioè è quella soluzione per cui la funzione obiettivo vale di meno. Ogni volta che l'insieme delle soluzioni ammissibili è finito, il numero di alternative, dell'ordine di, tende a crescere esponenzialmente, dunque la risoluzione del problema non è semplice. A tal fine si ha bisogno di soluzioni approssimate, che non sono quella ottima. Nel momento in cui si approssima si vuole però sapere come, cosa si va a perdere. Si parla di soluzioni α-approssimate.

̅̅ ∈ : ≤ ≥ 1 *

Per soluzioni α-approssimate si intende tirar fuori una soluzione ammissibile tale per cui il rapporto tra soluzione ammissibile e soluzione ottima è pari α. Si vorrebbe che il rapporto sia il più piccolo possibile, l'ideale è pari a 1. Ovviamente non si sa quanto vale il rapporto perché non si conosce la soluzione ottima allora si può far riferimento al lower bound. Oppure c'è un teorema che afferma che se si applica greedy si può dire quanto vale alpha. Tanto minore è tanto migliore è l'approssimazione.

Altra cosa che si può fare per valutare la soluzione è calcolare il rapporto tra la soluzione ammissibile e la soluzione ottenuta con il rilassamento lineare:

* : =≥1

Non sempre può essere dimostrata l'ottimalità di una soluzione. Spesso bisogna accontentarsi di soluzioni approssimate non ottime ma la Programmazione Lineare, con la teoria della dualità, fornisce un solido quadro teorico per la definizione di algoritmi approssimati (Lower e Upper Bounds).

(, ):

Dato un grafo orientato ≥ un vettore capacità (quanti bit al secondo riesco ad inserire nel collegamento) || ∈ un vettore domanda (quanti bit/s voglio avere di quelli che fluiscono) domanda negativa indica produzione ||(, , ), ∈ si definisce FLUSSO di un vettore (cioè un vettore che ha tante componenti quanto sono gli archi e le componenti possono assumere valori reali) tale che:

0 ≤ ≤

Usando la teoria dei grafi è possibile vedere come sia intuitivo visualizzare, , :

Con c e x che hanno dimensione pari al numero degli archi (blu, verde) e d che ha dimensione pari al numero dei nodi (rosso). Ancora più visibile nel grafo è la questione di flusso e capacità: ogni arco rispetta la condizione secondo cui il valore del flusso è maggiore o uguale di 0 (non deve essere negativo) e non supera la capacità a disposizione. Altra proprietà importante dei flussi è il principio di conservazione: la somma dei flussi entranti in un nodo meno la somma dei flussi uscenti dal nodo è pari alla domanda del nodo stesso:

∑ - ∑ = ∀ ∈ - + () ∈ () ∈ - =

Il flusso è un vettore x, l'ottimizzazione combinatoria va a cercare una soluzione x all'interno dell'insieme ammissibile finito S. Occorre individuare un valore di flusso date certe capacità. Risolvere un problema di questo tipo significa risolvere il duale di massimo flusso, risolvibile con algoritmi dedicati o con il metodo del simplesso. Finora si è parlato di soluzioni ammissibili, un flusso ammissibile x su un grafo G, di capacità c e domanda d, è un vettore che ha ciascuna componente maggiore di 0 e minore della capacità dell'arco a cui è riferito. Seconda condizione è che sia verificato il principio di conservazione al nodo: il flusso associato agli archi entranti nel nodo al netto dei flussi uscenti dal nodo deve essere uguale alla domanda del nodo d. L'insieme di vettori ammissibile è un insieme di vettori che ha le seguenti proprietà:

• Ogni componente è positiva
• Ogni componente è minore della capacità
• La somma delle componenti del vettore entranti e uscenti da ogni nodo rispettano il vincolo di conservazione del flusso

Questa è la descrizione di S, l'insieme delle soluzioni ammissibile del problema di ottimizzazione combinatoria. La formulazione di questo problema è un poliedro delineato come:

∑ ∑0 ≤ ≤ - = ∀ ∈ - + () ∈ () ∈

Non esiste un solo poliedro che contiene tutte le soluzioni. L'insieme delle soluzioni possibili può essere formulato in vari modi.

Si studierà il caso in cui nel grafo non fluisce un solo bene ma p beni, e il flusso non è relativo ad un solo cliente ma più flussi fluiscono contemporaneamente nella stessa rete. Questo è quello che succede nella realtà: più flussi diversi come Netflix, Mediaset, Amazon vengono distribuiti sulla stessa rete, condividono cioè lo stesso collegamento (telecom) pacchetti che arrivano insieme (poi si suddividono a me, al vicino…) nello stesso luogo a proprietari diversi.

|| ∈ = 1, …, p vettori domanda

Hanno domande in termini di throughput differenti, interessa conoscerle perché se si riserva una capacità grande e non serve, si sta sprecando denaro. Negli stessi luoghi Poste e Fiat hanno domande diverse perché sono vettori domanda indipendenti. Per soddisfare questa domanda ci sono beni (in questo caso pacchetti di bit) differenti. In ciascun nodo si conserva il flusso complessivo e in particolare il flusso di ciascun bene: ogni gruppo di pacchetti deve rispettare sempre la legge di conservazione del flusso. Occorre ora generalizzare il concetto di flusso: non è qualcosa di omogeneo ma si parla di flusso multi-bene, “multi-commodity”, flusso nel quale sono inclusi più vettori domanda. Per risolvere il problema l'instradamento lo definisce telecom per far rispettare i vincoli di capacità e la conservazione del flusso: i problemi non possono essere risolti separatamente perché bisogna rispettare il vincolo di capacità. Non si può dimensionare la rete con capacità enormi da non avere problematiche perché le risorse sono scarse e si creano colli di bottiglia per rispondere alle domande dei clienti. I problemi di massimo flusso quindi non sono separabili, occorre risolvere il problema per tutti contemporaneamente: si parla di neutrality, non si risolve il problema per un sottoinsieme di utenti privilegiati (es. solo per gli utenti che pagano, cosa che invece succede ora in USA).

Il problema di massimo flusso è “facile” perché la matrice del grafo è totalmente unimodulare. La totale unimodularità è persa quando si accorpano i problemi. Grazie al metodo del rilassamento Lagrangiano si riesce a risolvere un problema costituito da un insieme di problemi facili che ha un vincolo che li accorpa. In questo caso il vincolo che unisce tutti i sottoproblemi è il vincolo di capacità. Il problema totale viene risolto risolvendo i sottoproblemi separatamente e inserendo il vincolo di capacità (vincolo che rende il problema difficoltoso) nella funzione obiettivo moltiplicato per un opportuno coefficiente di penalità. Il rilassamento Lagrangiano costruisce una funzione non-differenziabile il cui massimo fornisce un Lower Bound per il problema intero. Ogni problema di cammino minimo ha comunque il dover bilanciare tempi, costi e velocità.

Nei problemi di flusso multicommodity o singlecommodity

• È data la topologia della rete, grafo G cioè a priori è definita la struttura della rete (le tecnologie del futuro consentiranno di modificare la tipologia della rete in funzione del servizio, sarà il servizio a modificare la rete in funzione del bisogno)
• È data la domanda, matrice D (nel caso di single-commodity si ha un solo vettore)
• Sono date le capacità degli archi (vettore c)
• Sono dati i costi dei flussi sui singoli archi (vettore w)

Si vuole determinare il flusso (“multicommodity”) di costo minimo.

Nei problemi di “network design”

• È data la domanda (matrice D)
• Sono dati i costi di installazione di capacità (vettore k)
• Sono dati i costi dei flussi sui singoli archi (vettore w)

Si vuole determinare la topologia della rete cioè le capacità c che garantisce un flusso ammissibile a minimo costo complessivo; ora si devono risolvere due problemi contemporaneamente, decidere come è fatto il grafo e che capacità installare.

Sistemi di indipendenza: definizioni ed esempi

Si consideri un insieme base di elementi: {1,2,Γ = … , } Nella realtà questi elementi possono essere degli eventi elementari cioè cose semplici che capitano (1) o non capitano(0). S, insieme delle soluzioni ammissibili, suo sottoinsieme, è un insieme finito.

{ } = , , … , ⊆Γ1 2

Sono cioè tutti i vettori a componenti 0,1 che rappresentano una soluzione del problema:

Tmin c x

Un esempio di problema di questo tipo è un problema di flusso, con flusso che può avere valore al più pari 0 ≤ ≤ 1 a 1. Tutte le x che rispettano il vincolo di conservazione del flusso (perché il vincolo di è rispettato per definizione) fanno parte di S. Ogni evento può essere riscritto in funzione del vettore d'incidenza (o caratteristico) e tutti i vettori possibili sono in numerosità pari a . Ciascun vettore rappresenta un sottoinsieme del sistema di indipendenza. Non tutti i problemi di ottimizzazione combinatoria sono sistemi d'indipendenza ma vale il viceversa: è ⇒ ⊆ Γ ↔ ⊆ ⇒ ∈ S, insieme delle soluzioni ammissibili, è un sistema di indipendenza se e solo se gli insiemi che formano la Γ famiglia S sono un sottoinsieme dell'insieme base e se e solo se vale il principio di ereditarietà cioè tutti i possibili sottoinsiemi T di appartengono ancora a S.

Si parla di proprietà di ereditarietà: se l'insieme appartiene alla famiglia ogni suo possibile sottoinsieme appartiene ancora alla famiglia. Ovviamente l'insieme vuoto fa sempre parte della famiglia. L'ereditarietà è la cosa che richiedo in più i sistemi di indipendenza rispetto ai problemi di PL01. A partire dall'insieme base si costruisce una famiglia (insieme di insiemi) di vettori qualunque. Il problema diventa un sistema d'indipendenza quando ci si restringe ad una famiglia tale per cui S contiene tutti i suoi sottoinsiemi.

0 1 0 0 0 1 0 0 0 00 0 1 0 0 1 1 0 0 00 0 0 1 0 0 1 0 0 0= , , , , , , , , ,0 0 0 0 1 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 1{ [0] [0] [0] [0] [0] [0] [ 0] [0] [1] [1]}0 1 0 0 0 10 10 0 1 0 0 0 0 1 = , , , , , ,Esempio2 : insieme delle soluzioni ammissibili.0 0 0 1 0 00 10 0 0 0 1 0 0 0[0] [0] [ 0] [0] [0] [1] [1] [0]{ }Ognuno di questi vettori rappresenta un insieme: si può scrivere vicino ad ogni vettore l'indice delle componenti. Questa famiglia di vettori ha come insieme un insieme di questo tipo:

Generalizzazione di una base

Un albero ricoprente di un grafo è una base.

È ⇒ ∈ ⋀ ⊃ ⇒ ∉

Una base è un insieme della famiglia massimale, cioè non è contenuto in nessun altro. È cioè l'insieme più grande di vettori indipendenti. B è una base di S se e solo se B è un elemento della famiglia S e B contiene T implica che T è un dipendente di S. ∈ → è ∉ → è

Dato un insieme qualunque, questo insieme se è indipendente è certamente contenuto in una base: o lui è una base o può essere espanso fino ad arrivare ad una base. Partendo da un insieme indipendente quindi si possono aggiungere elementi fino ad arrivare ad una base. Dato l'insieme delle basi è possibile definire tutti gli indipendenti.

Circuiti

Un circuito C è un insieme di elementi che non appartengono alla famiglia S ma tale che tutti i suoi sottoinsiemi appartengono alla famiglia 4,6,7 non è un circuito perché il sottoinsieme 4,6 o 4,7 non appartengono alla famiglia. 4,6 – 3,4 sono esempi di circuito.

Dato l'insieme delle basi è possibile definire tutti gli indipendenti. Se non contiene il vuoto non è un sistema di indipendenza. Sia le basi che i circuiti definiscono il sistema d'indipendenza: { ∈ ↔ ⊆ : }

Indipendenti = sottoinsiemi di G contenuti in qualche base:

Indipendenti = sottoinsiemi di G che non contengono un circuito (ogni dipendente contiene un circuito): ∈ ↔ { ⊈ : }

Esempi di sistemi indipendenza

1. Insiemi stabili = { (, )} S è un sistema d'indipendenza costituito da tutti gli insieme stabili di un grafo cioè insieme di nodi a coppie non adiacenti. Sono nodi per cui nessuna coppia dell'insieme è collegato da un arco. {∅, { }, { } } = , …1 1 2 Più gli insiemi indipendenti crescono più è difficili individuarli. L'insieme più grande di insieme che si riesce a costruire è una base. Si può evidenziare come due basi diverse hanno cardinalità diversa.