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.

Refined Estimation of Earthquake Source Parameters: Methods, Applications and Scaling Relationships

The objective of this work of thesis is the refined estimations of source parameters. To such a purpose we used two different approaches, one in the frequency domain and the other in the time domain. In frequency domain, we analyzed the P- and S-wave displacement spectra to estimate spectral parameters, that is corner frequencies and low frequency spectral amplitudes. We used a parametric modeling approach which is combined with a multi-step, non-linear inversion strategy and includes the correction for attenuation and site effects. The iterative multi-step procedure was applied to about 700 microearthquakes in the moment range 1011-1014 N•m and recorded at the dense, wide-dynamic range, seismic networks operating in Southern Apennines (Italy). The analysis of the source parameters is often complicated when we are not able to model the propagation accurately. In this case the empirical Green function approach is a very useful tool to study the seismic source properties. In fact the Empirical Green Functions (EGFs) consent to represent the contribution of propagation and site effects to signal without using approximate velocity models. An EGF is a recorded three-component set of time-histories of a small earthquake whose source mechanism and propagation path are similar to those of the master event. Thus, in time domain, the deconvolution method of Vallée (2004) was applied to calculate the source time functions (RSTFs) and to accurately estimate source size and rupture velocity. This technique was applied to 1) large event, that is Mw=6.3 2009 L’Aquila mainshock (Central Italy), 2) moderate events, that is cluster of earthquakes of 2009 L’Aquila sequence with moment magnitude ranging between 3 and 5.6, 3) small event, i.e. Mw=2.9 Laviano mainshock (Southern Italy).

New approach in the diagnosis and therapy of hyperphenylalaninemia

Background. Phenylketonuria is the most prevalent inborn error of aminoacid metabolism. Is an autosomal recessive disorder. It results from mutations in the phenylalanine hydroxilase (PAH) gene. Phenotypes can vary from mild hyperphenylalaninemia to a severe phenylketonuria wich, if untreated, results in severe mental retardation. Thanks to neonatal screening programmes, early detection and promp dietetic intervention (phenylalanine restricted diet lifelong) has allowed to avoid neurocognitive complications. Recently, a new therapy is become widely used: the oral supplementation with the PAH cofactor (BH4), wich can alleviate the diet burden. Genotype-phenotype correlation is a reliable tool to predict metabolic phenotype in order to establish a better tailored diet and to assess the potential responsiveness to BH4 therapy. Aim Molecular analysis of the PAH gene, evaluation of genotype-phenotype correlation and prediction of BH4 responsiveness in a group of HPA patients living in Emilia Romagna. Patients and methods. We studied 48 patients affected by PAH deficiency in regular follow-up to our Metabolic Centre. We performed the molecular analysis of these patients using genomic DNA extracted from peripheral blood samples Results. We obtained a full genotipic characterization of 46 patients. We found 87 mutant alleles and 35 different mutations, being the most frequent IVS10-11 G>A (19.3%), R261Q (9.1%), R158Q (9.1%), R408Q (6.8%) and A403V (5.7%), including 2 new ones (L287, N223Y) ever described previously. Notably, we found 15 mutations already identified in BH4-responsive patients, according to the literature. We found 42 different genotipic combinations, most of them in single patients and involving a BH4-responsive mutation. Conclusion. BH4 responsiveness is shown by a consistent number of PAH deficient hyperphenylalaninemic patients. This treatment, combined with a less restricted diet or as monotherapy, can reduce nutritional complications and improve the quality of life of these patients.

Quantum effects and dynamics in hydrogen-bonded systems: a first-principles approach to spectroscopic experiments

Computer simulations have become an important tool in physics. Especially systems in the solid state have been investigated extensively with the help of modern computational methods. This thesis focuses on the simulation of hydrogen-bonded systems, using quantum chemical methods combined with molecular dynamics (MD) simulations. MD simulations are carried out for investigating the energetics and structure of a system under conditions that include physical parameters such as temperature and pressure. Ab initio quantum chemical methods have proven to be capable of predicting spectroscopic quantities. The combination of these two features still represents a methodological challenge. Furthermore, conventional MD simulations consider the nuclei as classical particles. Not only motional effects, but also the quantum nature of the nuclei are expected to influence the properties of a molecular system. This work aims at a more realistic description of properties that are accessible via NMR experiments. With the help of the path integral formalism the quantum nature of the nuclei has been incorporated and its influence on the NMR parameters explored. The effect on both the NMR chemical shift and the Nuclear Quadrupole Coupling Constants (NQCC) is presented for intra- and intermolecular hydrogen bonds. The second part of this thesis presents the computation of electric field gradients within the Gaussian and Augmented Plane Waves (GAPW) framework, that allows for all-electron calculations in periodic systems. This recent development improves the accuracy of many calculations compared to the pseudopotential approximation, which treats the core electrons as part of an effective potential. In combination with MD simulations of water, the NMR longitudinal relaxation times for 17O and 2H have been obtained. The results show a considerable agreement with the experiment. Finally, an implementation of the calculation of the stress tensor into the quantum chemical program suite CP2K is presented. This enables MD simulations under constant pressure conditions, which is demonstrated with a series of liquid water simulations, that sheds light on the influence of the exchange-correlation functional used on the density of the simulated liquid.

Comparison between analytical and numerical methods for the assessment of masonry arch bridges: Case study of Clemente Bridge on Savio river

This research has focused on the study of the behavior and of the collapse of masonry arch bridges. The latest decades have seen an increasing interest in this structural type, that is still present and in use, despite the passage of time and the variation of the transport means. Several strategies have been developed during the time to simulate the response of this type of structures, although even today there is no generally accepted standard one for assessment of masonry arch bridges. The aim of this thesis is to compare the principal analytical and numerical methods existing in literature on case studies, trying to highlight values and weaknesses. The methods taken in exam are mainly three: i) the Thrust Line Analysis Method; ii) the Mechanism Method; iii) the Finite Element Methods. The Thrust Line Analysis Method and the Mechanism Method are analytical methods and derived from two of the fundamental theorems of the Plastic Analysis, while the Finite Element Method is a numerical method, that uses different strategies of discretization to analyze the structure. Every method is applied to the case study through computer-based representations, that allow a friendly-use application of the principles explained. A particular closed-form approach based on an elasto-plastic material model and developed by some Belgian researchers is also studied. To compare the three methods, two different case study have been analyzed: i) a generic masonry arch bridge with a single span; ii) a real masonry arch bridge, the Clemente Bridge, built on Savio River in Cesena. In the analyses performed, all the models are two-dimensional in order to have results comparable between the different methods taken in exam. The different methods have been compared with each other in terms of collapse load and of hinge positions.

LCA-GIS Integrated approach for a Sustainable Land Use Under Energy Crops

In genere, negli studi di vocazionalità delle colture, vengono presi in considerazione solo variabili ambientali pedo-climatiche. La coltivazione di una coltura comporta anche un impatto ambientale derivante dalle pratiche agronomiche ed il territorio può essere più o meno sensibile a questi impatti in base alla sua vulnerabilità. In questo studio si vuole sviluppare una metodologia per relazionare spazialmente l’impatto delle colture con le caratteristiche sito specifiche del territorio in modo da considerare anche questo aspetto nell’allocazione negli studi di vocazionalità. LCA è stato utilizzato per quantificare diversi impatti di alcune colture erbacee alimentari e da energia, relazionati a mappe di vulnerabilità costruite con l’utilizzo di GIS, attraverso il calcolo di coefficienti di rischio di allocazione per ogni combinazione coltura-area vulnerabile. Le colture energetiche sono state considerate come un uso alternativo del suolo per diminuire l’impatto ambientale. Il caso studio ha mostrato che l’allocazione delle colture può essere diversa in base al tipo e al numero di impatti considerati. Il risultato sono delle mappe in cui sono riportate le distribuzioni ottimali delle colture al fine di minimizzare gli impatti, rispetto a mais e grano, due colture alimentari importanti nell’area di studio. Le colture con l’impatto più alto dovrebbero essere coltivate nelle aree a vulnerabilità bassa, e viceversa. Se il rischio ambientale è la priorità, mais, colza, grano, girasole, e sorgo da fibra dovrebbero essere coltivate solo nelle aree a vulnerabilità bassa o moderata, mentre, le colture energetiche erbacee perenni, come il panico, potrebbero essere coltivate anche nelle aree a vulnerabilità alta, rappresentando cosi una opportunità per aumentare la sostenibilità di uso del suolo rurale. Lo strumento LCA-GIS inoltre, integrato con mappe di uso attuale del suolo, può aiutare a valutarne il suo grado di sostenibilità ambientale.

Methods for Clearance Influence Analysis in Planar and Spatial Mechanisms

This doctoral dissertation presents a new method to asses the influence of clearancein the kinematic pairs on the configuration of planar and spatial mechanisms. The subject has been widely investigated in both past and present scientific literature, and is approached in different ways: a static/kinetostatic way, which looks for the clearance take-up due to the external loads on the mechanism; a probabilistic way, which expresses clearance-due displacements using probability density functions; a dynamic way, which evaluates dynamic effects like the actual forces in the pairs caused by impacts, or the consequent vibrations. This dissertation presents a new method to approach the problem of clearance. The problem is studied from a purely kinematic perspective. With reference to a given mechanism configuration, the pose (position and orientation) error of the mechanism link of interest is expressed as a vector function of the degrees of freedom introduced in each pair by clearance: the presence of clearance in a kinematic pair, in facts, causes the actual pair to have more degrees of freedom than the theoretical clearance-free one. The clearance-due degrees of freedom are bounded by the pair geometry. A proper modelling of clearance-affected pairs allows expressing such bounding through analytical functions. It is then possible to study the problem as a maximization problem, where a continuous function (the pose error of the link of interest) subject to some constraints (the analytical functions bounding clearance- due degrees of freedom) has to be maximize. Revolute, prismatic, cylindrical, and spherical clearance-affected pairs have been analytically modelled; with reference to mechanisms involving such pairs, the solution to the maximization problem has been obtained in a closed form.

Methods for the estimation of the cortical activity and connectivity during cognitive tasks in humans

The research activity characterizing the present thesis was mainly centered on the design, development and validation of methodologies for the estimation of stationary and time-varying connectivity between different regions of the human brain during specific complex cognitive tasks. Such activity involved two main aspects: i) the development of a stable, consistent and reproducible procedure for functional connectivity estimation with a high impact on neuroscience field and ii) its application to real data from healthy volunteers eliciting specific cognitive processes (attention and memory). In particular the methodological issues addressed in the present thesis consisted in finding out an approach to be applied in neuroscience field able to: i) include all the cerebral sources in connectivity estimation process; ii) to accurately describe the temporal evolution of connectivity networks; iii) to assess the significance of connectivity patterns; iv) to consistently describe relevant properties of brain networks. The advancement provided in this thesis allowed finding out quantifiable descriptors of cognitive processes during a high resolution EEG experiment involving subjects performing complex cognitive tasks.

Machine-learning methods for structure prediction of β-barrel membrane proteins

Different types of proteins exist with diverse functions that are essential for living organisms. An important class of proteins is represented by transmembrane proteins which are specifically designed to be inserted into biological membranes and devised to perform very important functions in the cell such as cell communication and active transport across the membrane. Transmembrane β-barrels (TMBBs) are a sub-class of membrane proteins largely under-represented in structure databases because of the extreme difficulty in experimental structure determination. For this reason, computational tools that are able to predict the structure of TMBBs are needed. In this thesis, two computational problems related to TMBBs were addressed: the detection of TMBBs in large datasets of proteins and the prediction of the topology of TMBB proteins. Firstly, a method for TMBB detection was presented based on a novel neural network framework for variable-length sequence classification. The proposed approach was validated on a non-redundant dataset of proteins. Furthermore, we carried-out genome-wide detection using the entire Escherichia coli proteome. In both experiments, the method significantly outperformed other existing state-of-the-art approaches, reaching very high PPV (92%) and MCC (0.82). Secondly, a method was also introduced for TMBB topology prediction. The proposed approach is based on grammatical modelling and probabilistic discriminative models for sequence data labeling. The method was evaluated using a newly generated dataset of 38 TMBB proteins obtained from high-resolution data in the PDB. Results have shown that the model is able to correctly predict topologies of 25 out of 38 protein chains in the dataset. When tested on previously released datasets, the performances of the proposed approach were measured as comparable or superior to the current state-of-the-art of TMBB topology prediction.

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Techniques and Methods for a multi-scale analysis of neuromuscular fatigue

This thesis proposes an integrated holistic approach to the study of neuromuscular fatigue in order to encompass all the causes and all the consequences underlying the phenomenon. Starting from the metabolic processes occurring at the cellular level, the reader is guided toward the physiological changes at the motorneuron and motor unit level and from this to the more general biomechanical alterations. In Chapter 1 a list of the various definitions for fatigue spanning several contexts has been reported. In Chapter 2, the electrophysiological changes in terms of motor unit behavior and descending neural drive to the muscle have been studied extensively as well as the biomechanical adaptations induced. In Chapter 3 a study based on the observation of temporal features extracted from sEMG signals has been reported leading to the need of a more robust and reliable indicator during fatiguing tasks. Therefore, in Chapter 4, a novel bi-dimensional parameter is proposed. The study on sEMG-based indicators opened a scenario also on neurophysiological mechanisms underlying fatigue. For this purpose, in Chapter 5, a protocol designed for the analysis of motor unit-related parameters during prolonged fatiguing contractions is presented. In particular, two methodologies have been applied to multichannel sEMG recordings of isometric contractions of the Tibialis Anterior muscle: the state-of-the-art technique for sEMG decomposition and a coherence analysis on MU spike trains. The importance of a multi-scale approach has been finally highlighted in the context of the evaluation of cycling performance, where fatigue is one of the limiting factors. In particular, the last chapter of this thesis can be considered as a paradigm: physiological, metabolic, environmental, psychological and biomechanical factors influence the performance of a cyclist and only when all of these are kept together in a novel integrative way it is possible to derive a clear model and make correct assessments.

Simulation Guided Navigation in cranio-maxillo-facial surgery: a new approach to improve intraoperative three-dimensional accuracy and reproducibility during surgery.

The aim of this PhD thesis " Simulation Guided Navigation in cranio- maxillo- facial surgery : a new approach to Improve intraoperative three-dimensional accuracy and reproducibility during surgery ." was at the center of its attention the various applications of a method introduced by our School in 2010 and has as its theme the increase of interest of reproducibility of surgical programs through methods that in whole or in part are using intraoperative navigation. It was introduced in Orthognathic Surgery Validation a new method for the interventions carried out according to the method Simulation Guided Navigation in facial deformities ; was then analyzed the method of three-dimensional control of the osteotomies through the use of templates and cutting of plates using the method precontoured CAD -CAM and laser sintering . It was finally proceeded to introduce the method of piezonavigated surgery in the various branches of maxillofacial surgery . These studies have been subjected to validation processes and the results are presented .

Decomposition Methods and Network Design Problems

Decomposition based approaches are recalled from primal and dual point of view. The possibility of building partially disaggregated reduced master problems is investigated. This extends the idea of aggregated-versus-disaggregated formulation to a gradual choice of alternative level of aggregation. Partial aggregation is applied to the linear multicommodity minimum cost flow problem. The possibility of having only partially aggregated bundles opens a wide range of alternatives with different trade-offs between the number of iterations and the required computation for solving it. This trade-off is explored for several sets of instances and the results are compared with the ones obtained by directly solving the natural node-arc formulation. An iterative solution process to the route assignment problem is proposed, based on the well-known Frank Wolfe algorithm. In order to provide a first feasible solution to the Frank Wolfe algorithm, a linear multicommodity min-cost flow problem is solved to optimality by using the decomposition techniques mentioned above. Solutions of this problem are useful for network orientation and design, especially in relation with public transportation systems as the Personal Rapid Transit. A single-commodity robust network design problem is addressed. In this, an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. A set of new instances that are computationally hard for the natural flow formulation are solved by means of a new heuristic algorithm. Finally, an efficient decomposition-based heuristic approach for a large scale stochastic unit commitment problem is presented. The addressed real-world stochastic problem employs at its core a deterministic unit commitment planning model developed by the California Independent System Operator (ISO).

Bioconjugation and synthetic approach towards enantioenriched gem-difluoromethylene compounds through carbenium ions

Bioconjugation of peptides and asymmetric synthesis of gem-difluoromethylene compounds are areas of the modern organic chemistry for which mild and selective methods continue to be developed. This thesis reports new methodologies for these two areas based on the use of stabilized carbenium ions. The reaction that makes the bioconjugation of peptides possible takes place via the direct nucleophilic substitution of alcohols and is driven by the spontaneous formation of stabilized carbenium ions in water. By reacting with the thiol group of cysteine in very mild conditions and with a high selectivity, these carbenium ions allow the site-specific ligation of polypeptides containing cysteine and their covalent derivatization with functionalized probes. The ligation of the indole ring of tryptophan, an emerging target in bioconjugation, is also shown and takes place in the same conditions. The second area investigated is the challenging access to optically active gem-difluoromethylene compounds. We describe a methodology relying on the synthesis of enantioenriched 1,3-benzodithioles intermediates that are shown to be precursors of the corresponding gem-difluoromethylene analogues by oxidative desulfurization-fluorination. This synthesis takes advantage of the highly enantioselective organocatalytic α-alkylation of aldehydes with the benzodithiolylium ion and of the wide possibilities of synthetic transformations offered by the 1,3-benzodithiole group. This approach allows the asymmetric access to complex gem-difluoromethylene compounds through a late-stage fluorination step, thus avoiding the use of fluorinated building blocks.

On the car sequencing problem: analysis and solution methods

This work deals with the car sequencing (CS) problem, a combinatorial optimization problem for sequencing mixed-model assembly lines. The aim is to find a production sequence for different variants of a common base product, such that work overload of the respective line operators is avoided or minimized. The variants are distinguished by certain options (e.g., sun roof yes/no) and, therefore, require different processing times at the stations of the line. CS introduces a so-called sequencing rule H:N for each option, which restricts the occurrence of this option to at most H in any N consecutive variants. It seeks for a sequence that leads to no or a minimum number of sequencing rule violations. In this work, CS’ suitability for workload-oriented sequencing is analyzed. Therefore, its solution quality is compared in experiments to the related mixed-model sequencing problem. A new sequencing rule generation approach as well as a new lower bound for the problem are presented. Different exact and heuristic solution methods for CS are developed and their efficiency is shown in experiments. Furthermore, CS is adjusted and applied to a resequencing problem with pull-off tables.