Branch-and-Cut

Branch-and-cut è il framework di risoluzione esatto per la programmazione lineare intera mista (MIP) che sta alla base di ogni solver MIP moderno, commerciale o open-source. Combina due idee: (a) **branch-and-bound** — dividere il problema intero in sotto-problemi più piccoli tramite branching di variabili, risolvere il rilassamento LP in ciascun nodo e potare i sotto-alberi il cui bound LP sia peggiore della migliore soluzione ammissibile corrente; (b) **piani di taglio** — prima del branching aggiungere disuguaglianze valide (tagli) che ogni soluzione intera ammissibile soddisfa ma che tagliano via l'ottimo LP frazionario corrente, stringendo il rilassamento e riducendo il gap di bound. L'approccio è stato introdotto da Dantzig, Fulkerson e Johnson (1954) sul Travelling Salesman Problem (TSP) — hanno usato tagli di eliminazione dei sub-tour all'interno di una ricerca branch-and-bound e risolto un'istanza di 49 città all'ottimo. Padberg e Rinaldi (1991) hanno generalizzato il framework con routine di separazione che individuano i tagli violati al volo. Oggi branch-and-cut è il metodo esatto di default per TSP, VRP, scheduling, localizzazione di impianti e decine di altri problemi di ottimizzazione combinatoria; le prestazioni dei solver sul TSP hanno superato 85K+ nodi (Applegate, Bixby, Chvátal e Cook 2006). Tagli usati in pratica: eliminazione di sub-tour, disuguaglianze a pettine (comb), tagli di clique, tagli di Gomory, tagli di arrotondamento intero misto, tagli lift-and-project.