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

Nathan Adelgren, Akshay Gupte*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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
Pages (from-to)909-933
JournalINFORMS Journal on Computing
Issue number2
Early online date21 Oct 2021
Publication statusPublished - 1 Mar 2022


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

Cite this