Augmenting bi-objective branch and bound by scalarization-based information

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

Mathematical Methods of Operations Research, 2024, vol. 100, issue 1, No 5, 85-121

Abstract: Abstract While branch and bound based algorithms are a standard approach to solve single-objective (mixed-)integer optimization problems, multi-objective branch and bound methods are only rarely applied compared to the predominant objective space methods. In this paper we propose modifications to increase the performance of multi-objective branch and bound algorithms by utilizing scalarization-based information. We use the hypervolume indicator as a measure for the gap between lower and upper bound set to implement a multi-objective best-first strategy. By adaptively solving scalarizations in the root node to integer optimality we improve both, upper and lower bound set. The obtained lower bound can then be integrated into the lower bounds of all active nodes, while the determined solution is added to the upper bound set. Numerical experiments show that the number of investigated nodes can be significantly reduced by up to 83% and the total computation time can be reduced by up to 80%.

Keywords: Multi-objective optimization; Multi-objective branch and bound; Integer programming; Hypervolume indicator (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-024-00854-3 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:mathme:v:100:y:2024:i:1:d:10.1007_s00186-024-00854-3

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

DOI: 10.1007/s00186-024-00854-3

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().