Ricerca operativa - Appunti completi del corso

Una soluzione ottima del rilassamento lineare trovata rappresenta la miglior soluzione perquel sottoproblema: se è peggiore dell’ottimo candidato allora si può evitare di esplorare unsottoalbero perché sicuramente non si troverà una soluzione migliore. Tale valorerappresenta 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 indue sottoproblemi, in cui ogni nodo figlio eredita tutti i vincoli del padre e un vincoloaggiuntivo (es. x<=4 e x>=5 se x*=4.5)
3. Se la soluzione ottima del rilassamento lineare è maggiore dell’ottimo candidatoallora si continua ad

esplorare l'albero, al contrario si interrompe l'esplorazione di quel sottoalbero4. 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

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 le 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. 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 es. 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.

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 ogni arco è associato un costo per unità di flusso e la capacità associata di flusso, con ogni nodo che è un emittente di flusso sulla rete o un ricettore di flusso oppure di solo transito. Si vuole instradare il flusso dai nodi che lo immettono sulla rete verso i