Tropical linear-fractional programming and parametric mean payoff games

Abstract

Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the tropical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.

34 pages, 9 figures, minor corrections, additions and improvements

References in corpus (4)

• Duality and separation theorems in idempotent semimodules
• The tropical analogue of polar cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The level set method for the two-sided eigenproblem

Cited by in corpus (18)

• Tropicalizing the simplex algorithm
• A multidimensional tropical optimization problem with nonlinear objective function and linear constraints
• A constrained tropical optimization problem: complete solution and application example
• The level set method for the two-sided eigenproblem
• Combinatorial simplex algorithms can solve mean payoff games
• Tropical optimization problems with application to project scheduling with minimum makespan
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Tropical linear algebra with the Lukasiewicz T-norm
• Tropical optimization problems
• Algebraic solution of tropical polynomial optimization problems
• Algebraic solutions of tropical optimization problems
• On $2\times 2$ Tropical Commuting Matrices
• A complete closed-form solution to a tropical extremal problem
• A tropical extremal problem with nonlinear objective function and linear inequality constraints
• Minimizing maximum lateness in two-stage projects by tropical optimization
• Using matrix sparsification to solve tropical linear vector equations
• Tropical analogues of a Dempe-Franke bilevel optimization problem
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games