Monomial tropical cones for multicriteria optimization

Michael Joswig, Georg Loho

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)


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
Issue number2
Publication statusPublished - 2020
Externally publishedYes


  • Discrete multicriteria optimization
  • Monomial ideals
  • Tropical convexity


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

Cite this