Finding a representative nondominated set for multi-objective mixed integer programs


Ceyhan G., Koksalan M., LOKMAN B.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.272, sa.1, ss.61-77, 2019 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 272 Sayı: 1
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1016/j.ejor.2018.06.012
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.61-77
  • Anahtar Kelimeler: Multiple objective programming, Mixed integer programming, Nondominated point, Representative subset, COMBINATORIAL OPTIMIZATION PROBLEMS, NON-DOMINATED VECTORS, DISCRETE REPRESENTATIONS, RECURSIVE ALGORITHM, LINEAR-PROGRAMS, EFFICIENT, POINTS, METAHEURISTICS, PPM
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well. (C) 2018 Elsevier B.V. All rights reserved.