Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets

Sune Lauth Gadegaard (), Lars Relund Nielsen () and Matthias Ehrgott ()
Additional contact information
Sune Lauth Gadegaard: Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, DK-8210 Aarhus V, Denmark;
Lars Relund Nielsen: Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, DK-8210 Aarhus V, Denmark;
Matthias Ehrgott: Department of Management Science, Lancaster University, Lancaster LA1 4YX, United Kingdom

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 790-804

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 that 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. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with 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 linear programming 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 that different 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 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0846 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:4:p:790-804

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().