Graph theory is fascinating branch of math. Leonhard Euler introduced the concept of Graph Theory in his paper about the seven bridges of Konigsberg published in 1736. In a nutshell, graph theory is the study of pair-wise relationships between objects. Each object is represented using a vertex and in case of a relationship between a pair of vertices, they will be connected using an edge. In this dissertation, graph theory is used to study several important combinatorial optimization problems. In chapter 2, we study the multi-dimensional assignment problem using their underlying hypergraphs. It will be shown how the MAP can be represented by a k-partite graph and how any solution to MAP is associated to a k-clique in the respective k-partite graph. Two heuristics are proposed to solve the MAP and computational studies are performed to compare the performance of the proposed methods with exact solutions. On the heels of chapter 3, a new branch-and-bound method is proposed to solve the problem of finding all k-cliques in a k-partite graph. The new method utilizes bitsets as the data-structure to represent graph data. A new pruning method is introduced in BitCLQ, and CPU instructions are used to improve the performance of the branch-and-bound method. BitCLQ gains up to 300% speed up over existing methods. In chapter 4, two new heuristic to solve decomposable cost MAP's are proposed. The proposed heuristic are based on the partitioning of the underlying graph representing the MAP. In the first heuristic method, MAP's are partitioned into several smaller MAP's with the same dimensiality and smaller cardinality. The solution to the original MAP is constructed incrementally, by using the solutions obtained from each of the smaller MAP's. The second heuristic works in the same fashion. But instead of partitioning the graph along the cardinality, graphs are divided into smaller graphs with the same cardinality but smaller dimensionality. The result of each heuristic is then compared with a well-known existing heuristic. An important problem in graph theory is the maximum clique problem (MCQ). A clique in a graph is defined as a complete subgraph. MCQ problem entails finding the size of the largest clique contained in a graph. General branch-and-bound methods to solve MCQ use graph coloring to find an upper bound on the size of the maximum clique. Recently, a new MAX-SAT based branch-and-bound method for MCQ is proposed that improves the quality of the upper bound obtained from graph coloring. In chapter 5, a branch and bound algorithm is proposed for the maximum clique problem. The proposed method uses bitsets as the data-structure. The result of the computational studies to compare the proposed method with existing methods for MCQ is provided. Chapter 6 contains an application of a graph theory in solving a risk management problem. A new mixed-integer mathematical model to formulate a risk-based network is provided. It will be shown that an optimal solution of the model is a maximal clique in the underlying graph representing the network. The model is then solved using a graph-theoretic approach and the results are compared to CPLEX.

Dans ce travail, nous exploitons le potentiel offert par les véhicules autonomes coopératifs, pour fluidifier le trafic dans une intersection isolée puis dans un réseau d’intersections. Nous proposons le protocole SVAC (Système du Véhicule Actionneur Coopératif) permettant de réguler une intersection isolée. SVAC est basé sur une distribution individuelle du droit de passage qui respecte un ordre précis donné par une séquence de passage.Pour optimiser la séquence de passage, nous définissons la politique PED (Politique d’Evacuation Distribuée) permettant d’améliorer le temps d’évacuation total de l’intersection. La création de la séquence de passage est étudiée à travers deux modélisations. Une modélisation sous forme de graphes permettant le calcul de la solution optimale en connaissant les dates d’arrivée de tous les véhicules, et une modélisation de type réseaux de Petri avec dateurs pour traiter la régulation temps-réel. Des tests réels avec des véhicules équipés ont été réalisés pour étudier la faisabilité du protocole SVAC. Des simulations mettant en jeu un trafic réaliste permettent ensuite de montrer la capacité de fluidifier le trafic par rapport à une régulation classique par feux tricolores.La régulation d’un réseau d’intersections soulève les problèmes d’interblocage et de réorientation du trafic. Nous proposons le protocole SVACRI (Système du Véhicule Actionneur Coopératif pour les Réseaux d’Intersections) qui permet d’éliminer à priori les risques d’interblocage à travers la définition de contraintes d’occupation et de réservation de l’espace et du temps. Nous étudions également la possibilité d’améliorer la fluidité du trafic à travers le routage des véhicules, en tirant avantage du protocole SVACRI. Enfin, nous généralisons le système de régulation proposé pour la synchronisation des vitesses aux intersections. / The objective of this work is to use the potential offered by the wireless communication and autonomous vehicles to improve traffic flow in an isolated intersection and in a network of intersections. We define a protocol, called CVAS (Cooperative Vehicle Actuator System) for managing an isolated intersection. CVAS distributes separately the right of way to each vehicle according to a specific order determined by a computed sequence.In order to optimize the sequence, we define a DCP (Distributed Clearing Policy) to improve the total evacuation time of the intersection. The control strategy is investigated through two modeling approaches. First graph theory is used for calculating the optimal solution according to the arrival times of all vehicles, and then a timed Petri Net model is used to propose a real-time control algorithm. Tests with real vehicles are realized to study the feasibility of CVAS. Simulations of realistic traffic flows are performed to assess our algorithm and to compare it versus conventional traffic lights.Managing a network of intersections raises the issue of gridlock. We propose CVAS-NI protocol (Cooperative Vehicle actuator system for Networks of Intersections), which is an extension of CVAS protocol. This protocol prevents the deadlock in the network through occupancy and reservation constraints. With a deadlock free network we extend the study to the traffic routing policy. Finally, we generalize the proposed control system for synchronizing the vehicle velocities at intersections.

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.

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.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

In this thesis, we study two problems in combinatorial optimization, the dominating set problem and the robustness problem. In the first half of the thesis, we focus on the dominating set problem in grid graphs and present a distributed algorithm for finding near optimal dominating sets on grids. The dominating set problem is a well-studied mathematical problem in which the goal is to find a minimum size subset of vertices of a graph such that all vertices that are not in that set have a neighbor inside that set. We first provide a simpler proof for an existing centralized algorithm that constructs dominating sets on grids so that the size of the provided dominating set is upper-bounded by the ceiling of (m+2)(n+2)/5 for m by n grids and its difference from the optimal domination number of the grid is upper-bounded by five. We then design a distributed grid domination algorithm to locate mobile agents on a grid such that they constitute a dominating set for it. The basis for this algorithm is the centralized grid domination algorithm. We also generalize the centralized and distributed algorithms for the k-distance dominating set problem, where all grid vertices are within distance k of the vertices in the dominating set. In the second half of the thesis, we study the computational complexity of checking a graph property known as robustness. This property plays a key role in diffusion of information in networks. A graph G=(V,E) is r-robust if for all pairs of nonempty and disjoint subsets of its vertices A,B, at least one of the subsets has a vertex that has at least r neighbors outside its containing set. In the robustness problem, the goal is to find the largest value of r such that a graph G is r-robust. We show that this problem is coNP-complete. En route to showing this, we define some new problems, including the decision version of the robustness problem and its relaxed version in which B=V \ A. We show these two problems are coNP-hard by showing that their complement problems are NP-hard.

This dissertation aims at analyzing complex problems arising in the context of dynamical networks, proteomics, and disease prevention. First, a new graph-based method for proving global stability of synchronization in directed dynamical networks is developed. This method utilizes stability and graph theories to clarify the interplay between individual oscillator dynamics and network topology. Secondly, a graph-theoretical algorithm is proposed to predict Ca2+-binding site in proteins. The new algorithm enables us to identify previously-unknown Ca2+-binding sites, and deepens our understanding towards disease-related Ca2+-binding proteins at a molecular level. Finally, an optimization model and algorithm to solve a disease prevention problem are described at the population level. The new resource allocation model is designed to assist clinical managers to make decisions on identifying at-risk population groups, as well as selecting a screening and treatment strategy for chlamydia and gonorrhea patients under a fixed budget. The resource allocation model and algorithm can have a significant impact on real treatment strategy issues.

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook