Let G be an undirected graph on n vertices and let S(G) be the class of all real-valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let V = {1, 2, . . . , n} be the vertex set of G. A scheme on G is a function f : V → {0, 1}. Given a scheme f on G, there is an associated class of matrices Sf (G) = {A ∈ S(G)|aii = 0 if and only if f(i) = 0}. A scheme f is said to be constructible if there exists a matrix A ∈ Sf (G) with rank A = min{rank M|M ∈ S(G)}. We explore properties of constructible schemes and give a complete classification of which schemes are constructible for paths and cycles. We also consider schemes on complete graphs and show the existence of a graph for which every possible scheme is constructible.

We introduce and study a novel graph optimization problem to search for multiple cliques with the maximum overall weight, to which we denote as the Maximum Weighted Multiple Clique Problem (MWMCP). This problem arises in research involving network-based data mining, specifically, in bioinformatics where complex diseases, such as various types of cancer and diabetes, are conjectured to be triggered and influenced by a combination of genetic and environmental factors. To integrate potential effects from interplays among underlying candidate factors, we propose a new network-based framework to identify effective biomarkers by searching for "groups" of synergistic risk factors with high predictive power to disease outcome. An interaction network is constructed with vertex weight representing individual predictive power of candidate factors and edge weight representing pairwise synergistic interaction among factors. This network-based biomarker identification problem is then formulated as a MWMCP. To achieve near optimal solutions for large-scale networks, an analytical algorithm based on column generation method as well as a fast greedy heuristic have been derived. Also, to obtain its exact solutions, an advanced branch-price-and-cut algorithm is designed and solved after studying the properties of the problem. Our algorithms for MWMCP have been implemented and tested on random graphs and promising results have been obtained. They also are used to analyze two biomedical datasets: a Type 1 Diabetes (T1D) dataset from the Diabetes Prevention Trial-Type 1 (DPT-1) Study, and a breast cancer genomics dataset for metastasis prognosis. The results demonstrate that our network-based methods can identify important biomarkers with better prediction accuracy compared to the conventional feature selection that only considers individual effects.

Combinatorial optimisation problems (COPs) pervade human society: scheduling, design, layout, distribution, timetabling, resource allocation and project management all feature problems where the solution is some combination of elements, the overall value of which needs to be either maximised or minimised (i.e., optimised), typically subject to a number of constraints. Thus, techniques to efficiently solve such problems are an important area of research. A popular group of optimisation algorithms are the metaheuristics, approaches that specify how to search the space of solutions in a problem independent way so that high quality solutions are likely to result in a reasonable amount of computational time. Although metaheuristic algorithms are specified in a problem independent manner, they must be tailored to suit each particular problem to which they are applied. This thesis investigates a number of aspects of the application of the relatively new Ant Colony Optimisation (ACO) metaheuristic to different COPs.The standard ACO metaheuristic is a constructive algorithm loosely based on the foraging behaviour of ant colonies, which are able to find the shortest path to a food source by indirect communication through pheromones. ACO’s artificial pheromone represents a model of the solution components that its artificial ants use to construct solutions. Developing an appropriate pheromone representation is a key aspect of the application of ACO to a problem. An examination of existing ACO applications and the constructive approach more generally reveals how the metaheuristic can be applied more systematically across a range of COPs. The two main issues addressed in this thesis are biases inherent in the constructive process and the systematic selection of pheromone representations.The systematisation of ACO should lead to more consistently high performance of the algorithm across different problems. Additionally, it supports the creation of a generalised ACO system, capable of adapting itself to suit many different combinatorial problems without the need for manual intervention.

There are many real world assignment, scheduling and planning tasks which can be classified as combinatorial optimisation problems (COPs). These are usually formulated as a mathematical problem of minimising or maximising some cost function subject to a number of constraints. Usually, such problems are NP hard, and thus, whilst it is possible to find exact solutions to specific problems, in general only approximate solutions can be found. There are many algorithms that have been proposed for finding approximate solutions to COPs, ranging from special purpose heuristics to general search meta-heuristics such as simulated annealing and tabu search. General meta-heuristic algorithms like simulated annealing have been applied to a wide range of problems. In most cases, the designer must choose an appropriate data structure and a set of local operators that define a search neighbourhood. The variability in representation techniques, and suitable neighbourhood transition operators, has meant that it is usually necessary to develop new code for each problem. Toolkits like the one developed by Ingber's Adaptive Simulated Annealing (Ingber 1993, 1996) have been applied to assist rapid prototyping of simulated annealing codes, however, these still require the development of new programs for each type of problem. There have been very few attempts to develop a general meta-heuristic solver, with the notable exception being Connolly's General Purpose Simulated Annealing (Connolly 1992). In this research, a general meta-heuristic based system is presented that is suitable for a wide range of COPs. The main goal of this work is to build an environment in which it is possible to specify a range of COPs using an algebraic formulation, and to produce a tailored solver automatically. This removes the need for the development of specific software, allowing very rapid prototyping. Similar techniques have been available for linear programming based solvers for some years in the form of the GAMS (General Algebraic Modelling System) (Brooke, Kendrick, Meeraus and Raman 1997) and AMPL (Fourer, Gay and Kernighan 1993) interfaces. The new system is based on a novel linked list data structure rather than the more conventional vector notation due to the natural mapping between COPS and lists. In addition, the modelling system is found to be very suitable for processing by meta-heuristic search algorithms as it allows the direct application of common local search operators. A general solver is built that is based on the linked list modelling system. This system is capable of using meta-heuristic search engines such as greedy search, tabu search and simulated annealing. A number of implementation issues such as generating initial solutions, choosing and invoking appropriate local search transition operators and producing suitable incremental cost expressions, are considered. As such, the system can been seen as a good test-bench for model prototypers and those who wish to test various meta-heuristic implementations in a standard way. However, it is not meant as a replacement or substitute for efficient special purpose search algorithms. The solver shows good performance on a wide range of problems, frequently reaching the optimal and best-known solutions. Where this is not the case, solutions within a few percent deviation are produced. Performance is dependent on the chosen transition operators and the frequency with which each is applied. To a lesser extent, the performance of this implementation is influenced by runtime parameters of the meta-heuristic search engine.

This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.

Šajā darbā mēs pētam kombinatoriskās kartes, kas tiek kodētas kā permutāciju pāri, pielietojot ģeometrisku ideju, ka stūri starp šķautnēm grafam, kas izvietots uz virsmas, ir elementi, uz kuriem permutācijas darbojas.<br />Ģeometriskās kombinatoriskās kartes kā arī parciālās kartes tiek aplūkotas, ciklu pārklājumu teorija, kas dod objektus, kas atbilst cikliem grafā, tiek attīstīta. Tiek atrastas dažas permutāciju formulas, kas rēķina grafu teorētiskos pielietojumos aktuālus karšu raksturlielumus. Visa darba ideja ir meklēt noderīgus pielietojumus: atrast permutāciju izteiksmēs rēķināmus raksturlielumus, kuriem atbilst grafu teorētiski raksturlielumi.<br />Datorprograma, kas rēķina permutāciju formulas un no attīstītās teorijas iegūtos algoritmus, ir izveidota.

Pathway optimization is, in general, a very demanding task due to the complex, nonlinear and largely unknown interactions of enzymes, regulators and metabolites. While in vitro reconstruction and pathway analysis is a viable alternative, a major limitation of this approach is the availability of the pathway enzymes for reliable pathway reconstruction. Here, we report the application of RNA display methods for the construction of fusion (chimeric) molecules, comprising mRNA and the protein they express, that can be used for the above purpose. The chimeric molecule is immobilized via hybridization of its mRNA end with homologous capture DNA spotted on a substrate surface. We show that the protein (enzyme) end of the fusion molecule retains its function under immobilized conditions and that the enzymatic activity is proportional to the amount of capture DNA spotted on the surface of a microarray or 96-well microplate. The relative amounts of all pathway enzymes can thus be changed at will by changing the amount of the corresponding capture DNA. Hence, entire pathways can be reconstructed and optimized in vitro from genomic information alone by generating chimeric molecules for all pathway enzymes in a single in vitro translation step and hybridizing on 96-well microplates where each well contains a different combination of capture DNA. We provide validation of this concept with the sequential reactions catalyzed by luciferase and nucleoside diphosphate kinase and further illustrate this method with the optimization of the five-step pathway for trehalose synthesis. Multi-enzyme pathways leading to the synthesis of specialty molecules can thus be optimized from genomic information about the pathway enzymes, provided the latter retain their activity under the in vitro immobilized conditions. / Singapore-MIT Alliance (SMA)

Synechocystis PCC 6803 is a photosynthetic bacterium that has the potential to make bioproducts from carbon dioxide and light. Biochemical production from photosynthetic organisms is attractive because it replaces the typical bioprocessing steps of crop growth, milling, and fermentation, with a one-step photosynthetic process. However, low yields and slow growth rates limit the economic potential of such endeavors. Rational metabolic engineering methods are hindered by limited cellular knowledge and inadequate models of Synechocystis. Instead, inverse metabolic engineering, a scheme based on combinatorial gene searches which does not require detailed cellular models, but can exploit sequence data and existing molecular biological techniques, was used to find genes that (1) improve the production of the biopolymer poly-3-hydroxybutyrate (PHB) and (2) increase the growth rate. A fluorescence activated cell sorting assay was developed to screen for high PHB producing clones. Separately, serial sub-culturing was used to select clones that improve growth rate. Novel gene knock-outs were identified that increase PHB production and others that increase the specific growth rate. These improvements make this system more attractive for industrial use and demonstrate the power of inverse metabolic engineering to identify novel phenotype-associated genes in poorly understood systems. / Singapore-MIT Alliance (SMA)

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

Consider the problem of maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two variants of the problem are studied, with or without specific constraints linking together the tolls on the arcs. The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is first shown theoretically, as these are facet defining for the restricted one and two commodity problems. Also, we prove that some of the valid inequalities proposed, together with several constraints of the linear program, provide a complete description of the convex hull of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. / Considérons le problème qui consiste à maximiser les profits issus de la tarification d’un sous-ensemble d’arcs d’un réseau de transport, où les flots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin, comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes spécifiques reliant les niveaux de tarifs sur les arcs. Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. Enfin, nous soulignons les liens entre le problème de tarification de réseau étudié dans cette thèse et un problème plus classique de tarification de produits en gestion.