The state of the art in MILP formulations for the guillotine 2D knapsack and related problems

Abstract

This thesis advances the state of the art in Mixed-Integer Linear Programming (MILP) formulations for Guillotine 2D Cutting Problems by (i) proposing a (re-)formulation that improves on a state-of-the-art formulation by cutting down its size and symmetries; (ii) adapting a previously-known reduction in a novel way for the preprocessing phase of the mentioned formulations; (iii) providing extensive experiments comparing the state of the art and the proposed formulation over many literature datasets; (iv) proposing a hy bridised variant of the mentioned formulations which improves the performance for some hard instances; (v) proposing and validating a rotation-only symmetry-breaking strategy for the mentioned formulations. This thesis focuses on the Guillotine 2D Knapsack Prob lem with orthogonal and unrestricted cuts, constrained demand, unlimited stages, and no rotation. However, the formulation may be adapted to many related problems including the Guillotine 2D Multiple Knapsack Problem, the Guillotine 2D Cutting Stock Problem, and the Guilltone 2D Orthogonal Packing Problem, all three of which are approached and experimented upon in this thesis. The code is available. Concerning the set of 59 instances used to benchmark the the state-of-the-art formulation in which the author took inspiration, and summing the statistics for all models generated, the proposed formulation has only a small fraction of the variables and constraints of the original model (respectively, 3.07% and 8.35%). The enhanced formulation also takes about 4 hours to solve all instances while the original formulation takes 12 hours to solve 53 of them (the other 6 runs hit a three-hour time limit each). In a recently proposed set of 80 harder instances, the enhanced formulation (with and without the pricing framework) found: 22 optimal solutions for the unrestricted problem (5 already known, 17 new); 22 optimal solutions for the restricted problem (all new for the problem and none is the same as the optimal unrestricted solution); better lower bounds for 25 instances; better upper bounds for 58 instances. Concerning other formulations for the problem in the literature, the proposed formulation has shorter run times, and it proves the optimality for more in stances. The proposed formulation only fails to deliver good solutions in the datasets that no formulation was able to solve any instance. In such datasets, other formulations did deliver good primal solutions even if they could not solve any instance.

Essa tese avança o estado da arte em formulações de Programação Linear Inteira (PLI) para Problemas de Corte Guilhotinado 2D pela (i) propondo uma (re-)formulação que melhora uma formulação do estado da arte por meio da redução do seu tamanho e suas simetrias; (ii) adaptando uma redução já conhecida de forma inovadora para a fase de pré processamento dessas formulações; (iii) provendo extensivos experimentos comparando o estado da arte e a formulação proposta sobre vários conjuntos de instância da litera tura; (iv) propondo uma variante hibridizada das formulações mencionadas que melhora a performance para algumas instâncias difíceis; (v) propondo e validando uma estratégia de quebra de simetrias para as formulações mencionadas. O nosso foco é o Problema da Mochila 2D Guilhotinado com cortes ortogonais e irrestritos, demanda limitada, estágios ilimitados, e sem rotação – entretanto, a formulação pode ser adaptada para vários proble mas relacionados incluindo o problema da mochila múltipla 2D guilhotinada, o problema do corte de estoque 2D guilhotinado, e o problema de empacotamento ortogonal 2D gui lhotinado, todos os três são abordados e alvo de experimentos nessa tese. O código está disponível. Considerando as 59 instâncias usadas nos experimentos da formulação em que o autor se inspirou, e somando os valores para todos os modelos gerados, a formulação proposta tem apenas uma pequena fração das variáveis e restrições do modelo original (respec tivamente, 3.07% e 8.35%). A formulação melhorada soluciona todas as 59 instâncias em cerca de 4 horas enquanto a formulação original soluciona 53 em 12 horas (as outras 6 instâncias não são solucionadas dentro do limite de 3 horas por instância). Em um conjunto de 80 instâncias difíceis recentemente proposto, a formulação melhorada (com e sem a estrutura de precificação) encontrou: 22 soluções ótimas para o problema com cor tes irrestritos (5 já conhecidas, 17 novas); 22 soluções ótimas para o problema com cortes restritos (todas novas para o problema e nenhuma é a mesma que do problema de cortes irrestritos); melhores limitantes inferiores para 25 instâncias; melhores limitantes superiores para 58 instâncias. Considerando outras formulações para o problema na literatura, a formulação proposta apresenta tempos de execução menores, e prova a otimalidade para mais instâncias. Somente nos conjuntos de instâncias em que nenhuma formulação solu- cionou instância alguma é que a formulação proposta falhou em encontrar boas soluções primais enquanto outras formulações obtiveram êxito. A formulação proposta somente falhou em obter soluções de boa qualidade nos conjuntos de instâncias em que nenhuma formulação conseguiu solucionar instância alguma. Nesses conjuntos de dados, outras formulações obtiveram boas soluções primais mesmo não sendo capazes de solucionar instância alguma.