Adapting Branching and Queuing for Multi-objective Branch and Bound

Julius Bauß () and Michael Stiglmayr ()
Additional contact information
Julius Bauß: University of Wuppertal
Michael Stiglmayr: University of Wuppertal

Chapter Chapter 68 in Operations Research Proceedings 2023, 2025, pp 535-541 from Springer

Abstract: Abstract Branch and bound algorithms have to cope with several additional difficulties in the multi-objective case. Not only the bounding procedure is considerably weaker, but also the handling of upper and lower bound sets requires much more computational effort since both sets can be of exponential size. Thus, the order in which the subproblems are considered is of particular importance. Thereby, it is crucial not only to find efficient solutions as soon as possible but also to find a set of (efficient) solutions whose images are well distributed along the non-dominated frontier. In this paper we evaluate the performance of multi-objective branch and bound algorithms depending on branching and queuing of subproblems. We use, e.g., the hypervolume indicator as a measure for the gap between lower and upper bound set to implement a multi-objective best-first strategy. We test our approaches on multi-objective knapsack and generalized assignment problems.

Keywords: Multi-objective branch-and-bound; Multi-objective integer programming; Hypervolume; Branching strategy (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:lnopch:978-3-031-58405-3_68

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_68

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().