A study on exponential-size neighborhoods for the bin packing problem with conflicts

Renatha Capua (), Yuri Frota (), Luiz Satoru Ochi () and Thibaut Vidal ()
Additional contact information
Renatha Capua: Universidade Federal Fluminense
Yuri Frota: Universidade Federal Fluminense
Luiz Satoru Ochi: Universidade Federal Fluminense
Thibaut Vidal: Pontifícia Universidade Católica do Rio de Janeiro

Journal of Heuristics, 2018, vol. 24, issue 4, No 4, 667-695

Abstract: Abstract We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce $${\mathcal O}(1)$$ O ( 1 ) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.

Keywords: Metaheuristics; Bin packing with conflicts; Large neighborhood search; Ejection chains; Assignment; Set covering (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9372-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:24:y:2018:i:4:d:10.1007_s10732-018-9372-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9372-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().