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.

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.

Oxylipins biosynthesis in Lactobacillus helveticus in the presence of oxidative stress

This PhD thesis is aimed at studying the possible pathways and the mechanisms that can trigger oxylipins biosynthesis, and particularly that of short chain aldehydes and alcohols, in Lactobacillus helveticus, also in the presence of oxidative stress, using a totally labelled linoleic acid as precursor. In plants and fungi these molecules, involved in defence mechanisms against pathogens and in communication systems, derive from the oxidation of cellular unsaturated fatty acids (UFAs) and their accumulation is associated with stress exposure. Since some oxylipins are produced also by lactobacilli, it is possible to hypothesize that a metabolic pathway from UFAs to oxylipins, similar to what happens in plants and fungi, is present also in lactic acid bacteria. The results obtained pointed out that some volatile molecules are the result of UFAs catabolism, since they appear only when cells are incubated in their presence. Labelled linoleic acid is integrated in the membrane and subsequently transformed into aldehydes and alcohols, whose extent and carbon atoms number depend on stress exposure. The enzymes responsible for this metabolic pathway in plants and fungi (e.g. lipoxygenase, dioxygenase) seem to be absent in Lactobacillus helveticus and in other lactobacilli. Proteomic analyses show the over expression of many proteins, including thioredoxin reductase (part of the bacterial oxidative defence system), mainly in cells grown with linoleic acid without oxidative stress exposure, confirming that linoleic acid itself induces oxidative stress. 6 general oxidoreductases (class including dioxygenases and peroxidase) were found and therefore a deeper investigation on them could be productive in elucidating all steps involved in oxylipins biosynthesis in bacteria. Due to the multiple role of oxylipins (flavouring agents, antimicrobial compounds and interspecific signalling molecules) the identification of genes involved and regulating factors should have an important biotechnological impact, also allowing the overproduction of selected bioactive molecules.

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.

Phenotypic and molecular characterization of ethylene biosynthesis in apples

Ethylene plays an important role in apple fruit development. Its biosynthesis is catalyzed by two enzymes ACS and ACO. The first is considered to catalyzes the rate-limiting step of ethylene production and in apple two different alleles (MdACS1-1 and MdACS1-2) of this gene have been identified. The presence in the promoter region of MdACS1-2 allele of a SINE insertion is considered to be responsible for a low transcription level and a pronounced reduction in ethylene production in apple cultivar homozygous for this allele. However, the specific expression of each MdACS1 allele has never been reported as well as any in vivo analysis of its 5’-flanking region. With the present study we addressed these issues by developing a set of qPCR allele specific primers for MdACS1 and by a functional characterization of the MdACS1 promoters by transient expression analysis. qPCR analysis on different apple tissues and stages of development demonstrated that MdACS1-2 allele is never express and that MdACS1-1 allele is ripening-related and expresses predominantly but not exclusively in apple fruit. To test MdACS1 promoter in fruit the only protocol available in literature for transient transformation of apple fruit was evaluated and optimized. Twenty chimeric promoter::reporter constructs were generated and analyzed by Agrobacterium-transient transformation. The in vivo analysis allowed to identify an enhancer-like region of 261 bp in MdACS1 promoter and a region of 57 bp in MdACS1-2 responsible, also if not alone, in the inactivation of the MdACS1-2 allele. Through the assessment of ethylene production in a segregating progeny derived from the cross between Fuji and Mondial Gala (homozygous for MdACS1-2 allele) we demonstrated that at least two other genes may be involved in apple ethylene production. An hypothesis that could explain the difference between Fuji and Mondial Gala have been proposed.

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

Formulations and Metaheuristics for combinatorial optimization problems

Combinatorial optimization problems have been strongly addressed throughout history. Their study involves highly applied problems that must be solved in reasonable times. This doctoral Thesis addresses three Operations Research problems: the first deals with the Traveling Salesman Problem with Pickups and Delivery with Handling cost, which was approached with two metaheuristics based on Iterated Local Search; the results show that the proposed methods are faster and obtain good results respect to the metaheuristics from the literature. The second problem corresponds to the Quadratic Multiple Knapsack Problem, and polynomial formulations and relaxations are presented for new instances of the problem; in addition, a metaheuristic and a matheuristic are proposed that are competitive with state of the art algorithms. Finally, an Open-Pit Mining problem is approached. This problem is solved with a parallel genetic algorithm that allows excavations using truncated cones. Each of these problems was computationally tested with difficult instances from the literature, obtaining good quality results in reasonable computational times, and making significant contributions to the state of the art techniques of Operations Research.

Radical chemistry of the catechol/quinone system and its role in the control of lipid peroxidation and melanin biosynthesis

The catechol (1,2-dihydroxybenzene) is a privileged structural motif among natural antioxidants like flavonoids, owing to its reactivity with alkylperoxyl radicals due to the stability of the semiquinone radical. The exploration of the relevance and mechanism of this non-conventional antioxidant chemistry in heterogenous biomimetic systems (aqueous micelles and unilamellar liposomes) is explored for the first time in Chapter 1. Results show antioxidant behaviour that surpasses that of nature’s premiere antioxidant α-tocopherol and relies on the cross-dismutation of alkylperoxyl and hydroperoxyl radicals at the water-lipid interface with regeneration of the catechol function from the oxidized quinone. The design and synthesis of new biomimetic catechol-type antioxidants by conjugation of thiols (e.g. cysteine) with quinones highlighted an unusual 1,6-type regioselectivity, which had been previously reported but never fully rationalized. Owing to its importance both in nature and in the development of new antioxidants, we investigated it in detail in Chapter 2. We could prove the onsetting of a radical-chain mechanism intermediated by thiyl and thiosemiquinone radicals at the basis of the “anomalous nucleophilic addition” of thiols to ortho-quinones, which paves the way to better understanding of the chemistry of such systems. The oxidation of catechols to the corresponding quinones is also a key reaction in the biosynthesis of melanins, mediated by enzyme Tyrosinase.