Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Unsupervised reinforcement learning via state entropy maximization

Reinforcement Learning (RL) provides a powerful framework to address sequential decision-making problems in which the transition dynamics is unknown or too complex to be represented. The RL approach is based on speculating what is the best decision to make given sample estimates obtained from previous interactions, a recipe that led to several breakthroughs in various domains, ranging from game playing to robotics. Despite their success, current RL methods hardly generalize from one task to another, and achieving the kind of generalization obtained through unsupervised pre-training in non-sequential problems seems unthinkable. Unsupervised RL has recently emerged as a way to improve generalization of RL methods. Just as its non-sequential counterpart, the unsupervised RL framework comprises two phases: An unsupervised pre-training phase, in which the agent interacts with the environment without external feedback, and a supervised fine-tuning phase, in which the agent aims to efficiently solve a task in the same environment by exploiting the knowledge acquired during pre-training. In this thesis, we study unsupervised RL via state entropy maximization, in which the agent makes use of the unsupervised interactions to pre-train a policy that maximizes the entropy of its induced state distribution. First, we provide a theoretical characterization of the learning problem by considering a convex RL formulation that subsumes state entropy maximization. Our analysis shows that maximizing the state entropy in finite trials is inherently harder than RL. Then, we study the state entropy maximization problem from an optimization perspective. Especially, we show that the primal formulation of the corresponding optimization problem can be (approximately) addressed through tractable linear programs. Finally, we provide the first practical methodologies for state entropy maximization in complex domains, both when the pre-training takes place in a single environment as well as multiple environments.

Synthesis, multiscale-multiphase characterization and applications of thiophene-based biohybrids

Biohybrid derivatives of π-conjugated materials are emerging as powerful tools to study biological events through the (opto)electronic variations of the π-conjugated moieties, as well as to direct and govern the self-assembly properties of the organic materials through the organization principles of the bio component. So far, very few examples of thiophene-based biohybrids have been reported. The aim of this Ph. D thesis has been the development of oligothiophene-oligonucleotide hybrid derivatives as tools, on one side, to detect DNA hybridisation events and, on the other, as model compounds to investigate thiophene-nucleobase interactions in the solid state. To obtain oligothiophene bioconjugates with the required high level of purity, we first developed new synthetic ecofriendly protocols for the synthesis of thiophene oligomers. Our innovative heterogeneous Suzuki coupling methodology, carried out in EtOH/water or isopropanol under microwave irradiation, allowed us to obtain alkyl substituted oligothiophenes and thiophene based co-oligomers in high yields and very short reaction times, free from residual metals and with improved film forming properties. These methodologies were subsequently applied in the synthesis of oligothiophene-oligonucleotide conjugates. Oligothiophene-5-labeled deoxyuridines were synthesized and incorporated into 19-meric oligonucletide sequences. We showed that the oligothiophene-labeled oligonucletide sequences obtained can be used as probes to detect a single nucleotide polymorphism (SNP) in complementary DNA target sequences. In fact, all the probes showed marked variations in emission intensity upon hybridization with a complementary target sequence. The observed variations in emitted light were comparable or even superior to those reported in similar studies, showing that the biohybrids can potentially be useful to develop biosensors for the detection of DNA mismatches. Finally, water-soluble, photoluminescent and electroactive dinucleotide-hybrid derivatives of quaterthiophene and quinquethiophene were synthesized. By means of a combination of spectroscopy and microscopy techniques, electrical characterizations, microfluidic measurements and theoretical calculations, we were able to demonstrate that the self-assembly modalities of the biohybrids in thin films are driven by the interplay of intra and intermolecular interactions in which the π-stacking between the oligothiophene and nucleotide bases plays a major role.

Stochastic models and dynamic measures for the characterization of bistable circuits

During the last few years, a great deal of interest has risen concerning the applications of stochastic methods to several biochemical and biological phenomena. Phenomena like gene expression, cellular memory, bet-hedging strategy in bacterial growth and many others, cannot be described by continuous stochastic models due to their intrinsic discreteness and randomness. In this thesis I have used the Chemical Master Equation (CME) technique to modelize some feedback cycles and analyzing their properties, including experimental data. In the first part of this work, the effect of stochastic stability is discussed on a toy model of the genetic switch that triggers the cellular division, which malfunctioning is known to be one of the hallmarks of cancer. The second system I have worked on is the so-called futile cycle, a closed cycle of two enzymatic reactions that adds and removes a chemical compound, called phosphate group, to a specific substrate. I have thus investigated how adding noise to the enzyme (that is usually in the order of few hundred molecules) modifies the probability of observing a specific number of phosphorylated substrate molecules, and confirmed theoretical predictions with numerical simulations. In the third part the results of the study of a chain of multiple phosphorylation-dephosphorylation cycles will be presented. We will discuss an approximation method for the exact solution in the bidimensional case and the relationship that this method has with the thermodynamic properties of the system, which is an open system far from equilibrium.In the last section the agreement between the theoretical prediction of the total protein quantity in a mouse cells population and the observed quantity will be shown, measured via fluorescence microscopy.

Electrosynthesis and characterization of structured catalysts

In this research work the optimization of the electrochemical system of LDHs as catalytic precursors on FeCrAlY foams was carried out. Preliminary sintheses were performed on flat surfaces in order to easily characterize the deposited material. From the study of pH evolution vs time at different cathodic potentials applied to a Pt electrode, the theoretical best working conditions for the synthesis of single hydroxides and LDH compounds was achieved. In order to define the optimal potential for the synthesis of a particular LDH compound, the collected data were compared with the interval of precipitation determined by titration with NaOH. However, the characterization of the deposited material on Pt surfaces did not confirm the deposition of a pure and homogeneous LDH phase during the synthesis. Instead a sequential deposition linked to the pH of precipitation of the involved elements is observed. The same behavior was observed during the synthesis of the RhMgAl LDH on FeCrAlY foam as catalytic precursor. Several parameters were considered in order to optimize the synthesis.. The development of electrochemical cells with different feature, such as the counter electrode dimensions or the contact between the foam and the potentiostat, had been carried out in order to obtain a better coating of the foam. The influence of the initial pH of the electrolyte solution, of the applied potential, of the composition of the electrolytic solution were investigated in order to improve a better coating of the catalyst support. Catalytic tests were performed after the calcination of the deposited foam for the CPO and SR reactions, showing an improve of performances along with optimization of the precursors synthesis conditions.

Design, Synthesis and Characterization of N-Containing Organic Compounds

The needed of new intermediates/products for screening in the fields of drug discovery and material science is the driving force behind the development of new methodologies and technologies. Organic scaffolds are privileged targets for this scouting. Among them a priority place must be attributed to those including nitrogen functionalities in their scaffolds. It comes out that new methodologies, allowing the introduction of the nitrogen atom for the synthesis of an established target or for the curiosity driven researches, will always be welcome. The target of this PhD Thesis’ work is framed within this goal. Accordingly, Chapter 1 reports the preparation of new N-Heteroarylmethyl 3-carboxy-5-hydroxy piperidine scaffold, as potential and selective α-glucosidase inhibitors. The proposed reversible uncompetitive mechanism of inhibition makes them attractive as interesting candidate for drug development. Chapter 2 is more environmentally method-driven research. Eco-friendly studies on the synthesis of enantiomerically pure 1,4-dihydropyridines using “solid” ammonia (magnesium nitride) is reported via classical Hantzch method. Chapter 3 and Chapter 4 may be targeted as the core of the Thesis’s research work. Chapter 3 reports the studies addressed to the synthesis of N-containing heterocycles by using N-trialkylsilylimine/hetero-Diels–Alder (HAD) approach. New eco-friendly methodology as MAOS (Microwave Assisted Organic Synthesis) has been used as witness of our interest to a sustainable chemistry. Theoretical calculations were adopted to fully clarify the reaction mechanism. Chapter 4 is dedicated to picture the most recent studies performed on the application of N-Metallo-ketene imines (metallo= Si, Sn, Al), relatively new intermediates which are becoming very popular, in the preparation of highly functionalized N-containing derivatives, accordingly to the Thesis’ target. Derivatives obtained are designed in such a way that they could be of interest in the field of drug and new material chemistry.

Characterization of fold-related fractures in the carbonate rocks of the Cingoli anticline, northern Apennines, Italy

Thrust fault-related folds in carbonate rocks are characterized by deformation accommodated by different structures, such as joints, faults, pressure solution seams, and deformation bands. Defining the development of fracture systems related to the folding process is significant both for theoretical and practical purposes. Fracture systems are useful constrains in order to understand the kinematical evolution of the fold. Furthermore, understanding the relationships between folding and fracturing provides a noteworthy contribution for reconstructing the geodynamic and the structural evolution of the studied area. Moreover, as fold-related fractures influence fluid flow through rocks, fracture systems are relevant for energy production (geothermal studies, methane and CO2 , storage and hydrocarbon exploration), environmental and social issues (pollutant distribution, aquifer characterization). The PhD project shows results of a study carried out in a multilayer carbonate anticline characterized by different mechanical properties. The aim of this study is to understand the factors which influence the fracture formation and to define their temporal sequence during the folding process. The studied are is located in the Cingoli anticline (Northern Apennines), which is characterized by a pelagic multilayer characterized by sequences with different mechanical stratigraphies. A multi-scale analysis has been made in several outcrops located in different structural positions. This project shows that the conceptual sketches proposed in literature and the strain distribution models outline well the geometrical orientation of most of the set of fractures observed in the Cingoli anticline. On the other hand, the present work suggests the relevance of the mechanical stratigraphy in particular controlling the type of fractures formed (e.g. pressure solution seams, joints or shear fractures) and their subsequent evolution. Through a multi-scale analysis, and on the basis of the temporal relationship between fracture sets and their orientation respect layering, I also suggest a conceptual model for fracture systems formation.

Development and characterization of micromachined devices for separation techniques

Nowadays microfluidic is becoming an important technology in many chemical and biological processes and analysis applications. The potential to replace large-scale conventional laboratory instrumentation with miniaturized and self-contained systems, (called lab-on-a-chip (LOC) or point-of-care-testing (POCT)), offers a variety of advantages such as low reagent consumption, faster analysis speeds, and the capability of operating in a massively parallel scale in order to achieve high-throughput. Micro-electro-mechanical-systems (MEMS) technologies enable both the fabrication of miniaturized system and the possibility of developing compact and portable systems. The work described in this dissertation is towards the development of micromachined separation devices for both high-speed gas chromatography (HSGC) and gravitational field-flow fractionation (GrFFF) using MEMS technologies. Concerning the HSGC, a complete platform of three MEMS-based GC core components (injector, separation column and detector) is designed, fabricated and characterized. The microinjector consists of a set of pneumatically driven microvalves, based on a polymeric actuating membrane. Experimental results demonstrate that the microinjector is able to guarantee low dead volumes, fast actuation time, a wide operating temperature range and high chemical inertness. The microcolumn consists of an all-silicon microcolumn having a nearly circular cross-section channel. The extensive characterization has produced separation performances very close to the theoretical ideal expectations. A thermal conductivity detector (TCD) is chosen as most proper detector to be miniaturized since the volume reduction of the detector chamber results in increased mass and reduced dead volumes. The microTDC shows a good sensitivity and a very wide dynamic range. Finally a feasibility study for miniaturizing a channel suited for GrFFF is performed. The proposed GrFFF microchannel is at early stage of development, but represents a first step for the realization of a highly portable and potentially low-cost POCT device for biomedical applications.

Design and experimental characterization of antennas and wireless systems for innovative wearable and implantable ultra low–power applications

The present PhD thesis exploits the design skills I have been improving since my master thesis’ research. A brief description of the chapters’ content follows. Chapter 1: the simulation of a complete front–end is a very complex problem and, in particular, is the basis upon which the prediction of the overall performance of the system is possible. By means of a commercial EM simulation tool and a rigorous nonlinear/EM circuit co–simulation based on the Reciprocity Theorem, the above–mentioned prediction can be achieved and exploited for wireless links characterization. This will represent the theoretical basics of the entire present thesis and will be supported by two RF applications. Chapter 2: an extensive dissertation about Magneto–Dielectric (MD) materials will be presented, together with their peculiar characteristics as substrates for antenna miniaturization purposes. A designed and tested device for RF on–body applications will be described in detail. Finally, future research will be discussed. Chapter 3: this chapter will deal with the issue regarding the exploitation of renewable energy sources for low–energy consumption devices. Hence the problem related to the so–called energy harvesting will be tackled and a first attempt to deploy THz solar energy in an innovative way will be presented and discussed. Future research will be proposed as well. Chapter 4: graphene is a very promising material for devices to be exploited in the RF and THz frequency range for a wide range of engineering applications, including those ones marked as the main research goal of the present thesis. This chapter will present the results obtained during my research period at the National Institute for Research and Development in Microtechnologies (IMT) in Bucharest, Romania. It will concern the design and manufacturing of antennas and diodes made in graphene–based technology for detection/rectification purposes.

Design and Characterization of Curved and Spherical Flexure Hinges for Planar and Spatial Compliant Mechanisms

A flexure hinge is a flexible connector that can provide a limited rotational motion between two rigid parts by means of material deformation. These connectors can be used to substitute traditional kinematic pairs (like bearing couplings) in rigid-body mechanisms. When compared to their rigid-body counterpart, flexure hinges are characterized by reduced weight, absence of backlash and friction, part-count reduction, but restricted range of motion. There are several types of flexure hinges in the literature that have been studied and characterized for different applications. In our study, we have introduced new types of flexures with curved structures i.e. circularly curved-beam flexures and spherical flexures. These flexures have been utilized for both planar applications (e.g. articulated robotic fingers) and spatial applications (e.g. spherical compliant mechanisms). We have derived closed-form compliance equations for both circularly curved-beam flexures and spherical flexures. Each element of the spatial compliance matrix is analytically computed as a function of hinge dimensions and employed material. The theoretical model is then validated by comparing analytical data with the results obtained through Finite Element Analysis. A case study is also presented for each class of flexures, concerning the potential applications in the optimal design of planar and spatial compliant mechanisms. Each case study is followed by comparing the performance of these novel flexures with the performance of commonly used geometries in terms of principle compliance factors, parasitic motions and maximum stress demands. Furthermore, we have extended our study to the design and analysis of serial and parallel compliant mechanisms, where the proposed flexures have been employed to achieve spatial motions e.g. compliant spherical joints.