Algoritmi esatti per il Job Shop Scheduling: approcci Mathematical Programming

In questa tesi ci occuperemo di fornire un modello MIP di base e di alcune sue varianti, realizzate allo scopo di comprenderne il comportamento ed eventualmente migliorarne l’efficienza. Le diverse varianti sono state costruite agendo in particolar modo sulla definizione di alcuni vincoli, oppure sui bound delle variabili, oppure ancora nell’obbligare il risolutore a focalizzarsi su determinate decisioni o specifiche variabili. Sono stati testati alcuni dei problemi tipici presenti in letteratura e i diversi risultati sono stati opportunamente valutati e confrontati. Tra i riferimenti per tale confronto sono stati considerati anche i risultati ottenibili tramite un modello Constraint Programming, che notoriamente produce risultati apprezzabili in ambito di schedulazione. Un ulteriore scopo della tesi è, infatti, comparare i due approcci Mathematical Programming e Constraint Programming, identificandone quindi i pregi e gli svantaggi e provandone la trasferibilità al modello raffrontato.

Mathematical Modeling to Investigate Antiarrhythmic Drug Side Effects: Rate-Dependence Role in Ionic Currents and Action Potentials Shape in the O’Hara Model

Sudden cardiac death due to ventricular arrhythmia is one of the leading causes of mortality in the world. In the last decades, it has proven that anti-arrhythmic drugs, which prolong the refractory period by means of prolongation of the cardiac action potential duration (APD), play a good role in preventing of relevant human arrhythmias. However, it has long been observed that the “class III antiarrhythmic effect” diminish at faster heart rates and that this phenomenon represent a big weakness, since it is the precise situation when arrhythmias are most prone to occur. It is well known that mathematical modeling is a useful tool for investigating cardiac cell behavior. In the last 60 years, a multitude of cardiac models has been created; from the pioneering work of Hodgkin and Huxley (1952), who first described the ionic currents of the squid giant axon quantitatively, mathematical modeling has made great strides. The O’Hara model, that I employed in this research work, is one of the modern computational models of ventricular myocyte, a new generation began in 1991 with ventricular cell model by Noble et al. Successful of these models is that you can generate novel predictions, suggest experiments and provide a quantitative understanding of underlying mechanism. Obviously, the drawback is that they remain simple models, they don’t represent the real system. The overall goal of this research is to give an additional tool, through mathematical modeling, to understand the behavior of the main ionic currents involved during the action potential (AP), especially underlining the differences between slower and faster heart rates. In particular to evaluate the rate-dependence role on the action potential duration, to implement a new method for interpreting ionic currents behavior after a perturbation effect and to verify the validity of the work proposed by Antonio Zaza using an injected current as a perturbing effect.

Modeling and simulation of a synthetic genetic circuit that implements a multicelled behavior in a growing microcolony of E. coli

Synthetic Biology is a relatively new discipline, born at the beginning of the New Millennium, that brings the typical engineering approach (abstraction, modularity and standardization) to biotechnology. These principles aim to tame the extreme complexity of the various components and aid the construction of artificial biological systems with specific functions, usually by means of synthetic genetic circuits implemented in bacteria or simple eukaryotes like yeast. The cell becomes a programmable machine and its low-level programming language is made of strings of DNA. This work was performed in collaboration with researchers of the Department of Electrical Engineering of the University of Washington in Seattle and also with a student of the Corso di Laurea Magistrale in Ingegneria Biomedica at the University of Bologna: Marilisa Cortesi. During the collaboration I contributed to a Synthetic Biology project already started in the Klavins Laboratory. In particular, I modeled and subsequently simulated a synthetic genetic circuit that was ideated for the implementation of a multicelled behavior in a growing bacterial microcolony. In the first chapter the foundations of molecular biology are introduced: structure of the nucleic acids, transcription, translation and methods to regulate gene expression. An introduction to Synthetic Biology completes the section. In the second chapter is described the synthetic genetic circuit that was conceived to make spontaneously emerge, from an isogenic microcolony of bacteria, two different groups of cells, termed leaders and followers. The circuit exploits the intrinsic stochasticity of gene expression and intercellular communication via small molecules to break the symmetry in the phenotype of the microcolony. The four modules of the circuit (coin flipper, sender, receiver and follower) and their interactions are then illustrated. In the third chapter is derived the mathematical representation of the various components of the circuit and the several simplifying assumptions are made explicit. Transcription and translation are modeled as a single step and gene expression is function of the intracellular concentration of the various transcription factors that act on the different promoters of the circuit. A list of the various parameters and a justification for their value closes the chapter. In the fourth chapter are described the main characteristics of the gro simulation environment, developed by the Self Organizing Systems Laboratory of the University of Washington. Then, a sensitivity analysis performed to pinpoint the desirable characteristics of the various genetic components is detailed. The sensitivity analysis makes use of a cost function that is based on the fraction of cells in each one of the different possible states at the end of the simulation and the wanted outcome. Thanks to a particular kind of scatter plot, the parameters are ranked. Starting from an initial condition in which all the parameters assume their nominal value, the ranking suggest which parameter to tune in order to reach the goal. Obtaining a microcolony in which almost all the cells are in the follower state and only a few in the leader state seems to be the most difficult task. A small number of leader cells struggle to produce enough signal to turn the rest of the microcolony in the follower state. It is possible to obtain a microcolony in which the majority of cells are followers by increasing as much as possible the production of signal. Reaching the goal of a microcolony that is split in half between leaders and followers is comparatively easy. The best strategy seems to be increasing slightly the production of the enzyme. To end up with a majority of leaders, instead, it is advisable to increase the basal expression of the coin flipper module. At the end of the chapter, a possible future application of the leader election circuit, the spontaneous formation of spatial patterns in a microcolony, is modeled with the finite state machine formalism. The gro simulations provide insights into the genetic components that are needed to implement the behavior. In particular, since both the examples of pattern formation rely on a local version of Leader Election, a short-range communication system is essential. Moreover, new synthetic components that allow to reliably downregulate the growth rate in specific cells without side effects need to be developed. In the appendix are listed the gro code utilized to simulate the model of the circuit, a script in the Python programming language that was used to split the simulations on a Linux cluster and the Matlab code developed to analyze the data.

A mathematical introduction to Kerr black holes

Lo scopo della tesi è descrivere i buchi neri di Kerr. Dopo aver introdotto tutti gli strumenti matematici necessari quali tensori, vettori di Killing e geodetiche, enunceremo la metrica di Kerr, il teorema no-hair e il frame-dragging. In seguito, a partire dalla metrica di Kerr, calcoleremo e descriveremo le ergosfere, gli orizzonti degli eventi e il moto dei fotoni nel piano equatoriale.

Keller-Segel system, chemotaxis and applications to a mathematical model for Alzheimer's disease

In questa tesi viene presentato il modello di Keller-Segel per la chemiotassi, un sistema di tipo parabolico-ellittico che appare nella descrizione di molti fenomeni in ambito biologico e medico. Viene mostrata l'esistenza globale della soluzione debole del modello, per dati iniziali sufficientemente piccoli in dimensione N>2. La scelta di dati iniziali abbastanza grandi invece può causare il blow-up della soluzione e viene mostrato sotto quali condizioni questo si verifica. Infine il modello della chemiotassi è stato applicato per descrivere una fase della malattia di Alzheimer ed è stata effettuata un'analisi di stabilità del sistema.

Mathematical modelling of integrin-like receptors systems

Nel presente lavoro, ho studiato e trovato le soluzioni esatte di un modello matematico applicato ai recettori cellulari della famiglia delle integrine. Nel modello le integrine sono considerate come un sistema a due livelli, attivo e non attivo. Quando le integrine si trovano nello stato inattivo possono diffondere nella membrana, mentre quando si trovano nello stato attivo risultano cristallizzate nella membrana, incapaci di diffondere. La variazione di concentrazione nella superficie cellulare di una sostanza chiamata attivatore dà luogo all’attivazione delle integrine. Inoltre, questi eterodimeri possono legare una molecola inibitrice con funzioni di controllo e regolazione, che chiameremo v, la quale, legandosi al recettore, fa aumentare la produzione della sostanza attizzatrice, che chiameremo u. In questo modo si innesca un meccanismo di retroazione positiva. L’inibitore v regola il meccanismo di produzione di u, ed assume, pertanto, il ruolo di modulatore. Infatti, grazie a questo sistema di fine regolazione il meccanismo di feedback positivo è in grado di autolimitarsi. Si costruisce poi un modello di equazioni differenziali partendo dalle semplici reazioni chimiche coinvolte. Una volta che il sistema di equazioni è impostato, si possono desumere le soluzioni per le concentrazioni dell’inibitore e dell’attivatore per un caso particolare dei parametri. Infine, si può eseguire un test per vedere cosa predice il modello in termini di integrine. Per farlo, ho utilizzato un’attivazione del tipo funzione gradino e l’ho inserita nel sistema, valutando la dinamica dei recettori. Si ottiene in questo modo un risultato in accordo con le previsioni: le integrine legate si trovano soprattutto ai limiti della zona attivata, mentre le integrine libere vengono a mancare nella zona attivata.

Estensione dell'Abstraction Layer di DTNperf alle API di IBR-DTN

Sono dette “challenged networks” quelle reti in cui lunghi ritardi, frequenti partizionamenti e interruzioni, elevati tassi di errore e di perdita non consentono l’impiego dei classici protocolli di comunicazione di Internet, in particolare il TCP/IP. Il Delay-/Disruption-Tolerant Networking (DTN) è una soluzione per il trasferimento di dati attraverso queste reti. L’architettura DTN prevede l’introduzione, sopra il livello di trasporto, del cosiddetto “bundle layer”, che si occupa di veicolare messaggi, o bundle, secondo l’approccio store-and-forward: ogni nodo DTN conserva persistentemente un bundle finché non si presenta l’opportunità di inoltrarlo al nodo successivo verso la destinazione. Il protocollo impiegato nel bundle layer è il Bundle Protocol, le cui principali implementazioni sono tre: DTN2, l’implementazione di riferimento; ION, sviluppata da NASA-JPL e più orientata alle comunicazioni spaziali; IBR-DTN, rivolta soprattutto a dispositivi embedded. Ciascuna di esse offre API che consentono la scrittura di applicazioni in grado di inviare e ricevere bundle. DTNperf è uno strumento progettato per la valutazione delle prestazioni in ambito DTN. La più recente iterazione, DTNperf_3, è compatibile sia con DTN2 che con ION nella stessa versione del programma, grazie all’introduzione di un “Abstraction Layer” che fornisce un’unica interfaccia per l’interazione con le diverse implementazioni del Bundle Protocol e che solo internamente si occupa di invocare le API specifiche dell’implementazione attiva. Obiettivo della tesi è estendere l’Abstraction Layer affinché supporti anche IBR-DTN, cosicché DTNperf_3 possa essere impiegato indifferentemente su DTN2, ION e IBR DTN. Il lavoro sarà ripartito su tre fasi: nella prima esploreremo IBR DTN e le sue API; nella seconda procederemo all’effettiva estensione dell’Abstraction Layer; nella terza verificheremo il funzionamento di DTNperf a seguito delle modifiche, sia in ambiente esclusivamente IBR-DTN, sia ibrido.

Mathematical models for cellular aggregation: the chemotactic instability and clustering formation

In this thesis we present a mathematical formulation of the interaction between microorganisms such as bacteria or amoebae and chemicals, often produced by the organisms themselves. This interaction is called chemotaxis and leads to cellular aggregation. We derive some models to describe chemotaxis. The first is the pioneristic Keller-Segel parabolic-parabolic model and it is derived by two different frameworks: a macroscopic perspective and a microscopic perspective, in which we start with a stochastic differential equation and we perform a mean-field approximation. This parabolic model may be generalized by the introduction of a degenerate diffusion parameter, which depends on the density itself via a power law. Then we derive a model for chemotaxis based on Cattaneo's law of heat propagation with finite speed, which is a hyperbolic model. The last model proposed here is a hydrodynamic model, which takes into account the inertia of the system by a friction force. In the limit of strong friction, the model reduces to the parabolic model, whereas in the limit of weak friction, we recover a hyperbolic model. Finally, we analyze the instability condition, which is the condition that leads to aggregation, and we describe the different kinds of aggregates we may obtain: the parabolic models lead to clusters or peaks whereas the hyperbolic models lead to the formation of network patterns or filaments. Moreover, we discuss the analogy between bacterial colonies and self gravitating systems by comparing the chemotactic collapse and the gravitational collapse (Jeans instability).

A mathematical model of the early visual system and border completion via subriemannian Hamiltonian geodesics

In this thesis, we aim to discuss a simple mathematical model for the edge detection mechanism and the boundary completion problem in the human brain in a differential geometry framework. We describe the columnar structure of the primary visual cortex as the fiber bundle R2 × S1, the orientation bundle, and by introducing a first vector field on it, explain the edge detection process. Edges are detected through a lift from the domain in R2 into the manifold R2 × S1 and are horizontal to a completely non-integrable distribution. Therefore, we can construct a subriemannian structure on the manifold R2 × S1, through which we retrieve perceived smooth contours as subriemannian geodesics, solutions to Hamilton’s equations. To do so, in the first chapter, we illustrate the functioning of the most fundamental structures of the early visual system in the brain, from the retina to the primary visual cortex. We proceed with introducing the necessary concepts of differential and subriemannian geometry in chapters two and three. We finally implement our model in chapter four, where we conclude, comparing our results with the experimental findings of Heyes, Fields, and Hess on the existence of an association field.

Development of a heterogeneous clustering algorithm for particle shower reconstruction in high energy physics using the SYCL abstraction layer

Nei prossimi anni è atteso un aggiornamento sostanziale di LHC, che prevede di aumentare la luminosità integrata di un fattore 10 rispetto a quella attuale. Tale parametro è proporzionale al numero di collisioni per unità di tempo. Per questo, le risorse computazionali necessarie a tutti i livelli della ricostruzione cresceranno notevolmente. Dunque, la collaborazione CMS ha cominciato già da alcuni anni ad esplorare le possibilità offerte dal calcolo eterogeneo, ovvero la pratica di distribuire la computazione tra CPU e altri acceleratori dedicati, come ad esempio schede grafiche (GPU). Una delle difficoltà di questo approccio è la necessità di scrivere, validare e mantenere codice diverso per ogni dispositivo su cui dovrà essere eseguito. Questa tesi presenta la possibilità di usare SYCL per tradurre codice per la ricostruzione di eventi in modo che sia eseguibile ed efficiente su diversi dispositivi senza modifiche sostanziali. SYCL è un livello di astrazione per il calcolo eterogeneo, che rispetta lo standard ISO C++. Questo studio si concentra sul porting di un algoritmo di clustering dei depositi di energia calorimetrici, CLUE, usando oneAPI, l'implementazione SYCL supportata da Intel. Inizialmente, è stato tradotto l'algoritmo nella sua versione standalone, principalmente per prendere familiarità con SYCL e per la comodità di confronto delle performance con le versioni già esistenti. In questo caso, le prestazioni sono molto simili a quelle di codice CUDA nativo, a parità di hardware. Per validare la fisica, l'algoritmo è stato integrato all'interno di una versione ridotta del framework usato da CMS per la ricostruzione. I risultati fisici sono identici alle altre implementazioni mentre, dal punto di vista delle prestazioni computazionali, in alcuni casi, SYCL produce codice più veloce di altri livelli di astrazione adottati da CMS, presentandosi dunque come una possibilità interessante per il futuro del calcolo eterogeneo nella fisica delle alte energie.

Problems in physics and mathematics contexts with middle and high school classes: vertical and horizontal comparison

My thesis falls within the framework of physics education and teaching of mathematics. The objective of this report was made possible by using geometrical (in mathematics) and qualitative (in physics) problems. We have prepared four (resp. three) open answer exercises for mathematics (resp. physics). The test batch has been selected across two different school phases: end of the middle school (third year, 8\textsuperscript{th} grade) and beginning of high school (second and third year, 10\textsuperscript{th} and 11\textsuperscript{th} grades respectively). High school students achieved the best results in almost every problem, but 10\textsuperscript{th} grade students got the best overall results. Moreover, a clear tendency to not even try qualitative problems resolution has emerged from the first collection of graphs, regardless of subject and grade. In order to improve students' problem-solving skills, it is worth to invest on vertical learning and spiral curricula. It would make sense to establish a stronger and clearer connection between physics and mathematical knowledge through an interdisciplinary approach.