Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.

Methods for integrating machine learning and constrained optimization

In the framework of industrial problems, the application of Constrained Optimization is known to have overall very good modeling capability and performance and stands as one of the most powerful, explored, and exploited tool to address prescriptive tasks. The number of applications is huge, ranging from logistics to transportation, packing, production, telecommunication, scheduling, and much more. The main reason behind this success is to be found in the remarkable effort put in the last decades by the OR community to develop realistic models and devise exact or approximate methods to solve the largest variety of constrained or combinatorial optimization problems, together with the spread of computational power and easily accessible OR software and resources. On the other hand, the technological advancements lead to a data wealth never seen before and increasingly push towards methods able to extract useful knowledge from them; among the data-driven methods, Machine Learning techniques appear to be one of the most promising, thanks to its successes in domains like Image Recognition, Natural Language Processes and playing games, but also the amount of research involved. The purpose of the present research is to study how Machine Learning and Constrained Optimization can be used together to achieve systems able to leverage the strengths of both methods: this would open the way to exploiting decades of research on resolution techniques for COPs and constructing models able to adapt and learn from available data. In the first part of this work, we survey the existing techniques and classify them according to the type, method, or scope of the integration; subsequently, we introduce a novel and general algorithm devised to inject knowledge into learning models through constraints, Moving Target. In the last part of the thesis, two applications stemming from real-world projects and done in collaboration with Optit will be presented.

Adjustable robust optimization with nonlinear recourses

Over the last century, mathematical optimization has become a prominent tool for decision making. Its systematic application in practical fields such as economics, logistics or defense led to the development of algorithmic methods with ever increasing efficiency. Indeed, for a variety of real-world problems, finding an optimal decision among a set of (implicitly or explicitly) predefined alternatives has become conceivable in reasonable time. In the last decades, however, the research community raised more and more attention to the role of uncertainty in the optimization process. In particular, one may question the notion of optimality, and even feasibility, when studying decision problems with unknown or imprecise input parameters. This concern is even more critical in a world becoming more and more complex —by which we intend, interconnected —where each individual variation inside a system inevitably causes other variations in the system itself. In this dissertation, we study a class of optimization problems which suffer from imprecise input data and feature a two-stage decision process, i.e., where decisions are made in a sequential order —called stages —and where unknown parameters are revealed throughout the stages. The applications of such problems are plethora in practical fields such as, e.g., facility location problems with uncertain demands, transportation problems with uncertain costs or scheduling under uncertain processing times. The uncertainty is dealt with a robust optimization (RO) viewpoint (also known as "worst-case perspective") and we present original contributions to the RO literature on both the theoretical and practical side.

Ottimizzazione delle reti di distribuzione idrica tramite algoritmi genetici multi-obiettivo

Water distribution networks optimization is a challenging problem due to the dimension and the complexity of these systems. Since the last half of the twentieth century this field has been investigated by many authors. Recently, to overcome discrete nature of variables and non linearity of equations, the research has been focused on the development of heuristic algorithms. This algorithms do not require continuity and linearity of the problem functions because they are linked to an external hydraulic simulator that solve equations of mass continuity and of energy conservation of the network. In this work, a NSGA-II (Non-dominating Sorting Genetic Algorithm) has been used. This is a heuristic multi-objective genetic algorithm based on the analogy of evolution in nature. Starting from an initial random set of solutions, called population, it evolves them towards a front of solutions that minimize, separately and contemporaneously, all the objectives. This can be very useful in practical problems where multiple and discordant goals are common. Usually, one of the main drawback of these algorithms is related to time consuming: being a stochastic research, a lot of solutions must be analized before good ones are found. Results of this thesis about the classical optimal design problem shows that is possible to improve results modifying the mathematical definition of objective functions and the survival criterion, inserting good solutions created by a Cellular Automata and using rules created by classifier algorithm (C4.5). This part has been tested using the version of NSGA-II supplied by Centre for Water Systems (University of Exeter, UK) in MATLAB® environment. Even if orientating the research can constrain the algorithm with the risk of not finding the optimal set of solutions, it can greatly improve the results. Subsequently, thanks to CINECA help, a version of NSGA-II has been implemented in C language and parallelized: results about the global parallelization show the speed up, while results about the island parallelization show that communication among islands can improve the optimization. Finally, some tests about the optimization of pump scheduling have been carried out. In this case, good results are found for a small network, while the solutions of a big problem are affected by the lack of constraints on the number of pump switches. Possible future research is about the insertion of further constraints and the evolution guide. In the end, the optimization of water distribution systems is still far from a definitive solution, but the improvement in this field can be very useful in reducing the solutions cost of practical problems, where the high number of variables makes their management very difficult from human point of view.

Profilo psicopatologico e qualità della vita in bambini e adolescenti narcolettici: studio caso-controllo

Scopo del nostro lavoro è stato descrivere ed inquadrare gli aspetti psico-comportamentali e la qualità di vita della narcolessia in età evolutiva. Metodi: Abbiamo pertanto disegnato uno studio caso-controllo comprendente 30 pazienti narcolettici, 39 epilettici, e 39 controlli sani, appaiati per sesso e età. Risultati: La nostra popolazione di bambini e adolescenti affetti da narcolessia mostra un aumento delle problematiche internalizzanti. I due gruppi patologici hanno in comune punteggi più elevati rispetto ai controlli per i disturbi d’ansia, le difficoltà attentive e di socializzazione, i disturbi oppositivo-provocatori. Ciò che distingue, invece, i pazienti narcolettici, sono gli aspetti di ritiro e depressione, la tendenza alla somatizzazione, i problemi del pensiero ed i disturbi affettivi. Fattori di rischio psicopatologici per i giovani narcolettici sono risultati essere l’esordio precoce, il ritardo diagnostico, il sonno notturno disturbato, la minor latenza di sonno all’addormentamento, un maggior numero di SOREMP all’MSLT. Dall’altro lato la terapia farmacologica, un maggior numero di sonnellini spontanei e la durata di malattia, sembrano influenzare positivamente l’evoluzione comportamentale. La salute psicosociale dei giovani narcolettici, inoltre, risulta essere peggiore rispetto ai controlli sani, mentre la salute fisica non mostra differenze. I problemi internalizzanti influenzano negativamente tutti gli ambiti della salute di questi ragazzi, mentre la durata di malattia sembra migliorare il funzionamento scolastico. Conclusioni: Il nostro lavoro conferma che i giovani narcolettici presentano un maggior rischio psicopatologico sia rispetto ai controlli sani sia rispetto un’altra patologia neurologica cronica. Se da un lato alcuni aspetti comportamentali possono essere giustificati come una reazione adattativa verso una patologia neurologica invalidante, dall’altro un quadro distimico caratterizzato da ritiro e lamentele somatiche, sembra essere tipico dei bambini ed adolescenti narcolettici.

Networks, Uncertainty, Applications and a Crusade for Optimality

In this thesis we address a collection of Network Design problems which are strongly motivated by applications from Telecommunications, Logistics and Bioinformatics. In most cases we justify the need of taking into account uncertainty in some of the problem parameters, and different Robust optimization models are used to hedge against it. Mixed integer linear programming formulations along with sophisticated algorithmic frameworks are designed, implemented and rigorously assessed for the majority of the studied problems. The obtained results yield the following observations: (i) relevant real problems can be effectively represented as (discrete) optimization problems within the framework of network design; (ii) uncertainty can be appropriately incorporated into the decision process if a suitable robust optimization model is considered; (iii) optimal, or nearly optimal, solutions can be obtained for large instances if a tailored algorithm, that exploits the structure of the problem, is designed; (iv) a systematic and rigorous experimental analysis allows to understand both, the characteristics of the obtained (robust) solutions and the behavior of the proposed algorithm.

La traduzione e ricezione della letteratura cinese in Italia: questioni e strategie a partire dal caso delle traduzioni di alcuni romanzi di Su Tong, Yu Hua, Zhang Jie e Mo Yan

Negli ultimi anni, in Italia sono stati tradotti un gran numero di opere letterarie cinesi grazie all’impegno e alla passione di numerosi sinologi, studiosi e traduttori italiani. Tuttavia, gli studi sulla traduzione della letteratura cinese sono, sia in Cina che in Italia, relativamente pochi e non sempre uniformi: in Cina è difficile trovare dati completi, sistematici e dotati di un certo valore di riferimento, e in Italia, una ricerca di questo tipo ha avuto origine nell’ambito degli studi sinologici italiani, piuttosto che in quello degli studi sulla traduzione. A partire da una rassegna dei principali approcci agli studi sulla traduzione (letteraria) dalla seconda metà del XX secolo fino ai nostri giorni, questo lavoro di tesi tenta di analizzare da un lato le tendenze generali relative alla traduzione e alla pubblicazione delle opere letterarie cinesi in Italia in un arco temporale che va dal 1942 al 2018, tramite alcune analisi di tipo sia quantitativo che qualitativo basate su una tabella di dati concernenti la letteratura cinese sul mercato editoriale italiano che è stata costruita appositamente; dall’altro, questa ricerca intende investigare le strategie utilizzate per tradurre i diversi riferimenti culturali riscontrati nel corpus di testi scelti e che sono stati suddivisi nelle seguenti categorie: antroponimi, intertestualità, riferimenti al contesto politico e culturale, gastronomia e altri riferimenti culturali. Attraverso un’analisi comparativa e descrittiva dei testi di partenza e dei testi di arrivo, ai fini della tesi si sono indagate le problematiche riguardanti la traduzione e la ricezione della letteratura cinese in Italia e le tendenze che tale letteratura ha avuto sia in ambito editoriale che nel campo della traduzione letteraria.

Colocated multiple-input multiple-output radars for smart mobility

In recent years, radars have been used in many applications such as precision agriculture and advanced driver assistant systems. Optimal techniques for the estimation of the number of targets and of their coordinates require solving multidimensional optimization problems entailing huge computational efforts. This has motivated the development of sub-optimal estimation techniques able to achieve good accuracy at a manageable computational cost. Another technical issue in advanced driver assistant systems is the tracking of multiple targets. Even if various filtering techniques have been developed, new efficient and robust algorithms for target tracking can be devised exploiting a probabilistic approach, based on the use of the factor graph and the sum-product algorithm. The two contributions provided by this dissertation are the investigation of the filtering and smoothing problems from a factor graph perspective and the development of efficient algorithms for two and three-dimensional radar imaging. Concerning the first contribution, a new factor graph for filtering is derived and the sum-product rule is applied to this graphical model; this allows to interpret known algorithms and to develop new filtering techniques. Then, a general method, based on graphical modelling, is proposed to derive filtering algorithms that involve a network of interconnected Bayesian filters. Finally, the proposed graphical approach is exploited to devise a new smoothing algorithm. Numerical results for dynamic systems evidence that our algorithms can achieve a better complexity-accuracy tradeoff and tracking capability than other techniques in the literature. Regarding radar imaging, various algorithms are developed for frequency modulated continuous wave radars; these algorithms rely on novel and efficient methods for the detection and estimation of multiple superimposed tones in noise. The accuracy achieved in the presence of multiple closely spaced targets is assessed on the basis of both synthetically generated data and of the measurements acquired through two commercial multiple-input multiple-output radars.

Trajectory planning of single and dual-arm robots for time-optimal handling of liquids and objects

This Thesis studies the optimal control problem of single-arm and dual-arm serial robots to achieve the time-optimal handling of liquids and objects. The first topic deals with the planning of time-optimal anti-sloshing trajectories of an industrial robot carrying a cylindrical container filled with a liquid, considering 1-dimensional and 2-dimensional planar motions. A technique for the estimation of the sloshing height is presented, together with its extension to 3-dimensional motions. An experimental validation campaign is provided and discussed to assess the thoroughness of such a technique. As far as anti-sloshing trajectories are concerned, 2-dimensional paths are considered and, for each one of them, three constrained optimizations with different values of the sloshing-height thresholds are solved. Experimental results are presented to compare optimized and non-optimized motions. The second part focuses on the time-optimal trajectory planning for dual-arm object handling, employing two collaborative robots (cobots) and adopting an admittance-control strategy. The chosen manipulation approach, known as cooperative grasping, is based on unilateral contact between the cobots and the object, and it may lead to slipping during motion if an internal prestress along the contact-normal direction is not prescribed. Thus, a virtual penetration is considered, aimed at generating the necessary internal prestress. The stability of cooperative grasping is ensured as long as the exerted forces on the object remain inside the static-friction cone. Constrained-optimization problems are solved for 3-dimensional paths: the virtual penetration is chosen among the control inputs of the problem and friction-cone conditions are treated as inequality constraints. Also in this case experiments are presented in order to prove evidence of the firm handling of the object, even for fast motions.

Analysis and developments of uncertainty processors for real time flood forecasting

The hydrologic risk (and the hydro-geologic one, closely related to it) is, and has always been, a very relevant issue, due to the severe consequences that may be provoked by a flooding or by waters in general in terms of human and economic losses. Floods are natural phenomena, often catastrophic, and cannot be avoided, but their damages can be reduced if they are predicted sufficiently in advance. For this reason, the flood forecasting plays an essential role in the hydro-geological and hydrological risk prevention. Thanks to the development of sophisticated meteorological, hydrologic and hydraulic models, in recent decades the flood forecasting has made a significant progress, nonetheless, models are imperfect, which means that we are still left with a residual uncertainty on what will actually happen. In this thesis, this type of uncertainty is what will be discussed and analyzed. In operational problems, it is possible to affirm that the ultimate aim of forecasting systems is not to reproduce the river behavior, but this is only a means through which reducing the uncertainty associated to what will happen as a consequence of a precipitation event. In other words, the main objective is to assess whether or not preventive interventions should be adopted and which operational strategy may represent the best option. The main problem for a decision maker is to interpret model results and translate them into an effective intervention strategy. To make this possible, it is necessary to clearly define what is meant by uncertainty, since in the literature confusion is often made on this issue. Therefore, the first objective of this thesis is to clarify this concept, starting with a key question: should be the choice of the intervention strategy to adopt based on the evaluation of the model prediction based on its ability to represent the reality or on the evaluation of what actually will happen on the basis of the information given by the model forecast? Once the previous idea is made unambiguous, the other main concern of this work is to develope a tool that can provide an effective decision support, making possible doing objective and realistic risk evaluations. In particular, such tool should be able to provide an uncertainty assessment as accurate as possible. This means primarily three things: it must be able to correctly combine all the available deterministic forecasts, it must assess the probability distribution of the predicted quantity and it must quantify the flooding probability. Furthermore, given that the time to implement prevention strategies is often limited, the flooding probability will have to be linked to the time of occurrence. For this reason, it is necessary to quantify the flooding probability within a horizon time related to that required to implement the intervention strategy and it is also necessary to assess the probability of the flooding time.

Adipose-derived stem cells and tissue revascularization: enhancing islet survival and performance for diabetes care.

Pancreatic islet transplantation represents a fascinating procedure that, at the moment, can be considered as alternative to standard insulin treatment or pancreas transplantation only for selected categories of patients with type 1 diabetes mellitus. Among the factors responsible for leading to poor islet engraftment, hypoxia plays an important role. Mesenchymal stem cells (MSCs) were recently used in animal models of islet transplantation not only to reduce allograft rejection, but also to promote revascularization. Currently adipose tissue represents a novel and good source of MSCs. Moreover, the capability of adipose-derived stem cells (ASCs) to improve islet graft revascularization was recently reported after hybrid transplantation in mice. Within this context, we have previously shown that hyaluronan esters of butyric and retinoic acids can significantly enhance the rescuing potential of human MSCs. Here we evaluated whether ex vivo preconditioning of human ASCs (hASCs) with a mixture of hyaluronic (HA), butyric (BU), and retinoic (RA) acids may result in optimization of graft revascularization after islet/stem cell intrahepatic cotransplantation in syngeneic diabetic rats. We demonstrated that hASCs exposed to the mixture of molecules are able to increase the secretion of vascular endothelial growth factor (VEGF), as well as the transcription of angiogenic genes, including VEGF, KDR (kinase insert domain receptor), and hepatocyte growth factor (HGF). Rats transplanted with islets cocultured with preconditioned hASCs exhibited a better glycemic control than rats transplanted with an equal volume of islets and control hASCs. Cotransplantation with preconditioned hASCs was also associated with enhanced islet revascularization in vivo, as highlighted by graft morphological analysis. The observed increase in islet graft revascularization and function suggests that our method of stem cell preconditioning may represent a novel strategy to remarkably improve the efficacy of islets-hMSCs cotransplantation.

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.