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 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.