Il metodo ''Feasibility Pump'' per un problema MIP

M.Mastromarino: Il metodo ’Feasibility Pump’ per un problema MIP 3 INTRODUZIONE Un problema di Programmazione Lineare (PL) ` e un particolare Proble- ma di Ottimizzazione che ha come obiettivo la minimizzazione o la mas- simizzazione di una funzione lineare c T x sull’insieme delle soluzioni di un sistema di equazioni e disequazioni lineari. La funzione lineare c T x viene detta funzione obiettivo e le disequazioni ed equazioni lineari che definisco- no le soluzioni ammissibili vengono dette vincoli del problema. Risolvere un problema di Programmazione Lineare significa individuare una soluzio- ne ottima x ∗ o concludere che il problema ` e inferiormente illimitato (se il problema ` e di minino), superiormente illimitato ( se il problema ` e di massi- mo) o inammissibile. Un generico problema MIP (Programmazione Intera Mista) ` e un problema della forma:          min c T x Ax≥b x j intero ∀j∈ I dove A ` e una matrice mxn e I ` e il sottinsieme delle variabili vincolate ad essere intere. Lo scopo della mia tesi ` e quello di discutere un metodo per trovare una soluzione ammissibile per un generico problema MIP. Questo problema f` a parte della classe dei problemi NP-hard, che, a differenza del- le classi P, NP e degli NP-completi, non ` e limitata per definizione ai soli problemi di decisione [5]; vi appartengono infatti anche problemi di ottimiz- zazione e di altri generi. In particolare, discuter` o un nuovo approccio per calcolare le soluzioni MIP euristiche,chiamato‘Feasibility Pump’. Coniltermineeuristicosiintende