Branch-and-bound and objective branching with three or more objectives

TY - JOUR

T1 - Branch-and-bound and objective branching with three or more objectives

AU - Forget, Nicolas

AU - Gadegaard, Sune Lauth

AU - Klamroth, Kathrin

AU - Nielsen, Lars Relund

AU - Przybylski, Anthony

PY - 2022/12

Y1 - 2022/12

N2 - The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. These bound sets are used as a supplement to the classical dominance test to improve the computational time by imposing inequalities derived from (partial) dominance in the objective space. This process is called objective branching since it is mostly applied when generating child nodes. In this paper, we extend the concept of objective branching to multi-objective integer optimization problems with three or more objective functions. Several difficulties arise in this case, as there is no longer a lexicographic order among non-dominated outcome vectors when there are three or more objectives. We discuss the general concept of objective branching in any number of dimensions and suggest a merging operation of local upper bounds to avoid the generation of redundant sub-problems. Finally, results from extensive experimental studies on several classes of multi-objective optimization problems is reported.

AB - The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. These bound sets are used as a supplement to the classical dominance test to improve the computational time by imposing inequalities derived from (partial) dominance in the objective space. This process is called objective branching since it is mostly applied when generating child nodes. In this paper, we extend the concept of objective branching to multi-objective integer optimization problems with three or more objective functions. Several difficulties arise in this case, as there is no longer a lexicographic order among non-dominated outcome vectors when there are three or more objectives. We discuss the general concept of objective branching in any number of dimensions and suggest a merging operation of local upper bounds to avoid the generation of redundant sub-problems. Finally, results from extensive experimental studies on several classes of multi-objective optimization problems is reported.

KW - Bound sets

KW - Branch & bound

KW - Multi-objective combinatorial optimization

KW - Multi-objective integer programming

KW - Objective branching

UR - http://www.scopus.com/inward/record.url?scp=85137797302&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2022.106012

DO - 10.1016/j.cor.2022.106012

M3 - Journal article

AN - SCOPUS:85137797302

SN - 0305-0548

VL - 148

JO - Computers and Operations Research

JF - Computers and Operations Research

M1 - 106012

ER -