On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem

Audrey Cerqueus (), Xavier Gandibleux (), Anthony Przybylski () and Frédéric Saubion ()
Additional contact information
Audrey Cerqueus: Mines Saint-Étienne
Xavier Gandibleux: Université de Nantes
Anthony Przybylski: Université de Nantes
Frédéric Saubion: Université d’Angers

Journal of Heuristics, 2017, vol. 23, issue 5, No 1, 285-319

Abstract: Abstract This paper focuses on branching strategies that are involved in branch and bound algorithms when solving multi-objective optimization problems. The choice of the branching variable at each node of the search tree constitutes indeed an important component of these algorithms. In this work we focus on multi-objective knapsack problems. In the literature, branching heuristics used for these problems are static, i.e., the order on the variables is determined prior to the execution. This study investigates the benefit of defining more sophisticated branching strategies. We first analyze and compare a representative set of classic branching heuristics and conclude that none can be identified as the best overall heuristic. Using an oracle, we highlight that combining branching heuristics within the same branch and bound algorithm leads to considerably reduced search trees but induces high computational costs. Based on learning adaptive techniques, we propose then dynamic adaptive branching strategies that are able to select the suitable heuristic to apply at each node of the search tree. Experiments are conducted on the bi-objective 0/1 unidimensional knapsack problem.

Keywords: Multiple objective combinatorial optimization; 0/1 unidimensional knapsack problem; Branch and bound; Branching heuristics; Utilities; Adaptive strategies (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9346-9 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:23:y:2017:i:5:d:10.1007_s10732-017-9346-9

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

DOI: 10.1007/s10732-017-9346-9

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 ().