4.7 Article

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 302, Issue 3, Pages 909-924

Publisher

ELSEVIER
DOI: 10.1016/j.ejor.2022.01.047

Keywords

Multiple objective programming; Branch and bound; Combinatorial optimization; Linear relaxation; Warm-starting

Ask authors/readers for more resources

In this paper, a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems is proposed. The algorithm speeds up the computations and significantly reduces CPU time, effectively addressing the difficulties that arise when non-binary integer variables are introduced.
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. (C) 2022 The Author(s). Published by Elsevier B.V.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available