Programmazione Intera (IP)

La programmazione intera (pure IP) è la classe di problemi min c^T x s.t. Ax ≤ b, x ∈ Z^n_+ in forma canonica, dove tutte le variabili decisionali sono intere. Il caso 0-1 (binario) x ∈ {0,1}^n è la formulazione naturale dell'ottimizzazione combinatoria: zaino, assegnamento, set covering, set partitioning, problema del commesso viaggiatore (TSP), matching e colorazione di grafi. Complessità: l'IP pura compare come 0-1 IP nella lista dei 21 problemi NP-completi di Karp (1972); Lenstra (1983) mostrò che l'IP è risolvibile in tempo polinomiale in dimensione fissa (impraticabile quando la dimensione fa parte dell'input). Imporre l'integrità al rilassamento LP può spostare bruscamente l'ottimo; l'integrality gap è la misura canonica della forza della formulazione. L'algoritmo classico è il metodo dei piani di taglio di Gomory (1958): risolvere il rilassamento LP, se l'ottimo è frazionario generare un taglio di Gomory (dalle informazioni del tableau simplesso) che escluda l'ottimo LP corrente ma nessun punto intero ammissibile, aggiungerlo e risolvere di nuovo; converge in un numero finito di iterazioni a un ottimo intero (in teoria). In pratica branch-and-bound di Land e Doig (1960), poi branch-and-cut (Padberg e Rinaldi 1991), risulta più veloce. La teoria poliedrale — Chvátal (1973), Schrijver (1986) — deriva disuguaglianze valide (subtour-elimination, disuguaglianze di blossom per TSP) che avvicinano il rilassamento all'inviluppo convesso dei punti interi ammissibili. Applicazioni: TSP / routing di veicoli (Dantzig, Fulkerson e Johnson 1954), assegnamento, scheduling, flusso su rete, cutting stock (Gilmore e Gomory 1961), bin packing.