Cutting and packing : problems, models and exact algorithms

Abstract

Different integer programming models and exact algorithms for hard cutting and packing problems are addressed. We consider in particular the combinatorial problems of this family that are defined over a single dimension. The optimization procedures rely on tools from the field of integer programming, namely column generation, cutting planes and branch-and-bound. Integrating the three into the same algorithm is not straightforward, and has been used with some success only recently. The combined method is known as branch-and-price-and-cut. It requires a great part of customization, which is directly related to the specific problem that is being tackled. We consider three variants of the standard one-dimensional Cutting Stock Problem, and its packing counterpart, the Bin-Packing Problem. We study the case for which more than a single large object is available, and an optimal cutting or packing has to be found so as to minimize the total length or capacity used. A related problem, which consists in selecting the best assortment of large objects subject to cardinality constraints, is also investigated. The problem of maximizing the homogeneity of the plans, and hence reducing the number of setups involved with its execution, is addressed. This combinatorial problem is commonly referred to as the Pattern Minimization Problem, and is particularly hard. We propose to improve an existing model, and describe how to derive new valid cutting planes for it using an original approach. Finally, we describe an exact solution algorithm for the Ordered Cutting Stock Problem. This problem has been formulated recently. It consists in finding the best assignment of small items to the stock rolls, avoiding breaks among pre-defined lots of items. Three integer programming models are presented, along with two families of cutting planes and their respective separation algorithms. Different strategies are explored to improve the convergence of the column generation algorithm, when applied to one-dimensional cutting and packing problems. New dual cutting planes are presented, and we describe how existing ones can be extended to the whole branch-and-bound search tree, for a given branching scheme. Alternative methods based on model aggregation are also explored. Two strategies are proposed. The first is based on a simple row aggregation scheme, while the second relies on a more sophisticated double aggregation of rows and columns. All the procedures proposed were coded and tested. Various computational experiments were conducted to evaluate their performance, using, with this purpose, problem instances from the literature, and randomly generated instances. The results are presented and discussed throughout the thesis.

Au long de cette thèse, nous étudions plusieurs problèemes de découpe et d’empaquetage dont la difficulté est reconnue. Nous considérons en particulier les problèms combinatoires à une seule dimension. Les algorithmes d’optimisation que nous explorons s’appuient sur des méthodes du domaine de la programmation entière, notamment la génération de colonnes, la méthode des plans coupants et la méthode de séparation et évaluation. L’intégration de ces trois méthodes dans un même algorithme ne s’effectue pas directement. En fait, cette intégration n’a été réussie avec succès que très récemment. L’algorithme qui en résulte est connu sous le nom de méthode de séparation, génération de colonnes et plans coupants. Compte tenu du problème qui est abordé, beaucoup d’adaptations sont nécessaires pour parvenir à un algorithme performant. Nous considérons ici les variantes des problèmes standards à une dimension de découpe et d’empaquetage. Nous étudions le cas dans lequel plusieurs objets de grande dimension sont disponibles, et une solution optimale doit être trouvée de manière à minimiser la largeur totale, ou capacité, utilisée. Nous explorons également le problème qui consiste à choisir le meilleur lot d’objets de grande dimension quand il existe des restrictions de cardinalité. La maximisation de l’homogénéité des solutions de découpe, et correspondante minimisation du nombre de changements de patrons de découpe, sont également étudiées. Ce problème est connu sous le nom de Problème de Minimisation des Patrons de Découpes, et il est particulièrement difficil. Nous montrons comment un modèle qui a été récemment proposé peut être amélioré, et nous expliquons comment dériver des inégalités valides en utilisant une approche originale. Finalement, nous décrivons un algorithme de résolution exacte pour le problème de découpe ordonnée. Ce problème a été formulé récemment. Il consiste à trouver la meilleure association des petits et grands objets en évitant qu’il y ait des cassures entre les lots qui ont été prédéfinis. Nous proposons trois modèles de programmation entière, ainsi que deux familles de plans coupants et leurs algorithmes de séparation. Plusieurs stratégies ayant pour but d’améliorer la convergence de la méthode de génération de colonnes sont explorées. Nous considérons le cas particulier où cette méthode est appliquée à des problèmes de découpe et d’empaquetage à une dimension. Nous présentons de nouveaux plans coupants dans l’espace dual, et nous décrivons comment étendre d’autres abordages présentés dans la littérature scientifique à l’arbre généré par la méthode de séparation et d’évaluation, en assumant un schéma de séparation spécifique. Des méthodes alternatives basées sur l’aggrégation de modèles sont aussi explorées. Deux méthodes sont proposées. La première est basée sur un schéma simple d’aggrégation de restrictions, tandis que la seconde s’appuie sur une aggrégation plus sophistiquée de variables et de restrictions. Toutes les procédures proposées ont été programmées et testées. Plusieus expériences computationelles ont été menées pour évaluer leur performance en utilisant, à cet effet, des instances d´ecrites dans la littérature, et des instances générées aléatoirement. Nous présentons les résultats obtenus, et nous les discutons tout au long de la thèse.

Nesta tese, são apresentados diferentes modelos de programação inteira e algoritmos de resolução exacta para problemas difíceis de corte e empacotamento. Consideramos em particular os problemas combinatórios dessa família numa única dimensão. Os algoritmos de optimização que exploramos assentam em métodos do domínio da programação inteira, nomeadamente a geração de colunas, planos de corte e o método de partição e avaliação sucessivas. Integrar esses três métodos no mesmo algoritmo não é um exercício directo. Na realidade, isso foi conseguido só muito recentemente. O algoritmo resultante é designado de partição, geração de colunas e corte. Atendendo ao problema que é abordado, várias adaptações têm de ser efectuadas. Consideramos três variantes dos problemas standards de corte e empacotamento com uma dimensão. Estudamos o caso para o qual mais de um tipo de rolos ou contentores estão disponíveis, e uma solução óptima tem de ser encontrada de forma a minimizar a largura ou capacidade total utilizada. Investigamos também um problema relacionado no qual deve ser escolhido o melhor lote de rolos ou contentores atendendo a restrições de carnalidade. O problema no qual se pretende maximizar a homogeneidade das soluções de corte ou empacotamento, e dessa forma minimizar o número de mudanças que ocorrem quando se executa o plano, é analisado. Esse problema combinatório é também conhecido por Problema da Minimização de Padrões, e é de difícil resolução. Propomos melhorar um modelo existente, e descrevemos como derivar planos de corte válidos usando uma abordagem original. Finalmente, descrevemos um algoritmo de resolução exacta para o problema de corte ordenado. Esse problema foi formulado muito recentemente. Consiste em determinar a melhor afectação de itens aos rolos, evitando interrupções entre lotes pré-definidos de itens. Três modelos de programação inteira são apresentados, juntamente com duas famílias de planos de corte e os seus respectivos algoritmos de separação. Diferentes estratégias para melhorar a convergência do método de geração de colunas são exploradas. Consideramos o caso no qual esse método é aplicado a problemas de corte e empacotamento a uma dimensão. Novos cortes duais são apresentados, e descrevemos como cortes que já foram descritos na literatura podem ser extendidos à totalidade da árvore de partição, assumindo um esquema de partição específico. Métodos alternativos baseados em agregação de modelos são também explorados. Duas estratégias são propostas. A primeira é baseada num esquema simples de agregação de restrições, enquanto a segunda assenta num esquema mais sofisticado de restrições e variáveis. Todos os procedimentos propostos foram codificados e testados. Várias experiências computacionais foram levadas a cabo, usando, para isso, instâncias descritas na literatura, e instâncias geradas aleatoriamente. Os resultados são apresentados, e discutidos ao longo da tese.