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.

Effect of hypoxia and hyperglycemia on cell bioenergetics

Mitochondria have a central role in energy supply in cells, ROS production and apoptosis and have been implicated in several human disease and mitochondrial dysfunctions in hypoxia have been related with disorders like Type II Diabetes, Alzheimer Disease, inflammation, cancer and ischemia/reperfusion in heart. When oxygen availability becomes limiting in cells, mitochondrial functions are modulated to allow biologic adaptation. Cells exposed to a reduced oxygen concentration readily respond by adaptive mechanisms to maintain the physiological ATP/ADP ratio, essential for their functions and survival. In the beginning, the AMP-activated protein kinase (AMPK) pathway is activated, but the responsiveness to prolonged hypoxia requires the stimulation of hypoxia-inducible factors (HIFs). In this work we report a study of the mitochondrial bioenergetics of primary cells exposed to a prolonged hypoxic period . To shine light on this issue we examined the bioenergetics of fibroblast mitochondria cultured in hypoxic atmospheres (1% O2) for 72 hours. Here we report on the mitochondrial organization in cells and on their contribution to the cellular energy state. Our results indicate that prolonged hypoxia cause a significant reduction of mitochondrial mass and of the quantity of the oxidative phosphorylation complexes. Hypoxia is also responsible to damage mitochondrial complexes as shown after normalization versus citrate synthase activity. HIF-1α plays a pivotal role in wound healing, and its expression in the multistage process of normal wound healing has been well characterized, it is necessary for cell motility, expression of angiogenic growth factor and recruitment of endothelial progenitor cells. We studied hypoxia in the pathological status of diabetes and complications of diabetes and we evaluated the combined effect of hyperglycemia and hypoxia on human dermal fibroblasts (HDFs) and human dermal micro-vascular endothelial cells (HDMECs) that were grown in high glucose, low glucose concentrations and mannitol as control for the osmotic challenge.

Hydrodynamical simulations of galaxy clusters in dark energy cosmologies

In this work we investigate the influence of dark energy on structure formation, within five different cosmological models, namely a concordance $\Lambda$CDM model, two models with dynamical dark energy, viewed as a quintessence scalar field (using a RP and a SUGRA potential form) and two extended quintessence models (EQp and EQn) where the quintessence scalar field interacts non-minimally with gravity (scalar-tensor theories). We adopted for all models the normalization of the matter power spectrum $\sigma_{8}$ to match the CMB data. For each model, we perform hydrodynamical simulations in a cosmological box of $(300 \ {\rm{Mpc}} \ h^{-1})^{3}$ including baryons and allowing for cooling and star formation. We find that, in models with dynamical dark energy, the evolving cosmological background leads to different star formation rates and different formation histories of galaxy clusters, but the baryon physics is not affected in a relevant way. We investigate several proxies for the cluster mass function based on X-ray observables like temperature, luminosity, $M_{gas}$, and $Y_{X}$. We confirm that the overall baryon fraction is almost independent of the dark energy models within few percentage points. The same is true for the gas fraction. This evidence reinforces the use of galaxy clusters as cosmological probe of the matter and energy content of the Universe. We also study the $c-M$ relation in the different cosmological scenarios, using both dark matter only and hydrodynamical simulations. We find that the normalization of the $c-M$ relation is directly linked to $\sigma_{8}$ and the evolution of the density perturbations for $\Lambda$CDM, RP and SUGRA, while for EQp and EQn it depends also on the evolution of the linear density contrast. These differences in the $c-M$ relation provide another way to use galaxy clusters to constrain the underlying cosmology.

Advanced Techniques for Face Recognition under Challenging Environments

Automatically recognizing faces captured under uncontrolled environments has always been a challenging topic in the past decades. In this work, we investigate cohort score normalization that has been widely used in biometric verification as means to improve the robustness of face recognition under challenging environments. In particular, we introduce cohort score normalization into undersampled face recognition problem. Further, we develop an effective cohort normalization method specifically for the unconstrained face pair matching problem. Extensive experiments conducted on several well known face databases demonstrate the effectiveness of cohort normalization on these challenging scenarios. In addition, to give a proper understanding of cohort behavior, we study the impact of the number and quality of cohort samples on the normalization performance. The experimental results show that bigger cohort set size gives more stable and often better results to a point before the performance saturates. And cohort samples with different quality indeed produce different cohort normalization performance. Recognizing faces gone after alterations is another challenging problem for current face recognition algorithms. Face image alterations can be roughly classified into two categories: unintentional (e.g., geometrics transformations introduced by the acquisition devide) and intentional alterations (e.g., plastic surgery). We study the impact of these alterations on face recognition accuracy. Our results show that state-of-the-art algorithms are able to overcome limited digital alterations but are sensitive to more relevant modifications. Further, we develop two useful descriptors for detecting those alterations which can significantly affect the recognition performance. In the end, we propose to use the Structural Similarity (SSIM) quality map to detect and model variations due to plastic surgeries. Extensive experiments conducted on a plastic surgery face database demonstrate the potential of SSIM map for matching face images after surgeries.

Extending Implicit Computational Complexity and Abstract Machines to Languages with Control

The Curry-Howard isomorphism is the idea that proofs in natural deduction can be put in correspondence with lambda terms in such a way that this correspondence is preserved by normalization. The concept can be extended from Intuitionistic Logic to other systems, such as Linear Logic. One of the nice conseguences of this isomorphism is that we can reason about functional programs with formal tools which are typical of proof systems: such analysis can also include quantitative qualities of programs, such as the number of steps it takes to terminate. Another is the possiblity to describe the execution of these programs in terms of abstract machines. In 1990 Griffin proved that the correspondence can be extended to Classical Logic and control operators. That is, Classical Logic adds the possiblity to manipulate continuations. In this thesis we see how the things we described above work in this larger context.

Genus Bifidobacterium: taxonomy studies and gene expression analysis on folate pathway

Folates (vitamin B9) are essential water soluble vitamins, whose deficiency in humans may contribute to the onset of several diseases, such as anaemia, cancer, cardiovascular diseases, neurological problems as well as defects in embryonic development. Human and other mammals are unable to synthesize ex novo folate obtaining it from exogenous sources, via intestinal absorption. Recently the gut microbiota has been identified as an important source of folates and the selection and use of folate producing microorganisms represents an innovative strategy to increase human folate levels. The aim of this thesis was to gain a fundamental understanding of folate metabolism in Bifidobacterium adolescentis. The work was subdivided in three main phases, also aimed to solve different problems encountered working with Bifidobacterium strains. First, a new identification method (based on PCR-RFLP of hsp60 gene) was specifically developed to identify Bifidobacterium strains. Secondly, Bifidobacterium adolescentis biodiversity was explored in order to recognize representing strains of this species to be screened for their folate production ability. Results showed that this species is characterized by a wide variability and support the idea that a possible new taxonomic re-organization would be required. Finally B. adolescentis folate metabolism was studied using a double approach. A quantitative analysis of folate content was complemented by the examination of expression levels of genes involved in folate related pathways. For the normalization process, required to increase the robustness of the qRT-PCR analysis, an appropriate set of reference genes was tested using two different algorithms. Results demonstrate that B.adolescentis strains may represent an endogenous source of natural folate and they could be used to fortify fermented dairy products. This bio-fortification strategy presents many advantages for the consumer, providing native folate forms more bio-available, and not implicated in the discussed controversy concerning the safety of high intake of synthetic folic acid.

The dynamics of early-type galaxies as a tool to understand their hot coronae and their IMF

Dynamical models of galaxies are a powerful tool to study and understand several astrophysical problems related to galaxy formation and evolution. This thesis is focussed on a particular type of dynamical models, that are widely used in literature, and are based on the solution of the Jeans equations. By means of a numerical Jeans solver code, developed on purpose and able to build state-of-the-art advanced axisymmetric galaxy models, two of the main currently investigated issues in the field of research of early-type galaxies (ETGs) are addressed. The first topic concerns the hot and X-ray emitting gaseous coronae that surround ETGs. The main goal is to explain why flat and rotating galaxies generally exhibit haloes with lower gas temperatures and luminosities with respect to rounder and velocity dispersion supported systems. The second astrophysical problem addressed concerns instead the stellar initial mass function (IMF) of ETGs. Nowadays, this is a very controversial issue due to a growing number of works on ETGs, based on different and independent techniques, that show evidences of a systematic variation of the IMF normalization as a function of galaxy velocity dispersion or mass. These studies are changing the previous opinion that the IMF of ETGs was the same as that of spiral galaxies, and hence universal throughout the whole large family of galaxies.

Normare la vita. Biocontrollo e nuove tecnologie

Questa ricerca, suddivisa in due parti, si concentra sulle problematiche connesse alla normazione della vita e dei corpi delle donne al tempo delle biotecnologie. La Parte I è una genealogia filosofico-politica che ripercorre le tappe analitico-concettuali del dibattito intorno a biopolitica e tecnoscienza, a partire dai contributi teorici di poststrutturalismo e femminismo neomaterialista, e risponde alle domande: Cosa sono diventati i corpi nell’attuale società bio-info-modificata? Qual'è il ruolo delle scienze nelle metamorfosi che interessano soggettività e rapporti di potere? La Parte II è una cartografia dei modi in cui le biotecnologie, riguardanti i corpi delle donne, si sono sviluppate e diffuse. Essa indaga in modo transdisciplinare come in Italia, e più in generale in Europa, sono state normate le tecniche di interruzione volontaria di gravidanza e fecondazione in vitro. Ampio spazio è dedicato ai modi in cui gli attori della bioetica, istituzionale e non, i medici, laici e cattolici, e le case farmaceutiche hanno affrontato questi temi e quello della contraccezione ormonale maschile. Medicina riproduttiva e rigenerativa sono tematizzate sempre in relazione al quadro normativo, per mostrare in che modo esso influenzi l’accesso ai diritti alla salute e all’autodeterminazione delle donne. Il quadro normativo è analizzato, a sua volta, alla luce dei fatti storici più rilevanti e delle culture più diffuse. L’obiettivo della ricerca è duplice: da un lato essa ha il fine di mostrare il modo in cui i corpi delle donne, e la relativa potenza generatrice, siano diventati uno snodo fondamentale nell’articolazione del biocontrollo e nell'apertura dei nuovi mercati legati a medicina riproduttiva e rigenerativa; dall’altro si propone di argomentare come un biodiritto flessibile, a contenuto storico variabile, condiviso e partecipato, sia un’ipotesi praticabile e virtuosa, utile all'eliminazione del gender gap ancora esistente in materia di diritti riproduttivi e sessuali.