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.

La trasparenza nelle organizzazioni sanitarie: comunicare i risultati

La raccolta e l’utilizzo in chiave comparativa di dati di performance sanitaria risponde, tra le altre esigenze, a bisogni di accountability. Si osserva infatti a livello internazionale la diffusione di politiche di pubblicizzazione della qualità dei risultati: uno studio della letteratura di settore consente di confrontare i fattori più rilevanti delle principali esperienze di reporting già realizzate in Paesi dai sistemi sanitari molto diversi. Nel contesto italiano l’attenzione ai diritti dell’utente di concerto con la riforma del sistema informativo sanitario si pongono come premesse alla potenziale diffusione di dati di performance alla cittadinanza. Una interpretazione delle fonti normative e della giurisprudenza tramite il principio di trasparenza pare sostenere la tesi di una doverosità di informazione in capo alle amministrazioni pubbliche; l’analisi dei possibili scenari di impatto delle politiche di comunicazione ne condiziona però l’attuazione ad una programmazione strutturata e consapevole.

Coastal flood vulnerability assessment with geomatic methods: Test sites of western Thailand, Sydney (Australia) and aeolian islands (south tyrrhenian sea, Italy)

The work undertaken in this PhD thesis is aimed at the development and testing of an innovative methodology for the assessment of the vulnerability of coastal areas to marine catastrophic inundation (tsunami). Different approaches are used at different spatial scales and are applied to three different study areas: 1. The entire western coast of Thailand 2. Two selected coastal suburbs of Sydney – Australia 3. The Aeolian Islands, in the South Tyrrhenian Sea – Italy I have discussed each of these cases study in at least one scientific paper: one paper about the Thailand case study (Dall’Osso et al., in review-b), three papers about the Sydney applications (Dall’Osso et al., 2009a; Dall’Osso et al., 2009b; Dall’Osso and Dominey-Howes, in review) and one last paper about the work at the Aeolian Islands (Dall’Osso et al., in review-a). These publications represent the core of the present PhD thesis. The main topics dealt with are outlined and discussed in a general introduction while the overall conclusions are outlined in the last section.

Outcome respiratorio a lungo termine nei soggetti affetti da cardiopatia congenita sottoposti ad intervento cardiochirurgico

Introduction: In the last years cardiac surgery for congenital heart disease (CHD) reduced dramatically mortality modifying prognosis, but, at the same time, increased morbidity in this patient population. Respiratory and cardiovascular systems are strictly anatomically and functionally connected, so that alterations of pulmonary hemodynamic conditions modify respiratory function. While very short-term alterations of respiratory mechanics after surgery were investigated by many authors, not as much works focused on long-term changes. In these subjects rest respiratory function may be limited by several factor: CHD itself (fetal pulmonary perfusion influences vascular and alveolar development), extracorporeal circulation (CEC), thoracotomy and/or sternotomy, rib and sternal contusions, pleural adhesions and pleural fibrosis, secondary to surgical injury. Moreover inflammatory cascade, triggered by CEC, can cause endothelial damage and compromise gas exchange. Aims: The project was conceived to 1) determine severity of respiratory functional impairement in different CHD undergone to surgical correction/palliation; 2) identify the most and the least CHD involved by pulmonary impairement; 3) find a correlation between a specific hemodynamic condition and functional anomaly, and 4) between rest respiratory function and cardiopulmonary exercise test. Materials and methods: We studied 113 subjects with CHD undergone to surgery, and distinguished by group in accord to pulmonary blood flow (group 0: 28 pts with normal pulmonary flow; group 1: 22 pts with increased flow; group 2: 43 pts with decreased flow; group 3: 20 pts with total cavo-pulmonary anastomosis-TCPC) followed by the Pediatric Cardiology and Cardiac Surgery Unit, and we compare them to 37 age- and sex-matched healthy subjects. In Pediatric Pulmonology Unit all pts performed respiratory function tests (static and dynamic volumes, flow/volume curve, airway resistances-raw- and conductance-gaw-, lung diffusion of CO-DLCO- and DLCO/alveolar volume), and CHD pts the same day had cardiopulmonary test. They all were examined and had allergological tests, and respiratory medical history. Results: restrictive pattern (measured on total lung capacity-TLC- and vital capacity-VC) was in all CHD groups, and up to 45% in group 2 and 3. Comparing all groups, we found a significant difference in TLC between healthy and group 2 (p=0.001) and 3 (p=0.004), and in VC between group 2 and healthy (p=0.001) and group 1(p=0.034). Inspiratory capacity (IC) was decreased in group 2 related to healthy (p<0.001) and group 1 (p=0.037). We showed a direct correlation between TLC and VC with age at surgery (p=0.01) and inverse with number of surgical interventions (p=0.03). Reduced FEV1/FVC ratio, Gaw and increased Raw were mostly present in group 3. DLCO was impaired in all groups, but up to 80% in group 3 and 50% in group 2; when corrected for alveolar volume (DLCO/VA) reduction persisted in group 3 (20%), 2 (6.2%) and 0 (7.1%). Exercise test was impaired in all groups: VO2max and VE markedly reduced in all but especially in group 3, and VE/VCO2 slope, marker of ventilatory response to exercise, is increased (<36) in 62.5% of group 3, where other pts had anyway value>32. Comparing group 3 and 2, the most involved categories, we found difference in VO2max and VE/VCO2 slope (respectively p=0.02 and p<0.0001). We evidenced correlation between rest and exercise tests, especially in group 0 (between VO2max and FVC, FEV1, VC, IC; inverse relation between VE/VCO2slope and FVC, FEV1 and VC), but also in group 1 (VO2max and IC), group 2 (VO2max and FVC and FEV1); never in group 3. Discussion: According with literature, we found a frequent impairment of rest pulmonary function in all groups, but especially in group 2 and 3. Restrictive pattern was the most frequent alteration probably due to compromised pulmonary (vascular and alveolar) development secondary to hypoperfusion in fetal and pre-surgery (and pre-TCPC)life. Parenchymal fibrosis, pleural adhesions and thoracic deformities can add further limitation, as showed by the correlation between group 3 and number of surgical intervention. Exercise tests were limited, particularly in group 3 (complex anatomy and lost of chronotropic response), and we found correlations between rest and exercise tests in all but group 3. We speculate that in this patients hemodynamic exceeds respiratory contribution, though markedly decreased.

Geological and Structural evolution of the Eurasia Africa plate boundary in the Gulf of Cadiz Central Eastern Atlantic Sea.

Iberia Africa plate boundary, cross, roughly W-E, connecting the eastern Atlantic Ocean from Azores triple junction to the Continental margin of Morocco. Relative movement between the two plate change along the boundary, from transtensive near the Azores archipelago, through trascurrent movement in the middle at the Gloria Fracture Zone, to transpressive in the Gulf of Cadiz area. This study presents the results of geophysical and geological analysis on the plate boundary area offshore Gibraltar. The main topic is to clarify the geodynamic evolution of this area from Oligocene to Quaternary. Recent studies have shown that the new plate boundary is represented by a 600 km long set of aligned, dextral trascurrent faults (the SWIM lineaments) connecting the Gloria fault to the Riff orogene. The western termination of these lineaments crosscuts the Gibraltar accretionary prism and seems to reach the Moroccan continental shelf. In the past two years newly acquired bathymetric data collected in the Moroccan offshore permit to enlighten the present position of the eastern portion of the plate boundary, previously thought to be a diffuse plate boundary. The plate boundary evolution, from the onset of compression in the Oligocene to the Late Pliocene activation of trascurrent structures, is not yet well constrained. The review of available seismics lines, gravity and bathymetric data, together with the analysis of new acquired bathymetric and high resolution seismic data offshore Morocco, allows to understand how the deformation acted at lithospheric scale under the compressive regime. Lithospheric folding in the area is suggested, and a new conceptual model is proposed for the propagation of the deformation acting in the brittle crust during this process. Our results show that lithospheric folding, both in oceanic and thinned continental crust, produced large wavelength synclines bounded by short wavelength, top thrust, anticlines. Two of these anticlines are located in the Gulf of Cadiz, and are represented by the Gorringe Ridge and Coral Patch seamounts. Lithospheric folding probably interacted with the Monchique – Madeira hotspot during the 72 Ma to Recent, NNE – SSW transit. Plume related volcanism is for the first time described on top of the Coral Patch seamount, where nine volcanoes are found by means of bathymetric data. 40Ar-39Ar age of 31.4±1.98 Ma are measured from one rock sample of one of these volcanoes. Analysis on biogenic samples show how the Coral Patch act as a starved offshore seamount since the Chattian. We proposed that compression stress formed lithospheric scale structures playing as a reserved lane for the upwelling of mantle material during the hotspot transit. The interaction between lithospheric folding and the hotspot emplacement can be also responsible for the irregularly spacing, and anomalous alignments, of individual islands and seamounts belonging to the Monchique - Madeira hotspot.

Valorizzazione di cartografia storica attraverso moderne tecniche geomatiche: recupero metrico, elaborazione e consultazione in ambiente digitale

“Cartographic heritage” is different from “cartographic history”. The second term refers to the study of the development of surveying and drawing techniques related to maps, through time, i.e. through different types of cultural environment which were background for the creation of maps. The first term concerns the whole amount of ancient maps, together with these different types of cultural environment, which the history has brought us and which we perceive as cultural values to be preserved and made available to many users (public, institutions, experts). Unfortunately, ancient maps often suffer preservation problems of their analog support, mostly due to aging. Today, metric recovery in digital form and digital processing of historical cartography allow preserving map heritage. Moreover, modern geomatic techniques give us new chances of using historical information, which would be unachievable on analog supports. In this PhD thesis, the whole digital processing of recovery and elaboration of ancient cartography is reported, with a special emphasis on the use of digital tools in preservation and elaboration of cartographic heritage. It is possible to divide the workflow into three main steps, that reflect the chapter structure of the thesis itself: • map acquisition: conversion of the ancient map support from analog to digital, by means of high resolution scanning or 3D surveying (digital photogrammetry or laser scanning techniques); this process must be performed carefully, with special instruments, in order to reduce deformation as much as possible; • map georeferencing: reproducing in the digital image the native metric content of the map, or even improving it by selecting a large number of still existing ground control points; this way it is possible to understand the projection features of the historical map, as well as to evaluate and represent the degree of deformation induced by the old type of cartographic transformation (that can be unknown to us), by surveying errors or by support deformation, usually all errors of too high value with respect to our standards; • data elaboration and management in a digital environment, by means of modern software tools: vectorization, giving the map a new and more attractive graphic view (for instance, by creating a 3D model), superimposing it on current base maps, comparing it to other maps, and finally inserting it in GIS or WebGIS environment as a specific layer. The study is supported by some case histories, each of them interesting from the point of view of one digital cartographic elaboration step at least. The ancient maps taken into account are the following ones: • three maps of the Po river delta, made at the end of the XVI century by a famous land-surveyor, Ottavio Fabri (he is single author in the first map, co-author with Gerolamo Pontara in the second map, co-author with Bonajuto Lorini and others in the third map), who wrote a methodological textbook where he explains a new topographical instrument, the squadra mobile (mobile square) invented and used by himself; today all maps are preserved in the State Archive of Venice; • the Ichnoscenografia of Bologna by Filippo de’ Gnudi, made in the 1702 and today preserved in the Archiginnasio Library of Bologna; it is a scenographic view of the city, captured in a bird’s eye flight, but also with an icnographic value, as the author himself declares; • the map of Bologna by the periti Gregorio Monari and Antonio Laghi, the first map of the city derived from a systematic survey, even though it was made only ten years later (1711–1712) than the map by de’ Gnudi; in this map the scenographic view was abandoned, in favor of a more correct representation by means of orthogonal projection; today the map is preserved in the State Archive of Bologna; • the Gregorian Cadastre of Bologna, made in 1831 and updated until 1927, now preserved in the State Archive of Bologna; it is composed by 140 maps and 12 brogliardi (register volumes). In particular, the three maps of the Po river delta and the Cadastre were studied with respect to their acquisition procedure. Moreover, the first maps were analyzed from the georeferencing point of view, and the Cadastre was analyzed with respect to a possible GIS insertion. Finally, the Ichnoscenografia was used to illustrate a possible application of digital elaboration, such as 3D modeling. Last but not least, we must not forget that the study of an ancient map should start, whenever possible, from the consultation of the precious original analogical document; analysis by means of current digital techniques allow us new research opportunities in a rich and modern multidisciplinary context.

Potential fields study of Marsili basin and Palinuro volcanic complex

In this thesis Marsili back-arc basin and Palinuro Volcanic Complex (Southern Tyrrhenian Sea) have been investigated by using magnetic, bathymetric and gravimetric data. A new velocity model of opening of the Marsili basin has been proposed, highlighting the transition from the horizontal spreading of the back-arc to the vertical accretion of the Marsili seamount. Introducing gravity data, Marsili's internal structure has been modeled and a huge portion of the volcano with low density and vanishing magnetization has been detected. Forward modeling of Palinuro Volcanic Complex showed as Palinuro represents the shallowest evidence of a deep tectonic discontinuity and the possible transition domain between the oceanic crust of Marsili Basin and the continental crust related to the Appenninic chain.

Timing per l'inserimento in lista dei pazienti affetti da fibrosi cistica che necessitano di trapianto polmonare: casistica di un centro regionale di riferimento

Timing of waiting list entrance for patients with cystic fibrosis in need of pulmonary transplant: the experience of a regional referral centre Objective: Evaluation of parameters that can predict a rapid decay of general conditions of patients affected by Cystic Fibrosis (CF) with no specific criteria to be candidate to pulmonary transplant. Material and methods: Fifteen patients with CF who died for complications and 8 who underwent lung transplantation in the 2000-2010 decade, were enrolled. Clinical data 2 years before the event (body max index, FEV1%, number of EV antibiotic treatments per year, colonization with Methicillin-resistant Staphylococcus aureus (MRSA), pseudomonas aeruginosa mucosus, burkholderia cepacia, pulmonary allergic aspergilosis) were compared among the 2 groups. Results: Mean FEV1% was significantly higher and mean number of antibiotic treatment was lower in deceased than in the transplanted patients (p<0.002 and p<0.001 respectively). Although in patients who died there were no including criteria to enter the transplant list 2 years before the exitus, suggestive findings such as low BMI (17.3), high incidence of hepatic pathology (33.3%), diabetes (50%), and infections with MRSA infection (25%), Pseudomonas aeruginosa (83.3%) and burkholderia cepacia (8.3%) were found with no statistical difference with transplanted patients, suggesting those patients were at risk of severe prognosis. In patients who died, females were double than males. Conclusion: While evaluating patients with CF, negative prognostic factors such as the ones investigated in this study, should be considered to select individuals with high mortality risk who need stricter therapeutical approach and follow up. Inclusion of those patients in the transplant waiting list should be taken into account.