Il rilassamento Lagrangiano nella soluzione di problemi di programmazione lineare intera

L’applicazione di algoritmi di enumerazione implicita a problemi di programmazione li-neare intera (PLI) e ̀ basata sulla possibilita ̀ di avere, ad ogni nodo dell’albero di enumer-azione, un bound sul valore della soluzione ottima. Il metodo piu ̀ immediato per calcolare tale bound consiste nel risolvere un problema di programmazione lineare (PL) ottenuto rilassando i vincoli di interezza delle variabili. Tuttavia, esistono altri approcci. In questa dispensa vogliamo presentare l’approccio Lagrangiano, che e ̀ impiegato con successo in molti algoritmi di soluzione per un numero molto ampio di problemi di PLI. L’intuizione alla base dell’approccio Lagrangiano consiste nel vedere un problema di programmazione lineare intera “difficile ” come un problema “facile”, complicato pero ̀ da un insieme, in genere di dimensione ridotta, di vincoli ulteriori. Il rilassamento La-grangiano consiste nell’eliminazione di tali vincoli “indesiderati ” e nell’inserimento di questi nella funzione obiettivo, in modo tale da tenerne comunque conto nella soluzione del problema rilassato. Si consideri il seguente problema di Programmazione Lineare Intera PLI1: min cTx (1)