The search-and-remove algorithm for biobjective mixed-integer linear programming problems

In this study, an exact algorithm, called the search-and-remove (SR) algorithm, is proposed to compute the Pareto frontier of biobjective mixed-integer linear programming problems. At each stage of the algorithm, efficient slices (all integer variables are fixed in a slice) are searched with the dichotomic search algorithm and found slices are recorded and excluded from the decision space with the help of Tabu constraints. The algorithm is also enhanced with lower and upper bounds, which are updated at each stage of the algorithm. The SR algorithm continues until it is proved that all efficient slices of the biobjective mixed-integer linear programming (BOMILP) problem are found. The algorithm finally returns a set of potentially efficient slices including all efficient slices of the problem. Then, an upper envelope finding algorithm merges the Pareto frontiers of these slices to the Pareto frontier of the original problem. A computational analysis is performed on several benchmark problems and the performance of the algorithm is compared with state of the art methods from the literature.