An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs

Özpeynirci Ö., Köksalan M.

Management Science, cilt.56, sa.12, ss.2302-2315, 2010 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 56 Sayı: 12
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1287/mnsc.1100.1248
  • Dergi Adı: Management Science
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.2302-2315
  • Anahtar Kelimeler: Exact algorithm, Multiobjective optimization, Nondominated points
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm's performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives. © 2010 INFORMS.