Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

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

Nei primi due capitoli abbiamo analizzato computazionalmente un nuovo metodo euristico per trovare una soluzione ammissibile per problemi MIP generali, detto Feasibility Pump, il quale genera due traiettorie di punti x e˜x che soddisfano l’ammissibilità MIP in modo complementare.
Il metodo può anche essere interpretato come una strategia per creare una sequenza euristica di arrotondamenti in modo da trovare la soluzione per un problema MIP.
In seguito è stata analizzata una nuova versione euristica della Feasibility Pump e sono stati analizzati i risultati computazionali. L’idea è stata di sfruttare un concetto della Programmazione Vincolata, denominato Propagazione Vincolata, la quale risulta essere molto e?cace per quanto riguarda l’operazione di arrotondamento.
I risultati computazionali su entrambi i MIP binario e intero generale mostrano che il nuovo metodo trova più soluzioni ammissibili del suo predecessore, generalmente in un tempo computazionale più breve. Una delle caratteristiche principali del nuovo metodo è stata di ridurre il numero di iterazioni per raggiungere la convergenza, che implica una soluzione di migliore qualità del risultato finale.

Mostra/Nascondi contenuto.
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

Laurea liv.I

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Mariangela Mastromarino Contatta »

Composta da 30 pagine.

 

Questa tesi ha raggiunto 256 click dal 09/06/2011.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.