Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2016-02-17T11:41:50Z No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) / Made available in DSpace on 2016-02-17T11:41:50Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1276201 bytes, checksum: 9dd8fad80c483276a40101ee6a782d5b (MD5) Previous issue date: 2015-07-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work deals with the p-Cluster Editing Problem (p-CEP), which consists in performing a minimum number of editions (additions or removals of edges) in a graph G in order to transform it in a disjoint union of p cliques (clusters), where G and p are input data. p-CEP is a NP-Hard problem with applications in areas such as computational biology and machine learning. To solve this problem, we propose two new mathematical formulations and improvements in a formulation from the literature, as well as new valid inequalities. The three formulations were studied both theoretically, by comparing their linear relaxations, and practically, by implementing three exact algorithms: two based on Branch-and-Cut (BC) and one based on Branch-and-Price (BP). The proposed algorithms were tested in instances with up to 211 vertices. The results show the performance of the algorithms according to the graph density and the ratio between p and the number of vertices. Overall, the BC algorithms were superior to the BP algorithm. However, the latter obtained the best dual bounds in some instances. / Este trabalho trata do Problema de Edi¸c˜ao de p-Clusters (p-PEC), o qual consiste em realizar um n´umero m´ınimo de edi¸c˜oes (adi¸c˜oes ou remo¸c˜oes de arestas) em um grafo G de modo a transform´a-lo em uma uni˜ao disjunta de p cliques (ou clusters), sendo G e p dados de entrada. O p-PEC ´e um problema NP-Dif´ıcil que possui aplica¸c˜oes em ´areas como biologia computacional e aprendizagem de m´aquina. Para resolvˆe-lo, foram propostas duas novas formula¸c˜oes matem´aticas e melhorias em uma formula¸c˜ao proveniente da literatura, bem como novas desigualdades v´alidas. As trˆes formula¸c˜oes consideradas foram estudadas tanto teoricamente, atrav´es da compara¸c˜ao entre as relaxa¸c˜oes lineares, quanto empiricamente, atrav´es do desenvolvimento de trˆes algoritmos exatos: dois baseados em Branch-and-Cut (BC) e um baseado em Branch-and-Price (BP). Os algoritmos foram testados em instˆancias com at´e 211 v´ertices. Os resultados mostram o impacto da raz˜ao entre p e o n´umero de v´ertices, da densidade do grafo e das desigualdades nos desempenhos dos algoritmos. No geral, os algoritmos BC foram superiores ao algoritmo BP. Por´em, em algumas instˆancias, os melhores limites duais foram obtidos pelo algoritmo BP.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:28:53Z (GMT). No. of bitstreams: 1 Lopes_MauroCardoso_M.pdf: 3797752 bytes, checksum: c82bee131ad99d747e42150908135190 (MD5) Previous issue date: 2014 / Resumo: Investigamos uma variante do problema de localização e roteamento com relação de muitos-para-muitos concentradores que consiste em particionar o conjunto de vértices de um grafo em ciclos contendo exatamente um concentrador cada e determinar um ciclo adicional interligando todos os concentradores. Qualquer vértice do grafo pode ser um concentrador; faz parte do problema determinar quais vértices devem ser concentradores. Esse problema tem aplicações práticas relevantes em áreas como transporte urbano e redes de computadores. Desenvolvemos uma heurística baseada em busca local com operações de inserção, remoção e troca de vértices. Soluções iniciais são geradas de maneira aleatória, e suas vizinhanças são exploradas a fim de obter melhores soluções. Além disso, elaboramos um algoritmo exato com estrutura de branch-and-cut para a formulação em Programação Linear Inteira proposta. Restrições de capacidade e eliminação de caminhos são adicionadas como planos de corte, com algoritmos de separação baseados em árvores de corte mínimo e nas componentes conexas de um grafo suporte. Diversos experimentos computacionais mostram a capacidade de resolução do algoritmo exato para instâncias pequenas e da heurística para instâncias pequenas e médias. São comparados também os desempenhos para outras variantes do problema / Abstract: We investigate a variant of the many-to-many hub location-routing problem which consists in partitioning the set of vertices of a graph into cycles containing exactly one hub each and determining an extra cycle interconnecting all hubs. Any vertex of the graph can be a hub; it is part of the problem to determine which vertices should be hubs. This problem has relevant practical applications in areas such as urban transportation and computer networks. A local search based heuristic that considers add/remove and swap operations is developed. Initial solutions can be generated at random, and their neighborhoods are explored in order to get better solutions. Also a branch-and-cut approach that solves an integer formulation is investigated. Capacity and path elimination constraints are added in a cutting plane way, so the separation algorithms are based on the computation of min-cut trees and in the connected components of a support graph. Many computational experiments over several instances adapted from literature show the problem-solving capability of the exact algorithm for small instances and of the heuristic for small to medium-sized instances. We also compare the performance of other variants of the problem / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] A propagação de influências tem sido objeto de extensos estudos devido a seu importante impacto em redes sociais, epidemiologia e muitas outras áreas. A compreensão do mecanismo de propagação é crítica, por exemplo, para controlar a disseminação de notícias falsas ou controlar uma epidemia. Neste trabalho, seguimos uma perspectiva de otimização e identificamos o menor grupo de usuários que precisam ser convertidos para atingir um certo nível de influência em toda a rede. Portanto, estudamos formalmente o problema de influência de menor custo generalizado, propondo algoritmos de programação matemática para resolver este problema. Introduzimos novos algoritmos de planos de corte e separação, e os incorporamos em um algoritmo de branch-and-cut. Nossos resultados experimentais em instâncias da literatura demonstram a capacidade do método de resolver pequenas e médias instâncias, bem como diminuir o gap da melhor solução conhecida e inclusive encontrando também soluções ótimas para alguns problemas em aberto. / [en] Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding the propagation mechanism is critical, e.g., to control the spread of fake news or to control an epidemic. In this work, we follow an optimization perspective, and attempt to identify the smallest group of users that needs to be converted to achieve an certain influence level over the entire network. We therefore formally study the generalized least cost influence problem, proposing mathematical programming algorithms to solve the challenging problem. We introduce new cutting plane and separation algorithms and embed them into a branch-and-cut algorithm. Our experimental results on classical benchmark instances demonstrates the method ability to solve small-to medium-scale benchmark instances, also finding optimal solutions for some open problems.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema._________________________________________________________________________________________ ABSTRACT: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T07:24:38Z (GMT). No. of bitstreams: 1 Piva_Breno_M.pdf: 1251793 bytes, checksum: bf559620a7bdefeec032b5c87d196b5b (MD5) Previous issue date: 2009 / Resumo: O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema / Abstract: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

Les activités de transport et de gestion des stocks ont un impact important les unes sur les autres. Assurer un niveau de stock idéal peut demander des livraisons fréquentes, ce qui entraîne des coûts logistiques élevés. Pour optimiser les compromis entre les coûts de stock et de transport, des systèmes VMI (Vendor Managed Inventory) ont été développés pour gérer ensemble les opérations de stock et de transport. Pour un ensemble de clients ayant des demandes sur un horizon de temps, le problème de détermination des tournées et des quantités à livrer avec un coût minimum de gestion de stock et de transport est connu sous le nom de Inventory Routing Problem (IRP). Les systèmes à deux échelons ont également été étudiés pour améliorer le flux de véhicules dans les zones urbaines. étant donné que des nouvelles politiques de gestion sont apparues, dans le but de limiter le trafic des gros véhicules et leur vitesse dans les centres urbains, des Centres de Distribution (DC) sont mis en place pour coordonner les flux de marchandises à l'intérieur et à l'extérieur des zones urbaines. Les produits sont donc livrés aux clients par les fournisseurs via les DC.Nous proposons de combiner un système à deux échelons avec le IRP. Nous introduisons un Operational Two-Echelon Inventory Routing Problem (O-2E-IRP), ce qui est une nouvelle extension du IRP à notre connaissance. Dans le O-2E-IRP proposé, les clients doivent être servis par un fournisseur strictement via des DC et les tournées doivent être définis dans les deux échelons sur un horizon de temps donné. Trois politiques de réapprovisionnement et de configurations de routage différentes sont modélisées pour ce problème. Nous développons deux formulations mathématiques, ainsi qu'un algorithme Branch-and-Cut (B&C) combiné à une matheuristique pour résoudre le problème. De plus, nous analysons plusieurs inégalités valides disponibles pour le IRP et nous introduisons de nouvelles inégalités valides inhérentes au IRP à deux échelons. Des expériences de calcul approfondies ont été effectuées sur un ensemble d'instances générées de manière aléatoire. Les résultats obtenus montrent que les performances des méthodes sont liées à la politique de stock et à la configuration de routage.Dans le contexte d'un IRP à deux échelons, deux décisions tactiques importantes doivent être prises en plus des décisions de livraison de routage et de quantité de livraison: à partir de quel DC sera fourni chaque client et en utilisant quels véhicules ? Répondre à ces questions est extrêmement difficile car cela implique de pouvoir minimiser les coûts opérationnels d'un système de livraison VMI à deux échelons à long-terme et avec des demandes incertaines. Pour faire face à cela, nous présentons le Tactical Two-Echelon Inventory Routing Problem (T-2E-IRP) qui optimise les décisions en fonction d'un horizon à long-terme et en tenant compte des demandes stochastiques. Trois politiques de gestion des stocks sont modélisées et appliquées à un ou aux deux échelons. Nous développons une approche de simulation pour résoudre le T-2E-IRP sur un horizon de temps à long-terme. Nous proposons quatre formulations et deux algorithmes B&C pour définir l'affectation des clients et des véhicules aux DC en fonction d'un horizon de temps court. Ensuite, nous évaluons ces décisions d'affectation via un outil de simulation qui résout un sous-problème du T-2E-IRP, qui consiste en les décisions de livraisons du fournisseur aux DC et des DC aux clients, sur un horizon glissant. De nombreuses expériences sont effectuées pour un ensemble d'instances générées aléatoirement. L'impact de plusieurs paramètres utilisés pour déterminer l'affectation des clients et des véhicules aux DC sur le coût total est analysé. Basé sur des expériences, nous définissons la combinaison de paramètres qui fournit généralement les meilleurs résultats sur les instances générées. / Transport and inventory management activities have a great impact on each other. Ensuring an ideal inventory level can require frequent deliveries, leading to high logistics costs. To optimize the trade-offs between inventory and transportation costs, VMI (Vendor Managed Inventory) systems have been developed to manage inventory and transportation operations together. Given a set of customers with demands over a time horizon, the problem of determining routes and delivery quantities at a minimum inventory holding and transportation costs is known as Inventory Routing Problem (IRP). Two-echelon systems have also been studied to improve the freight vehicle flow inside urban areas. As new management policies have emerged, with the goal of limiting the traffic of large vehicles and their speed in urban centers, Distribution Centers (DC) are introduced to coordinate freight flows inside and outside the urban areas. Products are then delivered from the suppliers to the customers through the DC.We propose to combine a two-echelon system with the IRP. We introduce an Operational Two-Echelon Inventory Routing Problem (O-2E-IRP), which is a new extension of the IRP to the best of our knowledge. On the proposed O-2E-IRP, the customers must be served by a supplier strictly through DC and routes must be defined in both echelons over a given time horizon. Three different replenishment policies and routing configurations are modeled for this problem. We develop two mathematical formulations, and a Branch-and-Cut (B&C) algorithm combined with a matheuristic to solve the problem. In addition, we analyze several valid inequalities available for IRP, and we introduce new ones inherent to the IRP within two echelons. Extensive computational experiments have been carried out on a set of randomly generated instances. The obtained results show that the performance of the methods is related to the inventory policy and routing configuration.In the context of a two-echelon IRP, two important tactical decisions have to be taken in addition to route and quantity delivery decisions: from which DC will be supplied each customer and using which vehicles? Answering these questions is extremely difficult as it implies being able to minimize operational costs for a two-echelon VMI delivery system on long-term and with uncertain demands. In order to deal with this, we introduce the Tactical Two-Echelon Inventory Routing Problem (T-2E-IRP) that optimizes the decisions based on a long-term horizon and considering stochastic demands. Three inventory management policies are modeled and applied at one or both echelons. We develop a simulation approach to solve the T-2E-IRP on a long-term time horizon. We propose four formulations and two B&C algorithms to define the assignment of customers and vehicles to the DC based on a short time horizon. Then, we evaluate these assignment decisions through a simulation tool that solves a subproblem of the T-2E-IRP, which consists of the decisions of deliveries from the supplier to the DC and from the DC to the customers, on a rolling-horizon framework. Extensive computational experiments are performed for a set of randomly generated instances. The impact of several parameters used to determine the assignment of customers and vehicles to DC on the total cost is analyzed. Based on the experiments, we define the combination of parameters that generally provides the best results on the generated instances.