Skip to content
Back to outputs

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

Research output: Contribution to journalArticle

Standard

Finding a representative nondominated set for multi-objective mixed integer programs. / Ceyhan, Gokhan; Koksalan, Murat; Lokman, Banu.

In: European Journal of Operational Research, Vol. 272, No. 1, 01.01.2019, p. 61-77.

Research output: Contribution to journalArticle

Harvard

Ceyhan, G, Koksalan, M & Lokman, B 2019, 'Finding a representative nondominated set for multi-objective mixed integer programs', European Journal of Operational Research, vol. 272, no. 1, pp. 61-77. https://doi.org/10.1016/j.ejor.2018.06.012

APA

Vancouver

Ceyhan G, Koksalan M, Lokman B. Finding a representative nondominated set for multi-objective mixed integer programs. European Journal of Operational Research. 2019 Jan 1;272(1):61-77. https://doi.org/10.1016/j.ejor.2018.06.012

Author

Ceyhan, Gokhan ; Koksalan, Murat ; Lokman, Banu. / Finding a representative nondominated set for multi-objective mixed integer programs. In: European Journal of Operational Research. 2019 ; Vol. 272, No. 1. pp. 61-77.

Bibtex

@article{30de9c5953714a5281acc64d32cb4e2e,
title = "Finding a representative nondominated set for multi-objective mixed integer programs",
abstract = "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.",
author = "Gokhan Ceyhan and Murat Koksalan and Banu Lokman",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.ejor.2018.06.012",
language = "English",
volume = "272",
pages = "61--77",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

RIS

TY - JOUR

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

AU - Ceyhan, Gokhan

AU - Koksalan, Murat

AU - Lokman, Banu

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

U2 - 10.1016/j.ejor.2018.06.012

DO - 10.1016/j.ejor.2018.06.012

M3 - Article

VL - 272

SP - 61

EP - 77

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -

ID: 13066393