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.

Hypersurfaces with many singularities

1. Teil: Bekannte Konstruktionen. Die vorliegende Arbeit gibt zunächst einen ausführlichen Überblick über die bisherigen Entwicklungen auf dem klassischen Gebiet der Hyperflächen mit vielen Singularitäten. Die maximale Anzahl mu^n(d) von Singularitäten auf einer Hyperfläche vom Grad d im P^n(C) ist nur in sehr wenigen Fällen bekannt, im P^3(C) beispielsweise nur für d<=6. Abgesehen von solchen Ausnahmen existieren nur obere und untere Schranken. 2. Teil: Neue Konstruktionen. Für kleine Grade d ist es oft möglich, bessere Resultate zu erhalten als jene, die durch allgemeine Schranken gegeben sind. In dieser Arbeit beschreiben wir einige algorithmische Ansätze hierfür, von denen einer Computer Algebra in Charakteristik 0 benutzt. Unsere anderen algorithmischen Methoden basieren auf einer Suche über endlichen Körpern. Das Liften der so experimentell gefundenen Hyperflächen durch Ausnutzung ihrer Geometrie oder Arithmetik liefert beispielsweise eine Fläche vom Grad 7 mit $99$ reellen gewöhnlichen Doppelpunkten und eine Fläche vom Grad 9 mit 226 gewöhnlichen Doppelpunkten. Diese Konstruktionen liefern die ersten unteren Schranken für mu^3(d) für ungeraden Grad d>5, die die allgemeine Schranke übertreffen. Unser Algorithmus hat außerdem das Potential, auf viele weitere Probleme der algebraischen Geometrie angewendet zu werden. Neben diesen algorithmischen Methoden beschreiben wir eine Konstruktion von Hyperflächen vom Grad d im P^n mit vielen A_j-Singularitäten, j>=2. Diese Beispiele, deren Existenz wir mit Hilfe der Theorie der Dessins d'Enfants beweisen, übertreffen die bekannten unteren Schranken in den meisten Fällen und ergeben insbesondere neue asymptotische untere Schranken für j>=2, n>=3. 3. Teil: Visualisierung. Wir beschließen unsere Arbeit mit einer Anwendung unserer neuen Visualisierungs-Software surfex, die die Stärken mehrerer existierender Programme bündelt, auf die Konstruktion affiner Gleichungen aller 45 topologischen Typen reeller kubischer Flächen.

Climate signatures in corals of the tropical-temperate transition zone (Late Miocene, Crete/Greece)

The present study describes a Late Miocene (early Tortonian - early Messinian) transitional carbonate system that combines elements of tropical and cool-water carbonate systems (Irakleion Basin, island of Crete, Greece). As documented by stratal geometries, the submarine topography of the basin was controlled by tilting blocks. Coral reefs formed by Porites and Tarbellastrea occurred in a narrow clastic coastal belt along a „central Cretan landmass“, and steep escarpments formed by faulting. Extensive covers of level-bottom communities existed in a low-energy environment on the gentle dip-slope ramps of the blocks that show the widest geographical distribution within the basin. Consistent patterns of landward and basinward shift of coastal onlap in all outcrop studies reveal an overriding control of 3rd and 4th order sea level changes on sediment dynamics and facies distributions over block movements. An increasingly dry climate and the complex submarine topography of the fault block mosaic kept sediment and nutrient discharge at a minimum. The skeletal limestone facies therefore reflects oligotrophic conditions and a sea surface temperature (SST) near the lower threshold temperature of coral reefs in a climatic position transitional between the tropical coral reef belt and the temperate zone. Stable isotope records (δ18O, δ13C) from massiv, exceptionally preserved Late Miocene aragonite coral skeletons reflect seasonal changes in sea surface temperature and symbiont autotrophy. Spectral analysis of a 69 years coral δ18O record reveals significant variance at interannual time scales (5-6 years) that matches the present-day eastern Mediterranean climate variability controlled by the Arctic Oscillation/North Atlantic Oscillation (AO/NAO), the Northern Hemisphere’s dominant mode of atmospheric variability. Supported by simulations with a complex atmospheric general circulation model coupled to a mixed-layer ocean model, it is suggested, that climate dynamics in the eastern Mediterranean and central Europe reflect atmospheric variability related to the Icelandic Low 10 million years ago. Usually, Miocene corals are transformed in calcite spar in geological time and isotope values are reset by diagenetic alteration. It is demonstrated that the relicts of growth bands represent an intriguing source of information for the growth conditions of fossil corals. Recrystallized growth bands were measured systematically in massive Porites from Crete. The Late Miocene corals were growing slowly with 2-4 mm/yr, compatible with present-day Porites from high latitude reefs, a relationship that fits the position of Crete at the margin of the Miocene tropical reef belt. Over Late Miocene time (Tortonian - early Messinian) growth rates remained remarkably constant, and if the modern growth temperature relationship for massive Porites applies to the Neogene, minimum (winter) SST did not exceed 19-21°C.

Existence of solutions and asymtptotic limits of the Euler-Poisson and the quantum drift-diffusion systems

My work concerns two different systems of equations used in the mathematical modeling of semiconductors and plasmas: the Euler-Poisson system and the quantum drift-diffusion system. The first is given by the Euler equations for the conservation of mass and momentum, with a Poisson equation for the electrostatic potential. The second one takes into account the physical effects due to the smallness of the devices (quantum effects). It is a simple extension of the classical drift-diffusion model which consists of two continuity equations for the charge densities, with a Poisson equation for the electrostatic potential. Using an asymptotic expansion method, we study (in the steady-state case for a potential flow) the limit to zero of the three physical parameters which arise in the Euler-Poisson system: the electron mass, the relaxation time and the Debye length. For each limit, we prove the existence and uniqueness of profiles to the asymptotic expansion and some error estimates. For a vanishing electron mass or a vanishing relaxation time, this method gives us a new approach in the convergence of the Euler-Poisson system to the incompressible Euler equations. For a vanishing Debye length (also called quasineutral limit), we obtain a new approach in the existence of solutions when boundary layers can appear (i.e. when no compatibility condition is assumed). Moreover, using an iterative method, and a finite volume scheme or a penalized mixed finite volume scheme, we numerically show the smallness condition on the electron mass needed in the existence of solutions to the system, condition which has already been shown in the literature. In the quantum drift-diffusion model for the transient bipolar case in one-space dimension, we show, by using a time discretization and energy estimates, the existence of solutions (for a general doping profile). We also prove rigorously the quasineutral limit (for a vanishing doping profile). Finally, using a new time discretization and an algorithmic construction of entropies, we prove some regularity properties for the solutions of the equation obtained in the quasineutral limit (for a vanishing pressure). This new regularity permits us to prove the positivity of solutions to this equation for at least times large enough.

Pore structure and column efficiency of silica monoliths in high performance liquid chromatography (HPLC)

Five different methods were critically examined to characterize the pore structure of the silica monoliths. The mesopore characterization was performed using: a) the classical BJH method of nitrogen sorption data, which showed overestimated values in the mesopore distribution and was improved by using the NLDFT method, b) the ISEC method implementing the PPM and PNM models, which were especially developed for monolithic silicas, that contrary to the particulate supports, demonstrate the two inflection points in the ISEC curve, enabling the calculation of pore connectivity, a measure for the mass transfer kinetics in the mesopore network, c) the mercury porosimetry using a new recommended mercury contact angle values. rnThe results of the characterization of mesopores of monolithic silica columns by the three methods indicated that all methods were useful with respect to the pore size distribution by volume, but only the ISEC method with implemented PPM and PNM models gave the average pore size and distribution based on the number average and the pore connectivity values.rnThe characterization of the flow-through pore was performed by two different methods: a) the mercury porosimetry, which was used not only for average flow-through pore value estimation, but also the assessment of entrapment. It was found that the mass transfer from the flow-through pores to mesopores was not hindered in case of small sized flow-through pores with a narrow distribution, b) the liquid penetration where the average flow-through pore values were obtained via existing equations and improved by the additional methods developed according to Hagen-Poiseuille rules. The result was that not the flow-through pore size influences the column bock pressure, but the surface area to volume ratio of silica skeleton is most decisive. Thus the monolith with lowest ratio values will be the most permeable. rnThe flow-through pore characterization results obtained by mercury porosimetry and liquid permeability were compared with the ones from imaging and image analysis. All named methods enable a reliable characterization of the flow-through pore diameters for the monolithic silica columns, but special care should be taken about the chosen theoretical model.rnThe measured pore characterization parameters were then linked with the mass transfer properties of monolithic silica columns. As indicated by the ISEC results, no restrictions in mass transfer resistance were noticed in mesopores due to their high connectivity. The mercury porosimetry results also gave evidence that no restrictions occur for mass transfer from flow-through pores to mesopores in the small scaled silica monoliths with narrow distribution. rnThe prediction of the optimum regimes of the pore structural parameters for the given target parameters in HPLC separations was performed. It was found that a low mass transfer resistance in the mesopore volume is achieved when the nominal diameter of the number average size distribution of the mesopores is appr. an order of magnitude larger that the molecular radius of the analyte. The effective diffusion coefficient of an analyte molecule in the mesopore volume is strongly dependent on the value of the nominal pore diameter of the number averaged pore size distribution. The mesopore size has to be adapted to the molecular size of the analyte, in particular for peptides and proteins. rnThe study on flow-through pores of silica monoliths demonstrated that the surface to volume of the skeletons ratio and external porosity are decisive for the column efficiency. The latter is independent from the flow-through pore diameter. The flow-through pore characteristics by direct and indirect approaches were assessed and theoretical column efficiency curves were derived. The study showed that next to the surface to volume ratio, the total porosity and its distribution of the flow-through pores and mesopores have a substantial effect on the column plate number, especially as the extent of adsorption increases. The column efficiency is increasing with decreasing flow through pore diameter, decreasing with external porosity, and increasing with total porosity. Though this tendency has a limit due to heterogeneity of the studied monolithic samples. We found that the maximum efficiency of the studied monolithic research columns could be reached at a skeleton diameter of ~ 0.5 µm. Furthermore when the intention is to maximize the column efficiency, more homogeneous monoliths should be prepared.rn

Topological aspects of the human protein interaction network

It is currently widely accepted that the understanding of complex cell functions depends on an integrated network theoretical approach and not on an isolated view of the different molecular agents. Aim of this thesis was the examination of topological properties that mirror known biological aspects by depicting the human protein network with methods from graph- and network theory. The presented network is a partial human interactome of 9222 proteins and 36324 interactions, consisting of single interactions reliably extracted from peer-reviewed scientific publications. In general, one can focus on intra- or intermodular characteristics, where a functional module is defined as "a discrete entity whose function is separable from those of other modules". It is found that the presented human network is also scale-free and hierarchically organised, as shown for yeast networks before. The interactome also exhibits proteins with high betweenness and low connectivity which are biologically analyzed and interpreted here as shuttling proteins between organelles (e.g. ER to Golgi, internal ER protein translocation, peroxisomal import, nuclear pores import/export) for the first time. As an optimisation for finding proteins that connect modules, a new method is developed here based on proteins located between highly clustered regions, rather than regarding highly connected regions. As a proof of principle, the Mediator complex is found in first place, the prime example for a connector complex. Focusing on intramodular aspects, the measurement of k-clique communities discriminates overlapping modules very well. Twenty of the largest identified modules are analysed in detail and annotated to known biological structures (e.g. proteasome, the NFκB-, TGF-β complex). Additionally, two large and highly interconnected modules for signal transducer and transcription factor proteins are revealed, separated by known shuttling proteins. These proteins yield also the highest number of redundant shortcuts (by calculating the skeleton), exhibit the highest numbers of interactions and might constitute highly interconnected but spatially separated rich-clubs either for signal transduction or for transcription factors. This design principle allows manifold regulatory events for signal transduction and enables a high diversity of transcription events in the nucleus by a limited set of proteins. Altogether, biological aspects are mirrored by pure topological features, leading to a new view and to new methods that assist the annotation of proteins to biological functions, structures and subcellular localisations. As the human protein network is one of the most complex networks at all, these results will be fruitful for other fields of network theory and will help understanding complex network functions in general.

Effects of temperature and acidity on Mediterranean benthic calcifiers, in the face of globale climate change

The Mediterranean Sea is expected to react faster to global change compared to the ocean and is already showing more pronounced warming and acidification rates. A study performed along the Italian western coast showed that porosity of the skeleton increases with temperature in the zooxanthellate (i.e. symbiotic with unicellular algae named zooxanthellae) solitary scleractinian Balanophyllia europaea while it does not vary with temperature in the solitary non-zooxanthellate Leptopsammia pruvoti. These results were confirmed by another study that indicated that the increase in porosity was accompanied by an increase of the fraction of the largest pores in the pore-space, perhaps due to an inhibition of the photosynthetic process at elevated temperatures, causing an attenuation of calcification. B. europaea, L. pruvoti and the colonial non-zooxanthellate Astroides calycularis, transplanted along a natural pH gradient, showed that high temperature exacerbated the negative effect of lowered pH on their mortality rates. The growth of the zooxanthellate species did not react to reduced pH, while the growth of the two non-zooxanthellate species was negatively affected. Reduced abundance of naturally occurring B. europaea, a mollusk, a calcifying and a non-calcifying macroalgae were observed along the gradient while no variation was seen in the abundance of a calcifying green alga. With decreasing pH, the mineralogy of the coral and mollusk did not change, while the two calcifying algae decreased the content of aragonite in favor of the less soluble calcium sulphates and whewellite (calcium oxalate), possibly as a mechanism of phenotypic plasticity. Increased values of porosity and macroporosity with CO2 were observed in B. europaea specimens, indicating reduces the resistance of its skeletons to mechanical stresses with increasing acidity. These findings, added to the negative effect of temperature on various biological parameters, generate concern on the sensitivity of this zooxanthellate species to the envisaged global climate change scenarios.

Networks, Uncertainty, Applications and a Crusade for Optimality

In this thesis we address a collection of Network Design problems which are strongly motivated by applications from Telecommunications, Logistics and Bioinformatics. In most cases we justify the need of taking into account uncertainty in some of the problem parameters, and different Robust optimization models are used to hedge against it. Mixed integer linear programming formulations along with sophisticated algorithmic frameworks are designed, implemented and rigorously assessed for the majority of the studied problems. The obtained results yield the following observations: (i) relevant real problems can be effectively represented as (discrete) optimization problems within the framework of network design; (ii) uncertainty can be appropriately incorporated into the decision process if a suitable robust optimization model is considered; (iii) optimal, or nearly optimal, solutions can be obtained for large instances if a tailored algorithm, that exploits the structure of the problem, is designed; (iv) a systematic and rigorous experimental analysis allows to understand both, the characteristics of the obtained (robust) solutions and the behavior of the proposed algorithm.

Biomineralization in calcifying marine organisms

The objective of this theses is to contribute to the wide discussion about the biological control level on the biomineralization operated by calcifying organisms. In particular the intra-crystalline organic matrix associated with different coral species was studied and its role in the process was investigated. The main goals obtained from the research on corals included: (i) the discovery of the species specific role of the intra-crystalline organic matrix molecules in the precipitation of calcium carbonate; (ii) the definition of the role of magnesium ions in the control of the macromolecules assembly/aggregation and in the consequent calcium carbonate polymorphic selectivity; (iii) the discovery that in corals the biomineralization process is not affected by the sea water acidity, as consequence corals are able to construct their skeletons independently from the environmental conditions as far they survive. At the same time, investigations on different kind of vaterite, biogenic and synthetic, were also carried out and confirm the importance of the organism control on the biomineralization process and in particular on the co-existence of different crystalline structures of vaterite for enabling optimization of specific functions, through the employment of OM and acidic macromolecules.

New synthetic strategies towards indolizines and pyrroles

Indolizines and pyrroles are considered as “privileged” structures since their skeletons were found in many biologically active natural products and they possess a wide range of pharmaceutical properties. Syntheses of these small drug-like molecules are very important in medicinal chemistry. However, most existent methodologies are usually limited to specific substitution patterns or require impractical starting materials or expensive catalysts. Therefore, developing new methodologies for the synthesis of indolizines and pyrroles from commercially available or readily accessible sources is highly desirable.rnIn this PhD thesis, several methods has been described for the synthesis of indolizines and pyrroles. In the first part, indolizines carrying substituents in positions 1-3 were synthesized via a formal [3+2]-cycloaddition of pyridinium ylides and nitroalkenes. Pyridinium salts were prepared by N-alkylation of pyridines with cyanohydrin triflates which could be prepared from corresponding aldehydes via a Strecker reaction followed by O-triflylation. Nitroalkenes were simply prepared from the corresponding aldehydes and nitroalkanes in a nitroaldol condensation. Overall, this modular approach allows to construct the indolizine framework with various substitution patterns starting from a pyridine, two different aldehydes and a nitroalkane. In contrast to reported methods, the produced indolizines do not have to contain an electron-withdrawing group.rnIt has also been found that nitrile-stabilized 2-alkylpyridinium ylides cyclize to unstable 2-aminoindolizines via an intramolecular 5-exo-dig cyclization. Using an in situ acetylation of the amino group, N-protected 2-aminoindolizines could be synthesized. As a less common substitution pattern, indolizines carrying substituents in positions 5–8 were synthesized from enones and 2-(1H-pyrrol-1-yl)nitriles obtained from α-aminonitriles using a modified Paal-Knorr pyrrole synthesis. The decoration of the pyridine unit in the indolizine skeleton has been achieved by a one-pot conjugate addition/cycloaromatization sequence.rnIn the second part of the thesis, the diversity-oriented synthesis of pyrroles from 3,5-diaryl substituted 2H-pyrrole-2-carbonitriles (cyanopyrrolines) obtained in a cyclocondensation of enones with aminoacetonitrile hydrochloride is being discussed. 2,4-Di-, 2,3,5-trisubstituted pyrroles, pyrrole-2-carbonitriles and 2,2’-bipyrroles were synthesized in a one- or two-step protocol. While the microwave-assisted thermal elimination of HCN from cyanopyrrolines gave 2,4-disubstituted pyrroles, DDQ-oxidation of the same intermediates furnished pyrrole-2-carbonitriles. Furthermore, 2,3,5-trisubstituted pyrroles were obtained via a C-2-alkylation of the deprotonated cyanopyrrolines followed by the elimination of HCN. Finally, it has also been found that tetraaryl substituted 2,2’-bipyrroles could be synthesized by the oxidative dimerization of cyanopyrrolines using copper (II) acetate at 100 °C.rn

Geomorfologia del giacimento di orso delle caverne nella grotta di Govjestica, Valle di Praca, Bosnia-Ercegovina

In 2011 the GSB/USB caving group of Bologna has discovered, in the southern fossil branches of Govjestica cave (Valle di Praça, Bosnia) a fossil deposit of vertebrates containing bones of Ursus spelaeus, Capra ibex, Cricetulus migratorius and Microtus. On the basis of the U/Th ages of the bones, teeth and carbonate flowstone covering the fossils (60 ka), datings carried out in the laboratories of U-Series at Bologna, and on the disposition of the bones, a past connection between Govjestica and the nearby Banja Stjena cave is hypothesised. The closure of this passage has occurred suddenly through a collapse that has forced the last cave bears awakened from their winter sleep to stay blocked in Govjestica, and die. The connecting passage has later been covered with calcite flowstones and is no longer visible. This hypothesis is sustained by the rather scarce number of skeletons of cave bears found in Govjestica (a dozen of skulls against the often large amounts of cave bears found in similar caves): Govjestica cave, and especially the Room of the Bones in its southern part, has been used by cave bears only for a couple of centuries before these parts became inaccessible. Furthermore, the entrance of Banja Stjena cave was probably located close to or at the level of the Praça river, that has excavated its thalweg for around 20 metres in the last 60 ka.

Groups Acting on Tensor Products

Groups preserving a distributive product are encountered often in algebra. Examples include automorphism groups of associative and nonassociative rings, classical groups, and automorphism groups of p-groups. While the great variety of such products precludes any realistic hope of describing the general structure of the groups that preserve them, it is reasonable to expect that insight may be gained from an examination of the universal distributive products: tensor products. We give a detailed description of the groups preserving tensor products over semisimple and semiprimary rings, and present effective algorithms to construct generators for these groups. We also discuss applications of our methods to algorithmic problems for which all currently known methods require an exponential amount of work. (C) 2013 Elsevier B.V. All rights reserved.

SNA--a toolbox for the stoichiometric analysis of metabolic networks

BACKGROUND: Despite recent algorithmic and conceptual progress, the stoichiometric network analysis of large metabolic models remains a computationally challenging problem. RESULTS: SNA is a interactive, high performance toolbox for analysing the possible steady state behaviour of metabolic networks by computing the generating and elementary vectors of their flux and conversions cones. It also supports analysing the steady states by linear programming. The toolbox is implemented mainly in Mathematica and returns numerically exact results. It is available under an open source license from: http://bioinformatics.org/project/?group_id=546. CONCLUSION: Thanks to its performance and modular design, SNA is demonstrably useful in analysing genome scale metabolic networks. Further, the integration into Mathematica provides a very flexible environment for the subsequent analysis and interpretation of the results.

Bioconductor: Open software development for computational biology and bioinformatics

The Bioconductor project is an initiative for the collaborative creation of extensible software for computational biology and bioinformatics. We detail some of the design decisions, software paradigms and operational strategies that have allowed a small number of researchers to provide a wide variety of innovative, extensible, software solutions in a relatively short time. The use of an object oriented programming paradigm, the adoption and development of a software package system, designing by contract, distributed development and collaboration with other projects are elements of this project's success. Individually, each of these concepts are useful and important but when combined they have provided a strong basis for rapid development and deployment of innovative and flexible research software for scientific computation. A primary objective of this initiative is achievement of total remote reproducibility of novel algorithmic research results.

Effects of instructional changes on student learning of electrochemistry in an IB chemistry course

This study investigated the effectiveness of incorporating several new instructional strategies into an International Baccalaureate (IB) chemistry course in terms of how they supported high school seniors’ understanding of electrochemistry. The three new methods used were (a) providing opportunities for visualization of particle movement by student manipulation of physical models and interactive computer simulations, (b) explicitly addressing common misconceptions identified in the literature, and (c) teaching an algorithmic, step-wise approach for determining the products of an aqueous solution electrolysis. Changes in student understanding were assessed through test scores on both internally and externally administered exams over a two-year period. It was found that visualization practice and explicit misconception instruction improved student understanding, but the effect was more apparent in the short-term. The data suggested that instruction time spent on algorithm practice was insufficient to cause significant test score improvement. There was, however, a substantial increase in the percentage of the experimental group students who chose to answer an optional electrochemistry-related external exam question, indicating an increase in student confidence. Implications for future instruction are discussed.