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

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