Combinatorial optimisation problems (COPs) have been at the origin of the design of many optimal and heuristic solution frameworks such as branch-and-bound algorithms, branch-and-cut algorithms, classical local search methods, metaheuristics, and hyperheuristics. This thesis proposes a refined generic and parametrised infeasible local search (GPILS) algorithm for solving COPs and customises it to solve the traveling salesman problem (TSP), for illustration purposes. In addition, a rule-based heuristic is proposed to initialise infeasible local search, referred to as the parameterised infeasible heuristic (PIH), which allows the analyst to have some control over the features of the infeasible solution he/she might want to start the infeasible search with. A recursive infeasible neighbourhood search (RINS) as well as a generic patching procedure to search the infeasible space are also proposed. These procedures are designed in a generic manner, so they can be adapted to any choice of parameters of the GPILS, where the set of parameters, in fact for simplicity, refers to set of parameters, components, criteria and rules. Furthermore, a hyperheuristic framework is proposed for optimizing the parameters of GPILS referred to as HH-GPILS. Experiments have been run for both sequential (i.e. simulated annealing, variable neighbourhood search, and tabu search) and parallel hyperheuristics (i.e., genetic algorithms / GAs) to empirically assess the performance of the proposed HH-GPILS in solving TSP using instances from the TSPLIB. Empirical results suggest that HH-GPILS delivers an outstanding performance. Finally, an offline learning mechanism is proposed as a seeding technique to improve the performance and speed of the proposed parallel HH-GPILS. The proposed offline learning mechanism makes use of a knowledge-base to keep track of the best performing chromosomes and their scores. Empirical results suggest that this learning mechanism is a promising technique to initialise the GA's population.

Les pyrrolamides constituent une famille de produits naturels dotés de diverses activités biologiques et synthétisés par des actinobactéries. La congocidine et la distamycine, les molécules les plus connues de cette famille, sont capables de se lier à l'ADN de façon non covalente selon une certaine spécificité de séquence (succession de 4 paires de base A/T). Récemment, les gènes et la voie de biosynthèse de la congocidine ont été identifiés et caractérisés chez S. ambofaciens. Ceci a révélé un mécanisme original impliquant notamment de nouvelles enzymes et de nouvelles voies pour la biosynthèse des trois précurseurs nécessaires à l’assemblage de la congocidine. Nous avons entrepris d’étudier la régulation de la biosynthèse de la congocidine chez S. ambofaciens et d’isoler et de caractériser les groupes de gènes de biosynthèse de deux autres pyrrolamides, la distamycine et les pyrronamycines (produites respectivement par S distallicus et un streptomyces non caractérisé). L'objectif de cette étude est, dans un premier temps, d’améliorer notre compréhension des mécanismes impliqués lors de la biosynthèse de ces molécules (comme le mécanisme d’incorporation des pyrroles) et, par la suite, de manipuler les gènes identifiés pour synthétiser de nouvelles molécules pyrrolamides hybrides. / Pyrrolamides constitute a family of natural products with various biological activities, synthesized by actinobacteria. Congocidine (also called netropsin) and distamycin are the best characterized pyrrolamides, largely studied due to their ability to bind into the minor groove of the DNA double helix in a sequence specific manner (succession of four A/T bases). Recently, the congocidine biosynthetic pathway has been characterized in Streptomyces ambofaciens. We showed that an iterative Non Ribosomal Peptide Synthetase with an unusual architecture assembles congocidine, using precursors with undocumented biosynthetic pathways. With the aim of developing a combinatorial biosynthesis approach for the development of new pyrrolamides, we undertook the study of the regulation of congocidine biosynthesis in S. ambofaciens and the isolation of the distamycin and pyrronamycins biosynthetic gene clusters. Characterization of these clusters will result in a more detailed understanding of pyrrolamide biosynthesis (e.g. mechanism of pyrrole polymerization), and provide new tools (enzymes) and building blocks (precursors) necessary for combinatorial biosynthesis.

In this thesis, we provide constructive proofs of serveral generalizations of Sperner's Lemma, a combinatorial result which is equivalent to the Brouwer Fixed Point Theorem. This lemma makes a statement about the number of a certain type of simplices in the triangulation of a simplex with a special labeling. We prove generalizations for polytopes with simplicial facets, for arbitrary 3-polytopes, and for polygons. We introduce a labeled graph which we call a nerve graph to prove these results. We also suggest a possible non-constructive proof for a polytopal generalization.

Abstract not available

This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.

"June 27, 2004" / Includes bibliographical references (leaves 180-195) / xiii, 195 leaves : ill. ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, School of Architecture, Landscape Architecture and Urban Design, 2004

<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.</p><p>In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.</p>

Graduation date: 1998

Thesis (Ph. D.)--University of Oregon, 2006. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 83-84). Also available for download via the World Wide Web; free to University of Oregon users.

Thesis (doctoral)--Universität Bielefeld, 2003. / Includes bibliographical references (p. 147-152).