The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. Besides the classical dominance test, bound sets are used 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 tri-objective combinatorial optimization problems. Several difficulties arise in this case, as there is no longer a lexicographic order among nondominated outcome vectors in the multi-objective case, with more than two 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 subproblems. Numerical experiments on tri-objective knapsack, assignment and facility location problems show a significant speed-up in the B&B framework.
Citation
Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark School of Mathematics and Natural Sciences, University of Wuppertal, Gauß straße 20, 42119 Wuppertal - Germany Faculty of Sciences and Technologies, University of Nantes, 2 Rue de la Houssinière BP 92208, 44322 Nantes Cedex 03 - France. December 2020.