Ricerca operativa - Appunti completi del corso

Ricerca operativa

Algoritmi e complessità computazionale

Complessità f(n): si intende il numero di operazioni necessarie all’esecuzione dell’algoritmo in funzione della dimensione dell’input n. È intesa come complessità in tempo e si considera il caso pessimo.

• Problemi P: è noto un algoritmo che termina in tempo polinomiale alla dimensione dei dati (restituisce una soluzione ottima con una complessità polinomiale).
• Problemi NP: esiste un algoritmo che termina in tempo polinomiale rispetto alla dimensione dei dati nel caso si possa utilizzare un numero indeterminato di macchine in parallelo.
• Problemi NP-Hard: un algoritmo per risolvere uno di questi problemi può essere convertito in un algoritmo per risolvere un qualunque problema NP (a causa di una difficoltà intrinseca richiedono metodi che enumerano tutte le soluzioni possibili, perciò sono problemi irrisolvibili nei casi di importanza pratica).

Problema SAT

• Operatori: and, or, not.
• Clausole: or di variabili booleane.
• Formula in forma normale congiuntiva (and di clausole).

2-SAT è polinomiale, 3-SAT è NP-Hard. Per risolvere un problema 2-SAT si costruisce un grafo in cui ogni clausola (!Xi or Xh) genera due archi: (i,h) e (!h,!i). Il grafo si risolve provando ad assegnare dei valori alle variabili booleane ed eseguendo una propagazione backward (se nodo è F allora predecessori sono F) o forward (se nodo è T allora successori sono T). Una formula F è soddisfacibile se e solo se esiste un indice i tale che sul grafo G si può andare da Xi a !Xi e anche da !Xi a Xi (si verifica una contraddizione).

Se problema q è facile e p si riduce a q, allora anche p è facile. Se problema q è difficile e q si riduce a p, allora anche p è difficile.

Programmazione lineare

Definizione PL: Un problema è definito da:

• Variabili.
• Funzione obiettivo.
• Vincoli.

Un problema è di programmazione lineare se:

• Tutte le variabili sono continue.
• La funzione obiettivo è lineare.
• Tutti i vincoli sono funzioni lineari.

Assunzione forte: no economie di scala (date da relazioni non lineari) e no relazioni tra valori distinti delle variabili.

Assunzioni adatte per un problema modellato in PL

• Proporzionalità: in PL la funzione obiettivo e i vincoli sono funzioni lineari, per cui si hanno assunzioni forti come no economie di scala, no costi fissi, no punti di saturazione.
• Additività: il valore di una variabile non dipende dal valore di altre variabili.
• Divisibilità: il modello può avere valori frazionari, quindi bisogna eventualmente aggiungere dei requisiti di interezza.
• Certezza: i valori assegnati a ogni parametro devono essere costanti note (ottenuti tramite un processo di stima e con un’analisi di sensitività a posteriori).

Descrizione PL

1. La rappresentazione dei vincoli è data da un insieme di rette che si intersecano, formando un politopo.
2. Ci sono diverse curve di isocosto per profitto crescente, che possono essere spostate fino a che non si ha una intersezione non vuota con la regione non ammissibile.
3. Ogni punto che sta all’interno del politopo può essere ottenuto come combinazione convessa dei vertici del politopo.
4. Teorema di Minkowski-Weyl: se un politopo è limitato, allora esiste un vertice che è soluzione ottima del problema in PL.
5. In un problema di combinazione convessa un punto di ottimo locale è anche un ottimo globale.
6. Le funzioni lineari sono un caso particolare di funzioni convesse: l’algoritmo trova una soluzione globalmente ottima.

Per implementare un algoritmo che produca una soluzione localmente ottima (algoritmo di ricerca locale) occorre fornire:

1. Caratterizzazione algebrica dei vertici.
2. Caratterizzazione dell’intorno discreto di un vertice.
3. Definizione delle mosse, ossia lo spostamento dal vertice corrente ad un vertice adiacente.
4. Condizione di ottimalità e test di limitatezza.

Caratterizzazione algebrica dei vertici

1. Vincoli scritti in forma canonica (<=).
2. Vincoli riscritti in forma standard (=), aggiungendo le variabili di slack.
3. Vettore dello spazio Rⁿ riscritto come un sistema del tipo (vettore colonna attributi) * x1 + …
4. Il problema formulato è in R^m, ma si hanno n vincoli: si hanno quindi m-n gradi di libertà, che equivale ad azzerare m-n variabili.
5. Le variabili di scarto si azzerano sulla retta del vincolo corrispondente e hanno valore positivo all’interno del politopo: in ogni vertice si intersecano due vincoli, per cui si azzerano due variabili.
6. Si hanno le variabili in base (le cui colonne vanno a costruire la matrice di base) e le variabili fuori base (poste a 0): la base di un vertice è data da Ab*Xb=b (Matrice di base * Variabili in base = termini noti).
7. Non tutte le basi sono dei vertici del politopo: non basta che le colonne siano linearmente indipendenti, ma anche che le componenti della base non siano negative.

Caratterizzazione di intorno discreto di un vertice

L'algoritmo ad ogni iterazione verifica che se c'è un vertice adiacente con una valutazione migliore della funzione obiettivo: se c'è si sposta sul vertice e itera il procedimento, altrimenti si ha un'ottimalità locale nell'intorno.

Due vertici sono adiacenti su un politopo se:

• I vertici adiacenti in uno spazio Rⁿ condividono n-1 vincoli attivi.
• Le matrici di base di vertici adiacenti differiscono per 1 colonna.
• Due vertici adiacenti giacciono lungo il medesimo spigolo, il quale rappresenta la direzione di spostamento lungo la frontiera.

Intorno di un vertice: insieme di tutti i vertici le cui soluzioni di base ammissibili differiscono di un solo elemento.

Condizione di miglioramento della funzione obiettivo: c*d < 0 (c vettore in R^m, d direzione di spostamento).

Algoritmo del simplesso

È un algoritmo iterativo strutturato come una ricerca locale:

1. Si ha una soluzione ammissibile di partenza (un vertice, ossia una soluzione di base ammissibile).
2. Si valuta l’ottimalità della soluzione corrente: se non è soddisfatta si costruisce l’intorno.
3. Se c’è un vertice in cui il valore della funzione obiettivo migliora ci si sposta nel nuovo vertice.
4. L’algoritmo itera finché il vertice corrente non soddisfa le condizioni di ottimalità.

Nel caso peggiore l’algoritmo potrebbe richiedere di visitare tutti i vertici della regione ammissibile, comportando un numero esponenziale di iterazioni. Nel caso medio richiede invece una complessità lineare rispetto al numero di variabili, per cui è un algoritmo molto efficiente.

Test di ottimalità: la condizione sufficiente affinché una soluzione di base ammissibile sia ottima per un problema di minimo è che il vettore dei costi ridotti sia non negativo. Un costo ridotto negativo indica una condizione di miglioramento ed è utilizzato per decidere se spostarsi o meno su un nuovo vertice. Il costo ridotto di una variabile fuori base rappresenta la variazione della funzione obiettivo che si avrebbe se tale variabile entrasse in base. I costi ridotti delle variabili fuori base dicono quanto varia z al variare della corrispondente variabile. I costi ridotti delle variabili in base sono nulli.

Analisi post-ottimale

Analisi di sensitività: dice quanto è robusta la soluzione ottima trovata rispetto alla variazione di alcuni parametri del modello. In particolare per una variabile, il solver controlla quali sono le variazioni massime che può tollerare la soluzione ottima per rimanere tale rispetto alla variazione del coefficiente associato alla variabile. Nell’analisi di sensitività interessa valutare i cambiamenti che si manifestano nel valore ottimo a seguito di cambiamenti nei valori dei coefficienti della funzione obiettivo, dei vincoli o dei termini noti.

Analisi di post-ottimalità: stabilisce gli intervalli di variazione dei dati numerici del problema entro cui la base ottima del problema di PL non cambia.

Prezzi ombra: nel caso di un problema di mix produttivo, il valore ottimo dell’i-esima variabile duale indica il massimo prezzo che l’azienda sarebbe disposta a pagare per acquistare un’unità aggiuntiva della risorsa rappresentata dall’i-esimo vincolo. I valori ottimi delle variabili duali vengono anche detti prezzi ombra. Il prezzo ombra di una risorsa coincide quindi con il suo valore marginale.

Problema primale e duale

Descrivendo uno stesso problema in due spazi decisionali differenti si hanno due soluzioni, ciascuna con lo stesso valore di funzione obiettivo perché la soluzione rappresenta un punto di equilibrio e si ha lo stesso ottimo.

Corrispondenza tra problema primale e duale:

• Ad ogni vincolo del primale corrisponde una variabile nel duale.
• Ad ogni variabile nel primale corrisponde un vincolo nel duale.

Dato un problema di PL di minimo, esiste un altro problema di PL di massimo (il suo duale) che ha lo stesso valore di funzione obiettivo nel punto di ottimo. Il primale è associato ad un problema di minimo, mentre il duale è associato ad un problema di massimo.

Esempi: Vertex Cover - Matching.

Programmazione lineare intera

La PLI viene utilizzata in problemi che non godono della proprietà di divisibilità o che richiedono una modellazione con variabili binarie. Lavorando con variabili intere si ha che la regione ammissibile non è più convessa, quindi le soluzioni sono i punti della griglia intera contenuta all’interno del politopo.

Si ha quindi che il valore ottimo trovato con la PL è una stima ottimistica di quello trovato con PLI:

• Nella PL l’ottimo sta su un vertice, ma non è detto che tale vertice abbia coordinate intere.
• Nella PL si è meno selettivi e si comprendono molte più soluzioni rispetto alla PLI.

Caso ideale: il politopo associato ai vincoli ha tutti i vertici con coordinate intere (è combinazione convessa delle soluzioni intere) e il problema si risolverebbe come se fosse di PL. Questo è verificato se la matrice dei vincoli gode della proprietà di totale unimodalità: in questo caso si è sicuri che i vertici del politopo avranno tutti coordinate intere. Nel caso la matrice dei vincoli non sia unimodulare si deve usare l’algoritmo di Branch & Bound.

Branch & Bound

Si esegue il rilassamento continuo del problema a variabili intere, ottenendo soluzioni con valori frazionari. Il B&B si basa sul concetto di ‘dividi et impera’: si suddivide il problema principale difficile in sottoproblemi più semplici e si risolve il problema di massimo su ogni sottoinsieme, con l’ottimo globale che è dato dal massimo dell’ottimo di tutte le partizioni.

La struttura ottenuta è una struttura ad albero: ogni nodo rappresenta un sottoproblema e i suoi figli rappresentano i sottoinsiemi in cui si ha partizionato le soluzioni del nodo. Tale approccio non è ottimale perché comporta un’enumerazione di tutte le possibili soluzioni, con un costo esponenziale: il B&B esplora infatti parte dell’albero in modo implicito, escludendone parti a priori.

Una soluzione ottima del rilassamento lineare trovata rappresenta la miglior soluzione per quel sottoproblema: se è peggiore dell’ottimo candidato allora si può evitare di esplorare un sottoalbero perché sicuramente non si troverà una soluzione migliore. Tale valore rappresenta un bound.

Step:

1. Dato il problema rilassato si ottiene una soluzione ottima del rilassamento lineare, che rappresenta una stima ottimistica della soluzione ottima.
2. Se la soluzione non è intera si esegue una partizione della regione ammissibile in due sottoproblemi, in cui ogni nodo figlio eredita tutti i vincoli del padre e un vincolo aggiuntivo (es. x<=4 e x>=5 se x*=4.5).
3. Se la soluzione ottima del rilassamento lineare è maggiore dell’ottimo candidato allora si continua ad esplorare l’albero, al contrario si interrompe l’esplorazione di quel sottoalbero.
4. Si partiziona finché non si trova una regione non ammissibile oppure si trova un problema con una soluzione intera (che è quindi già la soluzione ottima per quel sottoalbero).

Flussi su rete

Grafi non orientati

Definizioni

• Cammino: sequenza di archi consecutivi con vertice in comune.
• Nodi connessi: esiste un cammino che li collega.
• Taglio: struttura che si ottiene operando una partizione dei nodi in due sottoinsiemi. Tutti i nodi che collegano un nodo tra i due insiemi sono detti archi di taglio.
• Albero di copertura: è un sottografo aciclico, connesso e massimale (massimale aciclico e minimo connesso).
• Grafo bipartito: si partizionano i nodi in due sottoinsiemi e gli unici archi che esistono hanno i due vertici nei due sottoinsiemi.
• Grafo hamiltoniano: esiste un ciclo che passa esattamente una volta da ciascun vertice.

Un grafo è bipartito se e solo se non contiene cicli dispari. Un grafo è connesso se e solo se una procedura di visita a partire da un qualsiasi nodo visita tutto il grafo.

Visita di un grafo non orientato

• Una struttura dati Q (coda o pila) contiene i nodi visitati ma non ancora processati.
• Si estrae un nodo da Q e per ogni arco adiacente si visita il nodo adiacente.
• Si ha memoria degli archi visitati (i quali nodi non dovranno essere inseriti in Q).
• Si ha memoria dei nodi da portare avanti nella procedura di visita (nodi non ancora visitati e che quindi dovranno essere inseriti in Q).

Grafi orientati

Arco (i,j) incidente in i e uscente in j: i è detta coda e j è detta testa.

• Stella uscente: set di archi uscenti da un nodo.
• Stella entrante: set di archi entranti in un nodo.
• Cammino orientato: gli archi devono essere consecutivi, ossia la testa di un arco è la coda dell’arco successivo lungo il cammino.
• Ciclo: è un cammino orientato chiuso.
• Grafo fortemente connesso: ogni coppia di nodi è raggiungibile attraverso un cammino orientato.
• Taglio orientato: gli archi sono orientati dal primo insieme al secondo insieme o viceversa.

Accoppiamento di massima cardinalità (matching) su grafo bipartito

Dato un grafo bipartito, si vuole selezionare il maggior numero di coppie, in cui ogni coppia è associata ad un arco: gli archi assumono valore 0 o 1 a seconda che siano selezionati o meno. Un matching, in generale, è un insieme di archi senza nodi in comune.

Vincoli del problema:

• Ogni elemento sta al più in una coppia.
• Le coppie di archi incidenti sul nodo è al più 1.

La matrice dei vincoli è totalmente unimodulare, quindi esistono algoritmi polinomiali per risolvere questo problema. Un nodo può essere esposto o accoppiato. Un arco può essere libero o accoppiato.

Il problema viene risolto attraverso la definizione di cammini alternanti aumentanti: è un cammino che va da un nodo esposto del primo insieme del grafo bipartito ad un nodo esposto nel secondo insieme, composto da una sequenza alternata di archi liberi e accoppiati. Una volta trovato un cammino, si inverte lo stato di tutti gli archi che compongono il cammino tra i due nodi esposti nei due sottoinsiemi. L’effetto è che scambiando lo stato di un arco del cammino da libero ad accoppiato (o da accoppiato a libero) si ottiene un matching con un arco in più.

L’algoritmo dei cammini alternanti aumentanti memorizza in una coda tutti i nodi esposti nel primo insieme del grafo bipartito e ad ogni iterazione verifica per ogni arco della stella uscente se riesce ad individuare un cammino alternante aumentante. Se viene trovato un cammino allora viene invertito lo stato di tutti gli archi del cammino.

Approccio greedy: selezionare ad ogni step l’arco con grado minore (più difficile da accoppiare). Non restituisce una soluzione ottimale.

Accoppiamento di massima cardinalità (matching) su grafi qualsiasi

Invece di utilizzare un cammino alternante aumentante si procede eseguendo la selezione di un arco e la selezione di un sottoinsieme di nodi.

Non-Crossing matching

Gli archi del matching non si devono incrociare. Si ha che se un elemento della prima coppia precede quello della seconda coppia, allora anche nel secondo insieme si deve rispettare tale condizione. Si costruisce un grafo bipartito dato dall’unione degli archi che collegano ad esempio la stessa lettera nelle due stringhe e si cerca il matching di massima cardinalità in cui gli archi non si incrociano.

Stable marriage

Si vuole ottenere una situazione stabile, in cui nessuno ha vantaggio a cambiare la propria scelta. Ogni vertice ha un ranking da 1 a N degli elementi dell’altro insieme (N è l’elemento preferito). Ogni nodo di sinistra si propone ad un nodo dell’insieme di destra in base al ranking più alto: se un nodo di destra è richiesto da più nodi allora sceglie il nodo con il ranking più alto, scartando gli altri nodi. Un nodo di sinistra rifiutato sceglierà poi un altro nodo sempre in base al ranking. La soluzione ottenuta è stabile perché, considerando tutte le coppie in soluzione, non si verifica la condizione per cui entrambi gli elementi avrebbero vantaggio ad essere accoppiati con un altro elemento.

Problemi di flusso su rete

• Problemi di cammino a costo minimo: gli archi hanno una direzione di percorrenza e un costo associato ad ogni arco.
• Problemi di flusso massimo: è un problema nella rete con un flusso che si muove e gli archi hanno un limite massimo nella quantità di flusso che può passare.
• Problema di flusso a costo minimo: ad