Programmazione Lineare Intera Mista (MILP)

La programmazione lineare intera mista (MILP) è la classe di problemi min c^T x + d^T y s.t. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ in forma canonica, dove x ∈ R^n sono variabili continue e y ∈ Z^p variabili intere. L'integrità è di solito binaria y ∈ {0,1}^p e modella decisioni logiche (investire/no, aprire/chiudere macchina, usare/non usare rotta, assegnazione prodotto-fornitore-periodo). Costi fissi, lotti discreti, disgiunzioni e formulazioni big-M impongono variabili intere. Complessità: MILP è NP-difficile (Cook 1971 per riduzione da SAT; molti dei 21 problemi NP-completi di Karp 1972 sono esprimibili come MILP); il rilassamento LP (rimuovendo l'integrità, sostituendola con y ≥ 0) è polinomiale e fornisce un lower bound in minimizzazione. L'algoritmo canonico è branch-and-bound di Land e Doig (1960) — risolvere il rilassamento LP, ramificare su una y_i frazionaria, potare i sottoalberi il cui bound è peggiore dell'incumbent. Gomory (1958) introdusse i tagli frazionari e Padberg e Rinaldi (1991) consolidarono il quadro branch-and-cut; i solver moderni combinano piani di taglio (Gomory, lift-and-project, MIR, cover), presolve di nodo, euristiche primali (feasibility pump, RINS), analisi dei conflitti e branch-and-bound parallelo. I modelli MILP coprono localizzazione impianti (Fixed Charge Facility Location), routing di veicoli, scheduling di produzione, assegnamento, packing, progettazione di reti, selezione di portafoglio (vincoli di cardinalità) e unit commitment energetico.