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

作者：Fattahi Ali; Turkay Metin^*

来源：European Journal of Operational Research, 2018, 266(2): 415-425.

DOI：10.1016/j.ejor.2017.09.026

• Multiple objective programming
• Integer programming

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.

• 出版日期2018-4-16