Tagli di Gomory

[CLaudio Nine]

Ciao a tutti,

ho una domanda per voi, che è stata posta ad un esame di Ricerca Operativa:

"In che modo i tagli di Gomory vengono utilizzati nell'algoritmo di Branch and Bound?"

Consideriamo un problema di Programmazione Lineare Intera $P$ ed un suo rilassamento (senza interezza) $P'$.

Io so che, nel problema $P'$, data una soluzione $bar(x)$ non intera, un taglio di Gomory è un nuovo vincolo al problema (una disequazione) che fa sì che tutte le soluzioni intere vengano mantenute nella regione ammissibile e la soluzione $bar(x)$ venga esclusa.

Nell'algoritmo di Branch and Bound, se trovo una soluzione non intera del problema rilassato $bar(x)$, quello che faccio è selezionare una componente non intera di $bar(x)$, ovvero $x_i$, e studiare due sottoproblemi in cui aggiungo rispettivamente i due seguenti vincoli:

$x_i <= text(floor)(x_i)$[nota]$text(floor)(x)$ sta per parte intera inferiore di $x$[/nota]

e

$x_i >= text(roof)(x_i)$[nota]$text(roof)(x)$ sta per parte intera superiore di $x$[/nota]

Chiaramente queste sono due disuguaglianze e due nuovi vincoli per i due sottoproblemi, tuttavia non mi sembrano tagli di Gomory.
Non mi sembrano generati nello stesso modo in cui si generano i tagli di Gomory.
Quindi non saprei come rispondere alla domanda posta dal Professore.

Voi cosa ne pensate?
Voi come rispondereste al quesito?

Grazie in anticipo!

[axpgn]

[ot]Dal "ceiling" si è passati al "roof" ? [/ot]