Cosa è una rete? Con il termine rete indichiamo un grafo G = (N, A) pesato, cioè ai cui nodi e/o archi sono associati dei valori numerici detti pesi
"Cosa vuol dire se l'etichetta b di un nodo è positiva?" "bi rappresenta la quantità del bene che esce dalla rete al nodo i. E' quindi detto domanda del nodo, e il nodo viene detto destinazione o pozzo."
Cosa vuol dire se il bi di un nodo è negativo? Rappresenta la quantità di bene che entra nella rete al nodo i. bi viene detto offerta del nodo, ed il nodo viene detto sorgente, o origine.
Cosa vuol dire se bi di un nodo è nullo? Vuol dire che i è un nodo di trasferimento.
"Nei problemi di flusso, la domanda globale è uguale all'offerta globale, questo significa che..." "La somma dei bi di tutti i nodi dev'essere uguale a zero, e la somma dei nodi di bilancio negativo dev'essere uguale a meno la somma dei nodi di bilancio positivo."
Quali sono gli elementi di un algoritmo di visita? La procedura di visita riceve in input il grafo orientato e un nodo origine, la radice r, e determina i nodi raggiungibili da r per mezzo di cammini orientati. Tali cammini individuano un albero che viene fornito attraverso il vettore predecessore.
"Qual è la complessità dell'algoritmo di visita?" "E' limitata superiormente dal numero di archi perché non si visita più di un nodo alla volta."
"L'implementazione di Q, insieme dei nodi da esaminare, come fila (queue), (FIFO), crea una procedura di visita..." BFS, Breadth-first search, In ampiezza, a ventaglio.
"L'implementazione di Q, insieme dei nodi da visitare come pila (stack) (LIFO), rende una procedura di visita..." DFS, depth first search, a scandaglio, in profondità.
Le procedure di visita in ampiezza e in profondità creano alberi diversi. VERO.
La procedura di visita in cui Q è implementato come fila (FIFO) determina, per ogni nodo i raggiungibile da r... Un cammino orientato da r a i di lunghezza minima in termini di numero di archi.
Definisci il problema del cammino minimo da r a t su un grafo orientato e pesato G = (N, A) dove ad ogni arco è associato un costo cij Per ogni cammino P in G il costo C(P) è dato dalla somma dei costi degli archi che lo costituiscono. Il problema del cammino minimo vuole minimizzare il costo di ciascuno dei cammini che dalla radice vanno agli altri nodi.
Il problema dei cammini minimi può essere inferiormente illimitato? Sì, succede quando nel grafo esiste un ciclo di costo negativo.
Esprimi il problema dei cammini minimi in termini di alberi. Il problema SPT (Shortest Path Tree) consiste nel determinare in G un albero dei cammini minimi.
"Nel problema dell'albero di cammini minimi, cosa rappresenta il vettore d?" "E' un vettore di etichette di nodi, d, che rappresenta il costo del cammino nell'albero dalla radice ad ogni singolo nodo."
Come trovare il vettore d nel problema dei cammini minimi? "Si può trovare facilmente attraverso una procedura di visita dell'albero a partire dalla radice."
Quali sono le condizioni di Bellman? di + cij >= dj, per ogni nodo del grafo.
Se il vettore di etichette dei nodi i verifica le condizioni di Bellman,
allora di è una valutazione inferiore del costo del cammino minimo da r a i, per ogni nodo i.
T è un albero dei cammini minimi di radice r se e solo se... il suo vettore di etichette d verifica le condizioni di Bellman
"Quali sono i passi dell'algoritmo SPT?" "Mediante una visita del grafo si determina un albero di copertura radicato in r, e le relative etichette d. Si controlla se esiste un arco (i, j) nel grafo originale che non soddisfa le condizioni di Bellman. Se esiste, si inserisce l'arco, nell'albero. Se non esiste abbiamo dimostrato che l'albero è ottimo."
"L'algoritmo SPT è un algoritmo di..." ricerca locale.
"In quali modi si può implementare l'algoritmo SPT?" Q può essere implementato come coda di priorità o come lista.
Cosa è una coda di priorità? "E' un insieme in cui ogni elemento ha associato un valore (chiave) e la scelta dell'elemento da estrarre avviene sulla base di questo valore."
Cosa vuol dire quando Q è implementato come una lista? (SPT) "In una lista, la scelta dell'elemento da estrarre dipende dalla posizione dell'elemento nella lista."
Come si implementa SPT con Q coda di priorità? La chiave di priorità è il vettore delle etichette d, e la priorità cresce al decrescere di di.
Descrivi SPT.S "SPT.S è la versione di SPT in cui ad ogni iterazione si estrae da Q l'elemento di etichetta minima. S sta per shortest first, e viene implementato con coda di priorità."
"L'algoritmo SPT.S, a code di priorità, o algoritmo di Dijkstra..." Ha un funzionamento per cui ogni nodo verrà inserito in Q al più una volta, purché non ci siano costi negativi. Pertanto ha complessità polinomiale.
"L'algoritmo di Dijkstra, o SPT.S, a coda di priorità ha complessità esponenziale..." solo se ci sono archi di costo negativo.
Gli algoritmi SPT in cui Q viene implementato come una lista sono detti SPT.L. In questi algoritmi... "L'inserimento può avvenire in testa o in coda, ma la rimozione può avvenire solo in testa."
Quali tipi di liste ci sono? "Fila (FIFO), o queue, l'inserzione avviene in coda e la rimozione in testa. Pila (LIFO), o stack, l'inserzione e la rimozione vengono effettuate in testa. Deque, lista a doppio ingresso."
Descrivi il problema MST. Dato un grafo non orientato, è il problema della determinazione di un albero di copertura tale che sia minimo il costo di T. Il costo di T sarà la somma del costo di tutti i suoi archi.
Come funziona un algoritmo greedy per MST? "Costruisce l'albero incrementalmente, mantenendo ad ogni passo due insiemi di archi, l'insieme degli archi inseriti e quello degli archi rimossi. Questi vengono aggiornati attraverso operazioni di inserzione e rimozione."
"Cos'è un albero di copertura di costo minimo?" "E' un sottografo connesso, privo di cicli, di costo minimo."
Cosa è un taglio? "E' la partizione in 2 insiemi dell'insieme di tutti i nodi."
"Cos'è l'insieme degli archi in un taglio?" "E' l'insieme degli archi del grafo che collegano un nodo che è da una parte del taglio, e un nodo che è dall'altra parte."
Descrivi la proprietà di ottimalità per cicli "Un grafo è un albero di copertura di costo minimo se il costo di ogni arco non appartenente all'albero è maggiore o uguale al costo di ciascun arco del ciclo che si viene a creare aggiungendo (i, j) all'albero."
Descrivi la proprietà di ottimalità per tagli "Un grafo è un albero di copertura di costo minimo se il costo di ciascun arco appartenente all'albero è minore o uguale al costo di ciascun arco del taglio che si viene a creare rimuovendolo dall'albero."
"Descrivi l'algoritmo di Kruskal" "Si ordinano gli archi per costo non decrescente (crescente) Si esaminano gli archi in quell'ordine. Se l'arco non forma un ciclo con S, si aggiunge ad S, altrimenti si aggiunge ad R."
"Descrivi l'algoritmo di Prim" "Ad ogni iterazione si costruisce e si aggiorna un taglio tale che una parte del taglio è un albero di copertura a costo minimo. Ogni iterazione si inserisce un arco in modo da mantenere la proprietà di ottimalità per tagli, infatti si sceglie l'arco di costo minimo tra quelli del taglio."
Quali dati offre un problema di flusso massimo? Capacità superiori degli archi, un nodo origine e un nodo destinazione.
In cosa consiste il problema del flusso massimo? Consiste nel determinare la massima quantità di flusso che si può inviare da s a t attraverso G.
"Cos'è il valore del flusso x?" "E' il bilanciamento del nodo sorgente, ovvero il flusso che va dal nodo sorgente al nodo pozzo."
Nel problema del flusso massimo, il vettore dei bilanci è... nullo
Un flusso ammissibile non è ottimo se... "E' possibile inviare altro flusso dall'origine alla destinazione."
La capacità di un cammino, theta, rappresenta... la massima quantità di flusso che è possibile inviare lungo questo cammino.
Se la capacità di un cammino è maggiore del suo flusso... è detto un cammino aumentante.
Come trovare cammini aumentanti? Con un grafo residuo.
In un grafo residuo... Ogni arco del grafo originale può essere rappresentato in due modi: nel suo verso originale se non è saturo, e nel verso opposto se non è vuoto.
Per ogni cammino aumentante nel grafo originale... esiste uno ed un solo cammino orientato nel grafo residuo.
"Come si verifica l'esistenza di un cammino aumentante nel PFM?" Con una visita del grafo residuo.
Il flusso di un taglio è... la quantità di flusso che attraversa il taglio.
Possiamo sfruttare i tagli in un problema di flusso massimo per dimostrare: che x è un flusso massimo se determiniamo un taglio la cui capacità è uguale a v.
Nel problema del flusso massimo, il massimo valore dei flussi ammissibili su G... "E' uguale alla minima capacità dei tagli di G che separano s da t."
Algoritmo per cammini aumentanti, ford-folkerson -Parte da un flusso ammissibile -ricerca un cammino aumentante -aumenta il flusso lungo il cammino di una quantità theta. -itera
Se le capacità degli archi sono numeri interi... Allora esiste almeno un flusso massimo intero.
Descrivi il problema di flusso di costo minimo... Data una rete, vogliamo trovare il flusso che costa di meno, soddisfando i bilanciamenti e rispettando le capacità degli archi.
Cosa è uno pseudoflusso? "E' un vettore x che rispetta tutti i vincoli di capacità sugli archi."
Definiamo lo sbilanciamento di un nodo i rispetto ad x la differenza tra il flusso entrante e il flusso uscente, meno il bilancio del nodo i.
Dx e Ox sono rispettivamente "L'insieme di tutti i nodi con eccedenza di flusso e di tutti i nodi con difetto di flusso."
Se non ci sono nodi sbilanciati, allora il vettore x rispetta i vincoli di conservazione del flusso ed è pertanto un flusso ammissibile.
Lo sbilanciamento complessivo di uno pseudoflusso è la somma degli sbilanciamenti di tutti i nodi con eccedenza di flusso, che è uguale alla somma degli sbilanciamenti dei nodi con difetto di flusso.
Inviare flusso lungo un cammino aumentante modifica solamente il bilancio degli estremi, mentre lo sbilanciamento di tutti gli altri nodi rimane invariato.
Uno pseudoflusso è minimale se è lo pseudoflusso di costo minimo tra quelli con lo stesso sbilanciamento.
Se uno pseudoflusso è minimale e ammissibile allora è ottimo per il problema del Flusso di Costo Minimo.
Uno pseudoflusso minimale
non ammette cicli aumentanti di costo negativo.
La capacità di un cammino P è la minima capacità degli archi di P nel grafo residuo
Costo di un cammino La somma dei costi degli archi del cammino nel grafo residuo
Ciclo aumentante ciclo orientato nel grafo residuo
Algoritmo dei cammini minimi successivi init: x pseudoflusso minimale 2) ricerca di un cammino aumentante di costo minimo 3) Se non esiste stop 4)Altrimenti aumentare di theta unità il flusso lungo il cammino trovato. 5) Iterare
"Complessità dell'algoritmo dei cammini minimi" Avviene un SPT.L Bellman-Ford per iterazione, e il numero massimo di iterazioni è lo sbilanciamento complessivo, quindi O(gmn) dove g è lo sbilanciamento.
"L'algoritmo dei cammini minimi successivi..." mantiene ad ogni passo uno pseudoflusso minimale x, e determina un cammino aumentante di costo minimo tra un nodo s e un nodo t, per diminuire, al minor costo possibile, lo sbilanciamento di x.
"L'uso di cammini aumentanti di costo minimo nei cammini minimi successivi mantiene la proprietà di" minimalità degli pseudoflussi.
Nel flusso di costo minimo, per un cammino P e uno pseudoflusso x, theta rappresenta la maggior diminuzione possibile... dello sbilanciamento complessivo corrispondente al cammino P e allo pseudoflusso x.
Lo sbilanciamento e(i) di un nodo è Il flusso che esce, meno il flusso che entra, meno il suo bilancio.
Se uno vuole ridurre lo sbilanciamento... deve spedire il flusso da un nodo che ha eccesso ad un nodo che ha difetto.
Quali sono le tre proprietà di un problema di Programmazione Lineare? numero finito n di variabili, funzione obbiettivo lineare, insieme ammissibile definito da un insieme finito di m vincoli lineari.
(Scarti complementari) Siano x una soluzione ammissibile per (P), y una soluzione ammissibile per (D) Se y ( b - Ax) = 0 allora sono entrambe soluzioni ottime
Riscrivi il teorema degli scarti complementari, in termini di vincoli attivi. Se Aix < bi => yi = 0. (se il vincolo i non è attivo nel problema primale, allora è attivo nel problema duale) Se yi > 0 => Aix = bi(se il vincolo i non è attivo nel problema duale, allora è attivo nel problema primale).
Sia x in Rn ammissibile per (P). Allora, x è una soluzione ottima se e solo se.. esiste un y ammissibile per (D) che soddisfa gli scarti complementari.
Sia y in Rn ammissibile per (D). Allora y è soluzione ottima se e solo se... Esiste un x ammissibile per (P) che soddisfa gli scarti complementari con y.
Graficamente, una soluzione di base ammissibile è...
Un vertice del problema.
Un base primale è degenere... Se una vincolo non appartenente alla base è attivo.
Una soluzione duale di base è ammissibile... Se yB è maggiore o uguale a zero.
Una soluzione di base duale è degenere se... Un vincolo che appartiene alla base è attivo, ovvero è uguale a zero.
Una coppia di soluzioni della stessa base... Soddisfa sempre gli scarti complementari.
Teorema della dualità debole Siano x sol.ne ammissibile di (P), e y sol.ne ammissibile di (D). Allora, il valore della funzione obbiettivo di (P) è minore o uguale al valore della funzione obbiettivo di (D). Quindi c*x <= y*b.
Se (P) è superiormente illimitato... allora (D) è vuoto.
Se (D) è inferiormente illimitato... Allora (P) è vuoto.
In pratica, il valore di (P) può essere al massimo il valore di (D).
x sol.ne amm. per (P), y per (D). Se cx = yb allora... Sono rispettivamente soluzioni ottime di (P) e di (D).
" in Rn è una direzione ammissibile per x se..." "Esiste un tale che è ammissibile per (P) per ogni lambda tra zero e lambda segnato."
Insomma, una direzione è ammissibile se... Permette di spostare la soluzione corrente di un passo lambda, senza uscire dalla regione ammissibile.
Una direzione per crescita per c*x "E' uno tale che è maggiore di zero. (prodotto scalare)."
Se non esistono direzioni ammissibili di crescita per x... Significa che x è una soluzione ottima per (P).
"Se il seguente sistema non ha soluzione , allora la soluzione x è ottima." " (La matrice A è ottenuta prendendo le righe i cui indici corrispondono ai vincoli attivi in x)"
Dualità forte. Supponiamo che (P) e (D) abbiano entrambi regioni ammissibili non vuote. Allora il massimo valore di (P) è uguale al minimo valore di (D).
Come sapere se un poliedro contiene vertici? Se il rango della matrice A è pari al numero di variabili, allora P possiede almeno un vertice.
In programmazione Lineare, cosa è una base? "E' un insieme di indici di lunghezza pari al numero di variabili tale che la sua matrice di base è invertibile. La matrice si ottiene prendendo le righe di indici appartenenti alla base."
Come si calcola una soluzione primale di base? "x segnato è pari all'inversa della matrice di base per bB ovvero le componenti in B del vettore b."
Quando è che una soluzione primale è ammissibile? Se soddisfa i vincoli del problema primale, ovvero se ANx <= bN, dove N sono gli indici non appartenenti alla base.
Quando una base primale è degenere? "E' degenere se ci sono vincoli attivi che non appartengono alla base."
"Sia B una base. Allora la coppia di soluzioni e ..." Soddisfano il teorema degli scarti complementari perché sono definite in modo da soddisfarli.
Sia x in Rn una soluzione primale di base ammissibile. Allora x è soluzione ottima di (P) se e solo se
esiste una base B associata a x t.c. la soluzione duale di base è ammissibile per (D).
Se x non è degenere allora... Esiste una sola base associata.
"In breve, cosa fa l'algoritmo del simplesso?" "Considera l'insieme dei vertici del problema principale, e, ad ogni passo, cerca un vertice che migliori il valore della funzione obbiettivo."
Quali sono i passi del simplesso primale? 1) Data una base primale ammissibile, si calcolano la soluzione primale e duale di base. 2) Se la soluzione duale è ammissibile, abbiamo trovato la soluzione ottima. 3) Altrimenti scegliere un h della base tale che yh viola i vincoli duali. 4) Trovare una direzione di crescita, pari a meno la colonna h-esima della matrice di base. 5) Il passo è il minimo dei passi ammissibili in ogni direzione. 6) Se il passo è infinito, il problema è illimitato. 7) Scegliere k in N tale che lambda = lambda di k 8) Cambiare base, togliendo h e mettendo k. Iterare.
Qual è la regola anticiclo di Bland? Se dobbiamo scegliere un indice, entrante o uscente, scegliamo il minimo tra quelli disponibili.
"Cosa è necessario per avviare l'algoritmo del simplesso duale?" Serve un y segnato, sol.ne duale di base ammissibile.
Come fare a capire se y segnato è una soluzione ottima di (D)? "E' una soluzione ottima se esiste una base B associata a y segnato t.c. la sol.ne primale di base x segnato è ammissibile per P."
Cosa è il simplesso duale? "E' una implementazione intelligente del simplesso primale applicato a (D) riscritto in formato primale."
Nel simplesso primale si parte con una base primale ammissibile, mentre... Nel simplesso duale si parte con B base duale ammissibile
"Nel simplesso primale l'ammissibilità duale significa che l'algoritmo termina perchè abbiamo trovato la soluzione. La non ammissibilità ci permette di trovare l'indice uscente. Nel simplesso duale..." "l'ammissibilità primale significa che abbiamo trovato la soluzione ottima. La non ammissibilità ci indica l'indice entrante."
Nel simplesso primale si cerca ad ogni iterazione una direzione di crescita. Nel simplesso duale... si cerca una soluzione di decrescita.
"Nel simplesso primale, se la direzione di crescita ammette passo infinito, significa che il problema è illimitato. Se ammette un passo finito, ci permette di trovare l'indice entrante. Nel simplesso duale..." "se la direzione di decrescita ammette un passo infinito, l'algoritmo si ferma. Se ammette un passo finito ci permette di trovare l'indice uscente."
Nel simplesso primale ad ogni iterazione troviamo una nuova base primale ammissibile. Nel simplesso duale...
troviamo una base duale ammissibile.
Che forma ha una base duale ammissibile?
La soluzione è ammissibile se contiene il vettore c, moltiplicato con la matrice di base inversa, negli indici di base, e zero nelle altre componenti, e tutte le componenti sono maggiori o uguali a zero.
"Come si verifica l'ammissibilità primale?" Dato un x che è il risultato del prodotto tra la matrice di base inversa e le componenti di base del vettore b, la sol.ne è ammissibile se il prodotto AN*x è minore o uguale a bN.
"Come trovare un indice entrante nell'algoritmo del simplesso duale?" "L'indice entrante è il minimo degli indici non appartenenti alla base, che violano l'ammissibilità primale. Insomma per cui Aix > bi."
"Quali sono le componenti di una direzione di decrescita d a partire da un vettore ?" "di è uguale a meno se l'indice appartiene alla base. E' uguale a uno se l'indice è l'indice entrante k, ed è uguale a zero altrimenti."
Come trovare una direzione di decrescita? "Chiamiamo k l'indice entrante scelto al passo precedente, e chiamiamo eta il prodotto tra Ak e la matrice di base inversa. Le componenti della direzione di decrescita sono queste: Se il suo indice appartiene alla base, la componente vale meno eta-i Se il suo indice è l'indice entrante k, la componente vale 1. Altrimenti, l'indice vale 0."
Quanto vale il passo di spostamento theta nel simplesso duale, data una direzione di decrescita? "Il passo di spostamento theta vale il massimo passo che può essere compiuto lungo d senza perdere l'ammissibilità duale, vale quindi il minimo dei rapporti tra yi e , t.c. maggiore di zero."
"Nel simplesso duale, come scegliere l'indice uscente?" "Se theta segnato è il massimo passo che può essere compiuto lungo d senza perdere l'ammissibilità duale, l'algoritmo fa uscire un indice h che determina tale passo. Ossia, l'indice di una componente di ytheta che diventerebbe negativa se fosse effettuato un passo più lungo di theta."
Riassumi brevemente i passi del simplesso duale Si parte con una base duale ammissibile. Se la soluzione primale di base è ammissibile, allora abbiamo trovato la soluzione ottima. Altrimenti, scegliamo un k tra gli indici dei vincoli non soddisfatti e non appartenenti alla base. Scegliamo il k minimo per la regola anticiclo di Bland. Calcoliamo un eta. Se tutte le componenti sono minori o uguali a zero, allora il problema primale non ha soluzioni. Altrimenti, scegliamo un h, indice di base che ha il minor passo theta ammissibile. Ora sostituiamo h con k nella base e iteriamo.
Reticolo intero "La regione ammissibile di un problema di PLI è l'intersezione tra il poliedro e i punti che appartengono a Z^n, ovvero l'insieme dei vettori a componenti intere di dimensione n."
In PLI, se x è sol.ne ottima di (P), ed è a componenti intere, allora... allora x è soluzione del problema intero corrispondente, ovvero (Pi)
Se tutti i vertici di P sono a componenti intere... Allora P ammette una sol.ne ottima a componenti intere.
Rilassamento continuo Il rilassamento continuo di un problema di PLI è un problema identico, eccetto per il fatto che non contiene il vincolo di interezza.
Diseguaglianza Valida "Dati un vettore d in Rn e un reale gamma, l'espressione d*x >= gamma, si dice diseguaglianza valida, se è vero che vale per qualsiasi x che appartiene all'involucro convesso di S."
Sia x una sol.ne ottima del rilassamento continuo (RCp). Una diseguaglianza valida si dice piano di taglio se... "aggiungendo la diseguaglianza ai vincoli del rilassamento continuo, si ottiene una regione ammissibile che approssima S (il reticolo intero) meglio di P, e ""taglia fuori"" la sol.ne ottima del relativo rilassamento continuo."
Come si costruisce un piano di taglio? "Bisogna scrivere il problema in forma duale, trovare una soluzione ottima del rilassamento continuo (RCd). Poi definire una matrice A trasposta, ottenuta moltiplicando AN e AB-1, dove le righe sono numerate secondo gli indici di N, e le colonne secondo gli indici di B. Scegliamo un r, indice di base t.c. yr segnato non è intero. J è l'indice di un vincolo non appartenente alla base, il cui Yj è uguale a zero nella soluzione. Per ogni j, imponiamo che la parte frazionaria, dell'elemento di A trasposta di riga j, e di colonna r, moltiplicato per yj, sia maggiore o uguale alla parte frazionaria di yr segnato. La diseguaglianza ottenuta è un piano di taglio per la soluzione y."
"Quali sono gli steps dell'algoritmo di Gomory?" Calcolare y segnato, sol.ne ottima di base del rilassamento continuo in forma duale. Se y segnato è intero, abbiamo trovato la nostra soluzione. Costruire un piano di taglio d*x >= gamma, relativo alla soluzione y segnato. Aggiungere la diseguaglianza valida ai vincoli del rilassamento continuo in forma duale, e iterare da capo.
Cosa è un metodo enumerativo? "I metodi enumerativi sono una famiglia di metodi risolutivi che si applica ai problemi di PLI con un numero finito di soluzioni. Sfruttano l'albero di enumerazione totale per analizzare il problema, valutando, direttamente o indirettamente, tutte le possibili soluzioni."
Quando conviene utilizzare un metodo enumerativo? "-Problemi di PLI con un numero finito di soluzioni -Possibilità di enumerare ""facilmente"" le soluzioni -Particolarmente idonei per i problemi combinatori ovvero con variabili binarie."
Albero di enumerazione totale "E' un albero radicato in un problema di base, dove i nodi di un determinato livello identificano una variabile e gli archi che portano al livello successivo i possibili valori della suddetta. Le foglie, indicano tutte le possibili soluzioni. Ogni nodo individua un sotto-albero, che identifica un sotto-problema del problema originale."
In un albero di enumerazione, ogni sottoproblema... "E' analogo al problema originale ma con un numero inferiore di variabili."
Come stimare la qualità delle soluzioni di un sottoproblema? Si considera un rilassamento, un problema che contiene tutte le soluzioni ammissibili del sottoproblema più altre.
"Come viene utilizzato il rilassamento dall'algoritmo branch and bound?" "L'algoritmo utilizza i rilassamenti come valutazioni superiori o inferiori della soluzione, a seconda che il problema sia di massimo o minimo"
Quali sono i quattro elementi di un algoritmo branch and bound? 1) una sol.ne ammissibile di partenza 2) un rilassamento del problema 3) regola di ramificazione 4) regole di potatura.
Quali sono le regole di potatura di un algoritmo B&B? 1) (Non-Ammissibilità) Il sottoalbero non contiene soluzioni ammissibili di P. 2) (Ottimizzazione) il valore ottimo del rilassamento del sottoproblema è peggiore, o non migliore, del valore della soluzione corrente. 3) (Ammissibilità) La soluzione ottima individuata per il rilassamento del sottoprob. è ammissibile per P.
"Se l'algoritmo B&B trova una nuova soluzione ammissibile, migliore della soluzione corrente..." La soluzione diventa la nostra nuova soluzione corrente.
Qual è il problema dello zaino? Dato uno zaino di capacità b, vogliamo inserire un certo numero di oggetti, rispettando il limite di peso, e massimizzando il beneficio.
Cosa è il beneficio unitario, o rendimento, di un oggetto nel problema dello zaino? "E' il rapporto tra il suo beneficio (ci) e il suo peso (ai)"
Qual è la tecnica euristica dei rendimenti discendenti? Riordinando le variabili secondo benefici unitari, in ordine decrescente, inseriremo un oggetto nello zaino se il suo peso non è maggiore della capacità residua.
A cosa serve la tecnica dei rendimenti discendenti? Può essere una soluzione ammissibile di partenza nel problema dello zaino.
A cosa serve il rilassamento continuo che ammette valori frazionari nel problema dello zaino? "E' una valutazione superiore del problema."
Qual è il problema del commesso viaggiatore? Un commesso viaggiatore vuole visitare n città (tornando infine alla città di partenza) minimizzando il percorso complessivo.
Definisci il ciclo Hamiltoniano "E' una sequenza di archi che inizia e finisce in uno stesso nodo, passando per gli altri nodi una sola volta."
Esprimi TSP in termini matematici Dato un grafo orientato con un costo, o distanza, su ciascun arco, trovare il ciclo hamiltoniano di costo minimo.
Cosa è un k-albero? "E' un albero di copertura per il sottografo ottenuto rimuovendo k e gli archi incidenti in k, reinserendo poi k con 2 archi incidenti in k."
Un ciclo hamiltoniano è un k-albero ma... non tutti i k-alberi sono cicli hamiltoniani.
Qual è un rilassamento del ciclo hamiltoniano? Un k-albero sullo stesso grafo.
Un ciclo hamiltoniano, in relazione ad un k-albero.. Un ciclo hamiltoniano è un k-albero in cui ogni nodo ha grado 2.
Tecnica euristica del nodo più vicino Tecnica utile per trovare una soluzione iniziale in TSP. Partendo da un nodo k, si procede aggiungendo via via tutti i nodi non ancora nel grafo, di costo minimo.
Come si usa il Branch and Bound applicato al problema del commesso viaggiatore? "Come sol.ne ammissibile di partenza si utilizza il risultato della tecnica euristica del nodo più vicino, ovvero, partendo dal nodo k, si aggiungono gli archi di costo minimo. Come rilassamento del problema si utilizza il k-albero di costo minimo. Le ramificazioni si effettuano imponendo di aggiungere, o rimuovere, l'arco di costo minimo. Le regole di potatura sono ovvie."
Problema dello Zaino: come si trova la soluzione del rilassamento senza vincolo di interezza? "Rilassamento I: utilizziamo il problema di partenza, senza il vincolo di binarietà, e il corrispondente problema duale: La soluzione ottima del duale risulta essere il massimo dei benefici unitari (beneficio/peso). L'indice del vincolo che viene soddisfatto come uguaglianza è detto k. Da cui la soluzione ottima del primale è che la componente i di x segnato è b/ai se i = k, altrimenti vale zero. Ovvero, il k-esimo componente è uguale a b (capacità) fratto il peso dell'oggetto k."
Problema dello Zaino: come si trova la soluzione del rilassamento che ammette valori frazionari? "Un secondo rilassamento si può ottenere ammettendo soluzioni con valori frazionari, ma compresi tra 0 e 1. In questo caso, riutilizzando il riordinamento, do un indice da 1 ad n a ciascuno degli oggetti, sulla base del loro ordinamento. Ora, prendo un h tale che la somma del peso degli oggetti prima di h sia minore o uguale alla capacità, e la somma del peso degli oggetti da 1 ad h+1 sia maggiore della capacità. Questo significa che h è l'ultimo oggetto inseribile nello zaino. La soluzione ottima si ottiene facendo valere h e le componenti prima di h 1, facendo valere le componenti maggiori di h+1 0, e facendo valere h+1 il rapporto tra (b - la somma degli oggetti minori o uguali ad h) e il peso di h+1. Si avrà che il vincolo è soddisfatto."
"Modifica il problema dello zaino per includere i seguenti vincoli ""Se prendo l'oggetto 1 non posso prendere l'oggetto 2"" ""Se prendo l'oggetto 3 devo prendere anche l'oggetto 1"" ""Se prendo sia 1 che 2 allora devo prendere anche 3""" 1) x1 + x2 <= 1 2) x1 -x3 >= 0 3) x1 + x2 <= x3 +1
"Per il problema del Commesso Viaggiatore che relazione c'è tra un ciclo hamiltoniano e un k-albero?" Un ciclo hamiltoniano è il caso specifico di un k-albero in cui ogni nodo ha grado 2. Il k-albero di costo minimo è un rilassamento del problema del ciclo hamiltoniano perchè contiene le soluzioni ammissibili del ciclo hamiltoniano ed altre.
Nel Problema TSP come si può trovare una soluzione ammissibile? Si trova una soluzione ammissibile con la tecnica euristica del nodo più vicino. Partendo da un k si aggiunge il nodo di costo minimo finché non si crea un ciclo.
Formulare problema dello zaino Dato uno zaino di capacità B, e un insieme di oggetti di peso ai e beneficio ci, inserire gli oggetti nello zaino in modo da massimizzare il beneficio totale e da non superare la capacità
"Durante il branch & bound, quando posso chiudere in una volta sola tutti i nodi dell'albero?" Quando trovo una soluzione ammissibile per il problema di partenza migliore di tutte le previsioni più ottimistiche di tutti gli altri sottoproblemi.
Come si trova il k-albero di costo minimo algoritmicamente "1) Il grafo originale è composto da un insieme di archi E e da un insieme di nodi V. Ora, eliminiamo da V un nodo k, e da E tutti i nodi incidenti in k. 2) Utilizziamo un algoritmo a scelta per ottenere l'albero di copertura di costo minimo. Ad esempio Prim. 3) Ora, aggiungiamo il nodo k 4) Aggiungiamo i due archi incidenti in k di costo minimo."