Ricerca operativa 2

V

07. Considerato il poliedro P' definito da tutte le disequazioni triangolo e il poliedro P'' definito da tutte le disequazioni a due partizioni

P'' è strettamente contenuto in P'

P'' è contenuto in P'

P' è contenuto in P''

P' = P''

08. Nel caso in cui |S|=1 e |T|=2 la disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T si riduce a

Una disequazione a due partizioni con termine noto nullo

Una disequazione non valida

Una disequazione triangolo

Una disequazione nulla

09. Nel caso in cui |S|=1 e |T|=2 la disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T si riduce a

Una disequazione triangolo

Non si può dire se non si conoscono i nodi in S e in T

Una disequazione inutile per il problema

Una disequazione non valida

10. Definire l'algoritmo euristico di separazione delle disequazioni a due partizioni per il problema di partizione in clique dei nodi di un grafo

11. Dimostrare che una disequazione triangolo è un caso particolare di disequazione a due partizioni

12. Spiegare in che relazione sono tra loro la formulazione con disequazioni triangolo e disequazioni a due partizioni valide per il problema di partizione in clique

dei nodi di un grafo

13. Illustrare la famiglia di disequazioni a due partizioni valide per il problema di partizione in clique dei nodi di un grafo

L’obiettivo dell’euristica di separazione è identificare due sottoinsiemi disgiunti e non vuoti S

10.

e T con |S| = 1 tali che la disequazione a due partizioni associata ai sottoinsiemi S e T sia

x’.

violata dalla soluzione l’insieme

Per ogni i appartenente ad N poniamo S = {i} e determiniamo W = {j appartenente N }

nell’insieme {j1……jn} 2,….,1

scegliamo un ordinamento W : W e poniamo T={j_i} per ogni k= poniamo

x’(ro(S,T))>1

T = T U {j_k} se |T| >1 e la disequazione a 2 partizioni (S,T) è violata.

La disequazione a due partizioni (S,T) è data dalla formula x(ro(S,T)) - x(E(S)) - x(E(T)) <= min {|S|,|T|} dove ro(S,T) è

11. l’insieme

degli archi che connettono i nodi in S e T ed E(S) e E(T) sono insiemi di partizioni relativi a S e T.

Nel caso in cui |S|=1 e |T| =2 la disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T si riduce

ad una disequazione triangolo in quanto x(ro(S,T)) - x(E(T)) <= 1 può essere vista come x_ij + x_ik (che

rappresenta x(ro(S,T)) ) - x_jk <= 1

Tutte le disequazioni triangolo che si possono definire per un grafo G(N,A) sono un caso particolare di

disequazione a due partizioni per una scelta opportuna di S e T

Una disequazione a due partizioni (S,T) associata ai sottoinsiemi S e T è valida per il poliedro P*.

12.

La disequazione a due aprtizioni (S,T) associati ai sottoinsiemi S e T definisce il poliedro P* = convs(S) se e

L’insieme

solo se S diverso da T. di tutte le disequazioni a due partizioni con S diverso da T non definiscono

P” P’

completamente il poliedroP*. Possiamo però concludere che è una formulazione migliore di e indichiamo

P” P’

quindi inclusione stretta a P* - -

Per il problema di partizione in clique dei nodi di un grafo non si conoscono tutte le disequazioni che

13.

definiscono la formulazione ottima P* = convs(S) ma conosciamo alcune famiglie di disequazioni valide per

P* e alcune famiglie che definiscono P*. In particolare si (P’)e

conoscono le disequazioni triangolo relative ai nodi i,j,k con x_ij + x_ik - x_jk <= 1 le disequazioni a due partizioni

relative ai sottoinsiemi (P”)

disgiunti e non vuoti S e T con x(ro(S,T)) - x(E(S)) - x(E(T)) <= min {|S|,|T|}

Lezione 022

01. Nell'applicazione del metodo dei piani di taglio al problema di partizione in clique dei nodi di un grafo

La separazione delle disequazioni a due partizioni è euristica

La separazione delle disequazioni triangolo è euristica

La separazione delle disequazioni a due partizioni è esatta

La separazione delle disequazioni a due partizioni non è necessaria

02. Determinare la soluzione ottima del problema di PL01 è

Facile se conosciamo una formulazione del problema

Possibile solo se possiamo rafforzare almeno una disequazione valida per il un poliedro contenente tutte e sole le soluzioni ammissibili del problema di PL01

Possibile solo se esiste una sequenza di Gomory

Sempre possibile attraverso la costruzione di una sequenza di Gomory

03. Nel metodo dei piani di taglio, aggiungendo disequazioni generate e rafforzate iterativamente

Si ottengono formulazioni sempre migliori

Si possono ottenere poliedri che non sono necessariamente una formulazione del problema di PL01

Si ottengono sequenze di Gomory di lunghezza infinita

Si ottengono formulazioni sempre più deboli

04. Il metodo del piano di taglio è

Un metodo generale esatto per la soluzione di problemi di PL

Un metodo generale euristico per la soluzione di problemi di PLI

Un metodo generale euristico per la soluzione di problemi di PL

Un metodo generale esatto per la soluzione di problemi di PLI

05. Nel metodo dei piani di taglio se l'oracolo di separazione non restituisce alcun iperpiano di separazione allora

Il metodo termina solo se la soluzione ottima dell'i-esimo poliedro è a componenti intere

Il metodo termina

Il metodo non termina

C'è un errore nella formulazione del problema

06. Nel metodo dei piani di taglio è necessario

Generare un numero finito di piani di taglio per produrre una formulazione con soluzione ottima intera

Generare un numero teoricamente infinito di piani di taglio per produrre una formulazione con soluzione ottima intera

Generare un numero finito di piani di taglio per produrre una soluzione frazionaria di valore ottimo e terminare

Generare un numero infinito di piani di taglio

07. Nell'applicazione del metodo dei piani di taglio al problema di partizione in clique dei nodi di un grafo

Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni triangolo

Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni triangolo e di disequazioni a due partizioni

Si applica il metodo branch and bound a un problema definito da un sottoinsieme di disequazioni a due partizioni

Non si applica il metodo branch and bound

08. Nel metodo dei piani di taglio aggiungendo la disequazione determinata dall'oracolo e rafforzata al poliedro corrente

Si ottiene un nuovo poliedro i+1 che non è necessariamente una formulazione del prolema di PL01

Si può ottenere un poliedro vuoto

Si ottiene un nuovo poliedro i+1 contenente tutte le soluzioni a componenti frazionarie tranne quella della formulazione i-esima

Si ottiene un nuovo poliedro i+1 contenente tutte le soluzioni a componenti intere in S tranne la soluzione frazionaria della formulazione i-esima

09. Nel metodo dei piani di taglio

Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora il metodo termina

Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora viene invocato l'oracolo di separazione su una qualsiasi soluzione ammissibile

della formulazione i-esima

Se la soluzione ottima della formulazione i-esima ha una sola componente frazionaria allora il metodo termina

Se la soluzione ottima della formulazione i-esima ha una o più componenti frazionarie allora viene invocato l'oracolo di separazione sulla soluzione ottima della

formulazione i-esima

10. Nel metodo dei piani di taglio

Se la soluzione ottima della formulazione i-esima ha almeno una componente intera allora il metodo termina

Se la soluzione ottima della formulazione i-esima ha tutte le componenti intere allora il metodo prosegue

Se la soluzione ottima della formulazione i-esima ha tutte le componenti intere allora il metodo termina

Se la lista dei sottoproblemi aperta è vuota il metodo termina

11. Dato un problema di PL01 si definisce iperpiano di separazione

L'iperpiano restituito da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni inammissibili per il

problema di PL01

L'iperpiano restituito da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni intere ammissibili

per il problema di PL01

La disequazione che partiziona l'insieme delle soluzioni intere ammissibili per il problema di PL01

La disequazione restituita da un oracolo di separazione per separare la soluzione ottima dell'i-esima formulazione di una sequenza di Gomory dalle soluzioni intere

ammissibili per il problema di PL01

12. In un problema di PL01, l'ipotesi di interezza delle componenti del vettore soluzione consente

Di risolvere sempre il problema in maniera euristica

Di risolvere sempre il problema in maniera esatta

Di rafforzare una disequazione valida per un poliedro contenente tutte e sole le soluzioni ammissibili del problema di PL01

Di eliminare alcuni elementi della sequenza di Gomory

13. Illustrare come applicare il metodo dei piani di taglio al problema di partizione in clique dei nodi di un grafo

14. Illustrare le principali caratteristiche del metodo dei piani di taglio

15. Definire i principali passi del metodo dei piani di taglio

Per il problema di partizione in clique dei nodi di un grafo possiamo applicare il metodo dei piani di taglio tenendo

13. P’ P”. P’

conto del fatto che conosciamo 2 formulazioni del problema : e Per si considera che è sempre possibile

enumerare tutte le 3 disequazioni triangolo per un grafo G(N,A) con n=|N| nodi e possiamo così sempre verificare se

una disequazione triangolo è violata dalla soluzione ottima senza inserire necessariamente tutte le disequazioni

triangolo nel problema. Se xi* che appartiene a Pi soddisfa tutte le disequazioni triangolo allora possiamo concluidere

che xi appartiene

P’ P”

a Per invece si definisce un algoritmo euristico per la separazione di una soluzione a componenti frazionarie dalle soluzioni

a componenti intere in S. l’oracolo

Dato che la separazioene avviene tramite euristiche se di separazione determina un iperepiano di

separazione allora possiamo rafforzare il problema corrente e procedere oltre, altrimenti non è possibile

P”

concludere che xi* appartiene a

Le principali caratteristiche sono definite da 2 concetti: rafforzamento di una disequazione valida per un poliedro e la sequenza

14. di gomory.

Nel primo caso sia aTx <= b una disequazione valida per il poliedro P. La disequazione Sommatoria[ai |xi <= b] è soddisfatta

per ogni vettore y appartenente a P intersezione {0,1}^n. La sequenza di Gomory è una sequenza di poliedri

P0,P1,P2…Pt con le seguenti proprietà: Pi è una formulazione del

problema PL01, x_i-1 non appartie