Branch-and-bound for biobjective mixed-integer linear programming

Nathan Adelgren, Akshay Gupte

Research output: Contribution to journalArticlepeer-review

Abstract

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contribution is new algorithms for obtaining dual bounds at a node, for checking node fathoming, presolve and duality gap measurement. Our branch-and-bound is a decision space search method since the branching is performed on the decision variables, akin to single objective problems. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances for empirical analysis of our method. We also perform comparisons against an objective space search algorithm from literature, which show that our branch-and-bound is able to compute the entire Pareto set in significantly lesser time.
Original languageEnglish
Number of pages45
JournalINFORMS Journal on Computing
Publication statusAccepted/In press - 19 Apr 2021

Fingerprint

Dive into the research topics of 'Branch-and-bound for biobjective mixed-integer linear programming'. Together they form a unique fingerprint.

Cite this