Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

The massless two-loop two-point function and zeta functions in counterterms of Feynman diagrams

The main part of this thesis describes a method of calculating the massless two-loop two-point function which allows expanding the integral up to an arbitrary order in the dimensional regularization parameter epsilon by rewriting it as a double Mellin-Barnes integral. Closing the contour and collecting the residues then transforms this integral into a form that enables us to utilize S. Weinzierl's computer library nestedsums. We could show that multiple zeta values and rational numbers are sufficient for expanding the massless two-loop two-point function to all orders in epsilon. We then use the Hopf algebra of Feynman diagrams and its antipode, to investigate the appearance of Riemann's zeta function in counterterms of Feynman diagrams in massless Yukawa theory and massless QED. The class of Feynman diagrams we consider consists of graphs built from primitive one-loop diagrams and the non-planar vertex correction, where the vertex corrections only depend on one external momentum. We showed the absence of powers of pi in the counterterms of the non-planar vertex correction and diagrams built by shuffling it with the one-loop vertex correction. We also found the invariance of some coefficients of zeta functions under a change of momentum flow through these vertex corrections.

Statistical Mechanics of Monomer-Dimer Models on Complete and Erdös-Rényi Graphs

Nella tesi sono trattate due famiglie di modelli meccanico statistici su vari grafi: i modelli di spin ferromagnetici (o di Ising) e i modelli di monomero-dimero. Il primo capitolo è dedicato principalmente allo studio del lavoro di Dembo e Montanari, in cui viene risolto il modello di Ising su grafi aleatori. Nel secondo capitolo vengono studiati i modelli di monomero-dimero, a partire dal lavoro di Heilemann e Lieb,con l'intento di dare contributi nuovi alla teoria. I principali temi trattati sono disuguaglianze di correlazione, soluzioni esatte su alcuni grafi ad albero e sul grafo completo, la concentrazione dell'energia libera intorno al proprio valor medio sul grafo aleatorio diluito di Erdös-Rényi.

Elektromagnetische Pionproduktion in manifest Lorentz-invarianter baryonischer chiraler Störungstheorie

In dieser Arbeit wurde die elektromagnetische Pionproduktion unter der Annahme der Isospinsymmetrie der starken Wechselwirkung im Rahmen der manifest Lorentz-invarianten chiralen Störungstheorie in einer Einschleifenrechnung bis zur Ordnung vier untersucht. Dazu wurden auf der Grundlage des Mathematica-Pakets FeynCalc Algorithmen zur Berechnung der Pionproduktionsamplitude entwickelt. Bis einschließlich der Ordnung vier tragen insgesamt 105 Feynmandiagramme bei, die sich in 20 Baumdiagramme und 85 Schleifendiagramme unterteilen lassen. Von den 20 Baumdiagrammen wiederum sind 16 als Polterme und vier als Kontaktgraphen zu klassifizieren; bei den Schleifendiagrammen tragen 50 Diagramme ab der dritten Ordnung und 35 Diagramme ab der vierten Ordnung bei. In der Einphotonaustauschnäherung lässt sich die Pionproduktionsamplitude als ein Produkt des Polarisationsvektors des (virtuellen) Photons und des Übergangsstrommatrixelements parametrisieren, wobei letzteres alle Abhängigkeiten der starken Wechselwirkung beinhaltet und wo somit die chirale Störungstheorie ihren Eingang findet. Der Polarisationsvektor hingegen hängt von dem leptonischen Vertex und dem Photonpropagator ab und ist aus der QED bekannt. Weiterhin lässt sich das Übergangsstrommatrixelement in sechs eichinvariante Amplituden zerlegen, die sich im Rahmen der Isospinsymmetrie jeweils wiederum in drei Isospinamplituden zerlegen lassen. Linearkombinationen dieser Isospinamplituden erlauben letztlich die Beschreibung der physikalischen Amplituden. Die in dieser Rechnung auftretenden Einschleifenintegrale wurden numerisch mittels des Programms LoopTools berechnet. Im Fall tensorieller Integrale erfolgte zunächst eine Zerlegung gemäß der Methode von Passarino und Veltman. Da die somit erhaltenen Ergebnisse jedoch i.a. noch nicht das chirale Zählschema erfüllen, wurde die entsprechende Renormierung mittels der reformulierten Infrarotregularisierung vorgenommen. Zu diesem Zweck wurde ein Verfahren entwickelt, welches die Abzugsterme automatisiert bestimmt. Die schließlich erhaltenen Isospinamplituden wurden in das Programm MAID eingebaut. In diesem Programm wurden als Test (Ergebnisse bis Ordnung drei) die s-Wellenmultipole E_{0+} und L_{0+} in der Schwellenregion berechnet. Die Ergebnisse wurden sowohl mit Messdaten als auch mit den Resultaten des "klassischen" MAID verglichen, wobei sich i. a. gute Übereinstimmungen im Rahmen der Fehler ergaben.

Learning with Kernels on Graphs: DAG-based kernels, data streams and RNA function prediction.

In many application domains data can be naturally represented as graphs. When the application of analytical solutions for a given problem is unfeasible, machine learning techniques could be a viable way to solve the problem. Classical machine learning techniques are defined for data represented in a vectorial form. Recently some of them have been extended to deal directly with structured data. Among those techniques, kernel methods have shown promising results both from the computational complexity and the predictive performance point of view. Kernel methods allow to avoid an explicit mapping in a vectorial form relying on kernel functions, which informally are functions calculating a similarity measure between two entities. However, the definition of good kernels for graphs is a challenging problem because of the difficulty to find a good tradeoff between computational complexity and expressiveness. Another problem we face is learning on data streams, where a potentially unbounded sequence of data is generated by some sources. There are three main contributions in this thesis. The first contribution is the definition of a new family of kernels for graphs based on Directed Acyclic Graphs (DAGs). We analyzed two kernels from this family, achieving state-of-the-art results from both the computational and the classification point of view on real-world datasets. The second contribution consists in making the application of learning algorithms for streams of graphs feasible. Moreover,we defined a principled way for the memory management. The third contribution is the application of machine learning techniques for structured data to non-coding RNA function prediction. In this setting, the secondary structure is thought to carry relevant information. However, existing methods considering the secondary structure have prohibitively high computational complexity. We propose to apply kernel methods on this domain, obtaining state-of-the-art results.

A multi-objective genetic algorithm optimisation using variable speed pumps in water distribution systems

Due to its practical importance and inherent complexity, the optimisation of distribution networks for supplying drinking water has been the subject of extensive study for the past 30 years. The optimization is governed by sizing the pipes in the water distribution network (WDN) and / or optimises specific parts of the network such as pumps, tanks etc. or try to analyse and optimise the reliability of a WDN. In this thesis, the author has analysed two different WDNs (Anytown City and Cabrera city networks), trying to solve and optimise a multi-objective optimisation problem (MOOP). The main two objectives in both cases were the minimisation of Energy Cost (€) or Energy consumption (kWh), along with the total Number of pump switches (TNps) during a day. For this purpose, a decision support system generator for Multi-objective optimisation used. Its name is GANetXL and has been developed by the Center of Water System in the University of Exeter. GANetXL, works by calling the EPANET hydraulic solver, each time a hydraulic analysis has been fulfilled. The main algorithm used, was a second-generation algorithm for multi-objective optimisation called NSGA_II that gave us the Pareto fronts of each configuration. The first experiment that has been carried out was the network of Anytown city. It is a big network with a pump station of four fixed speed parallel pumps that are boosting the water dynamics. The main intervention was to change these pumps to new Variable speed driven pumps (VSDPs), by installing inverters capable to diverse their velocity during the day. Hence, it’s been achieved great Energy and cost savings along with minimisation in the number of pump switches. The results of the research are thoroughly illustrated in chapter 7, with comments and a variety of graphs and different configurations. The second experiment was about the network of Cabrera city. The smaller WDN had a unique FS pump in the system. The problem was the same as far as the optimisation process was concerned, thus, the minimisation of the energy consumption and in parallel the minimisation of TNps. The same optimisation tool has been used (GANetXL).The main scope was to carry out several and different experiments regarding a vast variety of configurations, using different pump (but this time keeping the FS mode), different tank levels, different pipe diameters and different emitters coefficient. All these different modes came up with a large number of results that were compared in the chapter 8. Concluding, it should be said that the optimisation of WDNs is a very interested field that has a vast space of options to deal with. This includes a large number of algorithms to choose from, different techniques and configurations to be made and different support system generators. The researcher has to be ready to “roam” between these choices, till a satisfactory result will convince him/her that has reached a good optimisation point.

Abflusslose Senken – Instrumente in der Landschaftsanalyse und Indikatoren rezenter Krustenbewegungen

Innerhalb des Untersuchungsgebiets Schleswig-Holstein wurden 39.712 topographische Hohlformen detektiert. Genutzt wurden dazu ESRI ArcMap 9.3 und 10.0. Der Datenaufbereitung folgten weitere Kalkulationen in MATLAB R2010b. Jedes Objekt wurde räumlich mit seinen individuellen Eigenschaften verschnitten. Dazu gehörten Fläche, Umfang, Koordinaten (Zentroide), Tiefe und maximale Tiefe der Hohlform und Formfaktoren wie Rundheit, Konvexität und Elongation. Ziel der vorgestellten Methoden war die Beantwortung von drei Fragestellungen: Sind negative Landformen dazu geeignet Landschaftseinheiten und Eisvorstöße zu unterscheiden und zu bestimmen? Existiert eine Kopplung von Depressionen an der rezenten Topographie zu geologischen Tiefenstrukturen? Können Senken unterschiedlicher Entstehung anhand ihrer Formcharakteristik unterteilt werden? Die vorgenommene Klassifikation der großen Landschaftseinheiten basiert auf der Annahme, dass sowohl Jungmoränengebiete, ihre Vorflächen als auch Altmoränengebiete durch charakteristische, abflusslose Hohlformen, wie Toteislöcher, Seen, etc. abgegrenzt werden können. Normalerweise sind solche Depressionen in der Natur eher selten, werden jedoch für ehemalige Glaziallandschaften als typisch erachtet. Ziel war es, die geologischen Haupteinheiten, Eisvorstöße und Moränengebiete der letzten Vereisungen zu differenzieren. Zur Bearbeitung wurde ein Detektionsnetz verwendet, das auf quadratischen Zellen beruht. Die Ergebnisse zeigen, dass durch die alleinige Nutzung von Depressionen zur Klassifizierung von Landschaftseinheiten Gesamtgenauigkeiten von bis zu 71,4% erreicht werden können. Das bedeutet, dass drei von vier Detektionszellen korrekt zugeordnet werden können. Jungmoränen, Altmoränen, periglazialeVorflächen und holozäne Bereiche können mit Hilfe der Hohlformen mit großer Sicherheit voneinander unterschieden und korrekt zugeordnet werden. Dies zeigt, dass für die jeweiligen Einheiten tatsächlich bestimmte Senkenformen typisch sind. Die im ersten Schritt detektierten Senken wurden räumlich mit weiterreichenden geologischen Informationen verschnitten, um zu untersuchen, inwieweit natürliche Depressionen nur glazial entstanden sind oder ob ihre Ausprägung auch mit tiefengeologischen Strukturen in Zusammenhang steht. 25.349 (63,88%) aller Senken sind kleiner als 10.000 m² und liegen in Jungmoränengebieten und können vermutlich auf glaziale und periglaziale Einflüsse zurückgeführt werden. 2.424 Depressionen liegen innerhalb der Gebiete subglazialer Rinnen. 1.529 detektierte Hohlformen liegen innerhalb von Subsidenzgebieten, von denen 1.033 innerhalb der Marschländer im Westen verortet sind. 919 große Strukturen über 1 km Größe entlang der Nordsee sind unter anderem besonders gut mit Kompaktionsbereichen elsterzeitlicher Rinnen zu homologisieren.344 dieser Hohlformen sind zudem mit Tunneltälern im Untergrund assoziiert. Diese Parallelität von Depressionen und den teils über 100 m tiefen Tunneltälern kann auf Sedimentkompaktion zurückgeführt werden. Ein Zusammenhang mit der Zersetzung postglazialen, organischen Materials ist ebenfalls denkbar. Darüber hinaus wurden in einer Distanz von 10 km um die miozän aktiven Flanken des Glückstadt-Grabens negative Landformen detektiert, die Verbindungen zu oberflächennahen Störungsstrukturen zeigen. Dies ist ein Anzeichen für Grabenaktivität während und gegen Ende der Vereisung und während des Holozäns. Viele dieser störungsbezogenen Senken sind auch mit Tunneltälern assoziiert. Entsprechend werden drei zusammenspielende Prozesse identifiziert, die mit der Entstehung der Hohlformen in Verbindung gebracht werden können. Eine mögliche Interpretation ist, dass die östliche Flanke des Glückstadt-Grabens auf die Auflast des elsterzeitlichen Eisschilds reagierte, während sich subglazial zeitgleich Entwässerungsrinnen entlang der Schwächezonen ausbildeten. Diese wurden in den Warmzeiten größtenteils durch Torf und unverfestigte Sedimente verfüllt. Die Gletschervorstöße der späten Weichselzeit aktivierten erneut die Flanken und zusätzlich wurde das Lockermaterial exariert, wodurch große Seen, wie z. B. der Große Plöner See entstanden sind. Insgesamt konnten 29 große Depressionen größer oder gleich 5 km in Schleswig-Holstein identifiziert werden, die zumindest teilweise mit Beckensubsidenz und Aktivität der Grabenflanken verbunden sind, bzw. sogar auf diese zurückgehen.Die letzte Teilstudie befasste sich mit der Differenzierung von Senken nach deren potentieller Genese sowie der Unterscheidung natürlicher von künstlichen Hohlformen. Dazu wurde ein DEM für einen Bereich im Norden Niedersachsens verwendet, das eine Gesamtgröße von 252 km² abdeckt. Die Ergebnisse zeigen, dass glazial entstandene Depressionen gute Rundheitswerte aufweisen und auch Elongation und Exzentrizität eher kompakte Formen anzeigen. Lineare negative Strukturen sind oft Flüsse oder Altarme. Sie können als holozäne Strukturen identifiziert werden. Im Gegensatz zu den potentiell natürlichen Senkenformen sind künstlich geschaffene Depressionen eher eckig oder ungleichmäßig und tendieren meist nicht zu kompakten Formen. Drei Hauptklassen topographischer Depressionen konnten identifiziert und voneinander abgegrenzt werden: Potentiell glaziale Senken (Toteisformen), Flüsse, Seiten- und Altarme sowie künstliche Senken. Die Methode der Senkenklassifikation nach Formparametern ist ein sinnvolles Instrument, um verschiedene Typen unterscheiden zu können und um bei geologischen Fragestellungen künstliche Senken bereits vor der Verarbeitung auszuschließen. Jedoch zeigte sich, dass die Ergebnisse im Wesentlichen von der Auflösung des entsprechenden Höhenmodells abhängen.

Spectral theory of differential operators on finite metric graphs and on bounded domains

Die vorliegende Arbeit widmet sich der Spektraltheorie von Differentialoperatoren auf metrischen Graphen und von indefiniten Differentialoperatoren auf beschränkten Gebieten. Sie besteht aus zwei Teilen. Im Ersten werden endliche, nicht notwendigerweise kompakte, metrische Graphen und die Hilberträume von quadratintegrierbaren Funktionen auf diesen betrachtet. Alle quasi-m-akkretiven Laplaceoperatoren auf solchen Graphen werden charakterisiert, und Abschätzungen an die negativen Eigenwerte selbstadjungierter Laplaceoperatoren werden hergeleitet. Weiterhin wird die Wohlgestelltheit eines gemischten Diffusions- und Transportproblems auf kompakten Graphen durch die Anwendung von Halbgruppenmethoden untersucht. Eine Verallgemeinerung des indefiniten Operators $-tfrac{d}{dx}sgn(x)tfrac{d}{dx}$ von Intervallen auf metrische Graphen wird eingeführt. Die Spektral- und Streutheorie der selbstadjungierten Realisierungen wird detailliert besprochen. Im zweiten Teil der Arbeit werden Operatoren untersucht, die mit indefiniten Formen der Art $langlegrad v, A(cdot)grad urangle$ mit $u,vin H_0^1(Omega)subset L^2(Omega)$ und $OmegasubsetR^d$ beschränkt, assoziiert sind. Das Eigenwertverhalten entspricht in Dimension $d=1$ einer verallgemeinerten Weylschen Asymptotik und für $dgeq 2$ werden Abschätzungen an die Eigenwerte bewiesen. Die Frage, wann indefinite Formmethoden für Dimensionen $dgeq 2$ anwendbar sind, bleibt offen und wird diskutiert.

Le collocazioni in traduzione e interpretazione tra italiano e francese: Uno studio su eptic_01_2011

This dissertation aims at investigating differences in phraseological patterns in translated and interpreted language, on the basis of the intermodal corpus EPTIC_01_2011 and focusing on Italian and French. First of all, an overview is offered of the main studies and theories about corpus linguistics and collocations: the notion of corpus is defined and a typology (focusing on intermodal corpora) is presented, before moving on to the linguistic phenomenon of collocation and its investigation through corpus linguistics methods. Second, the general structure of EPTIC_01_2011 is presented, including the ways in which its texts have been assembled, edited through ad hoc conventions and enriched with metadata. The methodology proposed by Durrant and Schmitt (2009), slightly edited to fit the present study, has been used to extract and compare noun+adjective/adjective+noun bigrams from a quantitative point of view. A subset of these data have then been extracted and analysed manually. The results of the study are presented through graphs and examples, with an in-depth discussion of the bigrams considered. Lastly, the data collected are analysed and categorised in terms of shifts occurring in translation and in interpreting, potential causes are discussed and ideas for further research and for the development of the EPTIC corpus are sketched.

Le collocazioni in traduzione e interpretazione tra italiano e inglese: Uno studio su eptic_01_2011

The aim of this dissertation is to investigate the differences in the phraseological patterns used by Italian and English translators and interpreters through the intermodal corpus EPTIC_01_2011. First, the most important studies and theories about corpus linguistics and collocations are introduced. After defining the notion of “corpus”, the different types of corpora are categorised, giving particular attention to the intermodal one. Then the dissertation focuses on a description of collocations, as defined by the main linguistics scholars, and it describes some attempts to apply corpus linguistics to the study of collocations. Secondly, EPTIC_01_2011 is presented, with a description of its structure and of the text editing process carried out applying specific editing conventions and adding a set of metadata before each text. The analysis of collocation candidate bigrams (adjective+noun/noun+adjective) from a quantitative point of view, was conducted applying a methodology adapted from Durrant and Schmitt (2009). Qualitative analysis was also performed on a subsection of the data. The results of the study are presented through examples and graphs, giving particular attention to the interpretation of the data analysed from a qualitative perspective. Finally, results are summarised and categorised, and suggestions are made concerning the diverging choices made in translation and interpreting. The final section concentrates on further studies that could be carried out in the future, as well as on suggestions for corpus enlargement.

Laplace operator on finite graphs and a network diffusion model for the progression of the Alzheimer disease

Nella tesi viene descritto il Network Diffusion Model, ovvero il modello di A. Ray, A. Kuceyeski, M. Weiner inerente i meccanismi di progressione della demenza senile. In tale modello si approssima l'encefalo sano con una rete cerebrale (ovvero un grafo pesato), si identifica un generale fattore di malattia e se ne analizza la propagazione che avviene secondo meccanismi analoghi a quelli di un'infezione da prioni. La progressione del fattore di malattia e le conseguenze macroscopiche di tale processo(tra cui principalmente l'atrofia corticale) vengono, poi, descritte mediante approccio matematico. I risultati teoretici vengono confrontati con quanto osservato sperimentalmente in pazienti affetti da demenza senile. Nella tesi, inoltre, si fornisce una panoramica sui recenti studi inerenti i processi neurodegenerativi e si costruisce il contesto matematico di riferimento del modello preso in esame. Si presenta una panoramica sui grafi finiti, si introduce l'operatore di Laplace sui grafi e si forniscono stime dall'alto e dal basso per gli autovalori. Al fine di costruire una cornice matematica completa si analizza la relazione tra caso discreto e continuo: viene descritto l'operatore di Laplace-Beltrami sulle varietà riemanniane compatte e vengono fornite stime dall'alto per gli autovalori dell'operatore di Laplace-Beltrami associato a tali varietà a partire dalle stime dall'alto per gli autovalori del laplaciano sui grafi finiti.

Embedding Spatial Software Visualization in the IDE: an Exploratory Study

Software visualization can be of great use for understanding and exploring a software system in an intuitive manner. Spatial representation of software is a promising approach of increasing interest. However, little is known about how developers interact with spatial visualizations that are embedded in the IDE. In this paper, we present a pilot study that explores the use of Software Cartography for program comprehension of an unknown system. We investigated whether developers establish a spatial memory of the system, whether clustering by topic offers a sound base layout, and how developers interact with maps. We report our results in the form of observations, hypotheses, and implications. Key findings are a) that developers made good use of the map to inspect search results and call graphs, and b) that developers found the base layout surprising and often confusing. We conclude with concrete advice for the design of embedded software maps