Monomial tropical cones for multicriteria optimization

Abstract

We present an algorithm to compute all $n$ nondominated points of a multicriteria discrete optimization problem with $d$ objectives using at most $\mathcal{O}(n^{\lfloor d/2\rfloor })$ scalarizations. The method is similar to algorithms by Przybylski et al. (2010) and by Klamroth et al. (2015) 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.

19 pages, 2 figures; discussed further related work