This dissertation studies in depth the structure of the Discrete Ordered Median Problem (DOMP), to define new formulations and resolution algorithms. Furthermore we analyze an interesting extension for DOMP, namely MDOMP (Monotone Discrete Ordered Median Problem). This thesis is structured in three main parts.First, a widely theoretical and computational study is reported. It presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP. One of the achievements of the new formulation consists in its tighter LP-bound. Secondly, DOMP is addressed with a new set partitioning formulation using an exponential number of variables. This chapter develops a new formulation in which each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding distances. We use a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-cut-and-price algorithm to solve to optimality small to moderate size of DOMP in competitive computational time.To finish, the third contribution of this dissertation is to analyze and compare formulations for the monotone discrete ordered median problem. These formulations combine different ways to represent ordered weighted averages of elements by using linear programs together with the p-median polytope. This approach gives rise to two efficient formulations for DOMP under a hypothesis of monotonicity in the lambda vectors. These formulations are theoretically compared and also compared with some other formulations valid for the case of general lambda vector. In addition, it is also developed another new formulation, for the general case, that exploits the efficiency of the rationale of monotonicity. This representation allows to solve very efficiently some DOMP instances where the monotonicity is only slightly lost. Detailed computational tests on all these formulations is reported in the dissertation. They show that specialized formulations allow to solve to optimality instances with sizes that are far beyond the limits of those that can solve in the general case. / Cette dissertation étudie en profondeur la structure du "Discrete Ordered Median Problem" (DOMP), afin de proposer de nouvelles formulations et de nouveaux algorithmes de résolution. De plus, une extension intéressante du DOMP nommée MDOMP ("Monotone Discrete Ordered Median Problem") a été étudiée.Cette thèse a été structurée en trois grandes parties.La première partie présente une étude riche aux niveaux théorique et expérimentale. Elle développe plusieurs formulations pour le DOMP qui sont basées sur des problèmes d'ordonnancement largement étudiés dans la littérature. Plusieurs d'entres elles nécessitent un nombre réduit de contraintes pour définir le problème en ce qui concerne certaines formulations connues antérieurement. Les bornes inférieures, qui sont obtenues par la résolution de la relaxation linéaire, donnent de meilleurs résultats que les formulations précédentes et ceci même avec tout processus de renforcement désactivé. S'ensuit une étude du polyhèdre de notre formulation la plus forte qui montre sa proximité entre l'enveloppe convexe des solutions entières de notre problème. Un algorithme de branch and cut et d'autres méthodes de résolution sont ensuite comparés. Les expérimentations qui montrent la puissance de nos méthodes s'appuient sur deux grandes familles d'instances. Les premières sont générées aléatoirement et les secondes proviennent de Beasley's OR-library. Ces expérimentations mettent en valeur la qualité de la borne obtenue par notre formulation.La seconde partie propose une formulation "set partitioning" avec un nombre exponentiel de variables. Dans ce chapitre, la formulation comporte des variables associées à un ensemble de demandes affectées à la même facilité selon l'ordre établi sur leurs distances correspondantes. Nous avons alors développé un algorithme de génération de colonnes pour la résolution de la relaxation continue de notre modèle mathématique. Cet algorithme est ensuite déployé au sein d'un Branch-and-Cut-and-Price afin de résoudre des instances de petites et moyennes tailles avec des temps compétitifs.La troisième partie présente l'analyse et la comparaison des différentes formulations du problème DOMP Monotone. Ces formulations combinent plusieurs manières de formuler l'ordre des éléments selon les moyennes pondérées en utilisant plusieurs programmes linéaires du polytope du p-median. Cette approche donne lieu à deux formulations performantes du DOMP sous l'hypothèse de monotonie des vecteurs lambda. Ces formulations sont comparées de manière théorique puis comparées à d'autres formulations valides pour le cas général du vecteur lambda. Une autre formulation est également proposée, elle exploite l'efficacité du caractère rationnel de la monotonie. Cette dernière permet de résoudre efficacement quelques instances où la monotonie a légèrement disparue. Ces formulations ont fait l'objet de plusieurs expérimentations dècrites dans ce manuscrit de thèse. Elles montrent que les formulations spécifiques permettent de résoudre des instances plus importantes que pour le cas général. / Este trabajo estudia en profundidad la estructura del problema disctreto de la mediana ordenada (DOMP, por su acrónimo en inglés) con el objetivo de definir nuevas formulaciones y algoritmos de resolución. Además, analizamos una interesante extensión del DOMP conocida como el problema monótono discreto de la mediana ordenada (MDOMP, de su acrónimo en inglés).Esta tesis se compone de tres grandes bloques.En primer lugar, se desarrolla un detallado estudio teórico y computacional. Se presentan varias formulaciones nuevas para el problema discreto de la mediana ordenada (DOMP) basadas en su similaridad con algunos problemas de secuenciación. Algunas de estas formulaciones requieren de un cosiderable menor número de restricciones para definir el problema respecto a algunas de las formulaciones previamente conocidas. Además, las cotas inferiores proporcionadas por las relajaciones lineales mejoran a las obtenidas con formulaciones previas de la literatura incluso sin reforzar la nueva formulación. También presentamos un estudio poliédrico del politopo de asignación de nuestra formulación más compacta mostrando su proximidad con la envolvente convexa de las soluciones enteras del problema. Se comparan algunos procedimientos de resolución, entre los que destacamos un algoritmo de ramificación y corte. Amplios resultados computacionales sobre dos familias de instancias -aleatoriamente generadas y utilizando la Beasley's OR-library- muestran la potencia de nuestros métodos para resolver el DOMP.En el segundo bloque, el problema discreto de la mediana ordenada es abordado con una formulación de particiones de conjuntos empleando un número exponencial de variables. Este capítulo desarrolla una nueva formulación en la que cada variable corresponde a un conjunto de puntos de demanda asignados al mismo servidor con la información de la posición obtenida de ordenar las distancias correspondientes. Utilizamos generación de columnas para resolver la relajación continua del modelo. Después, empleamos un algoritmo de ramificación, acotación y "pricing" para resolver a optimalidad tamaños moderados del DOMP en un tiempo computacional competitivo.Por último, el tercer bloque de este trabajo se dedica a analizar y comparar formulaciones para el problema monótono discreto de la mediana ordenada. Estas formulaciones combinan diferentes maneras de representar medidas de pesos ordenados de elementos utilizando programación lineal junto con el politopo de la $p$-mediana. Este enfoque da lugar a dos formulaciones eficientes para el DOMP bajo la hipótesis de monotonía en su vector $lambda$. Se comparan teóricamente las formulaciones entre sí y frente a algunas de las formulaciones válidas para el caso general. Adicionalmente, se desarrolla otra formulación válida para el caso general que explota la eficiencia de las ideas de la monotonicidad. Esta representación permite resolver eficientemente algunos ejemplos donde la monotonía se pierde ligeramente. Finalmente, llevamos a cabo un detallado estudio computacional, en el que se aprecia que las formulaciones ad hoc permiten resolver a optimalidad ejemplos cuyo tamaño supera los límites marcados en al caso general. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB. / Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.

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.

A payment is the most fundamental aspect of a trade that involves funds. In recent years, the development of new payment services has accelerated significantly as the world has moved further into the digital era. This transition has led to an increased demand of digital payment solutions that can handle trades across the world. As trades today can be agreed at any time wherever the payer and payee are located, the party that mediates payments must at any time to be available in order to mediate an agreed exchange. This requires the payment service provider to always have funds available in the required countries and currencies in order for trades to always be available. This thesis concerns how a payment service provider can reallocate capital in a cost efficient way in order for trades to always be available. Traditionally, the reallocation of capital is done in a rule-based manner, which discard the cost dimension and thereby only focus on the reallocation itself. This thesis concerns methods to optimally reallocate capital focusing on the cost of transferring capital within the network. Where the concerned methods has the potential of transferring capital in a far more cost efficient way. When mathematically formulating the reallocation decisions as an optimization problem, the cost function is formulated as a linear program with both Boolean and real constraints. This impose non-feasibility of locating the optimal solution using traditional methods for linear programs, why developed traditional and more advanced methods were used. The model was evaluated based on a large number of simulations in comparison with the performance of a rule-based reallocation system. The developed model provides a significant cost reduction compared to the rule-based approach and thereby outperforms the traditional reallocation system. Future work should focus on expanding the model by broadening the available transfer options, by increasing the considered uncertainty via a bayesian treatment and finally by considering all cost aspects of the network. / En betalning är den mest fundamentala aspekten av handel som involverar kapital. De senaste åren har utvecklingen av nya betalmedel ökat drastiskt då världen fortsatt att utvecklas genom digitaliseringen. Utvecklingen har lett till en ökad efterfrågan på digitala betalningslösningar som kan hantera handel över hela världen. Då handel idag kan ske när som helst oberoende av var betalaren och betalningsmottagaren befinner sig, måste systemet som genomför betalningen alltid vara tillgängligt för att kunna förmedla handel mellan olika parter. Detta kräver att betalningssystemet alltid måste ha medel tillgängligt i efterfrågade länder och valutor för att handeln ska kunna genomföras. Den här uppsatsen fokuserar på hur kapital kostnadseffektivt kan omallokeras i ett betalsystem för att säkerställa att handel alltid är tillgängligt. Traditionellt har omallokeringen av kapital gjorts på ett regelbaserat sätt, vilket inte tagit hänsyn till kostnadsdimensionen och därigenom enbart fokuserat på själva omallokeringen. Den här uppsatsen använder metoder för att optimalt omallokera kapital baserat på kostnaderna för omallokeringen. Därigenom skapas en möjlighet att flytta kapital på ett avsevärt mer kostnadseffektivt sätt. När omallokeringsbesluten formuleras matematiskt som ett optimeringsproblem är kostnadsfunktionen formulerad som ett linjärt program med både Booleska och reella begränsningar av variablerna. Detta gör att traditionella lösningsmetoder för linjära program inte är användningsbara för att finna den optimala lösningen, varför vidareutveckling av tradtionella metoder tillsammans med mer avancerade metoder använts. Modellen utvärderades baserat på ett stort antal simuleringar som jämförde dess prestanda med det regelbaserade systemet. Den utvecklade modellen presterar en signfikant kostnadsreduktion i jämförelse med det regelbaserade systemet och överträffar därigenom det traditionellt använda systemet. Framtida arbete bör fokusera på att expandera modellen genom att utöka de potentiella överföringsmöjligheterna, att ta ökad hänsyn till osäkerhet genom en bayesiansk hantering, samt slutligen att integrera samtliga kostnadsaspekter i nätverket.

Dans cette thèse nous considérons deux problèmes d'optimisation combinatoire.Le premier s'appelle problème du double voyageur de commerce avec contraintes de piles. Dans ce problème, un véhicule doit ramasser un certain nombre d'objets dans une région pour les livrer à des clients situés dans une autre région. Lors du ramassage, les objets sont stockés dans les différentes piles du véhicule et la livraison des objets se fait selon une politique de type last-in-first-out. Le ramassage et la livraison consistent chacune en une tournée Hamiltonienne effectuée par le véhicule dans la région correspondante.Nous donnons une formulation linéaire en nombres entiers pour ce problème. Elle est basée sur des variables de précédence et sur des contraintes de chemins infaisables. Nous donnons par la suite des résultats polyédraux sur l'enveloppe convexe des solutions de notre formulation. En particulier, nous montrons des liens forts avec un polytope associé au problème du voyageur de commerce et des liens avec un polytope de type set covering. Cette étude polyédrale nous permet de renforcer la formulation initiale et de développer un algorithme de coupes et branchements efficace. Le deuxième problème que nous considérons consiste à trouver la description des polytopes lexicographiques. Ces derniers sont les enveloppes convexes des points entiers lexicographiquement compris entre deux points entiers fixés. Nous donnons une description complète de ces polytopes en termes d'inégalités linéaires. Nous démontrons que la famille des polytopes lexicographiques est fermée par intersection. / In this thesis we consider two problems arising in combinatorial optimization.The first one is the double traveling salesman problem with multiple stacks. In this problem a vehicle picks up a given set of items in a region and subsequently delivers them to demanding customers in another region. When an item is picked up, it is put in a stack of the vehicle. The items are delivered observing a last-in-first-out policy. The pickup phase and the delivery phase consist in two Hamiltonian circuits, each performed by the vehicle in the corresponding region. We give a new integer linear programming formulation for this problem. Its main features are the presence of precedence variables and new infeasible path constraints. We provide polyhedral results on the convex hull of the solutions to our formulation. In particular, we show strong links with a specific TSPpolytope and a specific set covering polytope. We deduce strengthening inequalities for the initial formulation, subsequently embedded in an efficient branch-and-cut algorithm. The second problem we consider consists in finding the description of the lexicographical polytopes. These are convex hulls of the integer points lexicographically between two given integer points. We give a complete description of these polytopes by means of linear inequalities. We show that the lexicographical polytope family is closed under intersection.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.