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.
|Number of pages||45|
|Journal||INFORMS Journal on Computing|
|Publication status||Accepted/In press - 19 Apr 2021|