Fathoming rules for biobjective mixed integer linear programs: Review and extensions
DISCRETE OPTIMIZATION, cilt.22, ss.341-363, 2016 (SCI-Expanded, Scopus)
- 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
- 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.