Programmazione Lineare Intera

Question 1

Reticolo intero

Answer 1

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.

Question 2

In PLI, se x è sol.ne ottima di (P), ed è a componenti intere, allora…

Answer 2

allora x è soluzione del problema intero corrispondente, ovvero (Pi)

Question 3

Se tutti i vertici di P sono a componenti intere…

Answer 3

Allora P ammette una sol.ne ottima a componenti intere.

Question 4

Rilassamento continuo

Answer 4

Il rilassamento continuo di un problema di PLI è un problema identico, eccetto per il fatto che non contiene il vincolo di interezza.

Question 5

Disuguaglianza Valida

Answer 5

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.

Question 6

Sia x una sol.ne ottima del rilassamento continuo (RCp). Una diseguaglianza valida si dice piano di taglio se…

Answer 6

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.

Question 7

Come si costruisce un piano di taglio?

Answer 7

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.

Question 8

Parte frazionaria

Answer 8

La parte frazionaria di un numero si ottiene sottraendo ad un numero la sua parte intera.

Question 9

Quali sono gli steps dell’algoritmo di Gomory?

Answer 9

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.

Question 10

Cosa è un metodo enumerativo?

Answer 10

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.

Question 11

Quando conviene utilizzare un metodo enumerativo?

Answer 11

• 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.

Question 12

Albero di enumerazione totale

Answer 12

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.

Question 13

In un albero di enumerazione, ogni sottoproblema…

Answer 13

E’ analogo al problema originale ma con un numero inferiore di variabili.

Question 14

Come stimare la qualità delle soluzioni di un sottoproblema?

Answer 14

Si considera un rilassamento, un problema che contiene tutte le soluzioni ammissibili del sottoproblema più altre.

Question 15

Come viene utilizzato il rilassamento dall’algoritmo branch and bound?

Answer 15

L’algoritmo utilizza i rilassamenti come valutazioni superiori o inferiori della soluzione, a seconda che il problema sia di massimo o minimo

Question 16

Quali sono i quattro elementi di un algoritmo branch and bound?

Answer 16

1) una sol.ne ammissibile di partenza
2) un rilassamento del problema
3) regola di ramificazione
4) regole di potatura.

Question 17

Quali sono le regole di potatura di un algoritmo B&B?

Answer 17

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 indivisuata per il rilassamento del sottoprob. è ammissibile per P.

Question 18

Se l’algoritmo B&B trova una nuova soluzione ammissibile, migliore della soluzione corrente…

Answer 18

La soluzione diventa la nostra nuova soluzione corrente.

Question 19

Qual è il problema dello zaino?

Answer 19

Dato uno zaino di capacità b, vogliamo inserire un certo numero di oggetti, rispettando il limite di peso, e massimizzando il beneficio.

Question 20

Cosa è il beneficio unitario, o rendimento, di un oggetto nel problema dello zaino?

Answer 20

E’ il rapporto tra il suo beneficio (ci) e il suo peso (ai)

Question 21

Qual è la tecnica euristica dei rendimenti discendenti?

Answer 21

Riordinando le variabili secondo benefici unitari, in ordine decrescente, inseriremo un oggetto nello zaino se il suo peso non è maggiore della capacità residua.

Question 22

A cosa serve la tecnica dei rendimenti discendenti?

Answer 22

Può essere una soluzione ammissibile di partenza nel problema dello zaino.

Question 23

Come funziona il rilassamento continuo che ammette valori frazionari?

Answer 23

Non lo so.

Question 24

A cosa serve il rilassamento continuo che ammette valori frazionari nel problema dello zaino?

Answer 24

E’ una valutazione superiore del problema.

Question 25

Qual è il problema del commesso viaggiatore?

Answer 25

Un commesso viaggiatore vuole visitare n città (tornando infine alla città di partenza) minimizzando il percorso complessivo.

Question 26

Definisci il ciclo Hamiltoniano

Answer 26

E' una sequenza di archi che inizia e finisce in uno stesso nodo, passando per gli altri nodi una sola volta.

Question 27

Esprimi TSP in termini matematici

Answer 27

Dato un grafo orientato con un costo, o distanza, su ciascun arco, trovare il ciclo hamiltoniano di costo minimo.

Question 28

Cosa è un k-albero?

Answer 28

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.

Question 29

Un ciclo hamiltoniano è un k-albero

Answer 29

ma non tutti i k-alberi sono cicli hamiltoniani

Question 30

Qual è un rilassamento del ciclo hamiltoniano?

Answer 30

Un k-albero sullo stesso grafo.

Question 31

Un ciclo hamiltoniano, in relazione ad un k-albero..

Answer 31

Un ciclo hamiltoniano è un k-albero in cui ogni nodo ha grado 2.

Question 32

Tecnica euristica del nodo più vicino

Answer 32

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.

Question 33

Come si usa il Branch and Bound applicato al problema del commesso viaggiatore?

Answer 33

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.

Question 34

Problema dello Zaino: come si trova la soluzione del rilassamento?

Answer 34

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.

Question 35

Problema dello Zaino: come si trova la soluzione del rilassamento? II

Answer 35

Rilassamento II: 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.

Question 36

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"

Answer 36

1) x1 + x2 <= 1 2) x1 -x3 >= 0 3) x1 + x2 <= x3 +1

Question 37

Per il problema del Commesso Viaggiatore che relazione c'è tra un ciclo hamiltoniano e un k-albero?

Answer 37

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.

Question 38

Nel Problema TSP come si può trovare una soluzione ammissibile?

Answer 38

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.

Question 39

-cos'è il rilassamento

Answer 39

Un rilassamento è un problema che contiene tutte le soluzioni ammissibili di un altro problema ma anche soluzioni non ammissibili per l'altro problema.

Question 40

-formulare problema dello zaino

Answer 40

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à

Question 41

Durante il branch & bound, quando posso chiudere in una volta sola tutti i nodi dell'albero?

Answer 41

Quando trovo una soluzione ammissibile per il problema di partenza migliore di tutte le previsioni più ottimistiche di tutti gli altri sottoproblemi.

Question 42

- Come si trova il k-albero di costo minimo algoritmicamente

Answer 42

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.