BRANCH-AND-CUT

Anche se la convergenza è garantita, il metodo dei piani di taglio "alla Gomory" risulta troppo lento per essere efficace in generale. Padberg e Rinaldi (1991) hanno proposto per primi di combinare Branch-and-Bound (B&B) e Metodo di Taglio denominando tale combinazione Branch-and-Cut: questa famiglia di algoritmi è oggi la più efficace risposta alla necessità di risolvere esattamente (cioè trovando un ottimo globale) un problema di Ottimizzazione Combinatoria difficile.

Il Branch-and-Cut (B&C) ricorre ad un albero decisionale del tutto analogo a quello del B&B. Si comincia col supporre che il problema sia stato formulato come problema di PLI e si costruisce un "serbatoio" (pool) di disuguaglianze valide per tutte le soluzioni intere (cioè per la regione di ammissibilità che abbiamo indicato con X). In pratica questo è in effetti un pool di algoritmi per cercare piani di taglio in presenza di una soluzione ottima frazionaria del rilassamento continuo del problema.

Si inizia il B&C come con il Metodo di Taglio risolvendo per un certo numero di iterazioni il problema di separazione di x* da X con l' aiuto del pool di algoritmi di cui sopra. Se si arriva ad una soluzione intera sappiamo che è quella ottima, ma anche quando ciò non accade l' ultima iterazione ci avrà dato una stima (per difetto se il problema è di minimo) del valore dell' ottimo che si presume migliore di quella ottenuta senza far ricorso al pool di disuguaglianze valide.

Si procede allora a ramificare (branch) ad esempio generando un sottoproblema per ogni valore intero permesso di una delle variabili frazionarie di x*. Ad ognuno dei sottoproblemi si applica di nuovo il Metodo di Taglio e così via.

Perché il B&C abbia successo è vitale che le stime ottenute siano più vicine possibile all' ottimo, cioè che i piani di taglio derivati dal pool siano i più vincolanti possibili. Un criterio spesso usato è quello di cercare famiglie di disuguaglianze che inducano faccette per X: sappiamo infatti che queste sono disuguaglianze forti in quanto si avvicinano il più possibile a conv(X) senza tagliare via niente.

Si noti che, dato che la convergenza è garantita dal processo di branch, è possibile utilizzare metodi euristici per la soluzione dei problemi di separazione, accettando che in certi casi non si trovi un taglio di una data famiglia anche se esiste.

Idealmente si vorrebbe disporre di procedure generalmente applicabili a qualunque problema di PLI. In questa direzione si sono fatti progressi notevoli (un esempio è il metodo Lift-and-Project di Balas et al.), ma non ancora definitivi. Finché tali procedure restano insoddisfacenti in pratica dal punto di vista del tempo di calcolo, l' alternativa è di studiare classi specifiche di problemi di PLI, per identificare famiglie di tagli con le relative procedure di separazione per rendere il più  efficace possibile l' uso del pool sopra illustrato.

BRANCH AND CUT

[inizializzazione] Sia z = max e P la sua regione di ammissibilità rilassata; z:=- , x* vuoto; si preprocessi il problema dato e lo si metta nella LISTANODI;

[uscita] if LISTANODI vuota then go to 8 else

scegli un nodo i e rimuovilo dalla LISTANODI;

[inizio iterazione] ripristina il rilassamento continuo Pⁱ dell'insieme Xⁱ; k:=1; Pⁱ_k:=Pⁱ;

[rilassamento continuo] risolvi zⁱ_k = max; if inammissibile go to 2 else

sia x^ik la soluzione;

[taglio] cerca di tagliare x^ik con gli algoritmi del pool; if tagli trovati then aggiungili a Pⁱ_k ottenendo Pⁱ_k+1; k:=k+1; go to 4 else

[potatura e aggiornamento] if zⁱ_k z then go to 2 else if x^ikIX then z := zⁱ_k ; x*:= x^ik; go to 2

[branching] crea due o più nuovi problemi Xⁱ_t con

rilassamenti Pⁱ_t e aggiungili a LISTANODI; go to 2

[fine] output x* (ottimo)
ALCUNE TECNICHE UTILIZZATE PER MIGLIORARE IL B&C

PREPROCESSING

• Rimuovere vincoli ridondanti
• Rinforzare i coefficienti dei vincoli
• Rinforzare i termini noti delle equazioni di vincolo
• Fissare variabili (quando possibile)

POSTPROCESSING

Quando z_LP non corrisponde ad una soluzione intera x*, se si dispone di una soluzione F ottenuta euristicamente, sappiamo che z_LP z* z_F. F può spesso ottenersi con semplici tecniche di arrotondamento delle variabili frazionarie (euristica primale).

AGGIUNGERE DISUGUAGLIANZE VALIDE IN GENERALE

Ad esempio vincoli tipo Zaino possono generare disuguaglianze di copertura violate da x* (questa tecnica è ben illustrata dal lavoro di Aardal et al. 1994 sul problema di allocazione ottima con vincoli di capacità).

STRATEGIA DI BRANCH

La scelta della variabile frazionaria su cui fare il Branch avviene secondo uno o un misto dei seguenti criteri (supponendo di avere a che fare con un problema di minimo in variabili binarie):

1. il valore più vicino a 0.5
2. il valore più vicino a 1
3. la variabile con il coefficiente di costo più alto
4. selezionando un insieme di variabili "promettenti",  calcolando per ognuna la stima per difetto ottenuto dal corrispondente sottoproblema, e scegliendo la variabile col valore inferiore di tale stima

e 3. sono stati usati da Padberg e Rinaldi per il TSP;

è spesso efficace insieme ad una tecnica depth-first

di selezione del problema da esaminare per primo fra quelli corrispondenti a nodi attivi dell' albero decisionale. Molte altre opzioni sono state proposte in tempi recenti.

10-EURISTICHE

Chiamiamo metodi euristici quelli che (contrariamente ai metodi approssimati) non danno nessuna garanzia a-priori sul valore di R(x,y).

RAGIONI PER SCEGLIERE UN' EURISTICA

• La soluzione deve essere ottenuta rapidamente e non sono disponibili metodi approssimati efficaci
• Istanza troppo grande per essere formulata come problema di PLI (o di MIP) di dimensione ragionevole
• Difficile formulare il problema come problema di PLI (o di MIP) perché troppo complicato
• Branch-and-Bound (o Branch-and-Cut) non arriva a trovare soluzioni in tempi di calcolo ragionevoli
• L' esperienza dice che un certo metodo euristico fornisce buone soluzioni, mentre i metodi esatti sono inefficaci

Distinguiamo fra euristiche COSTRUTTIVE (ad esempio il metodo GREEDY) e euristiche DI SCAMBIO (dette anche di RICERCA LOCALE)

Sia F l' insieme delle soluzioni ammissibili s di un generico problema di ottimizzazione combinatoria e c(s) la sua funzione costo e supponiamo, senza perdere in generalità, che si tratti di un problema di minimo:

min