Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Monte Carlo simulation of the WENDI-2 neutron dosimeter

Il presente lavoro di tesi, sviluppato nell’arco di sei mesi presso l’Institut Supérieur Industriel de Bruxelles (ISIB) in collaborazione con Ion Beam Application Group (IBA, Louvain la Neuve), ha come principale soggetto lo studio della risposta del rem meter WENDI-2 commercializzato da Thermo Scientific. Lo studio si è basato principalmente sull’uso del codice Monte Carlo MCNPX 2.5.0, simulando la risposta del detector sia in caso di campi di radiazione neutronica monoenergetici sia in corrispondenza di spettri neutronici continui. La prima fase è stata dedicata alla modellizzazione MCNPX del rem counter, consentendo così la valutazione della sua funzione risposta. Questa è stata ricostruita interpolando 93 punti, ciascuno calcolato in corrispondenza di un singolo valore di energia di una sorgente puntiforme, compreso tra 1 meV e 5 GeV. In tal caso è stata rilevata un’ottima corrispondenza tra i risultati ottenuti e quelli riportati nella letteratura scientifica esistente. In una seconda fase, al fine di ottenere informazioni sulla risposta di WENDI II in corrispondenza di campi complessi di radiazione, simulazioni MCNPX sono state realizzate riproducendo un ambiente di lavoro esistente presso la sede IBA di Louvain la Neuve: la risposta del detector è stata valutata in corrispondenza di 9 diverse posizioni all’interno di un bunker contenente un ciclotrone PET (18 MeV H-), implicando la rilevazione di campi di radiazione neutronica continui ed estesi dalle energie termiche fino a 18 MeV. I risultati ottenuti sono stati infine comparati con i valori di dose ambiente equivalente calcolata nelle stesse condizioni di irraggiamento.

On the Design of a Boolean-network Robot Swarm: Collective Recognition of Ground Patterns.

Uno dei principali ambiti di ricerca dell’intelligenza artificiale concerne la realizzazione di agenti (in particolare, robot) in grado di aiutare o sostituire l’uomo nell’esecuzione di determinate attività. A tal fine, è possibile procedere seguendo due diversi metodi di progettazione: la progettazione manuale e la progettazione automatica. Quest’ultima può essere preferita alla prima nei contesti in cui occorra tenere in considerazione requisiti quali flessibilità e adattamento, spesso essenziali per lo svolgimento di compiti non banali in contesti reali. La progettazione automatica prende in considerazione un modello col quale rappresentare il comportamento dell’agente e una tecnica di ricerca (oppure di apprendimento) che iterativamente modifica il modello al fine di renderlo il più adatto possibile al compito in esame. In questo lavoro, il modello utilizzato per la rappresentazione del comportamento del robot è una rete booleana (Boolean network o Kauffman network). La scelta di tale modello deriva dal fatto che possiede una semplice struttura che rende agevolmente studiabili le dinamiche tuttavia complesse che si manifestano al suo interno. Inoltre, la letteratura recente mostra che i modelli a rete, quali ad esempio le reti neuronali artificiali, si sono dimostrati efficaci nella programmazione di robot. La metodologia per l’evoluzione di tale modello riguarda l’uso di tecniche di ricerca meta-euristiche in grado di trovare buone soluzioni in tempi contenuti, nonostante i grandi spazi di ricerca. Lavori precedenti hanno gia dimostrato l’applicabilità e investigato la metodologia su un singolo robot. Lo scopo di questo lavoro è quello di fornire prova di principio relativa a un insieme di robot, aprendo nuove strade per la progettazione in swarm robotics. In questo scenario, semplici agenti autonomi, interagendo fra loro, portano all’emergere di un comportamento coordinato adempiendo a task impossibili per la singola unità. Questo lavoro fornisce utili ed interessanti opportunità anche per lo studio delle interazioni fra reti booleane. Infatti, ogni robot è controllato da una rete booleana che determina l’output in funzione della propria configurazione interna ma anche dagli input ricevuti dai robot vicini. In questo lavoro definiamo un task in cui lo swarm deve discriminare due diversi pattern sul pavimento dell’arena utilizzando solo informazioni scambiate localmente. Dopo una prima serie di esperimenti preliminari che hanno permesso di identificare i parametri e il migliore algoritmo di ricerca, abbiamo semplificato l’istanza del problema per meglio investigare i criteri che possono influire sulle prestazioni. E’ stata così identificata una particolare combinazione di informazione che, scambiata localmente fra robot, porta al miglioramento delle prestazioni. L’ipotesi è stata confermata applicando successivamente questo risultato ad un’istanza più difficile del problema. Il lavoro si conclude suggerendo nuovi strumenti per lo studio dei fenomeni emergenti in contesti in cui le reti booleane interagiscono fra loro.

Progettazione robusta di un motore Stirling

Descrizione dell'applicazione di tecniche di progettazione robusta, robust design, ad un motore Stirling per generazione di corrente elettrica. La progettazione robusta è una tecnica che permette lo sviluppo di prodotti cercando di minimizzare gli effetti negativi dovuti a variazioni inaspettate nei parametri di progetto, interessante, quindi, perchè in ambito industriale accade spesso che i valori nominali dei parametri per cui si progetta un dispositivo od una macchina siano diversi da quelli che si presentano nel suo reale funzionamento.

Towards model driven software development for Arduino platforms: a DSL and automatic code generation

La tesi ha lo scopo di esplorare la produzione di sistemi software per Embedded Systems mediante l'utilizzo di tecniche relative al mondo del Model Driven Software Development. La fase più importante dello sviluppo sarà la definizione di un Meta-Modello che caratterizza i concetti fondamentali relativi agli embedded systems. Tale modello cercherà di astrarre dalla particolare piattaforma utilizzata ed individuare quali astrazioni caratterizzano il mondo degli embedded systems in generale. Tale meta-modello sarà quindi di tipo platform-independent. Per la generazione automatica di codice è stata adottata una piattaforma di riferimento, cioè Arduino. Arduino è un sistema embedded che si sta sempre più affermando perché coniuga un buon livello di performance ed un prezzo relativamente basso. Tale piattaforma permette lo sviluppo di sistemi special purpose che utilizzano sensori ed attuatori di vario genere, facilmente connessi ai pin messi a disposizione. Il meta-modello definito è un'istanza del meta-metamodello MOF, definito formalmente dall'organizzazione OMG. Questo permette allo sviluppatore di pensare ad un sistema sotto forma di modello, istanza del meta-modello definito. Un meta-modello può essere considerato anche come la sintassi astratta di un linguaggio, quindi può essere definito da un insieme di regole EBNF. La tecnologia utilizzata per la definizione del meta-modello è stata Xtext: un framework che permette la scrittura di regole EBNF e che genera automaticamente il modello Ecore associato al meta-modello definito. Ecore è l'implementazione di EMOF in ambiente Eclipse. Xtext genera inoltre dei plugin che permettono di avere un editor guidato dalla sintassi, definita nel meta-modello. La generazione automatica di codice è stata realizzata usando il linguaggio Xtend2. Tale linguaggio permette di esplorare l'Abstract Syntax Tree generato dalla traduzione del modello in Ecore e di generare tutti i file di codice necessari. Il codice generato fornisce praticamente tutta la schematic part dell'applicazione, mentre lascia all'application designer lo sviluppo della business logic. Dopo la definizione del meta-modello di un sistema embedded, il livello di astrazione è stato spostato più in alto, andando verso la definizione della parte di meta-modello relativa all'interazione di un sistema embedded con altri sistemi. Ci si è quindi spostati verso un ottica di Sistema, inteso come insieme di sistemi concentrati che interagiscono. Tale difinizione viene fatta dal punto di vista del sistema concentrato di cui si sta definendo il modello. Nella tesi viene inoltre introdotto un caso di studio che, anche se abbastanza semplice, fornisce un esempio ed un tutorial allo sviluppo di applicazioni mediante l'uso del meta-modello. Ci permette inoltre di notare come il compito dell'application designer diventi piuttosto semplice ed immediato, sempre se basato su una buona analisi del problema. I risultati ottenuti sono stati di buona qualità ed il meta-modello viene tradotto in codice che funziona correttamente.

The cutting stock problem in the wood industry

This thesis proposes a solution for board cutting in the wood industry with the aim of usage minimization and machine productivity. The problem is dealt with as a Two-Dimensional Cutting Stock Problem and specific Combinatorial Optimization methods are used to solve it considering the features of the real problem.

Tecniche di riconoscimento del volto da identikit

La vera identità di un individuo è un'informazione molto preziosa. In generale le persone non hanno particolari remore a rivelare la propria identità e il riconoscimento non rappresenta un problema; l'unica motivazione che può portare un individuo a nascondere la propria identità è l'elusione dei rilevamenti delle forze dell'ordine per un certo tipo di attività criminale. In questi casi, risulta difficile procedere al riconoscimento attraverso caratteristiche biometriche come iride o impronte digitali, in quanto la loro acquisizione presuppone un certo grado di collaborazione da parte del soggetto. Il volto, invece, può essere ottenuto in modo segreto, non solo attraverso le ben note telecamere di videosorveglianza ma anche attraverso la ricostruzione fornita da un eventuale testimone oculare che assiste all'evento criminoso. Quest'ultimo, attraverso la descrizione verbale del sospettato e con l'ausilio delle capacità di un disegnatore, fornisce un contributo per la costruzione di un identikit o sketch del soggetto, favorendo quindi il processo di individuazione dell'identità del malvivente. Solitamente, una volta prodotto lo sketch, si effettua un confronto visivo con le fotografie segnaletiche già in possesso degli inquirenti e memorizzate all'interno di un'ipotetica banca dati. Tale confronto viene eseguito 'manualmente' da persone incaricate, comportando un inevitabile spreco di tempo; dotarsi di un sistema automatico in grado di ricercare la foto del sospettato più somigliante allo sketch a partire da quelle presenti all'interno di un database potrebbe aiutare le forze di polizia in una più celere individuazione del colpevole. Purtroppo, i metodi presenti allo stato dell'arte sul riconoscimento facciale non consentono un confronto diretto: fotografia e disegno sono due rappresentazioni del volto molto differenti in termini di ricchezza di dettagli e tessitura e pertanto non direttamente confrontabili. L'obiettivo del progetto di tesi è quello di esplorare una nuova strategia di valutazione automatica della similarità tra uno sketch e una fotografia consistente principalmente in un'analisi della conformazione dei volti, mediante estrazione dei contorni e calcolo di apposite feature.

Tecniche MonteCarlo per l'analisi di sistemi a rete

The assessment of the RAMS (Reliability, Availability, Maintainability and Safety) performances of system generally includes the evaluations of the “Importance” of its components and/or of the basic parameters of the model through the use of the Importance Measures. The analytical equations proposed in this study allow the estimation of the first order Differential Importance Measure on the basis of the Birnbaum measures of components, under the hypothesis of uniform percentage changes of parameters. The aging phenomena are introduced into the model by assuming exponential-linear or Weibull distributions for the failure probabilities. An algorithm based on a combination of MonteCarlo simulation and Cellular Automata is applied in order to evaluate the performance of a networked system, made up of source nodes, user nodes and directed edges subjected to failure and repair. Importance Sampling techniques are used for the estimation of the first and total order Differential Importance Measures through only one simulation of the system “operational life”. All the output variables are computed contemporaneously on the basis of the same sequence of the involved components, event types (failure or repair) and transition times. The failure/repair probabilities are forced to be the same for all components; the transition times are sampled from the unbiased probability distributions or it can be also forced, for instance, by assuring the occurrence of at least a failure within the system operational life. The algorithm allows considering different types of maintenance actions: corrective maintenance that can be performed either immediately upon the component failure or upon finding that the component has failed for hidden failures that are not detected until an inspection; and preventive maintenance, that can be performed upon a fixed interval. It is possible to use a restoration factor to determine the age of the component after a repair or any other maintenance action.

Algorithms for UAS insertion in civil air space

One of the most interesting challenge of the next years will be the Air Space Systems automation. This process will involve different aspects as the Air Traffic Management, the Aircrafts and Airport Operations and the Guidance and Navigation Systems. The use of UAS (Uninhabited Aerial System) for civil mission will be one of the most important steps in this automation process. In civil air space, Air Traffic Controllers (ATC) manage the air traffic ensuring that a minimum separation between the controlled aircrafts is always provided. For this purpose ATCs use several operative avoidance techniques like holding patterns or rerouting. The use of UAS in these context will require the definition of strategies for a common management of piloted and piloted air traffic that allow the UAS to self separate. As a first employment in civil air space we consider a UAS surveillance mission that consists in departing from a ground base, taking pictures over a set of mission targets and coming back to the same ground base. During all mission a set of piloted aircrafts fly in the same airspace and thus the UAS has to self separate using the ATC avoidance as anticipated. We consider two objective, the first consists in the minimization of the air traffic impact over the mission, the second consists in the minimization of the impact of the mission over the air traffic. A particular version of the well known Travelling Salesman Problem (TSP) called Time-Dependant-TSP has been studied to deal with traffic problems in big urban areas. Its basic idea consists in a cost of the route between two clients depending on the period of the day in which it is crossed. Our thesis supports that such idea can be applied to the air traffic too using a convenient time horizon compatible with aircrafts operations. The cost of a UAS sub-route will depend on the air traffic that it will meet starting such route in a specific moment and consequently on the avoidance maneuver that it will use to avoid that conflict. The conflict avoidance is a topic that has been hardly developed in past years using different approaches. In this thesis we purpose a new approach based on the use of ATC operative techniques that makes it possible both to model the UAS problem using a TDTSP framework both to use an Air Traffic Management perspective. Starting from this kind of mission, the problem of the UAS insertion in civil air space is formalized as the UAS Routing Problem (URP). For this reason we introduce a new structure called Conflict Graph that makes it possible to model the avoidance maneuvers and to define the arc cost function of the departing time. Two Integer Linear Programming formulations of the problem are proposed. The first is based on a TDTSP formulation that, unfortunately, is weaker then the TSP formulation. Thus a new formulation based on a TSP variation that uses specific penalty to model the holdings is proposed. Different algorithms are presented: exact algorithms, simple heuristics used as Upper Bounds on the number of time steps used, and metaheuristic algorithms as Genetic Algorithm and Simulated Annealing. Finally an air traffic scenario has been simulated using real air traffic data in order to test our algorithms. Graphic Tools have been used to represent the Milano Linate air space and its air traffic during different days. Such data have been provided by ENAV S.p.A (Italian Agency for Air Navigation Services).

Design and Setup of a New HPGe Detector Based Body Counter Capable of Detecting Also Low Energy Photon Emitters

The present work describes the development of a new body-counter system based on HPGe detectors and installed at IVM of KIT. The goal, achieved, was the improvement of the ability to detect internal contaminations in the human body, especially the ones concerning low-energy emitters and multiple nuclides. The development of the system started with the characterisation of detectors purchased for this specific task, with the optimisation of the different desired measurement configurations following and ending with the installation and check of the results. A new software has been developed to handle the new detectors.