Representing the nondominated set in multi-objective mixed-integer programs

Doğan I., Lokman B., Köksalan M.

European Journal of Operational Research, cilt.296, ss.804-818, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 296
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1016/j.ejor.2021.04.005
  • Dergi Adı: European Journal of Operational Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, International Bibliography of Social Sciences, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, EconLit, INSPEC, Public Affairs Index, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.804-818
  • Anahtar Kelimeler: Multi-objective mixed-integer programming, Representative set, Coverage gap, DISCRETE REPRESENTATIONS, SEARCH REGION, EFFICIENT
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

© 2021 Elsevier B.V.In this paper, we consider generating a representative subset of nondominated points at a prespecified precision in multi-objective mixed-integer programs (MOMIPs). The number of nondominated points grows exponentially with problem size and finding all nondominated points is typically hard in MOMIPs. Representing the nondominated set with a small subset of nondominated points is important for a decision maker to get an understanding of the layout of solutions. The shape and density of the nondominated points over the objective space may be critical in obtaining a set of solutions that represent the nondominated set well. We develop an exact algorithm that generates a representative set guaranteeing a prespecified precision. Our experiments on a variety of problems demonstrate that our algorithm outperforms existing approaches in terms of both the cardinality of the representative set and computation times.