Generating the noninferior set in mixed integer biobjective linear programs: An application to a location problem

An algorithm is proposed for generating an approximate representation of the noninferior set in the objective space of biobjective mixed integer linear programming problems. A measure of error in the approximate representation is developed to guide the generation of noninferior points. Noninferior points are iteratively added to the approximation in the regions where the deviation of the approximation from the exact noninferior set, i.e. error, is large. The main appeal of the algorithm is in its ability to produce an appoximation of the noninferior set of a desired accuracy with as few points as possible. A minimax objective based on the Tchebycheff distance metric is utilized to assure that all noninferior points can be generated by the algorithm. An example of a biobjective location problem is used to illustrate the applicability of the algorithm.