The two-dimensional knapsack problem with splittable items in stacks

• Tipo: Artigo em Revista Científica Internacional
• Data: 2022

Autores

Rapine, C (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP; Akbalik, A (Autor) Outra

Revista

Título: Omega

Vol. 112

ISSN: 0305-0483

Editora: Elsevier

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00W-KKM

DOI: 10.1016/j.omega.2022.102692

Abstract (EN): The two-dimensional knapsack problem consists in packing rectangular items into a single rectangular box such that the total value of packed items is maximized. In this article, we restrict to 2-stage nonexact guillotine cut packings and consider the variant with splittable items: each item can be horizontally cut as many times as needed, and a packing may contain only a portion of an item. This problem arises in the packing of semifluid items, like tubes of small radius, which has the property to behave like a fluid in one direction, and as a solid in the other directions. In addition, the items are to be packed into stable stacks, that is, at most one item can be laid on top of another item, necessarily wider than itself. We establish that this variant of the two-dimensional knapsack problem is NP-hard, and propose an integer linear formulation. We exhibit very strong dominance properties on the structure of extreme solutions, that we call canonical packings. This structure enables us to design polynomial time algorithms for some special cases and a pseudo-polynomial time algorithm for the general case. We also develop a Fully Polynomial Time Approximation Scheme (FPTAS) for the case where the height of each item does not exceed the height of the box. Finally, some numerical results are reported to assess the efficiency of our algorithms.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 12