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

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

DISCRETE OPTIMIZATION, cilt.22, ss.341-363, 2016 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 22
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1016/j.disopt.2016.09.003
  • Sayfa Sayıları: ss.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.