A one direction search method to find the exact nondominated frontier of biobjective mixed-binary linear programming problems

Abstract

The nondominated frontier (NDF) of a biobjective optimization problem is defined as the set of feasible points in the objective function space that cannot be improved in one objective function value without worsening the other. For a biobjective mixed-binary linear programming problem (BOMBLP), the NDF consists of some combination of isolated points and open, closed, or half-open/half-closed line segments. Some algorithms have been proposed in the literature to find an approximate or exact representation of the NDF. We present a one direction search (ODS) method to find the exact NDF of BOMBLPs. We provide a theoretical analysis of the ODS method and show that it generates the exact NDF. We also conduct a comprehensive experimental study on a set of benchmark problems and show the solution quality and computational efficacy of our algorithm.