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

Gokhan Ceyhan, Murat Koksalan, Banu Lokman

    Research output: Contribution to journalArticlepeer-review


    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.
    Original languageEnglish
    Pages (from-to)61-77
    JournalEuropean Journal of Operational Research
    Issue number1
    Early online date2 Jul 2018
    Publication statusPublished - 1 Jan 2019


    Dive into the research topics of 'Finding a representative nondominated set for multi-objective mixed integer programs'. Together they form a unique fingerprint.

    Cite this