Home > Research > Publications & Outputs > Bi-objective branch-and-cut algorithms based on...

Associated organisational unit

Electronic data

  • IJOCfinal_1

    Accepted author manuscript, 463 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets. / Gadegaard, Sune Lauth; Nielsen, Lars Relund; Ehrgott, Matthias.
In: INFORMS Journal on Computing, Vol. 31, No. 4, 01.11.2019, p. 790-804.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

APA

Vancouver

Gadegaard SL, Nielsen LR, Ehrgott M. Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets. INFORMS Journal on Computing. 2019 Nov 1;31(4):790-804. Epub 2019 Jun 14. doi: 10.1287/ijoc.2018.0846

Author

Gadegaard, Sune Lauth ; Nielsen, Lars Relund ; Ehrgott, Matthias. / Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets. In: INFORMS Journal on Computing. 2019 ; Vol. 31, No. 4. pp. 790-804.

Bibtex

@article{09d65e3492654e73b567065cc687b29e,
title = "Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets",
abstract = "Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method which can generate all rational compromises between the objectives. This paper proposes two distinct bound set based branch-and-cut algorithms for general bi-objective combinatorial optimization problems, based on implicit and explicit lower bound sets, respectively. The algorithm based on explicit lower bound sets computes, for each branchingnode, a lower bound set and compares it to an upper bound set. The other fathoms branching nodes by generating a single point on the lower bound set for each local nadir point. We outline several approaches for fathoming branching nodes and we propose an updating scheme for the lower bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that adjusts the weights of the objective functions such thatdifferent parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy {"}Pareto branching{"}. We prove the effectiveness of the algorithms through extensive computational results.",
keywords = "bi-objective branch-and-cut, bi-objective optimization, combinatorial optimization, branch-and-cut",
author = "Gadegaard, {Sune Lauth} and Nielsen, {Lars Relund} and Matthias Ehrgott",
year = "2019",
month = nov,
day = "1",
doi = "10.1287/ijoc.2018.0846",
language = "English",
volume = "31",
pages = "790--804",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

RIS

TY - JOUR

T1 - Bi-objective branch-and-cut algorithms based on LP-relaxation and bound sets

AU - Gadegaard, Sune Lauth

AU - Nielsen, Lars Relund

AU - Ehrgott, Matthias

PY - 2019/11/1

Y1 - 2019/11/1

N2 - Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method which can generate all rational compromises between the objectives. This paper proposes two distinct bound set based branch-and-cut algorithms for general bi-objective combinatorial optimization problems, based on implicit and explicit lower bound sets, respectively. The algorithm based on explicit lower bound sets computes, for each branchingnode, a lower bound set and compares it to an upper bound set. The other fathoms branching nodes by generating a single point on the lower bound set for each local nadir point. We outline several approaches for fathoming branching nodes and we propose an updating scheme for the lower bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that adjusts the weights of the objective functions such thatdifferent parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching". We prove the effectiveness of the algorithms through extensive computational results.

AB - Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method which can generate all rational compromises between the objectives. This paper proposes two distinct bound set based branch-and-cut algorithms for general bi-objective combinatorial optimization problems, based on implicit and explicit lower bound sets, respectively. The algorithm based on explicit lower bound sets computes, for each branchingnode, a lower bound set and compares it to an upper bound set. The other fathoms branching nodes by generating a single point on the lower bound set for each local nadir point. We outline several approaches for fathoming branching nodes and we propose an updating scheme for the lower bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that adjusts the weights of the objective functions such thatdifferent parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching". We prove the effectiveness of the algorithms through extensive computational results.

KW - bi-objective branch-and-cut, bi-objective optimization, combinatorial optimization, branch-and-cut

U2 - 10.1287/ijoc.2018.0846

DO - 10.1287/ijoc.2018.0846

M3 - Journal article

VL - 31

SP - 790

EP - 804

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -