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)$¹

e

$x_i >= text(roof)(x_i)$²

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!

---

Note

1. $text(floor)(x)$ sta per parte intera inferiore di $x$ ↑
2. $text(roof)(x)$ sta per parte intera superiore di $x$ ↑

[axpgn]

Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.

Dal "ceiling" si è passati al "roof" ?