An interactive approximation algorithm for multi-objective integer programs

Banu Lokman*, Murat Köksalan, Pekka J. Korhonen, Jyrki Wallenius

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

Abstract

We develop an interactive algorithm that approximates the most preferred solution for any multi-objective integer program with a desired level of accuracy, provided that the decision maker's (DM's) preferences are consistent with a nondecreasing quasiconcave value function. Using pairwise comparisons of the DM, we construct convex cones and eliminate the inferior regions that are close to being dominated by the cones in addition to the regions dominated by the cones. The algorithm allows the DM to change the desired level of accuracy during the solution process. We test the performance of the algorithm on a set of multi-objective combinatorial optimization problems. It performs very well in terms of the quality of the solution found, the solution time, and the required preference information.

Original languageEnglish
Pages (from-to)80-90
Number of pages11
JournalComputers and Operations Research
Volume96
DOIs
Publication statusPublished - 1 Aug 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • Approximation algorithm
  • Interactive algorithm
  • Multi-objective integer programming

Fingerprint Dive into the research topics of 'An interactive approximation algorithm for multi-objective integer programs'. Together they form a unique fingerprint.

  • Cite this