The study of theoretical and practical combinatorial optimization problems applied...
Compartmentalized knapsack problems: one-dimensional and two-dimensional cases
Two-dimensional cutting and packing problems with tetris-like items
Advanced search
The Compartmentalized Knapsack Problem
Full text
| |
| Author(s): |
Fabiano do Prado Marques
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2000-05-23 |
| Examining board members: |
Marcos Nereu Arenales;
Regina Esther Berretta;
Vitória Maria Miranda Pureza
|
| Advisor: | Marcos Nereu Arenales |
| Abstract | |
In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution. (AU) | |