Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

On-line adaptive visual tracking

Visual tracking is the problem of estimating some variables related to a target given a video sequence depicting the target. Visual tracking is key to the automation of many tasks, such as visual surveillance, robot or vehicle autonomous navigation, automatic video indexing in multimedia databases. Despite many years of research, long term tracking in real world scenarios for generic targets is still unaccomplished. The main contribution of this thesis is the definition of effective algorithms that can foster a general solution to visual tracking by letting the tracker adapt to mutating working conditions. In particular, we propose to adapt two crucial components of visual trackers: the transition model and the appearance model. The less general but widespread case of tracking from a static camera is also considered and a novel change detection algorithm robust to sudden illumination changes is proposed. Based on this, a principled adaptive framework to model the interaction between Bayesian change detection and recursive Bayesian trackers is introduced. Finally, the problem of automatic tracker initialization is considered. In particular, a novel solution for categorization of 3D data is presented. The novel category recognition algorithm is based on a novel 3D descriptors that is shown to achieve state of the art performances in several applications of surface matching.

Development of bionanotechnological strategies for signal enhancement in nucleic acids biosensors

Nucleic acid biosensors represent a powerful tool for clinical and environmental pathogens detection. For applications such as point-of-care biosensing, it is fundamental to develop sensors that should be automatic, inexpensive, portable and require a professional skill of the user that should be as low as possible. With the goal of determining the presence of pathogens when present in very small amount, such as for the screening of pathogens in drinking water, an amplification step must be implemented. Often this type of determinations should be performed with simple, automatic and inexpensive hardware: the use of a chemical (or nanotechnological) isothermal solution would be desirable. My Ph.D. project focused on the study and on the testing of four isothermal reactions which can be used to amplify the nucleic acid analyte before the binding event on the surface sensor or to amplify the signal after that the hybridization event with the probe. Recombinase polymerase amplification (RPA) and ligation-mediated rolling circle amplification (L-RCA) were investigated as methods for DNA and RNA amplification. Hybridization chain reaction (HCR) and Terminal deoxynucleotidil transferase-mediated amplification were investigated as strategies to achieve the enhancement of the signal after the surface hybridization event between target and probe. In conclusion, it can be said that only a small subset of the biochemical strategies that are proved to work in solution towards the amplification of nucleic acids does truly work in the context of amplifying the signal of a detection system for pathogens. Amongst those tested during my Ph.D. activity, recombinase polymerase amplification seems the best candidate for a useful implementation in diagnostic or environmental applications.

MetaVaccinology: a new vaccine discovery tool

In the last decade, the reverse vaccinology approach shifted the paradigm of vaccine discovery from conventional culture-based methods to high-throughput genome-based approaches for the development of recombinant protein-based vaccines against pathogenic bacteria. Besides reaching its main goal of identifying new vaccine candidates, this new procedure produced also a huge amount of molecular knowledge related to them. In the present work, we explored this knowledge in a species-independent way and we performed a systematic in silico molecular analysis of more than 100 protective antigens, looking at their sequence similarity, domain composition and protein architecture in order to identify possible common molecular features. This meta-analysis revealed that, beside a low sequence similarity, most of the known bacterial protective antigens shared structural/functional Pfam domains as well as specific protein architectures. Based on this, we formulated the hypothesis that the occurrence of these molecular signatures can be predictive of possible protective properties of other proteins in different bacterial species. We tested this hypothesis in Streptococcus agalactiae and identified four new protective antigens. Moreover, in order to provide a second proof of the concept for our approach, we used Staphyloccus aureus as a second pathogen and identified five new protective antigens. This new knowledge-driven selection process, named MetaVaccinology, represents the first in silico vaccine discovery tool based on conserved and predictive molecular and structural features of bacterial protective antigens and not dependent upon the prediction of their sub-cellular localization.

Per un'indagine comparata della relazione voce-movimento nel performer

The present study investigates the principles that effect the relationship between voice and movement in performance. The topic stresses a contemporary tendency, which emerges from the work of numerous artits and looks into a research field that has not yet been well explored. The research arises from what I observed and experienced during my performance practical work and what I deepened after theorical studies: expression through movement and voice reflects constant principles. The first two chapters of the former study analyze the compared lines of the inquiry, from a theoretical point of view (interior and exterior voice-movement spatial patterns, and temporal patterns) and a practical point of view referring to body, action and relation. The third one is a survey on 'vocal gesture' as devised by Francesca della Monica, a topic that finds here the first academic investigation, built after nine years sudies with the artist on the oral sources of her teaching. The research is based on practical and theorical sources (especially philosophical studies of Giovanni Piana, Carlo Serra, Merleau-Ponty; performing studies of Grotowski, Laban, Dalcroze, Tomatis; ancient greek philosophy and literature; bodywork tecqniques as Kineseology, Body-mind centering, Alexander, Feldenkrais). The purpose of the study is to theorize, sistematyze and expose clear lines of compared investigation awakening the performer's interest on a central issue of his work and drawing the researcher's attention to make further focusing on the matter. Abstract (Italian) La ricerca va incontro a una tendenza che la contemporaneità pone in risalto con l'opera di numerosi artisti, investigando un campo ancora poco visitato a livello critico. Essa teorizza, sistematizza ed espone le costanti riscontrate nella relazione tra voce e movimento. L'indagine deriva dal presupposto, a me suggerito dalla pratica e dallo scambio con maestri e performer, e qui approfondito e restituito a livello teorico, che nella danza e nel canto, nell'espressione attraverso il movimento o attraverso la voce, si riflettono gli stessi principi. La tesi è articolata in tre capitoli: i primi due sviluppano le linee di indagine comparata, prima da un punto di vista filosofico e poi da un punto di vista pratico, il terzo porta alla luce il concetto di gesto-vocale come inteso da Francesca della Monica, di cui questo studio rappresenta il primo contributo scientifico, aprendo una ricerca nuova agli studi di settore. Il primo capitolo, 'Risonanze', sviluppa le premesse filosofiche della questione, introduce il corpo come veicolo di voce e movimento, affronta il tema del movimento della voce nello spazio interno del corpo e nello spazio di relazione. Legge poi il movimento in termini temporali, secondo i concetti di istante, ritmo, forma e flusso. Il secondo capitolo, 'Costanti', espone le costanti concrete della relazione voce-movimento in riferimento allo spazio interno del corpo, all'azione, allo spazio esterno di relazione. Il terzo capitolo, 'Confini', analizza il gesto vocale, come inteso da Francesca della Monica, concetto sintesi dell'intera ricerca poiché integra, nella sua essenza, il movimento fisico e vocale, restituendo e approfondendo lo spettro di riflessioni emerse nei primi due capitoli. Il gesto vocale, nella sua accezione espressiva, così come il lavoro di Francesca della Monica, è ancora estraneo agli studi di settore e trova in questo studio un primo contributo accademico. Le fonti sono quelle dell'insegnamento orale di Francesca della Monica, che ho seguito per nove anni, fino a desumerne una mia personale sistematizzazione, integrata con altri punti di vista critici. Analizzo i diversi livelli di profondità del gesto vocale scandendo il tema secondo la categoria della relazione: relazioni motorie, relazioni materiche, relazioni spaziali, temporali, compositive e sinestesiche. Le fonti della ricerca sono scaturite da due sorgenti, quella sul campo, e quella della teoria, confluite qui in un unico flusso. Le fonti 'in presa diretta' sono state avvalorate e confrontate con le fonti relative agli studi di settore (in particolare per la filosofia Giovanni Piana, Carlo Serra, Merleau-Ponty, per il teatro, il canto e la danza Grotowski, Laban, Dalcroze, Tomatis) e le bodywork techniques (Kinesiologia, Body-mind centering, metodo Alexander, metodo Feldenkrais). Ampio spazio viene dato alla grecità antica, che propone sull'espressione di voce e movimento un pensiero integrato carico di speculazioni che racchiudono in nuce i principi sviluppati. Lo studio tenta di offrire un livello di lettura idoneo a suscitare l'interesse del performer, e a valere come momento di indagine per lo studioso, che possa da queste basi operare approfondimenti sulle connessioni proposte. L'obiettivo è restituire la conoscenza, intuita in virtù della pratica, elaborata ed arricchita grazie alla teoria, su un nodo fondamentale per gli studi teatrali e recente oggetto di attenzione da parte di critici e artisti.

Heterosis in maize (Zea mays, L.): characterization of heterotic quantitative trait loci (QTL) for agronomic traits in near isogenic lines (NILs) and their testcrosses

In a previous study on maize (Zea mays, L.) several quantitative trait loci (QTL) showing high dominance-additive ratio for agronomic traits were identified in a population of recombinant inbred lines derived from B73 × H99. For four of these mapped QTL, namely 3.05, 4.10, 7.03 and 10.03 according to their chromosome and bin position, families of near-isogenic lines (NILs) were developed, i.e., couples of homozygous lines nearly identical except for the QTL region that is homozygote either for the allele provided by B73 or by H99. For two of these QTL (3.05 and 4.10) the NILs families were produced in two different genetic backgrounds. The present research was conducted in order to: (i) characterize these QTL by estimating additive and dominance effects; (ii) investigate if these effects can be affected by genetic background, inbreeding level and environmental growing conditions (low vs. high plant density). The six NILs’ families were tested across three years and in three Experiments at different inbreeding levels as NILs per se and their reciprocal crosses (Experiment 1), NILs crossed to related inbreds B73 and H99 (Experiment 2) and NILs crossed to four unrelated inbreds (Experiment 3). Experiment 2 was conducted at two plant densities (4.5 and 9.0 plants m-2). Results of Experiments 1 and 2 confirmed previous findings as to QTL effects, with dominance-additive ratio superior to 1 for several traits, especially for grain yield per plant and its component traits; as a tendency, dominance effects were more pronounced in Experiment 1. The QTL effects were also confirmed in Experiment 3. The interactions involving QTL effects, families and plant density were generally negligible, suggesting a certain stability of the QTL. Results emphasize the importance of dominance effects for these QTL, suggesting that they might deserve further studies, using NILs’ families and their crosses as base materials.

"Crop elicitation": approccio innovativo per la valorizzazione delle proprietà funzionali in leguminose da granella

Crop elicitation: innovative approach for the valorization of grain legume functional properties. In Italy grain legume cultivation has encountered a drastic decrease due to several causes (productive, economic, social). In this regard, studies aimed at the setting up of agronomic techniques able to guarantee high and constant in planta yields of health-promoting compounds may concur at re-launching legume production. In this context, 22 accessions of grain legumes (17 Phaseolus vulgaris, 3 Phaseolus coccineus, 1 Vigna unguiculata and 1 Glycine max genotypes) were screened with the aim of identifying genotypes rich in health beneficial phytochemicals (α-amylase inhibitors, α -glucosidase inhibitors, polyphenols) and with low anti-nutritional compounds (lectins). A wide variability was observed among investigated accessions. Four genotypes (Verdone, Kidney Cina, Roviotto and DG) showed a α -amylase inhibitory activity significantly higher (approximately 30% more) than all other tested accessions. The α -amylase inhibitory activity was not correlated neither with the protein nor with the polyphenol contents. Conversely, the α -glucosidase inhibitory activity was positively correlated with grain color and polyphenol content: dark-colored seeds had a mean inhibitory activity of 83.64 ± 22.07%, whereas light-colored seeds had mean values of 21.11 ± 9.36%. As regards the anti-nutritional compounds, out of all common bean accessions, only DG showed no erythro-agglutination activity (lectins). Preliminary experiments, performed in controlled environment, permitted to highlight that different germination conditions markedly affect the synthesis and accumulation of functional compounds in legume seedlings. Those findings were confirmed with field trials performed in two different locations (Bologna and Pisa), on two bean genotypes (Verdone and Zolfino), during the 2004-2005 cropping season. Results showed that the application of abiotic stresses (no fertilization and /or no irrigation) lead to a significant increase of flavonoids in grains, but a decrease (up to 50%) in legume yields was also observed. Crop elicitation, even if valuable for boosting health-promoting compound synthesis in crops, must necessary cope with economically acceptable crop yields.

L'obbligazione doganale

Le competenze della Comunità europea nell’ambito tributario doganale tendono normalmente ad espandersi a discapito della sovranità fiscale degli Stati membri. Il diritto doganale è stato uno dei primi ambiti giuridici in cui le competenze nazionali sono state avocate a livello comunitario. In Italia e in Belgio, normative e procedure di livello statale continuano tuttavia ad essere presenti. La ricerca si propone di evidenziare gli attriti e le differenze che distinguono il sistema Comunitario doganale dai sistemi nazionali. Sono stati in particolare esaminati i meccanismi di applicazione del diritto comunitario negli Stati membri (con riferimento all’Italia e al Belgio). Una parte della trattazione, poi, è stata dedicata alla dimensione nazionale. Si è così cercato di evidenziare le differenze tra previsioni nazionali in materia doganale nel diritto italiano e belga. La ricerca sugli aspetti statici e dinamici dell’obbligazione doganale si è così confrontata con i seguenti aspetti: - la necessità di ricostruire a livello comunitario una teoria dell’obbligazione doganale, al fine di confrontarla, in un’ottica di coerenza, con la possibilità di mantenere un limite alla libera circolazione delle merci. Quest’ultima, infatti, si confronta e in parte trova una giustificazione nella tutela degli interessi finanziari della Comunità. - la riconduzione del modello comunitario ad una teoria generale tributaria. Il tributo doganale deve essere esaminato sulla base della legislazione comunitaria, che prevede una disciplina puntuale. Si tratta della base di partenza per verificare gli aspetti di disciplina del tributo in materia di soggetto passivo, presupposto, modello di attuazione, liquidazione, rimborso. - la comparazione delle discipline nazionali italiana e belga. La coerenza, propria delle tradizioni giuridiche nazionali, non risulta essere sempre salvaguardata. Si prospetta pertanto un attrito tra gli ordinamenti nazionali e quello comunitario.

Ingegneria di Manutenzione

Lo scopo di questa tesi di dottorato di ricerca consiste nel fornire la giusta collocazione della manutenzione fra le discipline dell'ingegneria, raccogliendo e formalizzando le metodologie di analisi di affidabilità e di pianificazione degli interventi all'interno di un unico processo di progettazione e di controllo. In linea di principio, un processo di analisi dei guasti e di programmazione della manutenzione deve essere in grado di fornire chiare e sicure risposte ai seguenti interrogativi: Quali sono le funzioni richieste e con quali criteri di prestazioni il sistema è chiamato ad assolverle? Qual'è l'andamento della disponibilità del sistema in funzione del tempo? Quanti guasti e di quale tipo si possono verificare durante la vita del sistema? Quali possono essere le conseguenze che ledono la sicurezza e la protezione ambientale? Quanti pezzi di ricambio sono necessari? Che tipo di interventi di manutenzione preventiva risultano tecnicamente fattibili? A quali scadenze devono essere programmati? A quanto ammonta la previsione del costo di esercizio del sistema? Quante squadre di manutenzione devono essere assegnate al sistema? Come deve essere organizzata la logistica di manutenzione? Con quali tecniche si prevede di riconoscere i guasti e quali procedure devono essere attivate per farvi fronte? E' possibile implementare tecniche di `condition monitoring' delle macchine? Su quali tempi di preavviso sui guasti si può contare? In tal senso, la manutenzione necessita delle tecniche e degli opportuni strumenti che siano in grado di misurarne l'efficacia e l'efficienza. L'efficacia in primo luogo, in quanto l'obiettivo principe consiste nel garantire che il sistema oggetto di studio continui a svolgere le proprie funzioni nei limiti di prestazioni accettabili, secondo le specifiche richieste degli utilizzatori. L'efficienza in secondo luogo, ma non per questo di minore importanza, in quanto perseguendo l'obiettivo di cui sopra, occorre impegnare il minimo di risorse possibili, organizzando con razionalità il supporto logistico del sistema al fine di raggiungere i massimi livelli di rendimento di gestione. La migliore strategia di manutenzione può essere pianificata, a priori, solo se si è in grado di prevedere con la necessaria precisione l'evoluzione del sistema nel suo contesto operativo futuro. E' allora possibile formulare un modello matematico del sistema, studiarne la dinamica ed osservare le reazioni alla simulazione di eventuali stimoli esterni. I metodi ed i modelli noti dell'ingegneria dei sistemi possono essere molto utili per la risoluzione di casi semplici, ma sovente richiedono la formulazione di ipotesi troppo restrittive che aumentano in modo inaccettabile la distanza del modello dalla realtà. Una strada alternativa ed affascinante, che ho percorso con entusiasmo durante questi tre anni di studi e ricerca, consiste nella simulazione numerica della vita del sistema, utilizzando il metodo Monte Carlo per la gestione dei processi stocastici di guasto e per l'esecuzione degli interventi di manutenzione. Ho quindi messo a punto il codice di simulazione RAMSES, perseguendo l'idea di costruire uno strumento di misura dell'efficacia e dell'efficienza di una politica di manutenzione simulata al calcolatore. Nella tesi si presentano i concetti di base dell'ingegneria dei sistemi applicata al caso della manutenzione e si introduce il formalismo della Reliability Centred Maintenance come miglior guida nella pianificazione delle schede di manutenzione. Si introducono le nozioni di base per fornire una struttura solida e corretta alla simulazione numerica dei sistemi riparabili e si presenta il codice RAMSES corredando le informazioni tecniche con i dovuti esempi ed applicazioni pratiche. Si conclude il lavoro, infine, con la presentazione di un modello di massima verosimiglianza particolarmente utile per le analisi dei dati sperimentali di guasto dei componenti.

La Ricostruzione 3D di Bologna nel XVI Secolo

Il lavoro presentato ha come oggetto la ricostruzione tridimensionale della città di Bologna nella sua fase rinascimentale. Tale lavoro vuole fornire un modello 3D delle architetture e degli spazi urbani utilizzabile sia per scopi di ricerca nell’ambito della storia delle città sia per un uso didattico-divulgativo nel settore del turismo culturale. La base del lavoro è una fonte iconografica di grande importanza: l’affresco raffigurante Bologna risalente al 1575 e situato in Vaticano; questa è una veduta a volo d’uccello di grandi dimensioni dell’intero tessuto urbano bolognese all’interno della terza cerchia di mura. In esso sono rappresentate in maniera particolareggiata le architetture civili e ecclesiastiche, gli spazi ortivi e cortilivi interni agli isolati e alcune importanti strutture urbane presenti in città alla fine del Cinquecento, come l’area portuale e i canali interni alla città, oggi non più visibili. La ricostruzione tridimensionale è stata realizzata tramite Blender, software per la modellazione 3D opensource, attraverso le fasi di modellazione, texturing e creazione materiali (mediante campionamento delle principali cromie presenti nell’affresco), illuminazione e animazione. Una parte della modellazione è stata poi testata all’interno di un GIS per verificare l’utilizzo delle geometrie 3D come elementi collegabili ad altre fonti storiche relative allo sviluppo urbano e quindi sfruttabili per la ricerca storica. Grande attenzione infine è stata data all’uso dei modelli virtuali a scopo didattico-divulgativo e per il turismo culturale. La modellazione è stata utilizzata all’interno di un motore grafico 3D per costruire un ambiente virtuale interattivo nel quale un utente anche non esperto possa muoversi per esplorare gli spazi urbani della Bologna del Cinquecento. In ultimo è stato impostato lo sviluppo di un’applicazione per sistemi mobile (Iphone e Ipad) al fine di fornire uno strumento per la conoscenza della città storica in mobilità, attraverso la comparazione dello stato attuale con quello ricostruito virtualmente.