Monomial tropical cones for multicriteria optimization

Michael Joswig, Georg Loho

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

We present an algorithm to compute all n nondominated points of a multicriteria discrete optimization problem with d objectives using at most On[d/2] ) scalarizations. The method is similar to algorithms by Przybylski, Gandibleux, and Ehrgott [Discrete Optim., 7 (2010), pp. 149-165] and by Klamroth, Lacour, and Vanderpooten [European J. Oper. Res., 245 (2015), pp. 767-778] with the same complexity. As a difference, our method employs a tropical convex hull computation, and it exploits a particular kind of duality which is special for the tropical cones arising. This duality can be seen as a generalization of the Alexander duality of monomial ideals.

Original languageEnglish
Pages (from-to)1172-1191
Number of pages20
JournalSIAM journal on discrete mathematics
Volume34
Issue number2
DOIs
Publication statusPublished - 2020
Externally publishedYes

Keywords

  • Discrete multicriteria optimization
  • Monomial ideals
  • Tropical convexity

Fingerprint

Dive into the research topics of 'Monomial tropical cones for multicriteria optimization'. Together they form a unique fingerprint.

Cite this