Metodo dei Piani di Taglio

Il metodo dei piani di taglio è una tecnica classica per la programmazione intera (IP) e la programmazione intera mista (MIP) che stringe iterativamente il rilassamento LP con **disuguaglianze valide** che tagliano l'ottimo LP frazionario senza escludere alcun punto intero ammissibile. Lo ha introdotto Gomory (1958) per la programmazione intera (taglio frazionario di Gomory) e Gomory (1960) per la variante intera mista (taglio misto-intero di Gomory). L'algoritmo procede così: risolvere il rilassamento LP; se la soluzione è intera, l'ottimo è trovato; altrimenti generare un taglio che esclude il punto frazionario ma preserva tutti i punti interi ammissibili, aggiungerlo al modello e risolvere di nuovo l'LP; iterare fino all'integrità. Le famiglie di taglio sono specifiche del problema: tagli di copertura per zaino, tagli di copertura di flusso, tagli di clique (colorazione di grafi/IP), arrotondamento misto-intero (MIR), tagli Chvátal-Gomory, tagli lift-and-project (Balas, Ceria e Cornuéjols 1993), disuguaglianze subtour e comb per TSP (Padberg-Rinaldi 1991). Poiché i tagli puri di Gomory convergono lentamente in pratica, le implementazioni moderne combinano tagli con branch and bound (branch-and-cut, Padberg e Rinaldi 1991) — l'architettura fondante dei solver MIP moderni. La generazione di tagli è automatica e in larga parte invisibile all'utente. Nemhauser e Wolsey (1988), Wolsey (1998) e Cornuéjols (2008) sono letture di riferimento.