Nondominated Points of Multi-objective Integer Programming Problems: Analysis, Approaches and Applications

  • Lokman, Banu (PI)
  • Koksalan, Murat (PI)
  • Ceyhan, Gokhan (PI)
  • Ozarik, Sami Serkan (PI)
  • Dogan, Ilgin (PI)

    Project Details


    Key findings

    In today's complex systems, decision makers (DMs) usually have to deal with optimization problems with conflicting objectives. In these problems, typically there does not exist a unique solution of interest. It is essential to find the nondominated points, for which an improvement in any objective is not possible without sacrificing in one of the remaining objectives. Since the number of nondominated points grows exponentially with the problem size, generating all nondominated points is not only difficult but also not practical.

    In this project, we develop a web-based decision support system for Multi-objective Integer Programs (MOIPs). We first develop an exact algorithm to generate all nondominated points. In order to study the characteristics of the nondominated sets, we introduce a density measure and search for common properties of the distributions of nondominated sets. Based on this analysis, we propose a procedure that estimates possible locations and distributions of nondominated points over the criterion space. We then develop algorithms to generate a set of points that represent the nondominated set well. Different from the existing studies, the algorithms are designed to generate subsets that represent the distribution properties of the nondominated set and the preferences of the DM. We tested performance of our algorithms that generate representative subsets on different MOIPs and the results show that the algorithms work well.
    We also develop an online tool that is accessible to other researchers. The software we develop is capable to interact with the DM and generate a representative set with a desired quality level. We also develop visualization tools to present the points to the DM and we present a digital library that provides a collection of test data sets for a variety of MOIPs.
    Effective start/end date15/04/1615/10/18


    Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.