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

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

CAPITOLO 1 Sia dato un problema MIP come quello descritto nell’introduzione e sia P :={x∈R n : Ax≥ b}ilpoliedroassociatoalsuorilassamentoLP.Conun piccolo abuso di notazione, diciamo che un punto x ` e intero se x j ` e intero ∀j ∈ I, dove con I indichiamo l’insieme degli indici che dovranno essere interi nell’insieme {1...n}. Analogamente, l’arrotondamento ˜ x di un dato x ` e ottenuto ponendo: ˜ x j :=    [x j ] se j ∈ I x j altrimenti dove [.] rappresenta l’arrotondamento scalare al pi` u vicino intero. Indichia- mo con: Δ(x,˜ x) = null j∈I | x j − ˜ x j | la distanza L 1 del vettore differenza tra un generico punto x ∈ P e il suo arrotondamento ˜ x. Possiamo assumere, senza perdita di generalit` a, che il modello MIP includa le seguenti variabili e vincoli aggiuntivi: - limiti sulle variabili: l j ≤ x j ≤ u j ∀j ∈ I; - vincoli aggiuntivi: x j = ˜ x j +x + j −x − j , in cui x + j , x − j ≥ 0 (dove al pi` u una tra x + j e x − j ` e diversa da zero). 5

Anteprima della Tesi di Mariangela Mastromarino

Anteprima della tesi: Il metodo ''Feasibility Pump'' per un problema MIP, Pagina 4

Laurea liv.I

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Mariangela Mastromarino Contatta »

Composta da 30 pagine.

 

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

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