In this thesis, we use integer programming techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in many decomposition schemes for difficult optimization problems. We begin with a study of the RCSPP polytope for the single resource case and obtain several new valid inequality classes. Separation routines are provided, along with a polynomial time algorithm for constructing an auxiliary conflict graph which can be used to separate well known valid inequalities for the node packing polytope. We establish some facet defining conditions when the underlying graph is acyclic and develop a polynomial time sequential lifting algorithm which can be used to strengthen one of the inequality classes. Next, we outline a branch-and-cut algorithm for the RCSPP. We present preprocessing techniques and branching schemes which lead to strengthened linear programming relaxations and balanced search trees, and the majority of the new inequality classes are generalized to consider multiple resources. We describe a primal heuristic scheme that uses fractional solutions, along with the current incumbent, to search for new feasible solutions throughout the branch-and-bound tree. A computational study is conducted to evaluate several implementation choices, and the results demonstrate that our algorithm outperforms the default branch-and-cut algorithm of a leading integer programming software package. Finally, we consider the dial-a-flight problem (DAFP), a new vehicle routing problem that arises in the context of on-demand air transportation and is concerned with the scheduling of a set of travel requests for a single day of operations. The DAFP can be formulated as an integer multicommodity network flow model consisting of several RCSPPs linked together by set partitioning constraints which guarantee that all travel requests are satisfied. Therefore, we extend our branch-and-cut algorithm for the RCSPP to solve the DAFP. Computational experiments with practical instances provided by the DayJet Corporation verify that the extended algorithm also outperforms the default branch-and-cut algorithm of a leading integer programming software package.

Random graph processes are most often used to investigate theoretical questions about random graphs. A randomised algorithm can be defined specifically for the purpose of finding some structure in a graph, such as a matching, a colouring or a particular kind of sub graph. Properties of the related random graph process then suggest properties, or bounds on properties, of the structure. In this thesis, we use a random graph process to analyse a particular load balancing algorithm from theoretical computer science. By doing so, we demonstrate that random graph processes may also be used to analyse other algorithms and systems of a random nature, from areas such as computer science, telecommunications and other areas of engineering and mathematics. Moreover, this approach can lead to theoretical results on the performance of algorithms that are difficult to obtain by other methods. In the course of our analysis we are also led to some results of the first kind, relating to the structure of the random graph. / The particular algorithm that we analyse is a randomised algorithm for an off-line load balancing problem with two choices. The load balancing algorithm, in an initial stage, mirrors an algorithm which finds the k-core of a graph. This latter algorithm and the related random graph process have been previously analysed by Pittel, Spencer and Wormald, using a differential equation method, to determine the thresholds for the existence of a k-core in a random graph. We modify their approach by using a random pseudograph model due to Bollobas and Frieze, and Chvatal, in place of the uniform random graph. This makes the analysis somewhat simpler, and leads to a shortened derivation of the thresholds and other properties of k-cores.(For complete abstract open document)

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2009. / Includes bibliographical references.

Thesis (Ph.D.)--Mathematics, Georgia Institute of Technology, 2008. / Committee Chair: Prof. Jean Bellissard; Committee Member: Prof. Claude Schochet; Committee Member: Prof. Michael Loss; Committee Member: Prof. Stavros Garoufalidis; Committee Member: Prof. Thang Le.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

Neste trabalho é apresentada uma nova abordagem de algoritmo evolutivo multiobjetivo, denominado MOEA/NSM (do inglês, Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). O algoritmo preserva em geral, características de um algoritmo evolutivo, concentrando qualidades de outras abordagens de sucesso na literatura em uma única abordagem, para que elas trabalhem em conjunto, por meio de subpopulações. O objetivo do estudo foi combinar as principais características dos algoritmos NSGA-II, SPEA2 e MOEA/D, e incluir ainda uma técnica de busca local para melhorar a busca no espaço de objetivos. O algoritmo MOEA/NSM foi comparado às demais abordagens clássicas utilizando 9 datasets para o problema do caixeiro viajante biobjetivo. Além disso, foram realizados experimentos aplicando também a busca local nas abordagens clássicas, resultando em considerável melhora nos resultados para esses algoritmos. A partir das fronteiras de Pareto resultantes dos experimentos, foram aplicadas as métricas de avaliação por Hipervolume, Epsilon (ε), R2, EAF, além do teste de hipótese estatístico Shapiro-Wilk. Os resultados apontaram um melhor desempenho do MOEA/NSM em relação aos demais, mesmo aplicando a busca local nas outras abordagens. Nesse sentido, o MOEA/NSM pode ser considerado um algoritmo que consegue encontrar soluções não denominadas de qualidade, tanto quanto os algoritmos clássicos da literatura. / This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of other approaches of success in the literature in a single approach, so that they work together, through subpopulations. The objective of the study was to combine the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also to include a local search technique to improve the objective space search. The MOEA/NSM algorithm was compared to the other classical approaches using 9 datasets for the biobjective traveling salesman problem. In addition, experiments were carried out also applying the local search in the classical approaches, resulting in a considerable improvement in the results for these algorithms. From the Pareto frontiers resulting from experiments, we applied the evaluation metrics by Hypervolume, Epsilon (ε), R2, EAF, in addition to the Shapiro-Wilk statistical hypothesis test. The results showed a better performance of the MOEA/NSM in relation to the others, even applying the local search in the others approaches. In this sense, the MOEA/NSM can be considered an algorithm that is able to find solutions not dominated of quality, as much as the classic algorithms of the literature.

La géométrie combinatoire est une large et belle branche des mathématiques. Cette thèse doctorale se compose de l'étude de cinq sujets différents dans ce domaine. Même si les problèmes et les techniques utilisés pour y faire face sont divers, ils partagent le mêeme objectif: Étudier l'interaction entre les structures combinatoires et géométriques. Dans le chapitre 1, nous étudions le problème suivant : pour un entier positif k, combien de points en position générale devons-nous prendre dans le plan de sorte que nous pouvons toujours trouver k d'entre eux définissant des triangles avec un rayon du cercle circonscrit distinct ? Cette question a été posée par Paul Erdös en 1975 qui a lui même proposé une solution en 1978. Toutefois, la preuve a omis par inadvertance un cas non trivial. Nous avons repris ce cas et donné une solution à la question en utilisant des outils de base de la géométrie algébrique et nous fournissons une borne polynomiale pour le nombre de points nécessaires.Dans le chapitre 2, nous sommes intéressés par de généralisations géométriques du critère de Hall pour les couplages dans les graphes bipartits (1935). Nous obtenons des théorèmes géométriques type Hall pour des ensembles convexes disjoints et pour points en position générale dans l'espace euclidien. Les outils de ce chapitre sont topologiques, et l'approche est motivés par une méthode remarquable introduite par Aharoni et Haxell en $2000$ ainsi que par ses généralisations.D'autre part, dans le chapitre 3, nous commençons par un théorème de Helly fractionné de 1979 due à A. Liu et M. Katchalski pour motiver un résultat combinatoire. Nous étudions des conditions combinatoires que des familles de graphes doivent avoir pour permettre d'obtenir des versions plus fine du théorème de Turán. Nous trouvons des liens intéressants entre les nombres de Turán, les nombres chromatiques et les nombres de clique dans la famille. Les outils de ce chapitre sont purement combinatoires.Dans le chapitre 4, nous nous concentrons sur l'obtention des résultats pour la bien connue classe des matroïde chemin du réseau introduite par Bonin, de Mier et Noy en 2003. La contribution principale est de prouver pour cette classe la validité d'une conjecture de Merino et Welsh (1999) sur une inégalité de certaines valeurs du polynôme de Tutte. Pour ce faire, nous introduisons et étudions des serpents, une classe spéciale de matroïdes chemin du réseau ``mince''.Enfin, dans le chapitre 5, nous étudions une variante d'un problème des transversales posé par J.L. Arocha, J. Bracho, L. Montejano et J.L. Ramírez-Alfonsín en 2010. Dans leur travaux originaux, ils ont rémarqué que si nous avons peu de points dans l'espace euclidien alors il est possible de trouver une transversale d'une dimension donnée qui travers les enveloppes convexes de tous les k-ensembles de points. De m&eme, ils montrent qu'il est impossible de trouver une telle transversale lorsque nous avons beaucoup de points. Les auteurs donnent des bornes spécifiques et ils laissent aussi quelques problèmes ouverts. Si la définition de transversale est légèrement plus restrictive, alors le problème peut être étudié en utilisant la théorie des matroïdes orientés. Dans la présente thèse, nous fournissons les détails de cette relation et nous donnons des bornes pour la famille de polytopes cycliques. / Combinatorial geometry is a broad and beautiful branch of mathematics. This PhD Thesis consists of the study of five different topics in this area. Even though the problems and the tools used to tackle them are diverse, they share a unifying goal: To explore the interaction between combinatorial and geometric structures.In Chapter 1 we study a problem by Paul Erdös: for a positive integer k, how many points in general position do we need in the plane so that we can always find a k-subset of them defining triangles with distinct circumradii? This question was posed in 1975 and Erdös himself proposed a solution in 1978. However, the proof inadvertently left out a non-trivial case. We deal with the case using basic tools from algebraic geometry and we provide a polynomial bound for the needed number of points.In Chapter 2 we are interested in providing geometric extensions of Hall's criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type theorems for pairwise disjoint convex sets and for points in general position in euclidean space. The tools of this chapter are topological, and are motivated by a remarkable method introduced by Aharoni and Haxell in 2000 and its generalizations.On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979 by A. Liu and M. Katchalski to motivate a combinatorial result. We study combinatorial conditions on families of graphs that allow us to have sharpened variants of Turán's theorem. We find interesting relations between the Turán numbers, the chromatic numbers and the clique numbers of graphs in the family. The tools in this chapter are only combinatorial.In Chapter 4 we focus on obtaining some results for the well studied class of lattice path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning an inequality involving certain values of the Tutte polynomial. In order to do this, we introduce and study snakes, a special class of ``thin'' lattice path matroids.Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L. Arocha, J. Bracho, L. Montejano and J.L. Ramírez-Alfonsín in 2010. In their original work, they realized that if we have few points in euclidean space then it is possible to find a transversal of a given dimension that goes through all the convex hulls of k-subsets of points. Similarly, they show that it is impossible to find such a transversal when we have many points. The authors give some specific bounds and they also leave some open problems. If the definition of transversal is slightly more restrictive, then the problem can be tackled using oriented matroid theory. We provide the details of the relation and we give bounds for the family of cyclic polytopes.

Dans cette thèse nous étudions trois jeux à objectif compétitif sur les graphes. Les jeux à objectif compétitif proposent une approche dynamique des problèmes d'optimisation discrètes. L'idée générale consiste à associer à un problème d'optimisation (coloration, domination, etc.) un jeu combinatoire partisan de la façon suivante. Deux joueurs construisent tour à tour la structure reliée au problème d'optimisation. L'un d'eux cherche à ce que cette structure soit le plus optimale possible, tandis que l'autre essaye de l'en empêcher. Sous l'hypothèse que les deux joueurs jouent optimalement, la taille de la structure obtenue définit un invariant ludique.Nous commençons par étudier une variante 1-impropre du jeu de coloration, qui est le premier et le plus étudié des jeux à objectif compétitif. Dans ce jeu, les joueurs colorient les sommets d'un graphe de sorte que deux sommets adjacents ne partagent jamais la même couleur. Dans la version 1-impropre, un sommet peut avoir au plus un voisin ayant la même couleur que lui. Nous considérons ensuite le jeu de domination, dans lequel les deux joueurs doivent construire un ensemble dominant, c'est-à-dire un ensemble de sommets du graphe tel que tout autre sommet est adjacent à l'un des membres de cet ensemble. Finalement, nous définissons un nouveau jeu à objectif compétitif, relié au problème de coloration distinguante. Dans ce jeu, il s'agit de construire une coloration qui n'est invariante par aucun des automorphismes du graphe. Nous soulevons plusieurs interrogations stimulantes concernant ce nouveau jeu, notamment sur la caractérisation des graphes ayant un invariant ludique infini, par l'existence d'automorphismes d'ordre deux. / In this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms.

Cette thèse considère le problème consistant à intégrer les décisions de routage et stockage lors de la conception de la chaîne logistique. Le but est de sélectionner des dépôts parmi un ensemble de candidats pour desservir un ensemble de détaillants à l’aide d’une flotte de véhicules de capacité permettant visiter plus d’un détaillant par route. On cherche à déterminer la localisation de ces dépôts et les tournées des véhicules afin de maintenir leurs niveaux optimaux de stocks. La demande chez les détaillants est connue à l’avance. Des applications dans les domaines de la logistique humanitaire et militaire sont envisageables. Pour résoudre le problème, deux matheuristiques sont proposées. Dans la première partie, une méthode coopérative qui combine des méthodes exactes pour le problème de conception de la chaîne logistique et des méthodes heuristiques de routage est présentée. Dans la deuxième partie, une méthode de décomposition utilisant une réformulation de Dantzig-Wolf sur les variables de routage est proposée. L’algorithme intègre les concepts de génération de colonnes, relaxation lagrangienne et recherche locale. Les résultats montrent la capacité des algorithmes à trouver des solutions de bonne qualité et nous estimons de façon empirique l’impact de considérer un modèle intégré au lieu d’utiliser une méthode d’optimisation séquentielle. De plus, les résultats des méthodes présentées sur des sous-problèmes sont aussi étudiés. Ces sont: le problème de localisation-routage, le problème de tournées avec gestion de stocks, et le problème de plus court chemin généralisé / The problem of designing a supply chain including simultaneously routing and inventory management decisions is studied in this thesis. The objective is to select a subset of depots to open, the inventory policies for a 2-echelon system, and the set of routes to perform distribution from the upper echelon to the next using a homogeneous fleet of vehicles over a finite planning horizon. Demand is considered to be known. Applications are found in humanitarian logistics and military logistics. To solve the problem, two matheuristic procedures are developed. On the first part a cooperative algorithm combining exact methods for the supply chain design problem and routing heuristics is presented. On the second part, a partition is proposed using a Dantzig-Wolf reformulation on the routing variables. An hybridization between column generation, Lagrangian relaxation and local search is proposed in this part, put together as a heuristic method. Furthermore, results demonstrate the capability of the algorithms to compute high quality solutions and empirically estimate the improvement in the cost function of the proposed model when compared to a sequential optimization approach. Furthermore, results of the proposed methodologies on benchmark instances for subproblems are studied as well. Those are the capacitated location-routing problem, the inventory-routing problem, and the generalized elementary shortest path problem

Les travaux de cette thèse concernent la résolution d'un problème de planification dans un réseau de distribution à deux échelons intégrant la gestion de stocks de produits périssables, le dimensionnement de lots, des alternatives d'approvisionnement. La livraison s'effectue directement entre un fournisseur et son client, sans tournée avec une flotte homogène de véhicules. Nous proposons un programme linéaire mixte, une heuristique constructive (déterministe) et une heuristique réactive randomisée. Pour certaines instances, le solveur de programme linéaire mixte ne fournit pas une bonne solution réalisable dans la limite de temps définie ou prend beaucoup de temps. Les heuristiques proposées sont rapides mais ne donnent pas de bonnes solutions pour certaines instances. Pour améliorer la qualité des solutions des heuristiques, la descente à voisinage variable (VND), la recherche locale itérative (ILS) et la recherche locale itérative à démarrages multiples (MS-ILS) sont développées.Toutes ces méthodes ont été incluses dans un APS (Advanced Planning System) et sont comparées avec CPLEX sur des instances extraites de bases de données réelles. Un générateur aléatoire d'instances est conçu pour plus de diversité pour les tests. Une relaxation lagrangienne est implémentée pour comparer les solutions des instances, pour lesquelles CPLEX ne fournit pas une bonne solution réalisable dans le temps imparti, avec les autres méthodes. Une heuristique lagrangienne, utilisant la relaxation lagrangienne et une heuristique de réparation, est également développée / This work presents a planning problem in a distribution network incorporating two levels inventory management of perishable products, lot-sizing, multi-sourcing and transport capacity with a homogeneous fleet of vehicles. A mixed integer linear programming (MILP) a greedy heuristic and a reactive randomized heuristic are developed to solve this real planning problem. There are some instances for which the solver CPLEX cannot give a good upper bound within the limited time and for other instances it takes a lot of time to solve MILP. The heuristics are alternatives to the mixed integer linear program to quickly solve some large instances taking into account original and difficult constraints. For some instances the gap between the solutions of the solver (MILP) and the heuristics becomes quite significant. The variable neighborhood descent (VND), the iterated local search (ILS) and the multi-start iterated local search (MS-ILS) are implemented. These methods are included in an APS (Advanced Planning System) and compared with a MILP solver. The instances are derived from actual data or built using a random generator of instances to have wider diversity for computational evaluation. A lagrangian relaxation is developed to compare the solutions of the instances, for which CPLEX cannot give a good upper bound within the limited time, with the other methods (greedy heuristic, VND, ILS and MS-ILS). A lagrangian heuristic is proposed; the solution of lagrangian relaxation is used to build a feasible solution with a repair heuristic