Resumo: Esta tese foca em otimização combinatória, um dos grandes campos em otimização. Esse campo consiste de problemas de decisão, nos quais é dado um conjunto discreto potencialmente enorme de soluções possíveis e deve-se encontrar uma única solução que otimize uma dada função objetivo. Esses problemas têm um grande número de aplicações no mundo real, principalmente em logística industrial e em cadeia de suprimentos. Primeiro, estudamos formulações de fluxo em redes que podem ser aplicadas a problemas gerais de otimização combinatória. Apresentamos um survey discutindo as fundamentações teóricas e as principais aplicações bem-sucedidas dos chamados modelos de fluxo em arcos pseudo-polinomiais. Em seguida, propomos novos métodos exatos para resolver tais modelos, envolvendo geração de colunas, regras de branching especializadas e estratégias de fixação de variáveis. Aplicamos os métodos de solução propostos a problemas bem estudados da literatura de corte, empacotamento e escalonamento, incluindo, por exemplo, os clássicos bin packing problem e cutting stock problem. Nossos experimentos computacionais mostram a eficácia dos métodos propostos, resolvendo na otimalidade um grande número de instâncias benchmark em aberto, de vários problemas. A segunda parte desta tese dá atenção especial à área de corte e empacotamento bidimensional, que está entre as áreas mais estudadas em otimização combinatória. Apresentamos uma revisão das referências mais relevantes que surgiram nas últimas duas décadas e propomos uma biblioteca online para organizar sistematicamente os materiais mais relevantes sobre tais problemas. Essas contribuições podem facilitar pesquisas futuras na área ativa de corte e empacotamento bidimensional. Nossa última contribuição diz respeito a um problema do mundo real surgido de uma empresa italiana de produção de carne. O problema é composto por um grande conjunto de decisões complexas, envolvendo a alocação diária de mão de obra e o escalonamento de pedidos na empresa. Para resolver esse problema, propomos uma heurística construtiva de três fases, implementada em um framework multi-start. Nosso algoritmo supera em média as decisões tomadas pela estratégia anterior da empresa Ver menos

Abstract: This thesis focuses on combinatorial optimization, one of the major optimization fields. This field consists of decision problems, in which we are given a potentially huge discrete set of possible solutions, and we must find a single solution that optimizes an objective function. Such problems have an extensive number of real world applications, mainly in industrial logistics and supply chain. First, we study network flow formulations that can be applied to general combinatorial optimization problems. We present a survey discussing theoretical foundations and main successful applications of the so-called pseudo-polynomial arc flow models. Then, we propose novel exact solution methods to solve such models, involving column generation, specialized branching rules, and variable fixing strategies. We apply the proposed solution methods to well-studied cutting, packing, and scheduling problems from the literature, including, for instance, the classical bin packing and cutting stock problems. Our computational experiments show the effectiveness of the proposed methods by solving to proven optimality an extensive number of open benchmark instances of several problems. The second part of this thesis give special attention to the area of two-dimensional cutting and packing problems, which is among the most studied areas in combinatorial optimization. We survey the most relevant references that appeared in the last two decades and propose an online library to systematically arrange the most relevant materials regarding such problems. These contributions can facilitate future research in the active area of two-dimensional cutting and packing. Our last contribution concerns a real world problem arising from an Italian meat-producing company. The problem consists of a large set of complex decisions, involving the daily workforce allocation and scheduling of orders in the company. To solve this problem, we propose a three-phase constructive heuristic, which is embedded in a multi-start framework. Our algorithm outperforms in average the decisions made by the former strategy of the company Ver menos