The forum of the Computer Science students of the University of Pisa

Domande orale Passacantando

queste sono alcune domande per l'orale di Mauro Passacantando in data 08/01/2019, l'esame e' alla lavagna:

- definizione di albero di copertura.
- modello del problema dei cammini minimi.
- condizioni di bellman, formula e a cosa servono.
- in un problema di PL cosa e' una base.
- come si calcola la soluzione duale.
- definizione del problema del commesso viaggiatore(modello) .
- come trovi ciclo hamiltoniano di costo minimo.
- cosa e' un k-albero e un'esempio.
- enunciato del lemma di farkas.
- definizione di direzione di recessione.
- cos'e' un taglio di gomory (formula e definizione).
- parte frazionaria di un numero.
- quando puoi chiudere un nodo su branch and bound(sia problemi di max e min).
- cos'e' un problema di copertura (modello) come trovare soluzione ammissibile (con tecniche euristiche).
- quando una soluzione base e' degenere (sia primale che duale).
- modello problema partizione di costo minimo, a che serve il problema.
- modello problema riempimento , a che serve.
- modello problema di copertura, dove si utilizza.
- cammino aumentante su cammini minimi successivi.
- enunciato teorema di scarti complementari.
- esempio di un problema di PL con duale ammissibile(analitico e geometrico).
- cos'e' un taglio in un grafo e che correllazione con flusso massimo.
- teorema max-flow-min-cut.
- cosa fa l'algoritmo simplesso duale ad ogni iterazione(stesso con primale).
- valore soluzione y nella nuova base duale che relazione c'e' con la vecchia base.
- se ho x e y soluzioni ammissibili quando gli scarti complementari sono rispettati.
- come sfruttare un grafo aciclico per trovare un albero di cammini minimi.
- forma generale di un problema di PLI.
- come modificare l'algoritmo di djistra per sapere solo cammino dal nodo scelto a destinazione non interessano tutti.
- modello flusso costo minimo.
- modello TSP.
- modello albero di copertura di costo minimo.
- disegna un grafo di flusso massimo e trova un taglio di capacita minima.
- cono di recessione cos'e' e un esempio.
- risolvere un problema di PL (metodo analitico e geometrico).
- condizioni di ottimalita PL e PLI.
- condizioni ottimalita flusso di costo minimo.
- condizioni ottimalita branch and bound.
- quando possiamo dire che un flusso e' massimo.


da anche esercizi da risolvere spiegando il ragionamento.

Teorema di rappresentazione dei poliedri
- formulare un esempio

Differenza tra un Ciclo Hamiltoniano e un r-albero

Branch and Bound
- Domanda: se Vi(P) = 50, Vi(P)=70, e all' i-esimo livello dell'albero ogni nodo ha Vi(P[i,j) compreso fra 50 e 70 non ammissibile per P, posso aggiornare Vi(P)? come?
- Modello flusso max
- Teorema max flow min cut (v=u(Ns,Nt)) e teorema generale (v=x(Ns,Nt)≤u(Ns,Nt))
- Come si trova il flusso sul taglio
- Teorema fondamentale della PL e disegnare un poliedro con i vertici e senza vertici (un poliedro è senza vertici quando lineal(P) ≠ 0)
- Disegnare un albero di copertura dove la sol è ottima per il problema dell’albero di copertura dei costi minimi e non è soluzione ottima dell’albero dei cammini minimi. Io ho disegnato un albero con archi (1,2)(2,3)(3,4) con costi 3, 2, 1 mentre i costi degli archi (1,3) e (2,4) rispettivamente 5 e 2.
Orale di Febbraio

-Tagli di Gomory
-Lemma di Farkas
-Esempio del sistema del lemma di Farkas avente soluzione
-Modello problema dei cammini minimi
-Differenza cammini minimi e albero di copertura
-Modello albero di copertura
-Toerema di dualità debole con dimostrazione
Orale di Luglio:

L'orale si tiene alla lavagna, il Passacantando è molto tranquillo.

Voto iniziale: 18
Voto finale: 20

Domande:

-Modello albero di costo minimo (vd. Libro)
-Qual è l'algoritmo associato al problema dell'albero di costo minimo (Algoritmo di Kruskal)
-Scarti complementari: a cosa serve la direzione di recessione e qual è
-Dove ritroviamo l'algoritmo di Kruskal? (lo usiamo per trovare l'r-albero senza il collegamento del nodo r-esimo)

In allegato aggiungo un file di preparazione all'orale (se manca qualcosa segnalatemelo)

Allegati

Ieri, 08/01/20, sono stato tutta la mattina e parte del pomeriggio a sentire gli orali, prima di essere interrogato io. Sono partito con una media di 29 grazie ai compitini e ho verbalizzato con 30. Scrivo le domande che mi ha fatto perché, durante la giornata di ieri, queste in particolare le ha fatte solo a me, e non mi sembra qualcuno le abbia già segnalate. Vanno considerate pertanto come domande "da lode", o comunque che potrebbe farvi se avete una media piuttosto alta.

1) Supponiamo di avere un problema dell'albero di copertura di costo minimo, e supponiamo di avere già trovato una soluzione ottima per quel problema, non importa con quale algoritmo. Se ora aumentiamo il costo di tutti gli archi del grafo di una costante (comune per tutti gli archi), la soluzione trovata rimane ottima?

2) Supponiamo, analogamente alla domanda precedente, di avere un problema di flusso massimo, e di avere trovato una soluzione ottima anche per questo problema. Di nuovo, supponiamo di aumentare di una costante la capacità di ogni arco del grafo. La soluzione rimane ottima nel nuovo grafo? Abbiamo gli stessi tagli di capacità minima nell'ottimo del nuovo problema?

3) Supponiamo di avere un problema di massimo di Programmazione Lineare Intera (che chiamiamo P), dove Vi(P)=10 e Vs(P)=50. Supponiamo di avere i seguenti nodi aperti con le relative valutazioni superiori:
Vs(P1)=40 (figlio sinistro di P)
Vs(P2)=45 (figlio destro di P)
Vs(P3)=37 (figlio sinistro di P1)
Vs(P4)=38 (figlio destro di P1)
Vs(P5)=35 (figlio sinistro di P2)
Vs(P6)=36 (figlio destro di P2)
L'esempio serve a rendere l'idea di un problema dove scendiamo molto in profondità con i nodi, ma non riusciamo mai a chiuderne uno. Le valutazioni superiori trovate per i problemi P1,P2,P3,P4,P5,P6 infatti non sono ammissibili per P. Non possiamo aggiornare quindi Vi(P), ma con questi dati, possiamo dire qualcosa riguardo Vs(P)? Spiegare anche il ragionamento alla base della risposta

4) Quando possiamo dire, in un problema dei cammini minimi, che la soluzione ottima ipoteticamente trovata è ottima?




Risposte:

1) La risposta è sì, l'aumento costante dei costi degli archi non cambia la soluzione ottima, banalmente perché, se prima avevamo scelto un arco di costo X al posto di un arco che non appartiene all'albero di costo Y, era perché X < Y. Se aggiungiamo una costante da entrambe le parti della disuguaglianza, questa rimane vera (X + c < Y + c).

2) La soluzione non rimane ottima, in quanto ovviamente possiamo spedire del flusso in più lungo gli archi. In generale no, non tutti i tagli di capacità minima del primo problema rimangono di capacità minima nel nuovo problema. Anzi, in generale, nel nuovo problema solo alcuni tagli di capacità minima "sopravvivono", mentre altri spariscono. Può anche succedere che se ne formino di nuovi però. Mi ha chiesto di fare un esempio concreto alla lavagna, disegnando prima un grafo qualunque con delle capacità sugli archi, e poi di disegnare lo stesso grafo aumentando le capacità di ogni arco di una costante scelta arbitrariamente da me, e in entrambi i casi di trovare i tagli di capacità minima e di metterli a confronto (e di confrontare anche l'ottimo dei due problemi, se li costruite in modo semplice l'ottimo ve lo ricavate senza dover applicare algoritmi).

3) Su questa non sono troppo sicuro della risposta, ma in generale, al livello i-esimo dell'albero, anche se non possiamo chiudere alcun nodo, possiamo sostituire Vs(P) con la massima valutazione superiore del livello corrente. Ad esempio, al livello 1 dell'esempio potevamo essere sicuri che Vs(P)=45, e al secondo livello sapevamo che Vs(P)=38.

4) La soluzione ottima del problema è anche l'unica soluzione ottima quando per ogni nodo j ∈ N, πj < πi + Ci,j. Ovvero, quando le condizioni di Bellman sono verificate in modo stretto.
Orale svolto alla lavagna. Passacantando è molto tranquillo.
1)Descrivere il problema di riempimento e di come possa essere applicato ad esso il branch and bound.
2)Problema dell'albero dei cammini minimi:determinare se dopo aver trovato l'albero in un grafo aumentando il costo degli archi di tutto il grafo di una costante c,l'albero rimane uguale.
3)Disegnare un poliedro,risolvere graficamente il simplesso primale e spiegare perché W è sempre positiva
4)Correlazione tra r-albero e ciclo hamiltoniano.

Risposte:
1)Ho spiegato a parole il problema di riempimento e successivamente ho scritto il modello. Per quanto riguarda il branch and bound,essendo la funzione obiettivo una funzione di massimo,per la valutazione inferiore e la soluzione ammissibile mi sono basato sullo zaino mentre per la valutazione superiore è più complicato perché essa cambia in base a come ordino i sottoinsiemi (cardinalità,occorrenze degli elementi). Inoltre non conviene fare un'enumerazione esplicità poiché il costo computazionale sarebbe molto alto.
2)La risposta è no poiché nel costo finale io sommo la costante c n volte con n pari a numero degli archi all'interno dell'albero. Ovviamente mi ha chiesto inizialmente di disegnare un grafo e di ricavarne l'albero ad occhio.
3)Ho disegnato un poliedro simile a quelli degli esercizi e ho svolto il simplesso graficamente. W è sempre positiva per vari motivi:perché si basa sul vettore c e sul vincolo che rimane attivo quindi va sempre verso una soluzione migliore,algebricamente mi ha fatto ricavare y segnato rispetto a c e la matrice A,inoltre se scrivo y segnato=c trasposto moltiplicato w^h,ho che le y segnate che sto considerando sono negative (condizione di stop del simplesso) ma w^h è l'h-esima colonna dell'inversa di Ab col segno negativo quindi -c trasposto=-y segnato e quindi basta semplicemente moltiplicare per -1 dimostrando che W è sempre positiva.
4)Un ciclo hamiltoniano è sempre un r-albero mentre un r-albero non è sempre un ciclo hamiltoniano.