Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Variability-tolerant High-reliability Multicore Platforms

Next generation electronic devices have to guarantee high performance while being less power-consuming and highly reliable for several application domains ranging from the entertainment to the business. In this context, multicore platforms have proven the most efficient design choice but new challenges have to be faced. The ever-increasing miniaturization of the components produces unexpected variations on technological parameters and wear-out characterized by soft and hard errors. Even though hardware techniques, which lend themselves to be applied at design time, have been studied with the objective to mitigate these effects, they are not sufficient; thus software adaptive techniques are necessary. In this thesis we focus on multicore task allocation strategies to minimize the energy consumption while meeting performance constraints. We firstly devise a technique based on an Integer Linear Problem formulation which provides the optimal solution but cannot be applied on-line since the algorithm it needs is time-demanding; then we propose a sub-optimal technique based on two steps which can be applied on-line. We demonstrate the effectiveness of the latter solution through an exhaustive comparison against the optimal solution, state-of-the-art policies, and variability-agnostic task allocations by running multimedia applications on the virtual prototype of a next generation industrial multicore platform. We also face the problem of the performance and lifetime degradation. We firstly focus on embedded multicore platforms and propose an idleness distribution policy that increases core expected lifetimes by duty cycling their activity; then, we investigate the use of micro thermoelectrical coolers in general-purpose multicore processors to control the temperature of the cores at runtime with the objective of meeting lifetime constraints without performance loss.

Study of molecules of astrochemical, astrophysical and atmospheric interest by means of High - Resolution Infrared Spectroscopy

The spectroscopic investigation of the gas-phase molecules relevant for the chemistry of the atmosphere and of the interstellar medium has been performed. Two types of molecules have been studied, linear and symmetric top. Several experimental high-resolution techniques have been adopted, exploiting the spectrometers available in Bologna, Venezia, Brussels and Wuppertal: Fourier-Transform-Infrared Spectroscopy, Cavity-Ring-Down Spectroscopy, Cavity-Enhanced-Absorption Spectroscopy, Tunable-Diode-Laser Spectroscopy. Concerning linear molecules, the spectra of a number of isotopologues of acetylene, 12C2D2, H12C13CD, H13C12CD, 13C12CD2, of DCCF and monodeuterodiacetylene DC4H, have been studied, from 320 to 6800 cm-1. This interval covers bending, stretching, overtone and combination bands, the focus on specific ranges depending on the molecule. In particular, the analysis of the bending modes has been performed for 12C2D2 (450-2200 cm-1), 13C12CD2 (450-1700 cm-1), DCCF (320-850cm-1) and DC4H (450-1100 cm-1), of the stretching-bending system for 12C2D2 (450-5500 cm-1) and of the 2nu1 and combination bands up to four quanta of excitation for H12C13CD, H13C12CD and 13C12CD2 (6130-6800 cm-1). In case of symmetric top molecules, CH3CCH has been investigated in the 2nu1 region (6200-6700 cm-1), which is particularly congested due to the huge network of states affected by Coriolis and anharmonic interactions. The bending fundamentals of 15ND3 (450-2700 cm-1) have been studied for the first time, characterizing completely the bending states, v2 = 1 and v4 = 1, whereas the analysis of the stretching modes, which evidenced the presence of several perturbations, has been started. Finally, the fundamental band nu4 of CF3Br in the 1190-1220 cm-1 region has been investigated. Transitions belonging to the CF379Br and CF381Br molecules have been identified since the spectra were recorded using a sample containing the two isotopologues in natural abundance. This allowed the characterization of the v4 = 1 state for both isotopologues and the evaluation of the bromine isotopic splitting.