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.

Determination of the gluon polarisation from open charm production at COMPASS

One of the main goals of the COMPASS experiment at CERN is the determination of the gluon polarisation in the nucleon. It is determined from spin asymmetries in the scattering of 160 GeV/c polarised muons on a polarised LiD target. The gluon polarisation is accessed by the selection of photon-gluon fusion (PGF) events. The PGF-process can be tagged through hadrons with high transverse momenta or through charmed hadrons in the final state. The advantage of the open charm channel is that, in leading order, the PGF-process is the only process for charm production, thus no physical background contributes to the selected data sample. This thesis presents a measurement of the gluon polarisation from the COMPASS data taken in the years 2002-2004. In the analysis, charm production is tagged through a reconstructed D0-meson decaying in $D^{0}-> K^{-}pi^{+}$ (and charge conjugates). The reconstruction is done on a combinatorial basis. The background of wrong track pairs is reduced using kinematic cuts to the reconstructed D0-candidate and the information on particle identification from the Ring Imaging Cerenkov counter. In addition, the event sample is separated into D0-candidates, where a soft pion from the decay of the D*-meson to a D0-meson, is found, and the D0-candidates without this tag. Due to the small mass difference between D*-meson and D0-meson the signal purity of the D*-tagged sample is about 7 times higher than in the untagged sample. The gluon polarisation is measured from the event asymmetries for the for the different spin configurations of the COMPASS target. To improve the statistical precision of the final results, the events in the final sample are weighted. This method results in an average value of the gluon polarisation in the x-range covered by the data. For the COMPASS data from 2002-2004, the resulting value of the gluon polarisation is $=-0.47+-0.44 (stat)+-0.15(syst.)$. The result is statistically compatible with the existing measurements of $$ in the high-pT channel. Compared to these, the open charm measurement has the advantage of a considerably smaller model dependence.

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.

Transport properties of YBa 2 Cu 3 O 7, PrBa 2 Cu 3 O 7-superlattices

The understanding of the coupling between superconducting YBa2Cu3O7 (YBCO) layers decoupled by non superconducting PrBa2Cu3O7 (PBCO) layers in c-axis oriented superlattices was the aim of this thesis. For this purpose two conceptually different kind of transport experiments have been performed. rnrnIn the first type of transport experiments the current is flowing parallel to the layers. Here the coupling is probed indirectly using magnetic vortex lines, which are penetrating the superlattice. Movement of the vortex segments in neighbouring YBCO layers is more or less coherent depending on the thickness of both the superconducting and non superconducting layers. This in-plane transport was measured either by sending an external current through bridges patterned in the superlattice or by an induced internal current. rnThe vortex-creep activation energy U was determined by analysis of the in-plane resistive transition in an external magnetic field B oriented along the c-axis. The activation energies for two series of superlattices were investigated. In one series the thickness of the YBCO layers was constant (nY=4 unit cells) and the number of the PBCO unit cells was varied, while in the other the number of PBCO layers was constant (nP=4) and nY varied. The correlation length of the vortex system was determined to be 80 nm along the c-axis direction. It was found that even a single PBCO unit cell in a superlattice effectively cuts the flux lines into shorter weakly coupled segments, and the coupling of the vortex systems in neighbouring layers is negligible already for a thickness of four unit cells of the PBCO layers. A characteristic variation of the activation energy for the two series of superlattices was found, where U0 is proportional to the YBCO thickness. A change in the variation of U0 with the current I in the specimen was observed, which can be explained in terms of a crossover in the vortex creep process, generated by the transport current. At low I values the dislocations mediated (plastic) vortex creep leads to thermally assisted flux-flow behaviour, whereas at high current the dc transport measurements are dominated by elastic (collective) creep.rnThe analysis of standard dc magnetization relaxation data obtained for a series superlattices revealed the occurrence of a crossover from elastic (collective) vortex creep at low temperature to plastic vortex creep at high T. The crossover is generated by the T dependent macroscopic currents induced in the sample. The existence of this creep crossover suggests that, compared with the well known Maley technique, the use of the normalized vortex creep activation energy is a better solution for the determination of vortex creep parameters.rnrnThe second type of transport experiments was to measure directly a possible Josephson coupling between superconducting CuO2 double planes in the superlattices by investigation of the transport properties perpendicular to the superconducting planes. Here three different experiments have been performed. The first one was to pattern mesa structures photolithographically as in previous works. The second used three-dimensional nanostructures cut by a focused ion beam. For the these two experiments insufficient patterning capabilities prevented an observation of the Josephson effect in the current voltage curves. rnA third experiment used a-axis and (110) oriented YBCO films, where in-plane patterning can in principle be sufficient to measure transport perpendicular to the superconducting planes. Therefore the deposition of films with this unusual growth orientation was optimized and investigated. The structural and microstructural evolution of c-axis to a-axis orientation was monitored using x-ray diffraction, scanning electron microscopy and magnetization measurements. Films with full a-axis alignment parallel to the substrate normal could be achieved on (100)SrTiO3. Due to the symmetry of the substrate the c-axis direction in-plane is twofold. Transferring the deposition conditions to films grown on (110)SrTiO3 allowed the growth of (110) oriented YBCO films with a unique in-plane c-axis orientation. While these films were of high quality by crystallographic and macroscopic visual inspection, electron microscopy revealed a coherent crack pattern on a nanoscale. Therefore the actual current path in the sample was not determined by the macroscopic patterning which prohibited investigations of the in-plane anisotropy in this case.rn

Implications of regional fault distribution and kinematics for the uplift of rift flanks around the Rwenzori Mountains, Southwestern Uganda

Das Ziel dieser Arbeit bestand in der Untersuchung der Störungsverteilung und der Störungskinematik im Zusammenhang mit der Hebung der Riftschultern des Rwenzori Gebirges.rnDas Rwenzori Gebirge befindet sich im NNE-SSWbis N-S verlaufenden Albertine Rift, des nördlichsten Segments des westlichen Armes des Ostafrikanischen Grabensystems. Das Albertine Rift besteht aus Becken unterschiedlicher Höhe, die den Lake Albert, Lake Edward, Lake George und Lake Kivu enthalten. Der Rwenzori horst trennt die Becken des Lake Albert und des Lake Edward. Es erstreckt sich 120km in N-S Richtung, sowie 40-50km in E-W Richtung, der h¨ochste Punkt befindet sich 5111 ü. NN. Diese Studie untersucht einen Abschnitt des Rifts zwischen etwa 1°N und 0°30'S Breite sowie 29°30' und 30°30' östlicher Länge ersteckt. Auch die Feldarbeit konzentrierte sich auf dieses Gebiet.rnrnHauptzweck dieser Studie bestand darin, die folgende These auf ihre Richtigkeit zu überprüfen: ’Wenn es im Verlauf der Zeit tatsächlich zu wesentlichen Änderungen in der Störungskinematik kam, dann ist die starke Hebung der Riftflanken im Bereich der Rwenzoris nicht einfach durch Bewegung entlang der Graben-Hauptst¨orungen zu erklären. Vielmehr ist sie ein Resultat des Zusammenspiels mehrerer tektonische Prozesse, die das Spannungsfeld beeinflussen und dadurch Änderungen in der Kinematik hervorrufen.’ Dadurch konzentrierte sich die Studie in erster Linie auf die Störungsanalyse.rnrnDie Kenntnis regionaler Änderungen der Extensionsrichtung ist entscheidend für das Verständnis komplexer Riftsysteme wie dem Ostafrikanischen Graben. Daher bestand der Kern der Untersuchung in der Kartierung von Störungen und der Untersuchung der Störungskinematik. Die Aufnahme strukturgeologischer Daten konzentrierte sich auf die Ugandische Seite des Rifts, und Pal¨aospannungen wurden mit Hilfe von St¨orungsdaten durch Spannungsinversion rekonstruiert.rnDie unterschiedliche Orientierung spr¨oder Strukturen im Gelände, die geometrische Analyse der geologischen Strukturen sowie die Ergebnisse von Mikrostrukturen im Dünnschliff (Kapitel 4) weisen auf verschiedene Spannungsfelder hin, die auf mögliche Änderungen der Extensionsrichtung hinweisen. Die Resultate der Spannungsinversion sprechen für Ab-, Über- und Blattverschiebungen sowie für Schrägüberschiebungen (Kapitel 5). Aus der Orientierung der Abschiebungen gehen zwei verschiedene Extensionsrichtungen hervor: im Wesentlichen NW-SE Extension in fast allen Gebieten, sowie NNE-SSW Extension im östlichen Zentralbereich.rnAus der Analyse von Blattverschiebungen ergaben sich drei unterschiedliche Spannungszustände. Zum Einen NNW-SSE bis N-S Kompression in Verbindung mit ENE-WSW bzw E-W Extension wurde für die nördlichen und die zentralen Ruwenzoris ausgemacht. Ein zweiter Spannungszustand mit WNW-ESE Kompression/NNE-SSW Extension betraf die Zentralen Rwenzoris. Ein dritter Spannungszustand mit NNW-SSE Extension betraf den östlichen Zentralteil der Rwenzoris. Schrägüberschiebungen sind durch dazu schräge Achsen charakterisiert, die für N-S bis NNW-SSE Kompression sprechen und ausschließlich im östlichen Zentralabschnitt auftreten. Überschiebungen, die hauptsächlich in den zentralen und den östlichen Rwenzoris auftreten, sprechen für NE-SW orientierten σ2-Achsen und NW-SE Extension.rnrnEs konnten drei unterschiedliche Spannungseinflüsse identifiziert werden: auf die kollisionsbedingte Bildung eines Überschiebungssystem folgte intra-kratonische Kompression und schließlich extensionskontrollierte Riftbildung. Der Übergang zwischen den beiden letztgenannten Spannungszuständen erfolgte Schrittweise und erzeugte vermutlich lokal begrenzte Transpression und Transtension. Gegenw¨artig wird die Störungskinematik der Region durch ein tensiles Spannungsregime in NW-SE bis N-S Richtung bestimmt.rnrnLokale Spannungsvariationen werden dabei hauptsächlich durch die Interferenzrndes regionalen Spannungsfeldes mit lokalen Hauptst¨orungen verursacht. Weitere Faktoren die zu lokalen Veränderungen des Spannungsfeldes führen können sind unterschiedliche Hebungsgeschwindigkeiten, Blockrotation oder die Interaktion von Riftsegmenten. Um den Einfluß präexistenter Strukturen und anderer Bedingungen auf die Hebung der Rwenzoris zu ermitteln, wurde der Riftprozeß mit Hilfe eines analogen ’Sandbox’-Modells rekonstruiert (Kapitel 6). Da sich die Moho-Diskontinuität im Bereich des Arbeitsgebietes in einer Tiefe von 25 km befindet, aktive Störungen aber nur bis zu einer Tiefe von etwa 20 km beobachtet werden können (Koehn et al. 2008), wurden nur die oberen 25 km im Modell nachbebildet. Untersucht und mit Geländebeobachtungen verglichen wurden sowohl die Reihenfolge, in der Riftsegmente entstehen, als auch die Muster, die sich im Verlauf der Nukleierung und des Wachstums dieser Riftsegmente ausbilden. Das Hauptaugenmerk wurde auf die Entwicklung der beiden Subsegmente gelegt auf denen sich der Lake Albert bzw. der Lake Edward und der Lake George befinden, sowie auf das dazwischenliegende Rwenzori Gebirge. Das Ziel der Untersuchung bestand darin herauszufinden, in welcher Weise das südwärts propagierende Lake Albert-Subsegment mit dem sinistral versetzten nordwärts propagierenden Lake Edward/Lake George-Subsegment interagiert.rnrnVon besonderem Interesse war es, in welcherWeise die Strukturen innerhalb und außerhalb der Rwenzoris durch die Interaktion dieser Riftsegmente beeinflußt wurden. rnrnDrei verschiedene Versuchsreihen mit unterschiedlichen Randbedingungen wurden miteinander verglichen. Abhängig vom vorherrschenden Deformationstyp der Transferzone wurden die Reihen als ’Scherungs-dominiert’, ’Extensions-dominiert’ und als ’Rotations-dominiert’ charakterisiert. Die Beobachtung der 3-dimensionalen strukturellen Entwicklung der Riftsegmente wurde durch die Kombination von Modell-Aufsichten mit Profilschnitten ermöglicht. Von den drei genannten Versuchsreihen entwickelte die ’Rotationsdominierten’ Reihe einen rautenförmiger Block im Tranferbereich der beiden Riftsegmente, der sich um 5−20° im Uhrzeigersinn drehte. DieserWinkel liegt im Bereich des vermuteten Rotationswinkel des Rwenzori-Blocks (5°). Zusammengefasst untersuchen die Sandbox-Versuche den Einfluss präexistenter Strukturen und der Überlappung bzw. Überschneidung zweier interagierender Riftsegmente auf die Entwicklung des Riftsystems. Sie befassen sich darüber hinaus mit der Frage, welchen Einfluss Blockbildung und -rotation auf das lokale Stressfeld haben.

Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

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.

Entwicklung eines biologischen Verfahrens zur Reduktion des Methanschlupfes von Gasaufbereitungsanlagen mittels Einsatz methanotropher Mikroorganismen

Im Rahmen dieser Arbeit wurde ein biologisches Verfahren zur Reduzierung des Methanschlupfes in Gasaufbereitungsanlagen entwickelt. Der Methanschlupf entsteht, wenn das in Biogasanlagen produzierte Biogas auf normierte Erdgasqualität aufgereinigt wird, welches notwendig ist, um es in das bestehende Erdgasnetz einleiten zu können. Bei dieser Aufreinigung wird aus dem Biogas auch ein Teil des Methans mit ausgewaschen und gelangt mit dem Abgas der Gasaufbereitungsanlage in die Umwelt. Bisher wird dieses methanhaltige Abgas verbrannt, da eine Freisetzung des starken Treibhausgases Methan durch das Erneuerbare-Energien-Gesetz untersagt ist. Dies reduziert die ökologische Bilanz und setzt die Wirtschaftlichkeit der gesamten Biogasanlage herab. rnUm das Methan mit Hilfe eines biologischen Verfahrens zu entfernen, wurden zunächst methanoxidierende Bakterien (MOB) aus verschiedenen Habitaten isoliert, darunter auch erstmalig aus Termiten. Der Nachweis erfolgte durch (quantitative) Polymerase-Kettenreaktion und Fluoreszenz-in-situ-Hybridisierung anhand spezifischer Primer bzw. Sonden für das Gen der partikulären Methanmonoxygenase, ein MOB kennzeichnendes Enzym. Ihr Titer wurde durch qPCR auf 10^2 - 10^3 MOB pro Termitendarm durch qPCR bestimmt. Mit Hilfe einer 16S rDNA Sequenzierung, der (n)SAPD-PCR, der Bestimmung der zellulären Fettsäurezusammensetzung sowie MALDI-TOF-MS-Analysen konnten die Termitenisolate der Gattung Methylocystis zugeordnet werden. Die fehlende Artzuweisung spricht jedoch für die Isolierung einer neuen Art. rnFür den Einsatz der Isolate in Gasaufbereitungsanlagen wurde in Zusammenarbeit mit dem Prüf- und Forschungsinstitut in Pirmasens ein Reaktor im Technikumsmaßstab entwickelt und konstruiert. Der Reaktor wurde mit synthetischen Aufwuchskörper befüllt, diese mit einem neu gewonnenen potenten Termitenisolat besiedelt und der methanhaltige Abgasstrom der Gasaufbereitungsanlage darüber geleitet. Es wurde eine Reduktion des Methans um 68 % innerhalb von 30 Stunden erzielt. Medienoptimierungen wiesen das Potential auf, diesen Verbrauch um das bis zu 4-fache weiter zu steigern. Da durch die Oxidation des Methans im Abgasstrom der Gasaufbereitungsanlage Zellmasse und Polyhydroxybuttersäure (PHB) aufgebaut wurde, können diese als Substrat zurück in die Biogasanlagen geleitet werden und die Wirtschaftlichkeit weiter verbessern. Die Wirksamkeit des in diesem Projekt entwickelten Verfahrens wurde somit eindeutig demonstriert.

The FGFRL1 receptor is shed from cell membranes, binds fibroblast growth factors (FGFs), and antagonizes FGF signaling in Xenopus embryos

FGFRL1 (fibroblast growth factor receptor like 1) is the fifth and most recently discovered member of the fibroblast growth factor receptor (FGFR) family. With up to 50% amino acid similarity, its extracellular domain closely resembles that of the four conventional FGFRs. Its intracellular domain, however, lacks the split tyrosine kinase domain needed for FGF-mediated signal transduction. During embryogenesis of the mouse, FGFRL1 is essential for the development of parts of the skeleton, the diaphragm muscle, the heart, and the metanephric kidney. Since its discovery, it has been hypothesized that FGFRL1 might act as a decoy receptor for FGF ligands. Here we present several lines of evidence that support this notion. We demonstrate that the FGFRL1 ectodomain is shed from the cell membrane of differentiating C2C12 myoblasts and from HEK293 cells by an as yet unidentified protease, which cuts the receptor in the membrane-proximal region. As determined by ligand dot blot analysis, cell-based binding assays, and surface plasmon resonance analysis, the soluble FGFRL1 ectodomain as well as the membrane-bound receptor are capable of binding to some FGF ligands with high affinity, including FGF2, FGF3, FGF4, FGF8, FGF10, and FGF22. We furthermore show that ectopic expression of FGFRL1 in Xenopus embryos antagonizes FGFR signaling during early development. Taken together, our data provide strong evidence that FGFRL1 is indeed a decoy receptor for FGFs.

WASP plays a novel role in regulating platelet responses dependent on alphaIIbbeta3 integrin outside-in signalling

The most consistent feature of Wiskott Aldrich syndrome (WAS) is profound thrombocytopenia with small platelets. The responsible gene encodes WAS protein (WASP), which functions in leucocytes as an actin filament nucleating agent -yet- actin filament nucleation proceeds normally in patient platelets regarding shape change, filopodia and lamellipodia generation. Because WASP localizes in the platelet membrane skeleton and is mobilized by alphaIIbbeta3 integrin outside-in signalling, we questioned whether its function might be linked to integrin. Agonist-induced alphaIIbbeta3 activation (PAC-1 binding) was normal for patient platelets, indicating normal integrin inside-out signalling. Inside-out signalling (fibrinogen, JON/A binding) was also normal for wasp-deficient murine platelets. However, adherence/spreading on immobilized fibrinogen was decreased for patient platelets and wasp-deficient murine platelets, indicating decreased integrin outside-in responses. Another integrin outside-in dependent response, fibrin clot retraction, involving contraction of the post-aggregation actin cytoskeleton, was also decreased for patient platelets and wasp-deficient murine platelets. Rebleeding from tail cuts was more frequent for wasp-deficient mice, suggesting decreased stabilisation of the primary platelet plug. In contrast, phosphatidylserine exposure, a pro-coagulant response, was enhanced for WASP-deficient patient and murine platelets. The collective results reveal a novel function for WASP in regulating pro-aggregatory and pro-coagulant responses downstream of integrin outside-in signalling.

Fragmentation with a Cut on Thrust: Predictions for B-factories

When high-energy single-hadron production takes place inside an identified jet, there are important correlations between the fragmentation and phase-space cuts. For example, when one-hadron yields are measured in on-resonance B-factory data, a cut on the thrust event shape T is required to remove the large b-quark contribution. This leads to a dijet final-state restriction for the light-quark fragmentation process. Here, we complete our analysis of unpolarized fragmentation of (light) quarks and gluons to a light hadron h with energy fraction z in e+e−→dijet+h at the center-of-mass energy Q=10.58  GeV. In addition to the next-to-next-to-leading order resummation of the logarithms of 1−T, we include the next-to-leading order nonsingular