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.

[pt] Esta tese generaliza a variante multi-período do clássico problema da Árvore de Steiner com coleta de prêmios (PCST), que visa encontrar um subgrafo conexo que maximize os prêmios recuperados de nós conectados menos o custo de utilização das arestas conectadas. Este trabalho adicionalmente: (a) permite que vértices sejam conectados à árvore em diferentes períodos de tempo; (b) impõe um orçamento pré-definido em arestas selecionadas em um horizonte específico de períodos de tempo; e (c) limita o comprimento total de arestas que podem ser adicionadas em um período de tempo. Um algoritmo branch-and-cut é fornecido para este problema, avaliando satisfatoriamente instâncias benchmark da literatura, adaptadas para uma configuração multi-período, de até aproximadamente 2000 vértices e 200 terminais em tempo razoável. / [en] This thesis generalizes the multi-period variant of the classical Prizecollecting Steiner Tree Problem, which aims at finding a connected subgraph that maximizes the revenues collected from connected nodes minus the costs to utilize the connecting edges. This work additionally: (a) allows vertices to be added to the tree at different time periods; (b) imposes a predefined budget on edges selected over a specific horizon of time periods; and (c) limits the total length of edges that can be added over a time period. A branch-and-cut algorithm is provided for this problem, satisfactorily evaluating benchmark instances from the literature, adapted to a multi-period setting, up to approximately 2000 vertices and 200 terminals in reasonable time.

Norrmejerier står inför förändringar vad gäller både mjölkkonsumtion och flytt av produktionen från Luleå mejeri till Umeå mejeri inom en snar framtid. Det har gett behov av ett verktyg för att snabbt kunna fatta beslut om systemet kan hantera en ökad mängd volym och antal produktkategorier. För att ta fram ett sådant verktyg skapades en matematisk optimeringsmodell uppbyggd i programvaran Python som gör det möjligt att köra programmet för olika scenarion. Modellen använder optimeringslösaren Pulp för att hitta en lösning på problemet. Den matematiska modellen baseras på Multi Commodity Flow Problem med tidsvariabel i kombination med Flow-shop scheduling och har modifierats efter systemet på Umeå mejeri. Det är en pessimistisk modell baserat på de antaganden som gjorts i rapporten. Programmet baseras på ett dygns produktion och avgör, genom att minimera den totala tiden det tar för flödet genom processen, om det finns kapacitet för en ökad produktion. Systemet i projektet är uppdelat i två subnätverk på grund av tidskomplexiteten och resultaten visar att implementering av en ytterligare produktkategori kan hanteras av båda subnätverken. En ökad volym med 10% av den befintliga kan endast hanteras av den första delen av nätverket. Det betyder att det finns tekniska begränsningar i det andra subnätverket. Genom tillägg av extra noder som kan användas till en viss straffkostnad kunde flaskhalsar identifieras och det visade sig att pastör 2P1 är en uppenbar flaskhals i systemet. Om man ökar produktionen ytterligare kan även silosarna behöva utökas för att hantera flödet. / Norrmejerier is facing changes in terms of both milk consumption and a move of the production from Luleå dairy to Umeå dairy in the near future. This has given rise to the need of a tool that quickly can make descisions about whether the system can handle an increased amount of volume and number of product categories. To produce such a tool a mathematical optimization model was created in Python which makes it possible to run the program for different scenarios. The model uses the optimization solver Pulp. The mathematical model is based on Multi Commodity Flow Problem with time variable combined with Flow-shop scheduling and has been modified according to the system at Umeå dairy. Based on the assumptions made in the report it is a pessimistic model. The program is based on one day's production and determines by minimizing the total time it takes for the flow to pass through the system, to see if there is enough capacity for increased production. The system in the project is divided into two subnetworks due to the time complexity and the results show that implementation of an additional product category can be handled by both subnetworks. An increased volume of 10% of the existing volume can only be handled by the first part of the network. This means that there are technical limitations in the second subnetwork. By adding extra nodes that can be used for a certain penalty cost, bottlenecks could be identified and it turned out that Pasteur 2P1 is an obvious bottleneck in the system. If the production increases further the silos may also need to be expanded to handle the flow in the system.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d'arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d'arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de "Branch and cut". Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales dans un schéma énumératif. Les approches heuristiques et l'algorithme exact que nous proposons sont comparés à d'autres heuristiques de la littérature et au Solveur de programmes linéaires Cplex . L'ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement de taille modérée.