Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

O problema de corte de estoque consiste em cortar objetos maiores, disponíveis em estoque, para produzir uma quantidade especificada de peças menores, de modo que uma certa função objetivo seja otimizada. Um modelo de otimização linear tem sido amplamente utilizado na solução deste problema desde os anos 60, que incorpora parte da estrutura combinatória inerente ao problema na construção das colunas da matriz de restrições. As colunas são construídas a cada iteração do Método Simplex, chamando-se geração de colunas. Apesar do método Simplex ser largamente utilizado para este tipo de problema, apresenta baixa convergência quando próximo da otimalidade, pouco melhorando a função objetivo. Assim, estratégias para aceleração do Método Simplex faz-se necessário, uma maneira consiste na redução do espaço dual, com a introdução de restrições (colunas no primal) que evite grandes variações nas variáveis duais, chamadas cortes duais. Neste trabalho, generalizamos duas famílias de cortes duais recentemente publicadas e analisamos o impacto computacional desses cortes duais sobre a convergência do Método Simplex / The cutting stock problem consists of cutting large available objects in stock to produce a quantity of ordered smaller itens, in such a way as to optimize a given objective function. A linear optmizatim model has been widely used to solve this problem since the 60s, in which part of a combinatorial structure of the problem is embedded. The columns of the constraint matrix are generated in each iteration of the Simplex Method, called the column generation technique. Although, the Simplex Method is widely used, it has a low convergence near to optimality. In this way, strategies to accelerate the Simplex Method are welcome which can be obtained by adding dual cuts (primal columns). The goal of this work is to study published dual cuts and to proposed others. In this book us extend two families of dual cuts, which were recently published, and analyse the computational impact of these dual cuts on the converge of the Simplex Method

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2004-07-30Bitstream added on 2014-06-13T20:55:45Z : No. of bitstreams: 1 cavali_r_me_sjrp.pdf: 560996 bytes, checksum: 6792ea8d0dd5f26eb5250b68217a4443 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Diariamente, em indústrias de móveis, painéis retângulares de madeira são cortados em retângulos menores para a manufatura de seus produtos. Por causa da possível perda de material envolvida neste processo e de sua influência no custo dos produtos, existe a necessidade de um planejamento prþevio para a realização dos cortes. Na maioria das empresas de móveis situadas na região Noroeste do estado de São Paulo, este planejamento é feito manualmente e não é uma tarefa simples. O enfoque deste trabalho þe analisar a utilização de um sistema computacional no planejamento do corte de painéis de madeira. Esta ferramenta é capaz de resolver o problema do corte bidimensional segundo o algoritmo de dois estþagios de Gilmory e Gomore. Aspectos práticos encontrados no corte dos painéis e estratégias adotadas pelas empresas no planejamento da produção são abordados. Além disso, apresentamos os resultados de um estudo computacional com base em dados reais de uma das empresas visitadas. / In the furniture industries, the cut of rectangular plates to produce smaller rectangular pieces is an every day task. To reduce the waste of material involved in this process and its influence in the cost of the products, a previous planning for the cuts is necessary. In the majority of the furniture companies situated at Northwest region of the state of São Paulo, the generation of cutting patterns is made manually and it is not a simple task. The goal of this work is to analyze the use of a computational system in the cutting patterns generation. This computational system is able to solve the two-dimensional cutting stock problem by the 2-stage Gilmory and Gomore method. Practical aspects found in the cutting patterns generation and strategies adopted for the companies in the production planning are discussed. We also report some results of the application of the computacional system to the cutting patterns generation based on real data of one company.

O presente trabalho desenvolve uma extensão do problema de corte de estoque unidimensional no caso em que a demanda pelos vários tipos de itens não é exatamente conhecida. Para considerar a aleatoriedade, foi proposto um modelo de programação estocástica de dois estágios com recurso. As varáveis de primeiro estágio são os números de barras cortadas por padrão de corte, e as variáveis de segundo estágio, os números de itens produzidos em escassez e em escassez. O objetivo do modelo é minimizar o custo total esperado. Para resolver a relaxação linear do modelo, foram propostos um método exato baseado no método Simplex com geração de colunas e uma estratégia heurística, que considera o valor esperado da demanda na resolução do problema de corte de estoque. As duas estratégias foram comparadas, assim como a possibilidade de resolver o problema de corte ignorando as incertezas. Finalmente, observou-se que é mais interessante determinar o valor ótimo do modelo recurso quando o problema sofre mais influência da aleatoriedade / This paper presents an integer linear optimization model of large scale for the one-dimensional cutting stock problem in the case which a demand is considered a random variable. To take this randomness into account, the problem was formulated as a two-stage stochastic linear program with recourse. The first stage decision variables are given by the number of bars that has to be cut according to each pattern, and the second stage decision variables by the number of holding items or backordering items production. The model objective is minimizes the total expected cost. We propose two methods to solve the model linear relaxation, one of them it is a Simplex-based method with column generation. The second method is a heuristic strategy that adopted the expected value of demand. We compare both strategies and the possibly of ignoring uncertainties on model. Finally, we observe that is much more interesting to determine the optimal recourse model solution when we have problems that are more afected by randomness

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

Submitted by GISLAINE MARA MELEGA null (gis_laine_m@hotmail.com) on 2017-03-27T18:20:11Z No. of bitstreams: 1 TESE_Gislaine Melega_Matemática.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-29T19:23:05Z (GMT) No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) / Made available in DSpace on 2017-03-29T19:23:05Z (GMT). No. of bitstreams: 1 melega_gm_dr_sjrp.pdf: 2710288 bytes, checksum: 9c3a4e388e7584cf0423182dcfdcced8 (MD5) Previous issue date: 2017-02-21 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução para este tipo de problema, com três níveis e vários períodos, é estudado a partir do desenvolvimento de métodos de solução considerando abordagens que superam as dificuldades do problema, que consistem no alto número de padrões de corte, estruturas em vários níveis (multiestágios) e variáveis binárias de preparo. Os métodos de solução propostos para o problema GILSCS são baseados em duas abordagens conhecidas da literatura, usadas com sucesso para resolver os problemas separadamente, que são o procedimento de geração de colunas e heurísticas de decomposição do tipo relax-and-fix. Estas estratégias e suas variações são combinadas à um pacote de otimização em um estudo computacional com dados gerados aleatoriamente. Uma revisão da literatura, em termos de métodos de solução, para o problema integrado também é apresentada. Outras contribuições desta tese consistem em propor diferentes modelos matemáticos para o problema integrado, combinando modelos alternativos para cada um dos problemas separadamente. Neste estudo, o objetivo é comparar e avaliar, com um extensivo estudo computacional, a qualidade e o impacto das diferentes formulações. O outro trabalho trata de uma aplicação do problema integrado em um indústria de móveis de pequeno porte, em que restrições específicas do ambiente industrial são abordadas, como estoque de segurança e ciclos da serra. A solução obtida pelo modelo proposto é comparada com uma simulação da prática da empresa. / In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the development of solution approaches that overcome the difficulties of the problem, which are the high number of cutting patterns, multi-level structures and the binary values of the setup variables. The solution methods proposed to the GILSCS problem are based on two known strategies from the literature which are used successfully to solve the problems separately, which are the column generation procedure and decomposition heuristics based on relax-and-fix procedure. These strategies and their variations are combined into an optimization package in a computational study with randomly generated data. A literature review, in terms of solution methods, to the integrated problem, is also presented. Other contributions of this thesis consist of proposing different mathematical models for the integrated problem combining alternative models for each one of the problems separately. In this study, the aim is to compare and evaluate, with an extensive computational study, the quality and the impact of these dfifferent formulations. Another study is an application of the integrated problem in a small furniture factory, in which specific constraints related to the industrial environment are addressed, such as, safety stock level constraints and saw cycles constraints. The solution obtained from the proposed model is compared to a simulation of the common practice in the company. / FAPESP: 2012/20631-2

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Made available in DSpace on 2014-07-29T14:57:52Z (GMT). No. of bitstreams: 1 Dissertacao Diego Galindo Pecin.pdf: 448272 bytes, checksum: 755b351108c1082bc3bdb084b7add6ec (MD5) Previous issue date: 2010-02-23 / This dissertation addresses the optimization of the Elementary Shortest Path Problem with a Capacity Constraint (ESPPCC) and describes algorithms for its resolution that make use of concepts such as Label-Setting, Bidirectional Dynamic Programming and Decremental State Space Relaxation. These algorithms were used in a robust CVRP s Branch-and- Cut-and-Price framework as the column generation mechanism. The resulting BCP was used to obtain results (lower bounds, processing time and the number of branching nodes generated) to several CVRP s test instances. These results are compared with previous ones obtained with the original BCP, which is based on k-cycle elimination. Elementary routes are also explored in a route enumeration context, which allows the enumeration of all possible relevant elementary routes, i.e., all routes that have a chance of being part of an optimal CVRP s solution. If the number of relevant routes is not too large (say, in the range of tenths of thousands), the overall problem may be solved by feeding a general MIP solver with a set-partition formulation containing only those routes. If this set-partition can be solved, the optimal solution will be found and no branch will be necessary. Sometimes this leads to very significant speedups when compared to traditional branch strategies. / Esta dissertação aborda o Problema do Caminho Elementar Mínimo com Restrição de Capacidade (ESPPCC Elementary Shortest Path Problem with a Capacity Constraint) e descreve algoritmos para a sua resolução que fazem uso de conceitos tais como Correção de Rótulos, Programação Dinâmica Bidirecional e Relaxação Decrescente do Espaço de Estados. Esses algoritmos foram usados como geradores de rotas elementares no subproblema de geração de colunas de um algoritmo BCP robusto para o CVRP. Os resultados (limites inferiores, tempo de processamento e número de nós gerados) obtidos, para algumas instâncias de teste do CVRP, são comparados aos obtidos na versão original desse algoritmo BCP, que utiliza rotas não elementares sem 3-ciclos ou 4-ciclos. Rotas elementares também são exploradas em um contexto de enumeração para o CVRP, a qual permite obter rotas (usando um critério baseado em limites e em custo reduzido) que possuem uma chance de pertencer a uma solução ótima. Se o número de rotas não for muito grande (na ordem de poucos de milhares), então todo o problema pode ser resolvido como um problema de particionamento de conjuntos contendo apenas tais rotas. Algumas vezes isso acelera o algoritmo Branch-and-Bound consideravelmente, quando comparado com estratégias tradicionais de particionamento (branching), já que muitos nós da árvore podem ser resolvidos sem a geração de novos nós.