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

Un software per il calcolo del gruppo di simmetria di un ILP

Si considerano istanze di problemi di Programmazione Lineare Intera dotati di simmetria. Vengono descritte alcune tecniche utilizzate per sfruttare la conoscenza delle simmetrie e un algoritmo per il calcolo del gruppo di simmetria di un ILP utilizzato da un noto software (Saucy). Viene apportato un miglioramento all'algoritmo e si realizza un software basato su tale algoritmo.
Si effettuano dei test su istanze binarie di problemi ILP e si verifica che le prestazioni sono al livello dell'attuale stato dell'arte.

Mostra/Nascondi contenuto.
Capitolo 1 Introduzione L’oggetto di questa tesi e un generico problema di Programmazione Lineare Intera (ILP). La modellazione matematica di numerosissimi problemi pratici, dalla logistica, alle telecomunicazioni no al decision-making, d a origine a problemi di ottimizzazione in cui le variabili possono assumere solo valori interi. Nel primo capitolo verranno date le denizioni principali, si mostrer a qualche esempio e si descriver a un algoritmo generale (Branch&Bound) con il quale questi problemi possono essere risolti. Ci si rivolger a in particolare ad una classe di problemi ILP che sono tra i pi u dicili da risolvere, quelli dotati di simmetria, ovvero quelli per cui una opportuna permutazione delle variabili di una soluzione del problema e an- cora una soluzione. Questa caratteristica pu o rendere altamente ineciente l’algoritmo Branch&Bound, impedendo la soluzione di tali problemi in tempi ragionevoli. Nel secondo capitolo si dar a la denizione di Gruppo di Simme- tria (G) di un problema di Programmazione Lineare Intera e si descriveranno alcune tecniche che sfruttano la conoscenza delle simmetrie per aumentare l’ecienza dell’algoritmo Branch&Bound. Ci si concentrer a sul problema della determinazione del gruppo di simmetria: allo stato dell’arte esistono alcuni software, tra cui Nauty (http://cs.anu.edu.au/people/bdm/nauty/) e Saucy (http://vlsicad.eecs.umich.edu/BK/SAUCY/), disponibili in ambien- te accademico, per il calcolo del gruppo degli automorsmi di un grafo, quindi si descriver a come utilizzare tali software per calcolare il gruppo di simmetria di un ILP. 1

Tesi di Laurea Magistrale

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Marco Perin Contatta »

Composta da 77 pagine.

 

Questa tesi ha raggiunto 914 click dal 21/02/2012.

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