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-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 22
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1016/j.disopt.2016.09.003
  • Dergi Adı: DISCRETE OPTIMIZATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.341-363
  • Anahtar Kelimeler: Nadir point, Nadir set, Bound set, Pareto point, Branch-and-bound, SPACE SEARCH ALGORITHM, BOUND ALGORITHM, OPTIMIZATION PROBLEMS, LOCATION PROBLEM, SOLVE
  • Erciyes Üniversitesi Adresli: Evet

Özet

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.