Department of Economics and Business Economics

Nicolas Joseph Forget

Branch-and-bound and objective branching with three objectives

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

Standard

Branch-and-bound and objective branching with three objectives. / Gadegaard, Sune Lauth; Relund, Lars; Forget, Nicolas Joseph et al.

In: optimization-online.org, 12.2020.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

Harvard

APA

CBE

MLA

Vancouver

Gadegaard SL, Relund L, Forget NJ, Klamroth K, Przybylski A. Branch-and-bound and objective branching with three objectives. optimization-online.org. 2020 Dec.

Author

Bibtex

@article{31e1cedefdaa44718ca6fd44b8dcbac9,
title = "Branch-and-bound and objective branching with three objectives",
abstract = "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.",
author = "Gadegaard, {Sune Lauth} and Lars Relund and Forget, {Nicolas Joseph} and Kathrin Klamroth and Anthony Przybylski",
year = "2020",
month = dec,
language = "English",
journal = "optimization-online.org",

}

RIS

TY - JOUR

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

AU - Gadegaard, Sune Lauth

AU - Relund, Lars

AU - Forget, Nicolas Joseph

AU - Klamroth, Kathrin

AU - Przybylski, Anthony

PY - 2020/12

Y1 - 2020/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. 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.

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. 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.

M3 - Journal article

JO - optimization-online.org

JF - optimization-online.org

ER -