The compartimentalised knapsack problem and applications

Author(s)

Fabiano do Prado Marques

• Document type: Doctoral Thesis
• Press: São Carlos. , gráficos, ilustrações, tabelas.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2004-11-29

Examining board members

Marcos Nereu Arenales; Carlos Eduardo Ferreira; Reinaldo Morabito Neto; Cid Carvalho de Souza; Horacio Hideki Yanasse

• Advisor: Marcos Nereu Arenales
• Field of knowledge: Engineering - Production Engineering
• Indexed in: Banco de Dados Bibliográficos da USP-DEDALUS
• Location: Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação. Biblioteca Prof. Achille Bassi; ICMSC/T; M357pm

Abstract

This work approaches the Compartmentalized Knapsack Problem which is a variation of the classical knapsack problem and it can be stated as the following hypothetical situation: a climber must load his/her knapsack with a number of items. Two numbers, an weight and a utility value are given for each item (so far, the problem coincides with the classical integer Knapsack Problem). However, the items are of different classes (food, medicine, utensils, etc.) and they have to be packed in separate compartments inside the knapsack. The compartments are flexible and have limited capacities. Each compartment has a fixed cost that depends on the class of items chosen to load it and, in addition, each new compartment introduces a loss of capacity of the knapsack. The Compartmentalized Knapsack Problem consists of determining suitable capacities of each compartment and how these compartments should be packed. The objective is to maximize a total utility value paid off the cost of the compartments. The problem can be modeled as an integer non-linear optimization problem and we have designed some heuristic methods for its solution, for which we present a computational study. A practical application arises in cutting steel rolls subject to a lamination process. (AU)