Finding nadir points in multi-objective integer programs

Koksalan M., LOKMAN B.

JOURNAL OF GLOBAL OPTIMIZATION, vol.62, no.1, pp.55-77, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 62 Issue: 1
  • Publication Date: 2015
  • Doi Number: 10.1007/s10898-014-0212-0
  • Journal Name: JOURNAL OF GLOBAL OPTIMIZATION
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.55-77
  • Keywords: Multi-objective, Integer programming, Nadir point, VALUES
  • Middle East Technical University Affiliated: Yes

Abstract

We address the problem of finding the nadir point in a multi-objective integer programming problem. Finding the nadir point is not straightforward, especially when there are more than three objectives. The difficulty further increases for integer programming problems. We develop an exact algorithm to find the nadir point in multi-objective integer programs with integer-valued parameters. We also develop a variation that finds bounds for each component of the nadir point with a desired level of accuracy. We demonstrate on several instances of multi-objective assignment, knapsack, and shortest path problems that the algorithms work well.