Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Insituto de Computação / Made available in DSpace on 2018-08-17T16:49:45Z (GMT). No. of bitstreams: 1 DelValle_AlineMarques_M.pdf: 1217777 bytes, checksum: 66f10d1b6b4533727cbe82431f97660d (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação, estudamos problemas de empacotamento com itens irregulares. Estamos particularmente interessados no Problema da Mochila Bidimensional: dados um recipiente de tamanho W x H e uma lista de itens bidimensionais, o objetivo é empacotar um subconjunto dos itens de forma a maximizar a área dos itens empacotados. Existem diversos trabalhos que lidam com problemas para itens e recipientes bidimensionais com forma regular (retangular). No entanto, são poucos os estudos que tratam de itens com formas irregulares. Nós propomos algoritmos de empacotamento para itens irregulares em recipientes limitados baseados no uso de No-Fit-Polygon (NFP). Este trabalho apresenta uma heurística GRASP para a versão restrita do Problema da Mochila: uma solução inicial gulosa é gerada e, em seguida, utiliza-se um algoritmo de busca local para melhorar solução atual. Uma estratégia híbrida também foi proposta para versão irrestrita do Problema da Mochila. Ela divide-se em passos de empacotamento de itens irregulares e empacotamento de itens regulares. Testamos os algoritmos com instâncias adaptadas do problema de Strip Packing. O GRASP obteve empacotamentos ótimos para várias instancias testadas e, mesmo para as instâncias em que o algoritmo não obteve resultados ótimos, os empacotamentos obtidos tiveram boa taxa de ocupação, com valores relativamente próximos do ótimo. O tempo de execução do algoritmo foi razoável. Na estratégia híbrida, obtiveram-se empacotamentos bons para a maioria das instâncias, com taxa de ocupação acima de 90% e tempos de execução relativamente baixos / Abstract: In this work, we study packing problems dealing with two dimensional irregular items. We are particularly interested in the knapsack version of the problem: given a container with size W x H and a list of two dimensional items, the goal is to pack a subset of items such that the total area of packed items is maximized. There are several works that deal with problems for the case where items and containers have regular shapes (rectangular). However, only a few studies deal with items with irregular shapes. We propose algorithms for packing irregular items in limited containers based on the use of No-Fit-Polygon (NFP). This work presents a GRASP algorithm for the restricted version of the Knapsack Problem: first, a greedy initial solution is generated, then, the local search algorithm is used to improve the current solution. A hybrid strategy has also been proposed for the unrestricted version of the Knapsack Problem. It is divided into steps of packing irregular items and packing regular items. We tested the algorithms using adapted instances for the Strip Packing problem. The GRASP algorithm achieved optimal packings for several of the tested instances, and, even for those that the algorithm did not, the obtained packings had a good occupancy rate, with values relatively close to the optimum. The runtime of the algorithm was reasonable. In the hybrid strategy, we obtained good packings for most of the instances, with occupancy rates above 90% and relatively low execution times / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T01:07:44Z (GMT). No. of bitstreams: 1 Queiroz_ThiagoAlvesde_D.pdf: 1460601 bytes, checksum: 0d83e25259c427329e25174c2e729e77 (MD5) Previous issue date: 2010 / Resumo: Problemas de Corte e Empacotamento são, em sua maioria, NP-difíceis e não existem algoritmos exatos de tempo polinomial para tais se for considerado P ¿ NP. Aplicações práticas envolvendo estes problemas incluem a alocação de recursos para computadores; o corte de chapas de ferro, de madeira, de vidro, de alumínio, peças em couro, etc.; a estocagem de objetos; e, o carregamento de objetos dentro de contêineres ou caminhões-baú. Nesta tese investigamos problemas de Corte e Empacotamento NP-difíceis, nas suas versões bi- e tridimensionais, considerando diversas restrições práticas impostas a tais, a saber: que permitem a rotação ortogonal dos itens; cujos cortes sejam feitos por uma guilhotina; cujos cortes sejam feitos por uma guilhotina respeitando um número máximo de estágios de corte; cujos cortes sejam não-guilhotinados; cujos itens tenham demanda (não) unitária; cujos recipientes tenham tamanhos diferentes; cujos itens sejam representados por polígonos convexos e não-convexos (formas irregulares); cujo empacotamento respeite critérios de estabilidade para corpos rígidos; cujo empacotamento satisfaça uma dada ordem de descarregamento; e, cujos empacotamentos intermediários e final tenham seu centro de gravidade dentro de uma região considerada "segura". Para estes problemas foram propostos algoritmos baseados em programação dinâmica; modelos de programação inteira; técnicas do tipo branch-and-cut; heurísticas, incluindo as baseadas na técnica de geração de colunas; e, meta-heurísticas como o GRASP. Resultados teóricos também foram obtidos. Provamos uma questão em aberto levantada na literatura sobre cortes não-guilhotinados restritos a um conjunto de pontos. Uma extensiva série de testes computacionais considerando instâncias reais e várias outras geradas de forma aleatória foram realizados com os algoritmos desenvolvidos. Os resultados computacionais, sendo alguns deles comparados com a literatura, comprovam a validade dos algoritmos propostos e a sua aplicabilidade prática para resolver os problemas investigados / Abstract: Several versions of Cutting and Packing problems are considered NP-hard and, if we consider that P ¿ NP, we do not have any exact polynomial algorithm for solve them. Practical applications arises for such problems and include: resources allocation for computers; cut of steel, wood, glass, aluminum, etc.; packing of objects; and, loading objects into containers and trucks. In this thesis we investigate Cutting and Packing problems that are NP-hard considering theirs two- and three-dimensional versions, and subject to several practical constraints, that are: that allows the items to be orthogonally rotated; whose cuts are guillotine type; whose cuts are guillotine type and performed in at most k stages; whose cuts are non-guillotine type; whose items have varying and unit demand; whose bins are of variable sizes; whose items are represented by convex and non-convex polygons (irregular shapes); whose packing must satisfy the conditions for static equilibrium of rigid bodies; whose packing must satisfy an order to unloading; and, whose intermediaries and resultant packing have theirs center of gravity inside a safety region; Such cutting and packing problems were solved by dynamic programming algorithms; integer linear programming models; branch-and-cut algorithms; several heuristics, including those ones based on column generation approaches, and metaheuristics like GRASP. Theoretical results were also provided, so a recent open question arised by literature about non-guillotine patterns restricted to a set of points was demonstrated. We performed an extensive series of computational experiments for algorithms developed considering several instances presented in literature and others generated at random. These results, some of them compared with the literature, validate the approaches proposed and suggest their applicability to deal with practical situations involving the problems here investigated / Doutorado / Doutor em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T17:39:45Z (GMT). No. of bitstreams: 1 Vignatti_AndreLuis_D.pdf: 822237 bytes, checksum: d9b8ad70708a9313f0d1ed9d64d39302 (MD5) Previous issue date: 2010 / Resumo: Nesta tese, estudamos versões de teoria dos jogos dos problemas de empacotamento de itens e balanceamento de carga. Consideramos que a implementação de um algoritmo centralizado de controle é inviável, fazendo com que as entidades participantes do sistema ajam de maneira egoísta. Assim, a escolha egoísta de estratégias pelas entidades pode ou não levar a um estado estável do sistema, chamado de equilíbrio de Nash. Dependendo das condições definidas pelo modelo utilizado, devemos embutir certas regras para as entidades, contanto que as entidades tenham incentivo de utilizá-las e que, além disso, façam com que o sistema alcance um equilíbrio de Nash. Os principais resultados desta tese são relativos ao tempo de convergência para o equilíbrio de Nash, ou seja, buscamos saber quantas vezes os agentes mudam suas estratégias até alcançarem o equilíbrio de Nash, seja agindo de maneira completamente egoísta ou seguindo certas regras. Para o jogo de empacotamento de itens, apresentamos limitantes teóricos para o tempo de convergência, olhando ambos os casos de atualizações seqüenciais ou simultâneas das estratégias. Para o jogo de balanceamento de carga consideramos um modelo distribuído assíncrono com entidades heterogêneas, apresentando algumas regras que as entidades devem seguir e realizamos simulações para comparar as regras apresentadas / Abstract: In this thesis, we study game-theorical versions of the bin packing and load balancing problems. We consider that the implementation of a centralized controller algorithm is not feasible, making the entities that participate in the system act in a selfish way. Thus, the selfish choice of the strategies by the entities may or may not lead to a stable state of the system, called Nash equilibrium. Depending on the conditions defined by the considered model, we must build certain rules for entities, provided that the entities have incentive to use them and also make the system reach a Nash equilibrium. The main results of this thesis are related to the convergence time to Nash equilibrium, i.e., we seek to know how many times the agents change their strategies until they reach a Nash equilibrium, whether they act in a completely selfish way or follow certain rules. For the bin packing game, we present theoretical bounds for the convergence time, considering both the cases of sequential or simultaneous updates of the strategies. For the load balancing game, we consider an asynchronous distributed model with heterogeneous entities, presenting some rules that the entities must follow and we carry out simulations to compare the presented rules / Doutorado / Teoria da Computação / Doutor em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1 Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5) Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação

In the real world, many problems are continuous in nature. In some cases, finding the global solutions for these problems is di±cult. The reason is that the problem's objective function is non convex, nor concave and even not differentiable. Tackling these problems is often computationally too expensive. Although the development in computer technologies are increasing the speed of computations, this often is not adequate, particularly if the size of the problem's instance are large. Applying exact methods on some problems may necessitate their linearisation. Several new ideas using heuristic approaches have been considered particularly since they tackle the problems within reasonable computational time and give an approximate solution. In this thesis, the variable neighbourhood search (VNS) metaheuristic (the framework for building heuristic) has been considered. Two variants of variable neighbourhood search metaheuristic have been developed, continuous variable neighbourhood search and reformulation descent variable neighbourhood search. The GLOB-VNS software (Drazic et al., 2006) hybridises the Microsoft Visual Studio C++ solver with variable neighbourhood search metaheuristics. It has been used as a starting point for this research and then adapted and modified for problems studied in this thesis. In fact, two problems have been considered, censored quantile regression and the circle packing problem. The results of this approach for censored quantile regression outperforms other methods described in the literature, and the near-optimal solutions are obtained in short running computational time. In addition, the reformulation descent variable neighbourhood search variant in solving circle packing problems is developed and the computational results are provided.

The thesis first addresses the typology of cutting problems and their relationship to the packing problems. These are categorized (Wascher et al (2005)) according to 5 basic kriteria into the so-called "refined problem types", which is the sufficiently detailed and practical segmentation of cutting problems. The thesis deals with a selected sample of some of the most interesting algorithms from the wide range of those used to solve the cutting problems. The Viswanathan-Bagchi algorithm for the exact solution of constrainted two-dimensional orthogonal Cutting stock probléme with gillotine cuts is briefly described. It enables to process a wide range of additional problem constraints. The body of the thesis concentrates on heuristic algorithms used to solve orthogonal Open dimension problems. The Best-fit algorithm according to Burke et al. (2004) is described in detail. The work introduces two modifications of this algorithm that helped improve the solution in 42 out of the 89 benchmark problems, while a worse solution was achieved only in 10 of them. Moreover, new and more effective data structures and procedures that enable to solve the testing exercise with approx 50 000 rectangles in just about 2,5 seconds have been introduced.

Os problemas de empacotamento de itens irregulares são problemas de corte e empacotamento, nos quais peças irregulares de menor tamanho (que chamamos de itens) devem ser empacotados inteiramente em uma peça grande (que chamamos de placa), obedecendo a restrições de nãosobreposição e minimizando as dimensões da placa. Para garantir a não-sobreposição, fazemos uso de retas separadoras, quer dizer, retas que separam um item de outro. Apresentamos modelos de programação não-linear para problemas de empacotamentos de itens regulares e irregulares que rotacionam livremente. Os itens podem ser círculos, polígonos convexos e não-convexos. A principal vantagem dos modelos é a simplicidade, já que estes utilizam somente conceitos básicos de geometria. Usamos o algoritmo de programação não-linear IPOPT (um algoritmo de tipo de pontos interiores), que faz parte da COIN-OR, para a resolução dos problemas. Testes computacionais foram executados usando instâncias conhecidas da literatura e os resultados foram comparados com resultados apresentados na literatura, obtidos com outras metodologias que também usam rotações livre, mostrando que nossos modelos são competitivos. Propomos também o uso de parábolas separadoras para a verificação de não-sobreposição na modelagem do problema, o que pode trazer ganhos computacionais e melhor qualidade de soluções. / The irregular packing problems are cutting and packing problems, in which smaller irregular pieces (which we call items) should be packaged entirely in one large piece (which we call a plate), obeying non-overlapping constraints and minimizing the dimensions of the plate. To ensure non-overlapping, we make use of separation lines, that is, lines that separate one item from another. We present nonlinear programming models for problems of packing regular and irregular items that rotate freely. The items can be circles, convex and nonconvex polygons. The main advantage of the models is their simplicity, because they use only basic geometry concepts. We use the nonlinear programming algorithm IPOPT (an algorithm of interior points type), which is part of COIN-OR, to solve the problems. Computational tests were performed using known instances of the literature and the results were compared with results presented in the literature, obtained with other methodologies that also use free rotations, showing that our models are competitive. We also propose the use of separating parabola to avoid items overlaping in the models, which could provide greater computational eficiency as well as solutions with better quality.

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.