Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem

Xavier Delorme, Xavier Gandibleux and Fabien Degoutin

European Journal of Operational Research, 2010, vol. 204, issue 2, 206-217

Abstract: The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original 'Strength Pareto Evolutionary Algorithm', which is a population-based metaheuristic. The second is an adaptation of the 'Greedy Randomized Adaptative Search Procedure', which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.

Keywords: Multiple; objective; programming; Metaheuristics; Set; packing; problem; Hybrid; method (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00758-9
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:204:y:2010:i:2:p:206-217

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().