Appunti Ottimizzazione Combinatoria Gestionale, Sapienza

Problemi di OC con funzione obiettivo lineare

Definizione dei problemi di OC con funzione obiettivo lineare

Un problema di Ottimizzazione Combinatoria (OC) ha come obiettivo la massimizzazione o la minimizzazione di una certa funzione obiettivo f(x) soggetta a determinati vincoli con particolari caratteristiche. In generale, dato un insieme di possibili alternative S, si deve trovare quell’alternativa che soddisfi determinati requisiti. Per scegliere la S migliore, è necessario stabilire un criterio di scelta quantitativo che ci permetta di determinare l’alternativa migliore: tale criterio è rappresentato da una funzione f(x), dove x è la variabile del problema.

Un modello di Ottimizzazione è composto quindi da un Problema di Decisione (ossia un problema del tipo max {f(x) : x∈ S}), dove x è la variabile di decisione. La soluzione di tale problema sarà un certo x* tale che f(x*) > f(x) per ogni x in S.

Il termine “Combinatoria” indica invece una condizione sull’insieme delle possibili alternative S: nei problemi di OC, infatti, si assume che S sia un insieme discreto, e che la cardinalità di S sia finita: 1 < |S| < ∞. Questo implica che la cardinalità dell’insieme delle Soluzioni Ammissibili per il nostro problema debba essere necessariamente finita. È quindi possibile determinare una soluzione del problema di decisione, procedendo per enumerazione completa.

Modelli di OC con funzione obiettivo lineare sono un particolare tipo di modello di OC, dove la funzione obiettivo è di tipo lineare. Tale modello ha una struttura caratteristica e tipica di seguito descritta. Definito un “insieme base” (B), ossia la totalità dei possibili eventi elementari, si definiscono soluzioni ammissibili SB l’insieme degli eventi che rispettano le condizioni date e quindi l’insieme delle possibili alternative che possono essere attuate.

Ad ogni possibile evento si associa quindi un costo o vantaggio elementare, parametri che permettono di determinare la funzione obiettivo o di costo c: S → R, con c(S) = Σ .

Relazione tra problemi di OC con f.o. lineare e problemi di PL01

Definiti come PL i problemi di Ottimizzazione Combinatoria aventi funzione obiettivo lineare, si definiscono PL01 quei problemi aventi tutte le caratteristiche dei PL, ma caratterizzati da variabili decisionali x, necessariamente binarie. Qualunque problema di OC con funzione obiettivo lineare può essere riscritto come problema di PL01. Tale procedimento può avvenire, ad esempio, rappresentando le variabili decisionali sottoforma di “vettori di incidenza”, ossia quei vettori che, dato B ed una sua soluzione ammissibile S, hanno componente i-esima pari a 1 se S e hanno componente nulla altrimenti.

Definizione del problema di “Pianificazione degli investimenti”

Un particolare problema di PL01 è quello di “pianificazione degli investimenti”. Dato l’insieme degli investimenti I e i relativi indici di redditività, si vuole determinare, tra i possibili investimenti effettuabili, quell’insieme di investimenti che garantisca maggiori guadagni. Tale insieme è vincolato dal budget dell’azienda nei diversi periodi j-esimi: dati = (, …) il vettore dei flussi di cassa associato all’investimento i-esimo, la somma dei flussi di cassa deve essere inferiore al budget di periodo. Le variabili di decisione sono le {0,1} a cui corrisponde o meno l’attivazione del progetto i-esimo.

Esempi di vincoli di relazioni tra Progetti

• i < j – se l’investimento j-esimo è attivato, i non può essere svolto.
• i ≤ j – i può essere attivato solo se j viene attivato.
• i + j < 1 – solo uno degli investimenti può essere attivato.
• i = (-j + 1) – i è svolto se j non viene svolto.
• i ≤ j + h + (1 – k) – i può essere svolto o se j è attivato o se h è attivato o se k non è attivato (con il diviso 3 vale l'“e”).

Esempio di pianificazione degli investimenti e formulazione naturale

Esempio con 3 investimenti e 7 periodi. Flussi di cassa:

Budget dei vari periodi b = {11, 20, 20, 20, 20, 0, 0}.

Formulazione naturale di:

• 10x₁ - 3x₂ + 5x₃ ≤ 11
• 10x₁ + 5x₂ + 5x₃ ≤ 20
• -12x₁ + 3x₂ + 5x₃ ≤ 20
• 10x₁ - 20x₂ + 0x₃ ≤ 20
• -20x₁ + 10x₂ - 5x₃ ≤ 20
• 0x₁ - 20x₂ - 10x₃ ≤ 0
• 0x₁ + 0x₂ - 20x₃ ≤ 0

Classi di complessità P ed NP

Concetti relativi alla complessità computazionale

Dato un problema di ottimizzazione combinatoria, si definiscono i relativi insiemi delle istanze “I” e delle soluzioni ammissibili “S”: tali insiemi determinano vincoli e variabili del problema, la cui funzione obiettivo si può quindi definire come F(I). Un modo per risolvere il problema, senza ricorrere all’enumerazione completa, è quello di determinare un algoritmo che permetta di trovare una soluzione ottima per il problema di massimizzazione o minimizzazione. Tale algoritmo deve avere due caratteristiche fondamentali: deve essere corretto ed efficiente.

Con “corretto” si intende la capacità propria dell’algoritmo di risolvere un dato problema. L’efficienza ha come benchmark lo spazio e il tempo. Per spazio si intendono il numero di bit utilizzati dall’algoritmo al fine di determinare una soluzione di F(I); per tempo si intende invece il numero di passi che la macchina compie per trovare la soluzione. La determinazione del numero di passi, e quindi il loro conteggio, dipende dal modello di macchina usata: per esempio, nella Random Access Machine, il conteggio si incrementa di un’unità ogni volta che viene compiuta un’“operazione elementare” (chiamata di funzioni, assegnazione di nomi a variabili, somma, divisione etc.). Il numero di passi eseguiti dalla macchina determina il “Tempo di esecuzione”.

Maggiore sarà il tempo richiesto dalla macchina per lo svolgimento completo dell’algoritmo, maggiore sarà la “complessità” dell’algoritmo stesso. In termini quantitativi è possibile definire la complessità come il numero di passi necessari per trovare la soluzione di un’istanza di dimensione SIZE(I), dove SIZE(I) corrisponde al numero di celle necessario per rappresentare I. Essa sarà dunque una funzione avente come variabile proprio la dimensione delle istanze – c(SIZE(I)).

Poiché non è nota a priori SIZE(I), e nemmeno la probabilità che si presenti una certa istanza, si studiano due casi particolari: il “caso migliore” B(d) ed il “caso peggiore” W(d). Il primo è di scarso interesse e si presenta rare volte. Il secondo invece corrisponde ad un caso patologico, in presenza del quale la macchina deve essere comunque in grado di risolvere il problema in tempi definiti. Per semplificare la trattazione si studiano gli “Upper Bound”, ossia gli ordini, di SIZE(I). Si dice che la “complessità nel caso peggiore” è O[g(SIZE(I))] se e solo se g(SIZE(I)) è Upper Bound di W(SIZE(I)). A seconda del fattore all’interno di O() si definiscono due tipi di complessità:

• Complessità Polinomiale - O(SIZE())
• Complessità Esponenziale – altrimenti

Classi di Complessità P e NP

Per ampliare la trattazione, senza limitarci quindi al modello della Random Access Machine, si introduce il concetto di Macchina di Turing: tale macchina è composta da componenti ideali:

• NASTRO: insieme infinito di celle (ad ognuna delle quali corrisponde un simbolo).
• TESTINA: strumento che legge o scrive sul Nastro.
• PROGRAMMA: uno strumento che dice alla macchina cosa fare per ogni stato e simbolo in input.
• STATO: appartiene all’insieme dei possibili stati della macchina.

Essa può essere di due tipi diversi:

• Deterministica.
• Non Deterministica.

La prima, per ogni valore in ingresso, segue un comportamento predeterminato, restituendo un certo output; la seconda, dato un input, può scegliere tra diverse opzioni, e quindi restituire tipi diversi di output. In relazione a tale differenziazione si definiscono 3 classi di problemi:

• P: problemi Polinomiali risolvibili con Macchina di Turing Deterministica.
• NP: problemi Polinomiali risolvibili con Macchina di Turing Non Deterministica.
• ExpT: problemi Esponenziali risolvibili con Macchina di Turing Deterministica.

Un problema che abbia complessità si dice NP-Hard, un problema che sia NP e che rientri in NP si dice NP-Completo.

Relazioni tra le classi P e NP

Tra le 3 classi vige un regime di inclusione: è chiaro che un problema P, può essere risolto anche con una Macchina di Turing Non Deterministica, non è scontato il contrario. Uno dei Millennium Problems riguarda proprio questo aspetto: è possibile dire che P ≡ NP? Tale fatto è di notevole importanza dal momento che molti problemi comuni (OC e PL01) si trovano nell’insieme NP-P, e sono oggi risolvibili solo in tempo esponenziale. La PL appartiene invece alla classe P.

Formulazioni e rilassamento lineare

Formulazione di un Problema di PL01

Un Problema di PL01 è caratterizzato da una funzione obiettivo lineare che si vuole massimizzare o minimizzare, all’interno di determinati vincoli S, inoltre le variabili di decisione x, sono vincolate ad assumere un valore binario x∈{0,1}. Si definisce Formulazione di PL01 il nuovo insieme P= {x∈S : x∩{0,1} = {0,1}}, la caratteristica dell’insieme P è quella di dover soddisfare la seguente proprietà. Si ottiene così la seguente relazione:

min{f(x) : x ∈ S} = min {f(x) : x ∈ S ∩ {0,1}} = min{f(x) : x ∈ P}

Definizione di Rilassamento Lineare

Un problema di PL01 potrebbe rientrare nella classe NP, e non sarebbe facile da risolvere. Per poter semplificare i calcoli si applica quindi un Rilassamento Lineare sul problema di PL01, ossia vengono eliminati i vincoli sulle variabili di decisione x, che può assumere valori reali, non necessariamente binari. In tal modo si ci riconduce ad un problema di PL e quindi ad una complessità di tipo P.

Definizione di Lower Bound e di Gap

Dato un insieme S, un Lower Bound (limitazione inferiore) è un valore di tutti gli elementi di S, un Upper Bound si definisce specularmente. Nota una soluzione ammissibile, il Lower Bound ci fornisce una certificazione di qualità relativa a tale soluzione. Infatti, studiando il “gap” che si instaura tra la soluzione ammissibile ed il LB, ossia la differenza tra i due valori, si può avere una misura dell’errore che si sta commettendo approssimando con una soluzione sub-ottimale.

Per migliorare il nostro algoritmo ci possono porre due distinti obiettivi:

• Miglioramento di LB
• Miglioramento della qualità della soluzione

Definizione di Qualità di Formulazione

Minore sarà la distanza tra il LB(P) e una data soluzione ammissibile, maggiore sarà la qualità della formulazione. Infatti, la soluzione ottima del problema originario di PL01 si trova all’interno dei due valori che stiamo rapportando. Minore sarà la loro distanza, minore sarà l’errore che stiamo commettendo nella ricerca del valore ottimo. Per rapportare due o più formulazioni si deve però determinare un criterio univoco che non dipenda dalla funzione obiettivo. Tale criterio afferma come minore sarà la dimensione del poliedro che applichiamo come limite sulla funzione obiettivo, e minore sarà il gap di quella formulazione: P₁ ⊆ P₂ è migliore di P₁ se il gap di P₂ è minore.

Definizione di Formulazione Ottima

Stabilito il criterio di qualità, è chiaro come una formulazione ottima possa essere definita come tale, se è inclusa in ogni altra possibile formulazione. Stiamo quindi cercando quel poliedro che sia contenuto in ogni altro possibile poliedro, in termini matematici: P* = {x ∈ R^n : Ax ≤ b} ⊆ P per ogni altra formulazione P. Se la Formulazione Ottima rispetta tali requisiti, è chiaro che l’insieme S, corrisponde con l’insieme dei vertici di R^n. Dal momento che la soluzione ottima su R^n si trova in corrispondenza dei vertici, è chiaro che la soluzione della Formulazione Ottima, sarà proprio uguale alla soluzione del problema di PL01.

Definizione Rilassamento della Formulazione Ottima

Purtroppo però non è immediata l’individuazione della formulazione ottima, talvolta è possibile però ricavarne un rilassamento, ovvero un poliedro che abbia le seguenti caratteristiche:

• Il poliedro P è una formulazione di S.
• Ax ≤ b è costituito da un insieme di famiglie di disequazioni appartenenti al sistema.

Ciascun rilassamento produce un Lower Bound della Formulazione Ottima.

Esempio numerico di Formulazione Naturale e di Formulazione Ottima per un problema di Pianificazione degli Investimenti in un singolo periodo

Formulazione naturale:

• 4x₁ + 2x₂ ≤ 5
• x₂ + x₁ ≤ 11
• x₂ ≤ 1
• x₁ ≥ 0
• x₂ ≤ 1
• x₂ ≥ 0

Algoritmi di Branch & Bound

Problemi risolti dall'algoritmo di Branch & Bound

L’algoritmo di Branch & Bound risolve problemi di PL01 (PLI). Dato un problema di Programmazione Lineare Intera, o Binaria, si vuole trovare numericamente, nell’insieme ammissibile S, l’ottimo: {min c(x) : x ∈ S} con x ∈ {0,1}, dove S corrisponde all’insieme dei punti interi (o binari) all’interno di un poliedro P (che corrisponde alla formulazione scelta).

Concetti di Branching e Bounding

Dato che il numero di punti ammissibili è finito, si potrebbe procedere per enumerazione completa. Tuttavia, la cardinalità dell’insieme delle soluzioni ammissibili potrebbe essere molto grande, e potremmo avere a che fare con un problema del tipo NP. Si potrebbe:

• Cambiare il tipo di enumerazione.
• Provare a migliorare la formulazione.
• Approssimare per difetto e per eccesso la soluzione in modo da ridurre il gap.

Non è detto però che arrotondando all’intero più vicino l’ottimo di un problema di PL, si ottenga un valore ammissibile oppure ottimo per il rispettivo problema PL01. Si cerca quindi di cambiare il tipo di enumerazione: si utilizzerà un approccio di soluzione basato sull’enumerazione implicita. Le idee di base di tale tipo di enumerazione sono le seguenti:

• Partizionamento dell’insieme ammissibile in insiemi più facili (sotto-problemi).
• Procurarsi una soluzione ammissibile per il singolo sotto-problema (ottimo corrente).
• Continuare a risolvere i restanti sotto-problemi, aggiornando ogni volta l’ottimo corrente, se necessario.

Tale concetto base si applica quindi mettendo in pratica 2 operazioni fondamentali:

• Branching – Tecniche per generare sotto-problemi semplici, ma non troppo numerosi.
• Bounding – Tecniche per valutare quanto di meglio potrei ottenere su un sotto-insieme.

Il processo di Branching si applica, nella maggior parte dei casi, utilizzando il metodo del “binario agli interi più vicino”: se risolvendo il rilassamento lineare si determina una soluzione con componenti non intere (frazionarie), per esempio preso il vettore x, si determina una componente con valore frazionario, questo implica che il sotto-problema non era sufficientemente facile.