Branch-and-Bound for Bi-objective Integer Programming

Sophie N. Parragh () and Fabien Tricoire ()
Additional contact information
Sophie N. Parragh: Institute of Production and Logistics Management, Johannes Kepler University Linz, 4040 Linz, Austria
Fabien Tricoire: Institute of Production and Logistics Management, Johannes Kepler University Linz, 4040 Linz, Austria

INFORMS Journal on Computing, 2019, vol. 31, issue 4, 805-822

Abstract: In bi-objective integer optimization the optimal result corresponds to a set of nondominated solutions. We propose a generic bi-objective branch-and-bound algorithm that uses a problem-independent branching rule exploiting available integer solutions and takes advantage of integer objective coefficients. The developed algorithm is applied to bi-objective facility location problems and the bi-objective set covering problem, as well as to the bi-objective team orienteering problem with time windows. In the latter case, lower bound sets are computed by means of column generation. Comparison with state-of-the-art exact algorithms shows the effectiveness of the proposed branch-and-bound algorithm.

Keywords: branch-and-bound; integer programming; bi-objective optimization; branch-and-price; orienteering (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0856 (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:805-822

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