Structural analysis of combinatorial optimization problem characteristics and their resolution using hybrid approaches

Many combinatorial problems coming from the real world may not have a clear and well defined structure, typically being dirtied by side constraints, or being composed of two or more sub-problems, usually not disjoint. Such problems are not suitable to be solved with pure approaches based on a single programming paradigm, because a paradigm that can effectively face a problem characteristic may behave inefficiently when facing other characteristics. In these cases, modelling the problem using different programming techniques, trying to ”take the best” from each technique, can produce solvers that largely dominate pure approaches. We demonstrate the effectiveness of hybridization and we discuss about different hybridization techniques by analyzing two classes of problems with particular structures, exploiting Constraint Programming and Integer Linear Programming solving tools and Algorithm Portfolios and Logic Based Benders Decomposition as integration and hybridization frameworks.

Combinatorial and Robust Optimisation Models and Algorithms for Railway Applications

This thesis deals with an investigation of combinatorial and robust optimisation models to solve railway problems. Railway applications represent a challenging area for operations research. In fact, most problems in this context can be modelled as combinatorial optimisation problems, in which the number of feasible solutions is finite. Yet, despite the astonishing success in the field of combinatorial optimisation, the current state of algorithmic research faces severe difficulties with highly-complex and data-intensive applications such as those dealing with optimisation issues in large-scale transportation networks. One of the main issues concerns imperfect information. The idea of Robust Optimisation, as a way to represent and handle mathematically systems with not precisely known data, dates back to 1970s. Unfortunately, none of those techniques proved to be successfully applicable in one of the most complex and largest in scale (transportation) settings: that of railway systems. Railway optimisation deals with planning and scheduling problems over several time horizons. Disturbances are inevitable and severely affect the planning process. Here we focus on two compelling aspects of planning: robust planning and online (real-time) planning.

Use of solvents and environmental friendly materials for applications in Green Chemistry

The present Thesis studies three alternative solvent groups as sustainable replacement of traditional organic solvents. Some aspects of fluorinated solvents, supercritical fluids and ionic liquids, have been analysed with a critical approach and their effective “greenness” has been evaluated from the points of view of the synthesis, the properties and the applications. In particular, the attention has been put on the environmental and human health issues, evaluating the eco-toxicity, the toxicity and the persistence, to underline that applicability and sustainability are subjects with equal importance. The “green” features of fluorous solvents and supercritical fluids are almost well-established; in particular supercritical carbon dioxide (scCO2) is probably the “greenest” solvent among the alternative solvent systems developed in the last years, enabling to combine numerous advantages both from the point of view of industrial/technological applications and eco-compatibility. In the Thesis the analysis of these two classes of alternative solvents has been mainly focused on their applicability, rather than the evaluation of their environmental impact. Specifically they have been evaluated as alternative media for non-aqueous biocatalysis. For this purpose, the hydrophobic ion pairing (HIP), which allows solubilising enzymes in apolar solvents by an ion pairing between the protein and a surfactant, has been investigated as effective enzymatic derivatisation technique to improve the catalytic activity under homogeneous conditions in non conventional media. The results showed that the complex enzyme-surfactant was much more active both in fluorous solvents and in supercritical carbon dioxide than the native form of the enzyme. Ionic liquids, especially imidazolium salts, have been proposed some years ago as “fully green” alternative solvents; however this epithet does not take into account several “brown” aspects such as their synthesis from petro-chemical starting materials, their considerable eco-toxicity, toxicity and resistance to biodegradation, and the difficulty of clearly outline applications in which ionic liquids are really more advantageous than traditional solvents. For all of these reasons in this Thesis a critical analysis of ionic liquids has been focused on three main topics: i) alternative synthesis by introducing structural moieties which could reduce the toxicity of the most known liquid salts, and by using starting materials from renewable resources; ii) on the evaluation of their environmental impact through eco-toxicological tests (Daphnia magna and Vibrio fischeri acute toxicity tests, and algal growth inhibition), toxicity tests (MTT test, AChE inhibition and LDH release tests) and fate and rate of aerobic biodegradation in soil and water; iii) and on the demonstration of their effectiveness as reaction media in organo-catalysis and as extractive solvents in the recovery of vegetable oil from terrestrial and aquatic biomass. The results about eco-toxicity tests with Daphnia magna, Vibrio fischeri and algae, and toxicity assay using cultured cell lines, clearly indicate that the difference in toxicity between alkyl and oxygenated cations relies in differences of polarity, according to the general trend of decreasing toxicity by decreasing the lipophilicity. Independently by the biological approach in fact, all the results are in agreement, showing a lower toxicity for compounds with oxygenated lateral chains than for those having purely alkyl lateral chains. These findings indicate that an appropriate choice of cation and anion structures is important not only to design the IL with improved and suitable chemico-physical properties but also to obtain safer and eco-friendly ILs. Moreover there is a clear indication that the composition of the abiotic environment has to be taken into account when the toxicity of ILs in various biological test systems is analysed, because, for example, the data reported in the Thesis indicate a significant influence of salinity variations on algal toxicity. Aerobic biodegradation of four imidazolium ionic liquids, two alkylated and two oxygenated, in soil was evaluated for the first time. Alkyl ionic liquids were shown to be biodegradable over the 6 months test period, and in contrast no significant mineralisation was observed with oxygenated derivatives. A different result was observed in the aerobic biodegradation of alkylated and oxygenated pyridinium ionic liquids in water because all the ionic liquids were almost completely degraded after 10 days, independently by the number of oxygen in the lateral chain of the cation. The synthesis of new ionic liquids by using renewable feedstock as starting materials, has been developed through the synthesis of furan-based ion pairs from furfural. The new ammonium salts were synthesised in very good yields, good purity of the products and wide versatility, combining low melting points with high decomposition temperatures and reduced viscosities. Regarding the possible applications as surfactants and biocides, furan-based salts could be a valuable alternative to benzyltributylammonium salts and benzalkonium chloride that are produced from non-renewable resources. A new procedure for the allylation of ketones and aldehydes with tetraallyltin in ionic liquids was developed. The reaction afforded high yields both in sulfonate-containing ILs and in ILs without sulfonate upon addition of a small amount of sulfonic acid. The checked reaction resulted in peculiar chemoselectivity favouring aliphatic substrates towards aromatic ketones and good stereoselectivity in the allylation of levoglucosenone. Finally ILs-based systems could be easily and successfully recycled, making the described procedure environmentally benign. The potential role of switchable polarity solvents as a green technology for the extraction of vegetable oil from terrestrial and aquatic biomass has been investigated. The extraction efficiency of terrestrial biomass rich in triacylglycerols, as soy bean flakes and sunflower seeds, was comparable to those of traditional organic solvents, being the yield of vegetable oils recovery very similar. Switchable polarity solvents as been also exploited for the first time in the extraction of hydrocarbons from the microalga Botryococcus braunii, demonstrating the efficiency of the process for the extraction of both dried microalgal biomass and directly of the aqueous growth medium. The switchable polarity solvents exhibited better extraction efficiency than conventional solvents, both with dried and liquid samples. This is an important issue considering that the harvest and the dewatering of algal biomass have a large impact on overall costs and energy balance.

Algorithms and Models For Combinatorial Optimization Problems

In this thesis we present some combinatorial optimization problems, suggest models and algorithms for their effective solution. For each problem,we give its description, followed by a short literature review, provide methods to solve it and, finally, present computational results and comparisons with previous works to show the effectiveness of the proposed approaches. The considered problems are: the Generalized Traveling Salesman Problem (GTSP), the Bin Packing Problem with Conflicts(BPPC) and the Fair Layout Problem (FLOP).

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

Abiotic and prebiotic phosphorus chemistry

The chief obstacle to understand the metabolic origin of life or RNA-based life is to identify a plausible mechanism for overcoming the clutter wrought by abiotic chemistry. Probably trough simple abiotic and then prebiotic reactions we could arrive to simple pre-RNA molecules. Here we report a possible preibiotic synthesis for heterocyclic compounds, and a self-assembling process of adenosine phosphates a constituent of RNA. In these processes we use a simple and prebiotic phosphorus cyclic compounds, as P4O10 and its derivatives. The processes are driven by the formation of hypercoordinated species that activate the processes by a factor of 106-8.

Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics

Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.

Sulfanyl Radical Addition to Alkynes: Revisiting an Old Reaction to Enter the Novel Realms of Green Chemistry, Bioconjugation, and Material Chemistry

In the last decade considerable attention has been devoted to the rewarding use of Green Chemistry in various synthetic processes and applications. Green Chemistry is of special interest in the synthesis of expensive pharmaceutical products, where suitable adoption of “green” reagents and conditions is highly desirable. Our project especially focused in a search for new green radical processes which might also find useful applications in the industry. In particular, we have explored the possible adoption of green solvents in radical Thiol-Ene and Thiol-Yne coupling reactions, which to date have been normally performed in “ordinary” organic solvents such as benzene and toluene, with the primary aim of applying those coupling reactions to the construction of biological substrates. We have additionally tuned adequate reaction conditions which might enable achievement of highly functionalised materials and/or complex bioconjugation via homo/heterosequence. Furthermore, we have performed suitable theoretical studies to gain useful chemical information concerning mechanistic implications of the use of green solvents in the radical Thiol-Yne coupling reactions.

From Folke Medicine to Medicine Chemistry: Study, Using in Vitro and Cellular Assays, of Receptors Mechanism Involved in the Activities of Natural Compounds

My Doctorate Research has been focused on the evaluation of the pharmacological activity of a natural extract of chestnut wood (ENC) towards the cardiovascular and gastrointestinal system and on the identification of the active compounds. The ENC has been shown to contain more than 10% (w/w) of phenolic compounds, of which tannins as Vescalgin and Castalgin are the more representative. ENC cardiovascular effects have been investigated in guinea pig cardiac preparations; furthermore its activity has been evalueted in guinea pig aorta strips. ENC induced transient negative chronotropic effect in isolated spontaneously beating right atria and simultaneously positive inotropic effect in left atria driven at 1 Hz. Cardiac cholinergic receptors are not involved in the negative chronotropic effect and positive inotropic effects are not related to adrenergic receptors. In vascular smooth muscle, natural extract of chestnut did not significantly change the contraction induced by potassium (80 mM) or that induced by noradrenaline (1μM). In guinea pig ileum, ENC reduced the maximum response to carbachol in a concentrationdependent manner and behaved as a reversible non competitive antagonist. In guinea pig ileum, the antispasmodic activity of ENC showed a significant antispasmodic activity against a variety of different spasmogenic agents including histamine, KCl, BaCl2. In guinea pig proximal colon, stomach and jejunum, ENC reduced the maximum response to carbachol in a concentrationdependent manner and behaved as a reversible non competitive antagonist. ENC contracted gallbladder guinea pig in a reversible and concentration-dependent manner. This effect does not involve cholinergic and cholecystokinin receptors and it is reduced by nifedipine. ENC relaxed Oddi sphincter smooth muscle. The cholecystokinetic and Oddi sphincter relaxing activities occurred also in guinea pigs fed a lithogenic diet. The cholecystokinetic occurred also in human gallbladder. The Fractionation of the extract led to the identification of the active fraction.

Chemistry of aerosol particles and fog droplets during fall-winter season in the Po Valley

Air quality represents a key issue in the so-called pollution “hot spots”: environments in which anthropogenic sources are concentrated and dispersion of pollutants is limited. One of these environments, the Po Valley, normally experiences exceedances of PM10 and PM2.5 concentration limits, especially in winter when the ventilation of the lower layers of the atmosphere is reduced. This thesis provides a highlight of the chemical properties of particulate matter and fog droplets in the Po Valley during the cold season, when fog occurrence is very frequent. Fog-particles interactions were investigated with the aim to determine their impact on the regional air quality. Size-segregated aerosol samples were collected in Bologna, urban site, and San Pietro Capofiume (SPC), rural site, during two campaigns (November 2011; February 2013) in the frame of Supersito project. The comparison between particles size-distribution and chemical composition in both sites showed the relevant contribution of the regional background and secondary processes in determining the Po Valley aerosol concentration. Occurrence of fog in November 2011 campaign in SPC allowed to investigate the role of fog formation and fog chemistry in the formation, processing and deposition of PM10. Nucleation scavenging was investigated with relation to the size and the chemical composition of particles. We found that PM1 concentration is reduced up to 60% because of fog scavenging. Furthermore, aqueous-phase secondary aerosol formation mechanisms were investigated through time-resolved measurements. In SPC fog samples have been systematically collected and analysed since the nineties; a 20 years long database has been assembled. This thesis reports for the first time the results of this long time series of measurements, showing a decrease of sulphate and nitrate concentration and an increase of pH that reached values close to neutrality. A detailed discussion about the occurred changes in fog water composition over two decades is presented.

Computational Methods in Biophysics and Medicinal Chemistry: Applications and Challenges

In this thesis I described the theory and application of several computational methods in solving medicinal chemistry and biophysical tasks. I pointed out to the valuable information which could be achieved by means of computer simulations and to the possibility to predict the outcome of traditional experiments. Nowadays, computer represents an invaluable tool for chemists. In particular, the main topics of my research consisted in the development of an automated docking protocol for the voltage-gated hERG potassium channel blockers, and the investigation of the catalytic mechanism of the human peptidyl-prolyl cis-trans isomerase Pin1.