Please use this identifier to cite or link to this item:
Type: Artigo de evento
Title: Approaches For The 2d 0-1 Knapsack Problem With Conflict Graphs
Author: De Queiroz T.A.
Miyazawa F.K.
Abstract: This work deals with the 0-1 knapsack problem in its two-dimensional variant, when there is a conflict graph related to pairs of conflicting items. Conflicting items must not be packed together in a same bin. This problem also arises as a subproblem in the bin packing problem and in supply chain scenarious. We propose a heuristic that generates iteratively a solution using a so called greedy randomized procedure. In order to avoid local optima solutions, a penalization memory list is used, and several packing strategies under a two-dimensional grid of points are considered. The heuristic solutions are compared with those ones computed by means of an integer programming model, also proposed in this work and solved with CPLEX solver. The heuristic got optimal solutions for 75% of the instances in a lower CPU time compared with that to solve the integer model. © 2013 IEEE.
Rights: fechado
Identifier DOI: 10.1109/CLEI.2013.6670612
Date Issue: 2013
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84893301621.pdf338.33 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.