Risposte alle domande esame

Algoritmo di branch and bound

L'algoritmo di Branch and Bound è un algoritmo che risolve in un tempo finito, anche se potrebbe essere molto lungo, problemi di ottimizzazione combinatoria. Questo si basa sui concetti di bounding e branching. L'idea di fondo è dividere il problema ammissibile in sottoproblemi ammissibili Pi più facili da risolvere tali che l'intersezione di tali sottoinsiemi sia l'insieme vuoto e la loro unione il problema di partenza.

È poi necessario trovare un ottimo corrente risolvendo un particolare Pi e risolvere tutti gli altri eliminando quelli dove il LB non è migliore dell'ottimo corrente e analizzando gli altri quindi aggiornando l'ottimo corrente quando si trovano soluzioni ammissibili migliori o partizionando nuovi sottoinsiemi.

Concetto di bounding

Il concetto di bounding si fonda sul rilassamento lineare, vale a dire il problema Pi viene risolto eliminando i vincoli di interezza e minimizzando. Si otterrà un valore che sarà minore o uguale della funzione con il vincolo di interezza. Il gap tra l'ottimo rilassato e l'ottimo non rilassato dipende dalla qualità della formulazione di Pi del sottoproblema Si. Inoltre, altre tecniche sono eliminare vincoli difficili e perciò il minimo diminuirà o al più resterà uguale, oppure si può modificare la fo in modo che pure essendo minore uguale di quella di partenza su quel particolare Pi sia più semplice da risolvere.

Concetto di branching

Il concetto di branching si basa sul fatto che, quando, dopo aver risolto il problema, si ottiene un xk che non è un vettore a componenti intere, ad esempio ha valore vk, allora si partiziona Pi in Pi+1 e Pi+2 dove:

• Pi+1 è Pi intersecato con gli x tali che x <= parte inferiore di vk
• Pi+2 è Pi intersecato con gli x tali che x >= parte superiore di vk.

In tal modo viene omessa una parte di Pi che non contiene comunque soluzioni intere e iterando il procedimento alla fine si arriverà a una soluzione intera. Tale schema va bene nel caso di minimizzazione, nel caso di massimizzazione è tutto il contrario.

Si inizia inizializzando una lista con P0, ad esempio il problema di partenza x0 non si pone o si mette uguale al valore trovato euristicamente, e si mette un UB peggiore possibile ovvero più infinito o cx0 se ne disponiamo. Poi si vede se la lista dei sottoproblemi è vuota. In caso affermativo x0 è l'ottimo, viceversa si sceglie un Pi della lista (rilassato linearmente) e si risolve il problema ottenendo un LBi (il minimo di Pi) e x(Si). Successivamente si verifica se LBi < UB; in caso negativo si torna indietro, vale a dire si sceglie un altro sottoproblema se disponibile (non ha senso andare avanti se quello che ho ottenuto è peggiore di quello che già ho). Se invece LBi < UB, allora ci si chiede se X(Pi) è intero: in caso affermativo, significa che è ammissibile anche per il problema senza rilassamento lineare (quello di partenza) e allora si pone UB=LB e x0=x(Pi), cioè uguale al vettore che mi genera LBi, e si torna a verificare un altro problema della lista. Se invece non è così, allora si fa il branching, dando vita a due nuovi sottoproblemi che si aggiungono a quelli già presenti nella lista e si ritorna al punto iniziale e così via.

Le scelte da effettuare sono molteplici: in primis quale sottoproblema scegliere. Il criterio di scelta può essere basato su logica:

• Fifo (il primo che entra nella lista è il primo che analizzo)
• Lifo (l'ultimo che entra in L è il primo che analizzo)
• Quello con minimo LB (che hanno LB più promettenti)

Altra scelta è come scegliere xk variabile di branching: si può scegliere o la variabile più intera o quella più frazionaria, o secondo un ordine prestabilito. È fondamentale ricordarsi che ogni scelta effettuata potrà influenzare l'algoritmo sia in modo positivo che negativo.

Algoritmo di Floyd-Warshall

Dato un grafo G(N,A) orientato e connesso e dei costi sugli archi wuv per ogni uv appartenente ad A, l'algoritmo ci trova il cammino minimo da ogni nodo a qualsiasi altro nodo. Dato un insieme di nodi N={1,2,...,n} definiamo Pij^d=(i,k1,k2,...,kq,j) e Nd={1,2,...,d) come il cammino minimo avente per estremi i e j e come nodi interni ovvero attraversabili dal cammino i nodi in Nd. Perciò avremmo che il costo del cammino Pij^k sarà dij^k; a questo punto si definisce una matrice DK dove ogni elemento sarà proprio il costo minimo per andare dal nodo i al nodo j potendo passare per nodi interni che vanno da 1 a k ovvero sarà associato ogni elemento al cammino Pij^k.

Avremo come punto di partenza la matrice D0 dove ogni elemento della matrice è proprio il costo dell'arco tra un nodo e un altro (se non c'è arco naturalmente si mette come costo più infinito). E poi, andando avanti, si costruirà la matrice D1, D2, D3 ecc... fino alla matrice Dn, dove per andare da un nodo a un altro si potranno attraversare tutti i nodi del grafo. Per passare dalla matrice D(k-1) alla matrice Dk, per ogni ij ovvero per ogni elemento si devono confrontare i costi dij^(k-1) con i costi dik^k-1 + dkj^k-1 e verrà posto nella matrice Dk il minimo tra i due valori.

Il significato è il seguente: se ho meno costi per andare da i a j passando per il nodo k (che al momento precedente mi era inaccessibile) allora sfrutto tale opportunità, in caso contrario conservo il costo del cammino precedente. Ogni volta che si costruisce una matrice D si costruisce anche una matrice pred delle stesse dimensioni di D dove per ogni coppia di nodi ci dice qual è il nodo precedente che si deve attraversare per arrivare al nodo di arrivo.

Nel momento in cui viene inizializzata la matrice D0, la matrice pred viene inizializzata in modo tale che per andar da un nodo a qualsiasi altro il predecessore sia il nodo di partenza (non posso passar per alcun nodo eccetto quello di partenza o di arrivo). Man mano che l'algoritmo va avanti la matrice pred viene aggiornata inserendo nel posto ij il predecessore nel cammino tra i e j.

Esempio

• N1 N2 N3 N4
• Costi:
• N1N2 4
• N1N3 2
• N1N4 1
• N3N1 -1
• N3N2 1
• N4N3 2

Algoritmo greedy

Definiamo algoritmo: procedura in grado di individuare, in passi successivi, una soluzione per una generica istanza di un problema. La complessità nel caso peggiore corrisponde al numero di passi da fare per determinare una soluzione con l'istanza più difficile da risolvere di dimensione size(I). Questa viene molto utilizzata perché il caso migliore si ottiene in situazioni molto favorevoli e poco probabili, mentre il caso peggiore pur presentandosi in istanze patologiche riesce comunque a rappresentare prudentemente la complessità dell'algoritmo.

Per poter essere ancora più sicuri di non prendere sotto-casi particolari, nella maggior parte delle volte si prende una approssimazione superiore g(size(I)) di W(size(I)) la cui complessità si indica con O(g(size(I))).

Avendo a disposizione un insieme base E={1,2,...,n} e avendo modo di verificare se una soluzione fa parte dell'insieme ammissibile S={F₁, F₂, ..., F_m} F ⊆ E, inoltre se H ⊆ F allora H è una soluzione parziale che può diventare una soluzione ammissibile aggiungendo elementi. L'idea che mette in piedi l'algoritmo di greedy è la seguente:

• Bisogna prima di tutto costruire una sequenza di soluzioni parziali H₀, H₁, H₂, H₃
• Partendo dall'insieme vuoto ovvero la soluzione parziale H₀
• A ogni iterazione aggiungiamo l'elemento che in quel momento genera la soluzione parziale di costo minimo (poiché tale algoritmo non ritorna sulle sue decisioni non garantisce di trovare la soluzione ottima).
• L'algoritmo finisce i suoi passi quando la soluzione parziale diventa soluzione ammissibile completa.