Algorithms and Models For Combinatorial Optimization Problems

In this thesis we present some combinatorial optimization problems, suggest models and algorithms for their effective solution. For each problem,we give its description, followed by a short literature review, provide methods to solve it and, finally, present computational results and comparisons with previous works to show the effectiveness of the proposed approaches. The considered problems are: the Generalized Traveling Salesman Problem (GTSP), the Bin Packing Problem with Conflicts(BPPC) and the Fair Layout Problem (FLOP).

An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

Gleichmäßig dünne Basen zweiter Ordnung

Eine Menge B nicht negativer ganzer Zahlen heißt Basis h-ter Ordnung, wenn jede nicht negative ganze Zahl Summe von höchstens h Elementen von B ist. Eine der großen Fragen der additiven Zahlentheorie ist die nach der effektivsten Basis h-ter Ordnung für ein gegebenes h>=2. Im Fokus des Interesses steht dabei der immer noch offene Fall h=2. Bezeichnet B(x) die Anzahl der Elemente b aus B mit 0= af(x), wobei f die Wurzelfunktion bezeichne. Andererseits gibt es Basen B zweiter Ordnung mit B(x) <= cf(x). Daher kann man den Limes superior S(B), den Limes inferior s(B) sowie im Falle der Existenz den Limes d(B) des Quotienten B(x) / f(x) als Dichtefunktionen von Basen zweiter Ordnung betrachten. J. W. S. Cassels konstruierte 1957 eine Basis C zweiter Ordnung mit d(C)=5,196…. G. Hofmeister gab 2001 eine Basis H zweiter Ordnung mit asymptotischer Wurzeldichte d(H)=4,638… an. In der vorliegenden Arbeit wird eine Basis S zweiter Ordnung mit asymptotischer Wurzeldichte d(S)=3,464… konstruiert. Darüber hinaus wird für die von J. W. S. Cassels, für die von G. Hofmeister und für die in dieser Arbeit verwendete Klasse von Basen zweiter Ordnung gezeigt, dass die asymptotische Wurzeldichte innerhalb der jeweiligen Klasse nicht mehr zu verbessern ist. Bisher war die Frage nach möglichen Verbesserungen innerhalb der jeweiligen Konstruktionsprinzipien offen geblieben.

Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics

Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

How teachers think about the role of digital technologies in student assessment in mathematics

This study concerns teachers’ use of digital technologies in student assessment, and how the learning that is developed through the use of technology in mathematics can be evaluated. Nowadays math teachers use digital technologies in their teaching, but not in student assessment. The activities carried out with technology are seen as ‘extra-curricular’ (by both teachers and students), thus students do not learn what they can do in mathematics with digital technologies. I was interested in knowing the reasons teachers do not use digital technology to assess students’ competencies, and what they would need to be able to design innovative and appropriate tasks to assess students’ learning through digital technology. This dissertation is built on two main components: teachers and task design. I analyze teachers’ practices involving digital technologies with Ruthven’s Structuring Features of Classroom Practice, and what relation these practices have to the types of assessment they use. I study the kinds of assessment tasks teachers design with a DGE (Dynamic Geometry Environment), using Laborde’s categorization of DGE tasks. I consider the competencies teachers aim to assess with these tasks, and how their goals relate to the learning outcomes of the curriculum. This study also develops new directions in finding how to design suitable tasks for student mathematical assessment in a DGE, and it is driven by the desire to know what kinds of questions teachers might be more interested in using. I investigate the kinds of technology-based assessment tasks teachers value, and the type of feedback they give to students. Finally, I point out that the curriculum should include a range of mathematical and technological competencies that involve the use of digital technologies in mathematics, and I evaluate the possibility to take advantage of technology feedback to allow students to continue learning while they are taking a test.

Hydrogels for DNA isolation from blood

This dissertation describes the synthesis of surface attached hydrogel biomaterials, characterization of their properties, evaluation of structuring concepts and the investigation of these materials in the isolation of DNA from human whole blood. Photosensitive hydrogel precursor materials on the basis of hydroxyethylmethacrylate (HEMA) were synthesized by free radical polymerization. In order to obtain surface bound hydrogel films, the precursors were deposited on a suitable substrate and subsequently irradatiated with UV - light to accomplish the formation of crosslinks in the film and create surface attachment. The composition of the polymerization precursor materials was determined by comprehensive NMR and GPC studies, revealing the copolymerizationrnbehaviour of the used monomers - HEMA derivatives and the photocrosslinkerrnMABP - and their respective distribution in the hydrogel precursors. The degree of crosslinking of the hydrogels was characterized with UV/vis spectroscopy. Stress-strain measurements were conducted in order to investigate the mechanical properties of the biomaterials. Moreover, the swelling process and biomolecule adsorption properties of the hydrogels were investigated with SPR/OW spectroscopy. For this, the deposition and binding of the hydrogels on gold or SiO2 surfaces was facilitated with photocrosslinkable adhesion promotors. The produced hydrogels were mechanically rigid and stablernunder the conditions of PCR and blood lysis. Furthermore, strategies towards the increase of hydrogel surface structure and porosity with porosigens, 2D laser interference lithography and photocleavable blockcopolymers were investigated. At last, a combinatorial strategy was used for the determination of the usefulness of hydrogels for the isolation from DNA from blood. A series of functionalized hydrogel precursors were synthesized, transferred to the surface inside a PCR tube and subsequently screened in regard to DNA adsorption properties with Taqman quantitative PCR. This approach yielded a promising candidate for a functional PCR tube coating that would allow the entire DNA isolation procedure being carried out in a single reaction container.rnThereforce, the practical application of such macromolecular architectures can be envisioned to improve industrial DNA diagnostic processes.

A causal model of mathematics performance in early adolescence: the role of sex

Using path analysis, the present investigation was done to clarify possible causal linkages among general scholastic aptitude, academic achievement in mathematics, self-concept of ability, and performance on a mathematics examination. Subjects were 122 eighth-grade students who completed a mathematics examination as well as a measure of self-concept of ability. Aptitude and achievement measures were obtained from school records. Analysis showed sex differences in prediction of performance on the mathematics examination. For boys, this performance could be predicted from scholastic aptitude and previous achievement in mathematics. For girls, performance only could be predicted from previous achievement in mathematics. These results indicate that the direction, strength, and magnitude of relations among these variables differed for boys and girls, while mean levels of performance did not.