Fathoming rules for biobjective mixed integer linear programs: Review and extensions

BELOTTI P., SOYLU B., Wiecek M. M.

DISCRETE OPTIMIZATION, vol.22, pp.341-363, 2016 (SCI-Expanded, Scopus) identifier identifier

  • Publication Type: Article / Article
  • Volume: 22
  • Publication Date: 2016
  • Doi Number: 10.1016/j.disopt.2016.09.003
  • Journal Name: DISCRETE OPTIMIZATION
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.341-363
  • Keywords: Nadir point, Nadir set, Bound set, Pareto point, Branch-and-bound
  • Erciyes University Affiliated: Yes

Abstract

We consider the class of biobjective mixed integer linear programs (BOMILPs). We review fathoming rules for general BOMILPs and present them in a unified manner. We then propose new fathoming rules that rely on solving specially designed LPs, hence making no assumption on the type of problem and only using polynomial-time algorithms. We describe an enhancement for carrying out these rules by performing a limited number of pivot operations on an LP, and then we provide insight that helps to make these rules even more efficient by either focusing on a smaller number of feasible solutions or by resorting to heuristics that limit the number of LPs solved. (C) 2016 Elsevier B.V. All rights reserved.