Optimization Online


Beam Search for integer multi-objective optimization

Thibaut Barthelemy (thibaut.barthelemy***at***univie.ac.at)
Sophie Parragh (sophie.parragh***at***univie.ac.at)
Fabien Tricoire (fabien.tricoire***at***univie.ac.at)
Richard Hartl (richard.hartl***at***univie.ac.at)

Abstract: Beam search is a tree search procedure where, at each level of the tree, at most W nodes are kept. This results in a metaheuristic whose solving time is polynomial in W. Popular for single-objective problems, beam search has only received little attention in the context of multi-objective optimization. By introducing the concepts of oracle and filter, we define a paradigm to understand multi-objective beam search algorithms. Its theoretical analysis engenders practical guidelines for the design of these algorithms. The guidelines, suitable for any problem whose variables are integers, are applied to address a bi-objective 0-1 knapsack problem. The solver obtained outperforms the existing non-exact methods from the literature.

Keywords: multi-objective combinatorial optimization; beam search; metaheuristic; knapsack problem; traveling salesman problem with profits

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Other Topics (Multi-Criteria Optimization )

Citation: Department of Business Administration, University of Vienna, 2015

Download: [PDF]

Entry Submitted: 04/24/2015
Entry Accepted: 04/24/2015
Entry Last Modified: 01/04/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society