Packing problems with fixed number of bins

Author(s)

Mauro Roberto Costa da Silva

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2025-01-27

Examining board members

Rafael Crivellari Saliba Schouery; Santiago Valdés Ravelo; Anand Subramanian; Edna Ayako Hoshino; André Luís Vignatti

• Advisor: Rafael Crivellari Saliba Schouery; Lehilton Lelis Chaves Pedrosa

Abstract

Packing problems with a fixed number of bins consist of, given a set of items and several bins of a given capacity, packing a subset of the items in the bins, maximizing or minimiz- ing a certain objective function, such as the sum of the values of the packed items. The Bi nary Knapsack Problem (KP), the Generalized Assignment Problem (GAP), the Multiple Knapsack Problem (MKP), and the Bin Packing Problem (BPP) are classic examples of packing problems, but only KP, GAP and MKP have a fixed number of bins since BPP allows new bins to be created. Other problems with this char- acteristic are Maxspace, Positional Knapsack Problem, and Extensible Bin Packing. The Maxspace is an advertising placement problem in which we want to display advertisements on a banner, maximizing the area occupied by the advertisements displayed. The Positional Knapsack Problem is a variant of Binary Knapsack Problem in which we want to place items in a knapsack, and the item’s value can vary ac- cording to the position in which it is packed. And the Extensible Bin Packing (EBP) is a packing problem in which we want to place several items in a fixed number of bins of the same size, but, unlike Maxspace and PKP, EBP requires that all items be packed, and allows the bins to be extended, increasing the cost of the solution proportionally to the total value of the extension. The main objective of this work is to develop new approx- imation and exact algorithms for packing problems with a fixed number of bins, more specifically to Maxspace, Positional Knapsack Problem, and Extensible Bin Packing, taking into account variants found in practice for these problems. In this work, we present a Polynomial-Time Approximation Scheme (PTAS) for a variant of Maxs- pace, a Fully Polynomial-Time Approximation Scheme (FPTAS) for a specific variation function of PKP, and a PTAS for PKP with a more general set of functions. In addition, we present algorithms using the arc-flow formulation and the branch-and-cut-and-price technique for EBP (AU)

• FAPESP's process: 20/13162-2 - Packing problems with fixed number of bins
• Grantee: Mauro Roberto Costa da Silva
• Support Opportunities: Scholarships in Brazil - Doctorate