Tropical Bi-Objective Pseudolinear Optimization as Parametric Mean-Payoff Games

We extend the parametric mean-payoff game framework of Parsons et al. to bi-objective tropical pseudolinear optimization with general two-sided constraints.

The problem is to simultaneously minimize two tropical pseudolinear objectives over the feasible set of a general two-sided system U otimes x oplus b is less than or equal to V otimes x oplus d, we characterize the Pareto front via a parametric mean-payoff game in two parameters ( lambda 1, lambda 2).

The feasibility region R is convex and the Pareto front P is a convex piecewise-linear curve with finitely many breakpoints, these properties are natural extensions of the single-parameter case to two parameters.

In addition, we give as a new result, the joint denominator bound: the cycle coefficients satisfy k 1( gamma ) + k 2( gamma ) is less than or equal to 2 for any elementary cycle gamma, yielding | Delta | is less than or equal to 2 for every 2 times 2 Newton system, except in the fully decoupled case, and implying that all breakpoints have half-integer coordinates for integer data.

Optimality and infeasibility certificates are given in terms of the cycle structure of the parametric game.

Two algorithms are developed, a directional bisection algorithm (O(n squared (n+m) log M) per direction) and a Newton scheme tracing the complete Pareto front via 2 times 2 linear solves in at most | S | steps, independent of M.

The directional bisection algorithm is pseudo-polynomial in n, m and M.

The Newton scheme is independent of M but requires up to |S| steps, where |S| is exponential in n.

Lastly, we give numerical experiments on random instances to confirm the directional bisection complexity bound exactly; the Newton scheme's worst-case bound is not attained by random instances but is shown to be tight via explicit adversarial constructions.