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


EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.268, no.1, pp.281-299, 2018 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 268 Issue: 1
  • Publication Date: 2018
  • Doi Number: 10.1016/j.ejor.2018.01.026
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.281-299
  • Keywords: Multiple objective programming, Biobjective mixed-integer linear programming, Integer programming, Bound sets, BOUND ALGORITHM, SET, POINTS, SOLVE
  • Erciyes University Affiliated: Yes


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. (C) 2018 Elsevier B.V. All rights reserved.