Monomial tropical cones for multicriteria optimization

We present an algorithm to compute all n nondominated points of a multicriteria discrete optimization problem with d objectives using at most O(nlfloor 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.