The irregular strip packing problem consists in the cutting of a set of two-dimensional pieces from an object of fixed width using the minimum possible length. Despite its economic importance for many industries, because of its resolution difficulty few exact methods have addressed this problem. Recently, a mixed integer programming model in which pieces are placed on a grid has been proposed. Although the model has proved the optimality for some large instances, it has a large number of non-overlap constraints, which grows quickly according to the discretization resolution and number of distinct pieces. This thesis proposes a clique covering model to reduce the number of constraints and improve the linear relaxation. The coverings were obtained by a heuristic developed by the author. The model has outperformed the previous model in most evaluated instances and obtained an optimal solution for instances with up to 25 pieces (22 distinct pieces) subject to grid discretization. Recently, another mixed integer programming model was proposed for the problem, but it may allow a large number of symmetric solutions. In this thesis, new symmetry breaking constraints are proposed to improve the model. Computational experiments were performed for instances with convex pieces. The results show the proposed formulation is better than the previous one for most instances, since it improves lower bounds and reduces run-time and number of nodes explored to prove optimality. A particular case of an irregular item is a polyomino. A polyomino is a set of unit squares connected by joining one of their edges. A quasi- polyomino is a polyomino generalization, since it is a subset of not necessarily connected squares obtained from an equidistant raster grid. Quasi-polyomino cutting and packing problems have many real applications, e.g., leather cutting, sheet metal stamping, design of printed circuit boards and layout of magazines and newspapers. In this thesis, we study the quasi-polyomino strip packing problem. We propose two integer programming models for the problem and evaluate them using state-of-the-art solvers. We evaluate the models using instances taken from the literature and both models obtained good results, solving to optimality an instance with 320 items (20 distinct items) on a strip of dimensions 44x50. As expected, we found more optimal solutions when there are no rotation and flips and when the dimensions of the items are small.

O problema de empacotamento em faixa de itens irregulares consiste em cortar um conjunto de itens bidimensionais a partir de um objeto com largura fixa usando o menor comprimento possível. Apesar de sua importância econômica para várias indústrias, devido a sua dificuldade de resolução poucos métodos exatos foram direcionados para o problema. Recentemente, um modelo de progamação inteira mista no qual os itens são posicionados sobre uma grelha foi proposto. Embora o modelo tenha provado a otimalidade para algumas instâncias de grande porte, ele possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a resolução da discretização e o número de itens distintos. Nesta tese, é proposto um modelo de cobertura por cliques para reduzir o número de restrições e melhorar a relaxação linear. As coberturas são obtidas através de uma heurística desenvolvida pelo próprio autor. O modelo obtido superou a performance do modelo anterior para a maioria das instâncias avaliadas e obteve uma solução ótima para instância com até 25 itens (22 itens distintos) sujeito à discretização da grelha. Recentemente, outro modelo de programação inteira mista foi proposto para o problema, mas ele permite um grande número de soluções simétricas. Nesta tese, novas restrições de quebra de simetria são propostas para melhorar o modelo. Experimentos computacionais foram realizados para instâncias com itens convexos. Os resultados indicaram que a formulação proposta é melhor que a anterior para a maioria das instâncias, uma vez que melhora os limitantes inferiores e reduz o tempo de execução e o número de nós explorados para provar a otimalidade. Um caso particular de item irregular é um poliominó. Um poliominó consiste em um conjunto de quadrados de mesma dimensão conexos pela junção de uma de suas arestas. Um quasi-poliominó é uma generalização do conceito de poliominó, uma vez que representa um subconjunto de quadrados não necessariamente conexos de uma malha quadriculada equidistante. Problemas de corte e empacotamento de quasi-poliominós possuem diversas aplicações reais, por exemplo, o corte de itens de couro, a estamparia de chapas metálicas, o desenho de placas de circuito impresso e a diagramação de páginas de revistas e jornais. Nesta tese, estudamos o problema de empacotamento em faixa de quasi-poliominós. São propostos dois modelos de programação inteira para o problema e realizados testes computacionais para avaliá-los. Os modelos foram avaliados utilizando instâncias da literatura e apresentaram bons resultados, obtendo uma solução ótima para uma instância com 320 itens (20 itens distintos) em um recipiente de dimensões 44x50. Como esperado, foram encontradas mais soluções ótimas quando não há rotações e reflexões e quando as dimensões dos itens são pequenas.