An exact algorithm for biobjective mixed integer linear programming problems

In this study, we develop a new criterion space search algorithm to find the Pareto frontier of biobjective mixed-integer linear programming problems. Our algorithm starts with the solution of an individual objective function and then sequentially finds all Pareto line segments and points, which are the elements of the Pareto frontier, of biobjective mixed-integer linear programming problems. At each iteration of the algorithm, one line segment (or one isolated point) of the Pareto frontier is detected. If there is no new Pareto line segment available, the algorithm ends. We provide numerical examples and present performance results of the algorithm over several test problems.