Antipodal random sequences with prescribed second-order statistics: application to Compressive Sensing and UWB system based on DS-CDMA

It is usual to hear a strange short sentence: «Random is better than...». Why is randomness a good solution to a certain engineering problem? There are many possible answers, and all of them are related to the considered topic. In this thesis I will discuss about two crucial topics that take advantage by randomizing some waveforms involved in signals manipulations. In particular, advantages are guaranteed by shaping the second order statistic of antipodal sequences involved in an intermediate signal processing stages. The first topic is in the area of analog-to-digital conversion, and it is named Compressive Sensing (CS). CS is a novel paradigm in signal processing that tries to merge signal acquisition and compression at the same time. Consequently it allows to direct acquire a signal in a compressed form. In this thesis, after an ample description of the CS methodology and its related architectures, I will present a new approach that tries to achieve high compression by design the second order statistics of a set of additional waveforms involved in the signal acquisition/compression stage. The second topic addressed in this thesis is in the area of communication system, in particular I focused the attention on ultra-wideband (UWB) systems. An option to produce and decode UWB signals is direct-sequence spreading with multiple access based on code division (DS-CDMA). Focusing on this methodology, I will address the coexistence of a DS-CDMA system with a narrowband interferer. To do so, I minimize the joint effect of both multiple access (MAI) and narrowband (NBI) interference on a simple matched filter receiver. I will show that, when spreading sequence statistical properties are suitably designed, performance improvements are possible with respect to a system exploiting chaos-based sequences minimizing MAI only.

Low Correlated Sequences & Architectures and Algorithms for Analog-to-Information Converters: Theory, Design, Implementation and Applications.

Most electronic systems can be described in a very simplified way as an assemblage of analog and digital components put all together in order to perform a certain function. Nowadays, there is an increasing tendency to reduce the analog components, and to replace them by operations performed in the digital domain. This tendency has led to the emergence of new electronic systems that are more flexible, cheaper and robust. However, no matter the amount of digital process implemented, there will be always an analog part to be sorted out and thus, the step of converting digital signals into analog signals and vice versa cannot be avoided. This conversion can be more or less complex depending on the characteristics of the signals. Thus, even if it is desirable to replace functions carried out by analog components by digital processes, it is equally important to do so in a way that simplifies the conversion from digital to analog signals and vice versa. In the present thesis, we have study strategies based on increasing the amount of processing in the digital domain in such a way that the implementation of analog hardware stages can be simplified. To this aim, we have proposed the use of very low quantized signals, i.e. 1-bit, for the acquisition and for the generation of particular classes of signals.

Seismic sequences analysis for estimation of earthquake source parameters: corner frequency, stress drop, and seismic moment observations

The present study has been carried out with the following objectives: i) To investigate the attributes of source parameters of local and regional earthquakes; ii) To estimate, as accurately as possible, M0, fc, Δσ and their standard errors to infer their relationship with source size; iii) To quantify high-frequency earthquake ground motion and to study the source scaling. This work is based on observational data of micro, small and moderate -earthquakes for three selected seismic sequences, namely Parkfield (CA, USA), Maule (Chile) and Ferrara (Italy). For the Parkfield seismic sequence (CA), a data set of 757 (42 clusters) repeating micro-earthquakes (0 ≤ MW ≤ 2), collected using borehole High Resolution Seismic Network (HRSN), have been analyzed and interpreted. We used the coda methodology to compute spectral ratios to obtain accurate values of fc , Δσ, and M0 for three target clusters (San Francisco, Los Angeles, and Hawaii) of our data. We also performed a general regression on peak ground velocities to obtain reliable seismic spectra of all earthquakes. For the Maule seismic sequence, a data set of 172 aftershocks of the 2010 MW 8.8 earthquake (3.7 ≤ MW ≤ 6.2), recorded by more than 100 temporary broadband stations, have been analyzed and interpreted to quantify high-frequency earthquake ground motion in this subduction zone. We completely calibrated the excitation and attenuation of the ground motion in Central Chile. For the Ferrara sequence, we calculated moment tensor solutions for 20 events from MW 5.63 (the largest main event occurred on May 20 2012), down to MW 3.2 by a 1-D velocity model for the crust beneath the Pianura Padana, using all the geophysical and geological information available for the area. The PADANIA model allowed a numerical study on the characteristics of the ground motion in the thick sediments of the flood plain.

Komparative Analyse der humanen Chromosomenregion 11p15.3 um die Gene LMO1,TUB und der orthologen Region in der Maus

Ziel der vorliegenden Arbeit war die vergleichende Sequenzierung und nachfolgende Analyse des syntänen chromosomalen Abschnitts auf dem kurzen Arm des humanen Chromosoms 11 in der Region 11p15.3 mit den Genen LMO1, TUB und dem orthologen Genomabschnitt der Maus auf Chromosom 7 F2. Die im Rahmen dieser Arbeit durchgeführte Kartierung dieser beiden chromosomalen Bereiche ermöglichte die Komplettierung einer genomischen Karte auf insgesamt über eine Megabase, die im Kooperationssequenzierprojekt der Universitäts-Kinderklinik und dem Institut für Molekulargenetik in Mainz erstellt wurde. Mit Hilfe von 28 PAC- und Cosmid-Klonen konnten in dieser Arbeit 383 kb an genomischer DNA des Menschen und mit sechs BAC- und PAC-Klonen 412 kb an genomischer DNA der Maus dargestellt werden. Dies ermöglichte erstmals die exakte Festlegung der Reihenfolge der in diesem chromosomalen Abschnitt enthaltenen Gene und die genaue Kartierung von acht STS-Markern des Menschen, bzw. vier STS-Sonden der Maus. Es zeigte sich dabei, dass die chromosomale Orientierung telomer-/centromerwärts des orthologen Bereichs in der Maus im Vergleich zum Menschen in invertierter Ausrichtung vorliegt. Die Sequenzierung von drei humanen Klonen ermöglichte die Bestimmung von 319.119 bp an zusammenhängender genomischer DNA. Dadurch konnte die genaue Lokalisation und Strukturaufklärung der Gene LMO1, ein putatives Tumorsuppressorgen, das mit der Entstehung von Leukämien assoziiert ist, und TUB, ein Transkriptionsmodulator, der in die Fettstoffwechselregulation involviert ist, vorgenommen werden. Für das murine Genom wurden 412.827 bp an neuer DNA-Sequenz durch Sequenzierung von ebenfalls drei Klonen generiert. Der im Vergleich zum Menschen ca. 100 kb größere Genombereich beinhaltete zudem die neuen Gene Stk33 und Eif3. Es handelte sich dabei um zwei Gene, die erst im Rahmen dieser Arbeit entdeckt und charakterisiert wurden. Die parallele Bearbeitung beider Genombereiche ermöglichte eine umfassende komparative Analyse nach kodierenden, funktionellen und strukturgebenden Sequenzabschnitten in beiden Spezies. Es konnten dabei für beide Organismen die Exon-Intron-Strukturen der Gene LMO1/Lmo1 und TUB/Tub geklärt. Zudem konnten vier neue Exons und zwei neue speziesspezifischer Spleißvarianten für TUB/Tub beschrieben werden. Die Identifizierung dieser neuen Spleißvarianten offenbart neue Möglichkeiten für alternative Regulation und Funktion, oder für eine veränderte Proteinstruktur, die weitere Erklärungsansätze für die Entstehung der mit diesen Genen assoziierten Erkrankungen zulässt. In der sequenzierten, größeren Genomsequenz der Maus konnte in den flankierenden, nicht mit der sequenzierten Humansequenz überlappenden Bereich das neue Gen Eif3 in seiner Exon-Intron-Struktur und die beiden letzten Exons 11 und 12 des Gens Stk33 kartiert und charakterisiert werden. Die umfangreiche Sequenzanalyse beider sequenzierter Genombereiche ergab für den Abschnitt des Menschen insgesamt 229 potentielle Exonsequenzen und für den Bereich der Maus 527 mögliche Exonbereiche. Davon konnten beim Menschen explizit 21 Exons und bei der Maus 31 Exons als exprimierte Bereiche identifiziert und experimentell mittels RT-PCR, bzw. durch cDNA-Sequenzierung verifiziert werden. Diese Abschnitte beschrieben nicht nur die Exonbereiche der oben genannten vier Gene, sondern konnten auch neuen nicht weiter definierten EST-Sequenzen zugeordnet werden. Mittels des Interspeziesvergleiches war darüber hinaus auch die Analyse der nichtkodierenden Intergen-Bereiche möglich. So konnten beispielsweise im ersten Intron des LMO1/Lmo1 sieben Sequenzbereiche mit Konservierungen von ca. 90% bestimmt werden. Auch die Charakterisierung von Promotor- und putativ regulatorischen Sequenzabschnitten konnte mit Hilfe unterschiedlicher bioinformatischer Analyse-Tools durchgeführt werden. Die konservierten Sequenzbereiche der DNA zeigen im Durchschnitt eine Homologie von mehr als 65% auf. Auch die Betrachtung der Genomorganisation zeigte Gemeinsamkeiten, die sich meist nur in ihrer graduellen Ausprägung unterschieden. So weist ein knapp 80 kb großer Bereich proximal zum humanen TUB-Gen einen deutlich erhöhten AT-Gehalt auf, der ebenso im murinen Genom nur in verkürzter Version und schwächer ausgeprägt in Erscheinung tritt. Die zusätzliche Vergleichsanalyse mit einer weiteren Spezies, den orthologen Genomabschnitten von Fugu, zeigte, dass es sich bei den untersuchten Genen LMO1 und TUB um sehr konservierte und evolutiv alte Gene handelt, deren genomisches Organisationsmuster sich auch bei den paralogen Genfamilienmitglieder innerhalb derselben Spezies wiederfindet. Insgesamt konnte durch die Kartierung, Sequenzierung und Analyse eine umfassende Datenbasis für die betrachtete Genomregion und die beschriebenen Gene generiert werden, die für zukünftige Untersuchungen und Fragestellungen wertvolle Informationen bereithält.

Charakterisierung einer pflanzlichen Variante des Cytoskelettproteins gamma-Tubulin durch Strukturmodellierung, Überexpression und Analyse der Interaktionspartner

Wie alle Eukaryoten besitzen auch höhere Pflanzen ein mikrotubuläres Cytoskelett. Einige Funktionen dieses Cytoskeletts sind relativ stark konserviert, andere dagegen scheinen sehr pflanzenspezifisch zu sein. Dies betrifft insbesondere charakteristische mikrotubuläre Netzwerke, die bei der Neubildung und der Verstärkung der Zellwände wichtige Rollen übernehmen. Wie der Aufbau dieser Netzwerke kontrolliert wird, ist bisher relativ unklar. Typische Mikrotubuli organisierende Zentren (MTOC), insbesondere Centrosomen oder Spindelpolkörper, sind bei höheren Pflanzen nicht beobachtet worden. Von pilzlichen und tierischen Organismen weiß man, dass gamma-Tubulin (gTUB) mit seinen assoziierten Proteinen in den MTOC bei der Nukleation von Mikrotubuli eine Schlüsselfunktion hat. Dieses Mitglied der Tubulin-Superfamilie wird aber auch in Pflanzen gefunden, dessen genaue Funktion bisher unbekannt ist. Zu Beginn der Arbeit wurden mittels in silico Berechnungen Strukturmodelle des pflanzlichen gTUBs aus Nicotiana tabacum erarbeitet, da die Struktur, die zu einem Verständnis der pflanzlichen Wachstumsregulation beitragen könnte, bisher unbekannt ist. Auf Grundlage der bioinformatischen Daten konnte für weitere Studien eine notwendige gTUB-Deletionsmutante entwickelt werden. Für Röntgendiffraktionsstudien und gTUB-Interaktionspartneranalysen war die Verfügbarkeit verhältnismäßig großer Proteinmengen notwendig. Die Expression der gTUB-Volllängensequenz in gelöster und aktiver Form stellte einen immanent wichtigen Zwischenschritt dar. Das Escherichia coli T7/lacO-Expressionssystem lieferte, trotz vielversprechender Erfolge in der Vergangenheit, kein gelöstes rekombinantes gTUB. So wurden zwar verhältnismäßig hohe Expressionsraten erzielt, aber das rekombinante gTUB lag quantitativ als Inclusion bodies vor. Eine Variationen der Expressionsparameter sowie umfangreiche Versuche mittels verschiedenster Konstrukte sowie potentiell die Löslichkeit erhöhenden Tags gTUB in gelöster Form in E. coli zu exprimieren blieben erfolglos. Eine Denaturierung der Inclusion bodies und Rückfaltung wurde aufgrund der wohl bei der Tubulinfaltung notwendigen komplexeren Chaperone sowie thermodynamischer Überlegungen ausgeschlossen. Die höher evolvierte Chaperonausstattung war ein Hauptgrund für die Verwendung der eukaryotischen Hefe-Expressionssysteme K. lactis und des S. cerevisiae-Stammes FGY217 zur gTUB-Expression. So konnten nach der Selektion nur transgene Hefe-Zellen dokumentiert werden, die die gTUB-Expressionskassette nachweislich an der vorgesehenen Zielposition in ihrem Genom integrierten, aber keine dokumentierbare Expression zeigten. Die wahrscheinlichste Begründung hierfür ist, dass ein erhöhter intrazellulärer gTUB-Titer mit dem Zellwachstum und der Zellteilung dieser eukaryotischen Organismen interferierte und durch Rückkopplungen die rekombinante gTUB-CDS aus N. tabacum ausgeschaltet wurde. Der Versuch einer transienten gTUB-Überexpression in differenzierten Blattgeweben höherer Pflanzen war eine logische Konsequenz aus den vorherigen Ergebnissen und lieferte, wenn auch nicht die für eine Proteinkristallisation notwendigen Mengen, gelöstes gTUB. Bestrebungen einer stabilen Transfektion von A. thaliana oder BY-2-Zellkulturen mit einer gTUB-CDS lieferten keine transgenen Organismen, was starke Interferenzen der rekombinanten gTUB-CDS in den Zellen vermuten lies. Transfektionsversuche mit nur GFP tragenden Konstrukten ergaben hingegen eine hohe Anzahl an transgenen Organismen, die auch verhältnismäßig starke Expressionsraten zeigten. Die erzielten Proteinmengen bei der transienten gTUB-Überexpression in N. benthamiana Blattgeweben, in Co-Expression mit dem Posttransriptional Gene Silencing-Suppressorprotein p19, waren für einen Pull-Down sowie eine massenspektroskopische Analyse der Interaktionspartner ausreichend und ergaben Befunde. Eine abschließende Auswertung des erarbeiteten massenspektroskopischen Datensatzes wird jedoch erst dann möglich sein, wenn das Tabak-Proteom vollständig sequenziert ist. Die Erweiterung der bestehenden pflanzlichen Vergleichsdatenbanken um das bisher bekannte Tabak-Proteom vervielfachte die Anzahl der in dieser Studie identifizierten gTUB-Interaktionspartner. Interaktionen mit dem TCP1-Chaperon untermauern die Hypothese der zur Faltung pflanzlichen gTUBs notwendigen Chaperone. Beobachtete gTUB-Degradationsmuster in Verbindung mit Interaktionen des 26S-Proteasoms deuten auf eine Gegenregulationen bei erhöhtem gTUB-Titer auf Proteinebene hin. Da Blattgewebe selbst nur noch über eine sehr geringe und inhomogene Teilungsaktivität verfügen ist diese Regulation hoch spannend. Auch konnte durch Co-Expression des PTGS-Suppressorproteins p19 gezeigt werden, dass bei der gTUB-Expression eine Regulation auf RNA-Ebene erfolgt.

Statistical methods for the analysis of DNA sequences: application to dinucleotide distribution in the human genome

Questa tesi si inserisce nell'ambito delle analisi statistiche e dei metodi stocastici applicati all'analisi delle sequenze di DNA. Nello specifico il nostro lavoro è incentrato sullo studio del dinucleotide CG (CpG) all'interno del genoma umano, che si trova raggruppato in zone specifiche denominate CpG islands. Queste sono legate alla metilazione del DNA, un processo che riveste un ruolo fondamentale nella regolazione genica. La prima parte dello studio è dedicata a una caratterizzazione globale del contenuto e della distribuzione dei 16 diversi dinucleotidi all'interno del genoma umano: in particolare viene studiata la distribuzione delle distanze tra occorrenze successive dello stesso dinucleotide lungo la sequenza. I risultati vengono confrontati con diversi modelli nulli: sequenze random generate con catene di Markov di ordine zero (basate sulle frequenze relative dei nucleotidi) e uno (basate sulle probabilità di transizione tra diversi nucleotidi) e la distribuzione geometrica per le distanze. Da questa analisi le proprietà caratteristiche del dinucleotide CpG emergono chiaramente, sia dal confronto con gli altri dinucleotidi che con i modelli random. A seguito di questa prima parte abbiamo scelto di concentrare le successive analisi in zone di interesse biologico, studiando l’abbondanza e la distribuzione di CpG al loro interno (CpG islands, promotori e Lamina Associated Domains). Nei primi due casi si osserva un forte arricchimento nel contenuto di CpG, e la distribuzione delle distanze è spostata verso valori inferiori, indicando che questo dinucleotide è clusterizzato. All’interno delle LADs si trovano mediamente meno CpG e questi presentano distanze maggiori. Infine abbiamo adottato una rappresentazione a random walk del DNA, costruita in base al posizionamento dei dinucleotidi: il walk ottenuto presenta caratteristiche drasticamente diverse all’interno e all’esterno di zone annotate come CpG island. Riteniamo pertanto che metodi basati su questo approccio potrebbero essere sfruttati per migliorare l’individuazione di queste aree di interesse nel genoma umano e di altri organismi.

Extraktion und nanoanalytische Charakterisierung refraktärer Nanometallpartikel frühester solarer Materie und Synthese metallischer Nanopartikel aus dotierten Ca-Mg-Al-Si-Schmelzen

Primitive kohlige Chondrite sind Meteorite, die seit ihrer Entstehung im frühen Sonnensystem kaum verändert wurden und dadurch einen Einblick in Prozesse geben, die zur Bildung und Veränderung der ersten festen Materie führten. Solche Prozesse können anhand von Bruchstücken dieser Meteorite detailliert im Labor studiert werden, sodass Rückschlüsse auf die Entwicklung unseres Sonnensystems im frühen Stadium getroffen werden können. Ca-, Al-reiche Einschlüsse (CAIs) aus chondritischen Meteoriten sind die ersten Festkörper des Sonnensystems und enthalten viele refraktäre Metallnuggets (RMNs), welche hauptsächlich aus den Elementen Os, Ir, Ru, Mo und Pt bestehen. Nach weit verbreiteter Ansicht sind diese Nuggets wahrscheinlich im Gleichgewicht mit dem solaren Nebel kondensiert, bereits früher oder gleichzeitig mit Oxiden und Silikaten. Die exakten Mechanismen, die zu ihren heute beobachteten Eigenschaften führten, sind allerdings unklar. Um frühere Arbeiten fortzuführen, wurde eine hohe Anzahl RMNs in vier unterschiedlichen Typen von Meteoriten detailliert studiert, darunter solche aus dem nahezu unveränderten Acfer 094, Allende (CV3ox), Leoville (CV3red) und Murchison (CM2). Die RMNs wurden in-situ, assoziiert mit ihren Wirtsmineralen und auch in Säurerückständen gefunden, deren Präparationsprozedur in dieser Arbeit speziell für RMNs durch eine zusätzliche Dichtetrennung verbessert wurde.rnDie Ergebnisse decken eine Reihe von Ungereimtheiten zwischen den beobachteten RMN-Eigenschaften und einer Kondensationsherkunft auf, sowohl für Kondensation in solarer Umgebung, als auch für Kondensation aus Material von Supernovae oder roten Riesen, für die die Kondensationssequenzen refraktärer Metalle speziell für diesen Vergleich berechnet wurden. Stattdessen wurden in dieser Arbeit neue Einblicke in die RMN-Entstehung und die Entwicklung der ersten Festkörper (CAIs) durch eine Kombination aus experimentellen, isotopischen, strukturellen und petrologischen Studien an RMNs gewonnen. Viele der beobachteten Eigenschaften sind mit Ausfällung der RMN aus einer CAI-Schmelze vereinbar. Ein solches Szenario wird durch entsprechende Untersuchungen an synthetisch hergestellten, mit refraktären Metallen im Gleichgewicht stehenden CAI-Schmelzen bestätigt. Es folgt aus den Ergebnissen, dass die Mehrzahl der RMNs isotopisch solar ist und alle untersuchten RMNs innerhalb von CAIs bei rascher Abkühlung (um bis zu 1000 °C/40 sek.) einer CAI-Schmelze gebildet wurden. rn

Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Exact quantum Monte Carlo methods for correlated electron systems

Thema dieser Arbeit ist die Entwicklung und Kombination verschiedener numerischer Methoden, sowie deren Anwendung auf Probleme stark korrelierter Elektronensysteme. Solche Materialien zeigen viele interessante physikalische Eigenschaften, wie z.B. Supraleitung und magnetische Ordnung und spielen eine bedeutende Rolle in technischen Anwendungen. Es werden zwei verschiedene Modelle behandelt: das Hubbard-Modell und das Kondo-Gitter-Modell (KLM). In den letzten Jahrzehnten konnten bereits viele Erkenntnisse durch die numerische Lösung dieser Modelle gewonnen werden. Dennoch bleibt der physikalische Ursprung vieler Effekte verborgen. Grund dafür ist die Beschränkung aktueller Methoden auf bestimmte Parameterbereiche. Eine der stärksten Einschränkungen ist das Fehlen effizienter Algorithmen für tiefe Temperaturen.rnrnBasierend auf dem Blankenbecler-Scalapino-Sugar Quanten-Monte-Carlo (BSS-QMC) Algorithmus präsentieren wir eine numerisch exakte Methode, die das Hubbard-Modell und das KLM effizient bei sehr tiefen Temperaturen löst. Diese Methode wird auf den Mott-Übergang im zweidimensionalen Hubbard-Modell angewendet. Im Gegensatz zu früheren Studien können wir einen Mott-Übergang bei endlichen Temperaturen und endlichen Wechselwirkungen klar ausschließen.rnrnAuf der Basis dieses exakten BSS-QMC Algorithmus, haben wir einen Störstellenlöser für die dynamische Molekularfeld Theorie (DMFT) sowie ihre Cluster Erweiterungen (CDMFT) entwickelt. Die DMFT ist die vorherrschende Theorie stark korrelierter Systeme, bei denen übliche Bandstrukturrechnungen versagen. Eine Hauptlimitation ist dabei die Verfügbarkeit effizienter Störstellenlöser für das intrinsische Quantenproblem. Der in dieser Arbeit entwickelte Algorithmus hat das gleiche überlegene Skalierungsverhalten mit der inversen Temperatur wie BSS-QMC. Wir untersuchen den Mott-Übergang im Rahmen der DMFT und analysieren den Einfluss von systematischen Fehlern auf diesen Übergang.rnrnEin weiteres prominentes Thema ist die Vernachlässigung von nicht-lokalen Wechselwirkungen in der DMFT. Hierzu kombinieren wir direkte BSS-QMC Gitterrechnungen mit CDMFT für das halb gefüllte zweidimensionale anisotrope Hubbard Modell, das dotierte Hubbard Modell und das KLM. Die Ergebnisse für die verschiedenen Modelle unterscheiden sich stark: während nicht-lokale Korrelationen eine wichtige Rolle im zweidimensionalen (anisotropen) Modell spielen, ist in der paramagnetischen Phase die Impulsabhängigkeit der Selbstenergie für stark dotierte Systeme und für das KLM deutlich schwächer. Eine bemerkenswerte Erkenntnis ist, dass die Selbstenergie sich durch die nicht-wechselwirkende Dispersion parametrisieren lässt. Die spezielle Struktur der Selbstenergie im Impulsraum kann sehr nützlich für die Klassifizierung von elektronischen Korrelationseffekten sein und öffnet den Weg für die Entwicklung neuer Schemata über die Grenzen der DMFT hinaus.

Computing primal solutions with exact arithmetics in SCIP.

The research for exact solutions of mixed integer problems is an active topic in the scientific community. State-of-the-art MIP solvers exploit a floating- point numerical representation, therefore introducing small approximations. Although such MIP solvers yield reliable results for the majority of problems, there are cases in which a higher accuracy is required. Indeed, it is known that for some applications floating-point solvers provide falsely feasible solutions, i.e. solutions marked as feasible because of approximations that would not pass a check with exact arithmetic and cannot be practically implemented. The framework of the current dissertation is SCIP, a mixed integer programs solver mainly developed at Zuse Institute Berlin. In the same site we considered a new approach for exactly solving MIPs. Specifically, we developed a constraint handler to plug into SCIP, with the aim to analyze the accuracy of provided floating-point solutions and compute exact primal solutions starting from floating-point ones. We conducted a few computational experiments to test the exact primal constraint handler through the adoption of two main settings. Analysis mode allowed to collect statistics about current SCIP solutions' reliability. Our results confirm that floating-point solutions are accurate enough with respect to many instances. However, our analysis highlighted the presence of numerical errors of variable entity. By using the enforce mode, our constraint handler is able to suggest exact solutions starting from the integer part of a floating-point solution. With the latter setting, results show a general improvement of the quality of provided final solutions, without a significant loss of performances.

Regular and exact categories

Lo scopo del lavoro è quello di presentare alcune proprietà di base delle categorie regolari ed esatte nel contesto della teoria delle categoria algebrica.