Appunti del corso Ottimizzazione Combinatoria 2, prof. Antonio Sassano

Ottimizzazione combinatoria II

Prof. Antonio Sassano

Appunti del corso 2018

Il file contiene gli appunti di tutte le lezioni del corso tenutosi da marzo a maggio 2018 e comprende l’intero programma di esame. Gli appunti sono stati presi in riferimento alle slide proiettate dal professore pertanto troverete queste ultime con accanto tutte le spiegazioni, gli approfondimenti e gli esempi di cui si è parlato a lezione.

Ottimizzazione combinatoria 2

Introduzione

S è un insieme finito: i modi di costruire vettori {0,1}ⁿ sono 2ⁿ. In generale prendiamo una soluzione qualsiasi, per sapere se è buona vediamo quanto vale il rapporto, vogliamo che sia il più piccolo possibile, se viene 1 abbiamo la soluzione ottima. Per determinare quel rapporto facciamo delle stime (esempio operazione di bound) e otteniamo un certo valore. Potremmo ottenere un valore accettabile anche mediante l’algoritmo di greedy, quindi possiamo sapere quanto vale α anche senza sapere quanto vale la soluzione ottima. Se eliminiamo la condizione che x deve essere 0 o 1 otteniamo un rilassamento lineare, X può assumere valori intermedi.

Algoritmi α-approssimati

Se parliamo di approssimazione dobbiamo capire quanto essa è buona. Non possiamo dimostrare sempre l’ottimalità di una soluzione, non tutte le euristiche vanno bene, spesso dobbiamo accontentarci di soluzioni non ottime ma α-approssimate (ovvero con α garantito). La programmazione lineare con la teoria della dualità forte fornisce un solido quadro teorico per la definizione di algoritmi approssimati (lower e upper bounds).

Chiameremo flusso in una rete G con capacità c e domanda un vettore x che ha tante componenti quanti archi, i valori delle componenti possono assumere numeri reali qualsiasi. Dobbiamo controllare se vale la conservazione del flusso. Conservazione: il valore del flusso entrante in un nodo (somma degli archi con la freccia sul nodo) deve essere uguale al flusso uscente (archi che hanno la coda nel nodo). S è l’insieme delle soluzioni ammissibili, è l’insieme di tutti i vettori che soddisfano le condizioni.

Problema del flusso su un grafo orientato

L’ottimizzazione combinatoria cerca una soluzione x che rappresenta il flusso che posso inviare di costo minimo. X è un vettore di flusso ammissibile (minore della capacità e maggiore di 0), soddisfa la conservazione del flusso (flusso entrante = flusso uscente).

Caso in cui più flussi fluiscono nella stessa rete contemporaneamente: unico vettore di capacità. Nell’esempio della slide abbiamo due grandi aziende, entrambe fanno la loro propria rete virtuale costruita sopra Telecom Italia: si cerca di far sì che questa abbia il minor costo possibile. I clienti sono rappresentati dai vettori domanda, i beni sono pacchetti distinguibili tra loro, quando facciamo il bilancio complessivo al nodo dobbiamo sommare i due flussi. Commodity è un bene di cui posso facilmente identificare i componenti.

Sulla rete ci sono tanti vettori domanda. Per sapere se i due flussi li possiamo accomodare contemporaneamente nella rete in modo tale da rispettare la capacità e la conservatività al nodo dobbiamo fare uno studio di ottimizzazione. Il fatto che su un nodo non si possa inviare un flusso maggiore della capacità porta ad accomunare i flussi che quindi non possono essere studiati separatamente.

Telecom ha come vantaggio il fatto che non garantisce in ogni momento un flusso uguale alla domanda (fino a 30Mb/s), tante volte dà meno del flusso richiesto per via della capacità.

No TUM = non totalmente unimodulare.

Net neutrality: ottimizzo e studio la rete per le prime n aziende, poi se avanza spazio vado a vedere a chi serve di più. Metodologia generale per affrontare un problema composto da tanti problemi facili ma che non possono essere risolti contemporaneamente perché c’è un vincolo che li accomuna. Si risolve togliendo il vincolo, quindi si scompone in tanti problemi facili ma c’è il rischio che poi con la soluzione trovata quel vincolo sia violato. Per evitare questo si inserisce il vincolo che accomuna nella funzione obiettivo moltiplicato per un opportuno coefficiente (questo lo abbiamo fatto col lagrangiano cercando di trasformare un problema vincolato in uno non vincolato).

Cammino di costo minimo: cammino minimo tra due punti col vincolo che a ciascun arco sia assegnato un costo di percorrenza.

Problema non differenziabile: ci sono dei punti in cui non esistono oppure esistono infinite derivate.

Sistemi di indipendenza: definizioni ed esempi

Fase di formulazione del problema: Dobbiamo vedere la struttura matematica, logica del problema che abbiamo di fronte (eliminare gli elementi complicanti). Si parte da un insieme base, un insieme di elementi (numeri interi, reali ecc.) finito (elementi che nella realtà corrispondono ad eventi elementari). Le soluzioni ammissibili diventeranno S, tanti sottoinsiemi dell’insieme base. Se l’insieme base ha n elementi S può avere al massimo tanti elementi quanti i vettori di incidenza (2ⁿ). Ciascun vettore 0,1 rappresenta un insieme.

Un sistema di indipendenza ha la struttura dell’insieme delle soluzioni di un problema di ottimizzazione combinatoria. Posso usare vettori o insiemi in modo intercambiabile: un vettore 0,1 può essere rappresentato con un insieme. Vettore [0 1 0 1 0] formato dagli elementi 2 e 4 è l’insieme {2,4}. Non tutti i problemi di ottimizzazione combinatoria sono sistemi di indipendenza, condizione extra: S è un sistema di indipendenza se e solo se tutte le volte che un insieme qualsiasi è contenuto in un insieme della famiglia allora appartiene anche lui alla famiglia: se c’è un insieme contenuto in un altro anche l’insieme contenuto.

Proprietà di ereditarietà: deve appartenere alla famiglia.

Essere ereditario vuol dire che se un insieme appartiene alla famiglia allora tutti i suoi sottoinsiemi appartengono alla famiglia. Ci potrebbe essere una famiglia che non è ereditaria, allora non costituisce un sistema di indipendenza. Dobbiamo controllare che ogni possibile sottoinsieme sia contenuto nella famiglia.

L’insieme vuoto deve essere sempre contenuto nella famiglia, altrimenti non è un sistema di indipendenza. Insieme di insiemi è una famiglia di sottoinsiemi. Se in basso a sinistra facessi un altro cerchio includendo il pallino senza cerchio intorno il problema non sarebbe più un sistema di indipendenza perché non tutti i sottoinsiemi a quel punto sarebbero inclusi.

L’insieme delle soluzioni ammissibili è S, famiglia di vettori a componenti 0,1. Sono tutti vettori di incidenza, ognuno di essi rappresenta un insieme, c’è quindi corrispondenza biunivoca tra vettori e insiemi. Una base è un insieme indipendente massimale (=che non è contenuto in un altro). Se B è una base allora tutte le volte che trovo un insieme T che contiene B sicuramente T non appartiene ad S. Le basi definiscono il sistema di indipendenza.

Circuito: insieme che non appartiene alla famiglia S ma tutti i suoi sottoinsiemi sì.

Abbiamo definito un sistema di indipendenza come una famiglia di sottoinsiemi. Le basi definiscono il sistema di indipendenza. Quando abbiamo una base possiamo prendere tutti i suoi sottoinsiemi e sappiamo che saranno tutti appartenenti alla famiglia. Un insieme appartiene alla famiglia se non contiene circuiti. Teorema: gli indipendenti sono i sottoinsiemi che non contengono un circuito. Gli insiemi stabili del grafo definiscono un sistema di indipendenza. Un insieme di nodi a coppie non adiacenti è un insieme stabile. 1,2,4,7 costituiscono un insieme stabile: nodi per cui nessuna coppia dell’insieme è collegata da un arco (costituiscono anche una base).

Un indipendente è un insieme di nodi a coppie non adiacenti. I nodi verdi non definiscono un indipendente perché v5 e v9 sono collegati da un arco. L’insieme vuoto è un indipendente, non ci sono coppie di V collegate tra di loro. L’insieme vuoto è stabile. 1 da solo è un indipendente. V1 v3 non è indipendente.

Basi diverse possono avere cardinalità differenti. Gli elementi elementari sono i singoli nodi. Nella slide abbiamo 9 elementi. I circuiti sono coppie di nodi collegati da un arco. V5 v8 sicuramente non appartiene all’insieme, tutti i suoi sottoinsiemi propri sono indipendenti. Un circuito non può mai contenere un altro circuito.

Devo sempre controllare l’ereditarietà: prendo un insieme stabile e vedo se i suoi sottoinsiemi sono stabili: se lo sono allora l’insieme è formato da indipendenti. Tutti i sottoinsiemi di un insieme stabile sono stabili, vale il principio di ereditarietà. I circuiti sono coppie di nodi che definiscono un arco. Si chiama matching di un grafo un insieme di archi non incidenti nello stesso nodo.

Matching vuol dire accoppiamento. Bisogna evitare che ci siano due archi scelti che incidono nello stesso nodo. L’insieme vuoto è un matching. Un arco preso da solo è un matching. Non può esserci un circuito fatto da un solo arco, da due sì, da 3 no. Le basi sono matching massimali ovvero accoppiamenti che non possono essere accresciuti. La base è un insieme indipendente massimale.

P=PN

Si tratta di due classi di problemi, P sono i problemi facili, PN quelli difficili.

Problema facile: tutte le foreste di un grafo. Dato un grafo posso prendere un insieme di archi che definiscono una foresta, ovvero un sottografo aciclico. I 4 archi in rosso nella figura indicano una foresta. Se prendo un insieme vuoto non esiste nessun ciclo, siamo in assenza di ciclo anche se non abbiamo due archi paralleli. Una base coincide con un albero ricoprente (albero che tocca tutti i nodi) ed è un grafo senza cicli, quindi una foresta che tocca tutti i nodi. Appena aggiunto un arco ad un albero ricoprente ottengo un ciclo, quindi ottengo un circuito fondamentale. I sottoinsiemi della foresta sono alberi ricoprenti. Se butto tutti gli archi tranne quelli rossi i due sottografi non hanno un collegamento.

Siamo nello spazio n-dimensionale. Γ è l’insieme base composto da tutti i vettori in Rⁿ, quindi Rⁿ è l’insieme di tutti i vettori n-dimensionali. Prendiamo una parte di questi. Q è un sottoinsieme dell’insieme base Γ. Q è indipendente quando i vettori che appartengono a Q sono tutti indipendenti. I vettori sono indipendenti quando la loro combinazione lineare mi dà 0 se e solo se λ_j=0 (ovvero l’unico modo per ottenere 0 è moltiplicare i vettori per 0). Tutto è vero per l’insieme vuoto. Presa la famiglia di vettori tutti linearmente indipendenti prendo tutte le possibili colonne linearmente indipendenti. A questo punto se un certo insieme è indipendente e tolgo uno di questi vettori mi rimane un sistema indipendente. Vale la proprietà dell’ereditarietà. Un circuito invece è un insieme lineare di vettori linearmente dipendenti (tutti i suoi sottoinsiemi sono indipendenti).

Quando si fa il metodo del simplesso si passa da una base ad un’altra aggiungendo una colonna ed eliminandone un’altra. Quando aggiungiamo una colonna abbiamo un insieme di colonne linearmente dipendente, quando la togliamo riotteniamo un sistema indipendente. Quindi prima creiamo un circuito e poi lo distruggiamo per riottenere una base.

Capital budgeting

Immaginiamo di avere un certo insieme di progetti da realizzare ed un budget. In ottimizzazione si chiama knapsack. Abbiamo un vincolo lineare, il ruolo svolto dalle variabili X è di attivazione, può assumere valori 1 o 0: 1 vuol dire progetto attivato, 0 progetto non attivato. L’insieme nullo è compatibile col budget. Se ho un insieme di progetti indipendenti e quindi compatibili col budget, posso dire che tutti i suoi sottoinsiemi sono compatibili con budget (vale l’ereditarietà), quindi ho un sistema di indipendenza. 1,2,3 è un progetto non compatibile ma ogni suo sottoinsieme è compatibile: 1,2,3 allora è un circuito.

La base è un sistema compatibile con il budget massimale. Gli elementi in questo caso sono le disequazioni. Tale sistema è un sistema non ammissibile, il sistema di indipendenza è dato da sottoinsiemi di disequazioni ammissibili. Il sistema completo è non ammissibile in quanto se i due sistemi sono inammissibili anche il sistema completo lo è. Sottoinsiemi dei singoli sistemi possono essere ammissibili. L’insieme a,b,d è un indipendente. Se un sistema è ammissibile e tolgo una disequazione sarà ancora ammissibile in quanto ho allargato il poliedro. Anche qui vale il principio di ereditarietà. Un circuito è un insieme di disequazioni non ammissibile i cui sottoinsiemi sono ammissibili. Una base è un insieme di disequazioni ammissibile massimale.

Immaginiamo un grafo connesso dove gli elementi sono le famiglie di archi in cui la rimozione di un arco non genera una disconnessione del grafo. L’insieme rosso è dipendente. In questo caso se tolgo solo un arco il grafo non si disconnette ma in generale potrebbe succedere. Se c’è un singolo arco che connette due componenti separate (BRIDGE) e lo rimuovo il grafo si disconnette. I circuiti devono essere un insieme di archi che se rimossi disconnettono il grafo, quindi un taglio. Un taglio divide il sistema in due sottoinsiemi. I circuiti sono tagli minimali. Una base in questo caso è il complemento di un albero ricoprente.

Sistemi di indipendenza: 3 applicazioni

Aste combinatorie (combinatorial auctions)

Meccanismi per un’asta:

• Asta in inglese: ciascuna offerta deve essere superiore a quella precedente, vince l’ultimo offerente e viene pagata l’ultima offerta.
• Asta giapponese: (si usa per lo più per il pesce) i prezzi crescono e quelli presenti se ne vanno man mano che non sono più disposti a pagare il prezzo corrente, l’ultimo offerente vince e paga il prezzo ultimo.
• Asta olandese: i prezzi scendono fino a quando non c’è uno che si candida per quel prezzo.
• A busta chiusa: è una delle aste più diffuse soprattutto per il codice degli appalti. Si prepara un business plan, si fa un’offerta a busta chiusa, tutte le buste vengono analizzate da un’entità che sceglierà l’offerta migliore. Potrebbe essere anche un’asta al ribasso: si dice quello che si deve fare, vince chi lo fa al miglior costo. Tali aste possono essere di vario tipo:
  • Primo prezzo: viene pagato il primo prezzo più alto, si va incontro alla maledizione del vincitore.
  • Second-price: non pago quello che ho offerto ma pago quello che ha offerto il secondo, si segue la teoria dei giochi.

Si dimostra che l’asta al primo prezzo è equivalente all’asta olandese e che l’asta al secondo prezzo è equivalente all’asta giapponese (dal punto di vista matematico). L’asta dovrebbe aiutare a pagare il bene quanto lo si valuta, nessuno è costretto a pagare più di quanto si è disposti a pagare. In caso di parità nelle aste scoperte (non a busta chiusa) conta il tempo nel quale vengono fatte le offerte, nelle aste a busta chiusa ci sono dei meccanismi extra che risolvono questi casi.

Complementarità e sostituibilità

• Diciamo che due oggetti A e B sono complementari se il valore di A e B è maggiore della somma dei due oggetti presi separatamente. L’offerente dice: se prendo solo il computer vale 10, se prendo solo il monitor vale 5, se li prendo entrambi il tutto vale 25.
• Due oggetti sono sostituti quando il loro valore insieme è minore della somma del valore dei due oggetti presi separatamente.

Vendere oggetti separatamente è inefficiente. La preoccupazione del progettista dell’asta è la soddisfazione del banditore ma anche degli acquirenti. Supponiamo che il banditore faccia due aste separate costringendo l’acquirente ad acquistare uno dei due oggetti senza sapere se può acquistare anche l’altro, quindi un’asta per il computer e una per il monitor. Chi deve fare un’offerta per il monitor potrebbe offrire il giusto (200) e perderlo di fronte a qualcun altro che offre di più (250). Se al contrario offrisse più di 200 nel caso in cui dovesse perdere l’asta per il computer si troverebbe di fronte ad una perdita. L’offerente sbaglierebbe quindi in entrambi i casi perché tutto dipende da come va la seconda asta.

Le aste sequenziali e le parallele sono inefficienti: mettono in crisi l’offerente ed egli potrebbe pagare un oggetto più di quanto lo valuta. Una soluzione potrebbe essere quella di vendere i due oggetti insieme.

Asta combinatoria

• La prima persona valuta 500 i due oggetti e offre esattamente 500.
• La seconda per portatile e video offre 700.
• La terza offre 300 per il portatile.

Il banditore deve decidere a chi assegnare. Il primo ed il terzo hanno offerte complementari che quindi porterebbero via tutti e 3 gli oggetti, vincono questi due. In questo modo gli acquirenti contenti sono 2 su 3 ed il banditore ha venduto il tutto alla somma più alta (800). In questa slide abbiamo massimizzato i due obiettivi contemporaneamente attraverso l’analisi di tutti i casi possibili. Le soluzioni massimali sono due: il primo ed il terzo oppure solo la seconda. L’insieme 2-3 non era ammissibile perché lo stesso oggetto non può essere venduto a due soggetti diversi. Questo problema lo abbiamo risolto in maniera e