Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs

Nicolas Joseph Forget; Sune Lauth Gadegaard; Lars Relund

doi:10.1016/j.ejor.2022.01.047

Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs

Bidragets oversatte titel: Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs

Nicolas Joseph Forget^*, Sune Lauth Gadegaard, Lars Relund

^*Corresponding author af dette arbejde

Institut for Økonomi

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

25 Downloads (Pure)

Abstract

In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.

Bidragets oversatte titel	Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs
Originalsprog	Engelsk
Tidsskrift	European Journal of Operational Research
Vol/bind	302
Nummer	3
Sider (fra-til)	909-924
Antal sider	16
ISSN	0377-2217
DOI	https://doi.org/10.1016/j.ejor.2022.01.047
Status	Udgivet - 1 nov. 2022

Adgang til dokumentet

10.1016/j.ejor.2022.01.047Licens: CC BY

1-s2.0-S0377221722000868-mainForlagets udgivne version, 3,09 MBLicens: CC BY

Andre filer og links

Link to publication in Scopus

Citationsformater

@article{750ae49032714753b041480075730a35,

title = "Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs",

abstract = "In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.",

keywords = "Branch and bound, Combinatorial optimization, Linear relaxation, Multiple objective programming, Warm-starting",

author = "Forget, {Nicolas Joseph} and Gadegaard, {Sune Lauth} and Lars Relund",

year = "2022",

month = nov,

day = "1",

doi = "10.1016/j.ejor.2022.01.047",

language = "English",

volume = "302",

pages = "909--924",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier BV",

number = "3",

}

Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs. / Forget, Nicolas Joseph; Gadegaard, Sune Lauth ; Relund, Lars.
I: European Journal of Operational Research, Bind 302, Nr. 3, 01.11.2022, s. 909-924.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

TY - JOUR

T1 - Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs

AU - Forget, Nicolas Joseph

AU - Gadegaard, Sune Lauth

AU - Relund, Lars

PY - 2022/11/1

Y1 - 2022/11/1

N2 - In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.

AB - In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.

KW - Branch and bound

KW - Combinatorial optimization

KW - Linear relaxation

KW - Multiple objective programming

KW - Warm-starting

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

U2 - 10.1016/j.ejor.2022.01.047

DO - 10.1016/j.ejor.2022.01.047

M3 - Journal article

AN - SCOPUS:85125127761

SN - 0377-2217

VL - 302

SP - 909

EP - 924

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -