Finding all nondominated points of multi-objective integer programs

LOKMAN B., Koksalan M.

JOURNAL OF GLOBAL OPTIMIZATION, cilt.57, sa.2, ss.347-365, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 57 Sayı: 2
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1007/s10898-012-9955-7
  • Dergi Adı: JOURNAL OF GLOBAL OPTIMIZATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.347-365
  • Anahtar Kelimeler: Multiple criteria, Combinatorial optimization, Nondominated point, COMBINATORIAL OPTIMIZATION, SPANNING TREE, EFFICIENT, ALGORITHM, SOLVE
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.