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.

Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

A candidate gene approach to identify DNA markers associated with meat quality and production traits: investigation of several cathepsin genes in Italian heavy pigs.

The cathepsin enzymes represent an important family of lysosomal proteinases with a broad spectrum of functions in many, if not in all, tissues and cell types. In addition to their primary role during the normal protein turnover, they possess highly specific proteolytic activities, including antigen processing in the immune response and a direct role in the development of obesity and tumours. In pigs, the involvement of cathepsin enzymes in proteolytic processes have important effects during the conversion of muscle to meat, due to their influence on meat texture and sensory characteristics, mainly in seasoned products. Their contribution is fundamental in flavour development of dry-curing hams. However, several authors have demonstrated that high cathepsin activity, in particular of cathepsin B, is correlated to defects of these products, such as an excessive meat softness together with abnormal free tyrosine content, astringent or metallic aftertastes and formation of a white film on the cut surface. Thus, investigation of their genetic variability could be useful to identify DNA markers associated with these dry cured hams parameters, but also with meat quality, production and carcass traits in Italian heavy pigs. Unfortunately, no association has been found between cathepsin markers and meat quality traits so far, in particular with cathepsin B activity, suggesting that other genes, besides these, affect meat quality parameters. Nevertheless, significant associations were observed with several carcass and production traits in pigs. A recent study has demonstrated that different single nucleotide polymorphisms (SNPs) localized in cathepsin D (CTSD), F (CTSF), H and Z genes were highly associated with growth, fat deposition and production traits in an Italian Large White pig population. The aim of this thesis was to confirm some of these results in other pig populations and identify new cathepsin markers in order to evaluate their effects on cathepsin activity and other production traits. Furthermore, starting from the data obtained in previous studies on CTSD gene, we also analyzed the known polymorphism located in the insulin-like growth factor 2 gene (IGF2 intron3-g.3072G>A). This marker is considered the causative mutation for the quantitative trait loci (QTL) affecting muscle mass and fat deposition in pigs. Since IGF2 maps very close to CTSD on porcine chromosome (SSC) 2, we wanted to clarify if the effects of the CTSD marker were due to linkage disequilibrium with the IGF2 intron3-g.3072G>A mutation or not. In the first chapter, we reported the results from these two SSC2 gene markers. First of all, we evaluated the effects of the IGF2 intron3-g.3072G>A polymorphism in the Italian Large White breed, for which no previous studies have analysed this marker. Highly significant associations were identified with all estimated breeding values for production and carcass traits (P<0.00001), while no effects were observed for meat quality traits. Instead, the IGF2 intron3-g.3072G>A mutation did not show any associations with the analyzed traits in the Italian Duroc pigs, probably due to the low level of variability at this polymorphic site for this breed. In the same Duroc pig population, significant associations were obtained for the CTSD marker for all production and carcass traits (P < 0.001), after excluding possible confounding effects of the IGF2 mutation. The effects of the CTSD g.70G>A polymorphism were also confirmed in a group of Italian Large White pigs homozygous for the IGF2 intron3-g.3072G allele G (IGF2 intron3-g.3072GG) and by haplotype analysis between the markers of the two considered genes. Taken together, all these data indicated that the IGF2 intron3-g.3072G>A mutation is not the only polymorphism affecting fatness and muscle deposition in pigs. In the second chapter, we reported the analysis of two new SNPs identified in cathepsin L (CTSL) and cathepsin S (CTSS) genes and the association results with meat quality parameters (including cathepsin B activity) and several production traits in an Italian Large White pig population. Allele frequencies of these two markers were evaluated in 7 different pig breeds. Furthermore, we mapped using a radiation hybrid panel the CTSS gene on SSC4. Association studies with several production traits, carried out in 268 Italian Large White pigs, indicated positive effects of the CTSL polymorphism on average daily gain, weight of lean cuts and backfat thickness (P<0.05). The results for these latter traits were also confirmed using a selective genotype approach in other Italian Large White pigs (P<0.01). In the 268 pig group, the CTSS polymorphism was associated with feed:gain ratio and average daily gain (P<0.05). Instead, no association was observed between the analysed markers and meat quality parameters. Finally, we wanted to verify if the positive results obtained for the cathepsin L and S markers and for other previous identified SNPs (cathepsin F, cathepsin Z and their inhibitor cystatin B) were confirmed in the Italian Duroc pig breed (third chapter). We analysed them in two groups of Duroc pigs: the first group was made of 218 performance-tested pigs not selected by any phenotypic criteria, the second group was made of 100 Italian Duroc pigs extreme and divergent for visible intermuscular fat trait. In the first group, the CTSL polymorphism was associated with weight of lean cuts (P<0.05), while suggestive associations were obtained for average daily gain and backfat thickness (P<0.10). Allele frequencies of the CTSL gene marker also differed positively among the visible intermuscular extreme tails. Instead, no positive effects were observed for the other DNA markers on the analysed traits. In conclusion, in agreement with the present data and for the biological role of these enzymes, the porcine CTSD and CTSL markers: a) may have a direct effect in the biological mechanisms involved in determining fat and lean meat content in pigs, or b) these markers could be very close to the putative functional mutation(s) present in other genes. These findings have important practical applications, in particular the CTSD and CTSL mutations could be applied in a marker assisted selection (MAS) both in the Italian Large White and Italian Duroc breeds. Marker assisted selection could also increase in efficiency by adding information from the cathepsin S genotype, but only in the Italian Large White breed.

Provenienza dei sedimenti arenitici nel bacino di Tracia (eo-oligocene, Turchia nord-occidentale e Grecia nord-orientale)

The Thrace Basin is the largest and thickest Tertiary sedimentary basin of the eastern Balkans region and constitutes an important hydrocarbon province. It is located between the Rhodope-Strandja Massif to the north and west, the Marmara Sea and Biga Peninsula to the south, and the Black Sea to the est. It consists of a complex system of depocenters and uplifts with very articulate paleotopography indicated by abrupt lateral facies variations. Its southeastern margin is widely deformed by the Ganos Fault, a segment of the North Anatolian strike-slip fault system . Most of the Thrace Basin fill ranges from the Eocene to the Late Oligocene. Maximum total thickness, including the Neogene-Quaternary succession, reaches 9.000 meters in a few narrow depocenters. This sedimentary succession consists mainly of basin plain turbiditic deposits with a significant volcaniclastic component which evolves upwards to shelf deposits and continental facies, with deltaic bodies prograding towards the basin center in the Oligocene. This work deals with the provenance of Eocene-Oligocene clastic sediments of the southern and western part of Thrace Basin in Turkey and Greece. Sandstone compositional data (78 gross composition analyses and 40 heavy minerals analyses) were used to understand the change in detrital modes which reflects the provenance and geodinamic evolution of the basin. Samples were collected at six localities, which are from west to est: Gökçeada, Gallipoli and South-Ganos (south of Ganos Fault), Alexandroupolis, Korudağ and North-Ganos (north of Ganos Fault). Petrologic (framework composition and heavy-mineral analyses) and stratigraphic-sedimentologic data, (analysis of sedimentologic facies associations along representative stratigraphic sections, paleocurrents) allowed discrimination of six petrofacies; for each petrofacies the sediment dispersal system was delineated. The Thrace Basin fill is made mainly of lithic arkoses and arkosic litharenites with variable amount of low-grade metamorphic lithics (also ophiolitic), neovolcanic lithics, and carbonate grains (mainly extrabasinal). Picotite is the most widespread heavy mineral in all petrofacies. Petrological data on analyzed successions show a complex sediment dispersal pattern and evolution of the basin, indicating one principal detrital input from a source area located to the south, along both the İzmir-Ankara and Intra-Pontide suture lines, and a possible secondary source area, represented by the Rhodope Massif to the west. A significant portion of the Thrace Basin sediments in the study area were derived from ophiolitic source rocks and from their oceanic cover, whereas epimetamorphic detrital components came from a low-grade crystalline basement. An important penecontemporaneous volcanic component is widespread in late Eocene-Oligocene times, indicating widespread post-collisional (collapse?) volcanism following the closure of the Vardar ocean. Large-scale sediment mass wasting from south to north along the southern margin of the Thrace Basin is indicated (i) in late Eocene time by large olistoliths of ophiolites and penecontemporaneous carbonates, and (ii) in the mid-Oligocene by large volcaniclastic olistoliths. The late Oligocene paleogeographic scenario was characterized by large deltaic bodies prograding northward (Osmancik Formation). This clearly indicates that the southern margin of the basin acted as a major sediment source area throughout its Eocene-Oligocene history. Another major sediment source area is represented by the Rhodope Massif, in particolar the Circum-Rhodopic belt, especially for plutonic and metamorphic rocks. Considering preexisting data on the petrologic composition of Thrace Basin, silicilastic sediments in Greece and Bulgaria (Caracciolo, 2009), a Rhodopian provenance could be considered mostly for areas of the Thrace Basin outside our study area, particularly in the northern-central portions of the basin. In summary, the most important source area for the sediment of Thrace Basin in the study area was represented by the exhumed subduction-accretion complex along the southern margin of the basin (Biga Peninsula and western-central Marmara Sea region). Most measured paleocurrent indicators show an eastward paleoflow but this is most likely the result of gravity flow deflection. This is possible considered a strong control due to the east-west-trending synsedimentary transcurrent faults which cuts the Thrace Basin, generating a series of depocenters and uplifts which deeply influenced sediment dispersal and the areal distribution of paleoenvironments. The Thrace Basin was long interpreted as a forearc basin between a magmatic arc to the north and a subduction-accretion complex to the south, developed in a context of northward subduction. This interpretation was challenged by more recent data emphasizing the lack of a coeval magmatic arc in the north and the interpretation of the chaotic deposit which outcrop south of Ganos Fault as olistoliths and large submarine slumps, derived from the erosion and sedimentary reworking of an older mélange unit located to the south (not as tectonic mélange formed in an accretionary prism). The present study corroborates instead the hypothesis of a post-collisional origin of the Thrace Basin, due to a phase of orogenic collapse, which generated a series of mid-Eocene depocenters all along the İzmir-Ankara suture (following closure of the Vardar-İzmir-Ankara ocean and the ensuing collision); then the slab roll-back of the remnant Pindos ocean played an important role in enhancing subsidence and creating additional accommodation space for sediment deposition.

Elaborazione di un algoritmo di pianificazione di ricostruzioni del cavo orale, dell'orofaringe, della mandibola.

1.Ricostruzione mandibolare La ricostruzione mandibolare è comunemente eseguita utilizzando un lembo libero perone. Il metodo convenzionale (indiretto) di Computer Aided Design e Computer Aided Manifacturing prevede il modellamento manuale preoperatorio di una placca di osteosintesi standard su un modello stereolitografico della mandibola. Un metodo innovativo CAD CAM diretto comprende 3 fasi: 1) pianificazione virtuale 2) computer aided design della dima di taglio mandibolari, della dima di taglio del perone e della placca di osteosintesi e 3) Computer Aided Manufacturing dei 3 dispositivi chirurgici personalizzati. 7 ricostruzioni mandibolari sono state effettuate con il metodo diretto. I risultati raggiunti e le modalità di pianificazione sono descritte e discusse. La progettazione assistita da computer e la tecnica di fabbricazione assistita da computer facilita un'accurata ricostruzione mandibolare ed apporta un miglioramento statisticamente significativo rispetto al metodo convenzionale. 2. Cavità orale e orofaringe Un metodo ricostruttivo standard per la cavità orale e l'orofaringe viene descritto. 163 pazienti affetti da cancro della cavità orale e dell'orofaringe, sono stati trattati dal 1992 al 2012 eseguendo un totale di 175 lembi liberi. La strategia chirurgica è descritta in termini di scelta del lembo, modellamento ed insetting. I modelli bidimensionali sono utilizzati per pianificare una ricostruzione tridimensionale con il miglior risultato funzionale ed estetico. I modelli, la scelta del lembo e l' insetting sono descritti per ogni regione. Complicazioni e risultati funzionali sono stati valutati sistematicamente. I risultati hanno mostrato un buon recupero funzionale con le tecniche ricostruttive descritte. Viene proposto un algoritmo ricostruttivo basato su template standard.

Administración y Bienes Culturales. Una comparación entre Italia y España

En este estudio se analizó la Administración Pública que tiene el encargo de la tutela y revalorización del Patrimonio Cultural, en una perspectiva comparativa entre los dos países. La investigación se dividió en dos partes. Una primera en la que se analizan las soluciones legales adoptadas por los diversos regímenes durante los siglos. Se busca analizar la respuesta legal dada históricamente a los problemática social de la conservación del Patrimonio Cultural y entender las políticas que la Administración había adoptado finalmente. Este histórico viaje terminará con la legislación vigente, y con el análisis de la Legislación inminentemente anterior, que ha sentado las bases de la actual estructura de la Administración Pública, que ejercerá las competencias relativas a la protección del patrimonio cultural. El estudio continúa con una segunda parte en la que, con dos capítulos, se procede a examinar la legislación que regula la organización de la Administración Pública tanto de Italia como de España. En cada uno de los países se analizan todos los niveles territoriales, así como los organismos o instituciones autónomas creadas dentro de los Organismos Públicos de cada Estado. El tercer capítulo supone una comparación y una crítica de ambas organizaciones. Ambas estructuras en ocasiones han surgido a partir de un punto en común, incluso, a pesar de haber tenido evoluciones distintas de conformidad a la especificidad del país, todavía presentan similitudes. Por otra parte, ambos países se han visto perjudicadas recientemente por las políticas relacionadas con los recortes en el gasto público, lo que llevó a la reducción de la Administración Pública, aunque no de un modo tan satisfactorio, como esperábamos. El estudio finaliza con las conclusiones obtenidas tras el análisis concienzudo de ambas administraciones.

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.