27 January 2025
14:00 Doctoral defense IC3 Auditorium
Theme
Packing Problems with Fixed Number of Containers
Student
Mauro Roberto Costa da Silva
Advisor / Teacher
Rafael Crivellari Saliba Schouery - Co-advisor: Lehilton Lelis Chaves Pedrosa
Brief summary
Packing problems have several practical applications, mainly in the logistics of the industrial and service sectors. Logistics is responsible for a considerable portion of the cost of services and products, and optimization of these processes can reduce costs, making products cheaper and more competitive. Packing problems with a fixed number of containers consist of, given a set of items and a number of containers of a given capacity, packing a subset of the items in the containers, maximizing or minimizing a certain objective function, such as the sum of the values of the packed items. The Binary 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 the KP, the GAP and the MKP have a fixed number of containers, since the BPP allows new containers to be created. Other problems with this characteristic are the Maxspace, the Positional Knapsack Problem and the Extensible Bin Packing. 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 the Binary Knapsack Problem in which we want to place items in a container and the value of the item can vary according to the position in which it is packed. Extensible Bin Packing (EBP) is a packing problem in which we want to add a quantity of items in a fixed number of containers of the same size, but, unlike Maxspace and PKP, EBP requires that all items be packed and allows the containers to be extended, increasing the cost of the solution proportionally to the total value of extension. The main objective of this work is to develop new approximation and exact algorithms for packing problems with a fixed number of containers, more specifically the Maxspace, Positional Knapsack Problem and Extensible Bin Packing problems, taking into account variants found in practice for these problems.
Examination Board
Headlines:
Rafael Crivellari Saliba Schouery | IC / UNICAMP |
Anand Subramanian | UFPB |
Edna Ayako Hoshino | UFMS |
Santiago Valdés Ravelo | IC / UNICAMP |
Andre Luís Vignatti | UFPR |
Substitutes:
Ruben Interian Kovaliova | IC / UNICAMP |
Carla Negri Lintzmayer | CMCC / UFABC |
Teobaldo Leite Bulhões Júnior | UFPB |