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 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 22
  • Publication Date: 2016
  • Doi Number: 10.1016/j.disopt.2016.09.003
  • Title of Journal : DISCRETE OPTIMIZATION
  • Page Numbers: pp.341-363


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.