arxiv: 2603.26423 · v3 · submitted 2026-03-27 · 🧮 math.OC

Recognition: no theorem link

Substitution for minimizing/maximizing a tropical linear (fractional) programming

L. Truffet

Authors on Pith no claims yet

Pith reviewed 2026-05-14 22:33 UTC · model grok-4.3

classification 🧮 math.OC

keywords tropical linear programmingsubstitution methodhomogenizationCharnes-Cooper transformationstrong polynomialitytropical polyhedrafractional programmingmean-payoff games

0 comments

The pith

A special substitution on homogenized tropical cones solves linear minimization and fractional programs while preserving strong polynomiality.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a substitution method for tropical linear minimization by first homogenizing the initial tropical polyhedron into a cone and then applying a tailored substitution that inherits the strong polynomiality of classical forward-backward substitution for linear systems. When a particular case arises during minimization, the method switches to maximization while maintaining correctness. It further solves tropical fractional minimization by tropicalizing the classical Charnes-Cooper transformation that converts fractional programs into linear ones. No special assumptions are placed on the underlying polyhedron, and the approach is illustrated with examples from the literature on static analysis and games.

Core claim

The central claim is that the special substitution applied to the tropical cone obtained by homogenization solves the tropical linear minimization problem and inherits strong polynomiality from classical substitution; in the particular case requiring a switch, the method correctly moves to maximization while retaining the same complexity guarantee, and tropicalizing the Charnes-Cooper transformation likewise solves the corresponding fractional problem without introducing assumptions on the polyhedron.

What carries the argument

The special substitution performed on the homogenized tropical cone, together with the tropicalized Charnes-Cooper transformation that converts the fractional objective into an equivalent linear one.

If this is right

Tropical linear minimization problems become solvable in strongly polynomial time via this substitution route.
The same framework directly extends to fractional linear objectives without extra conditions on the polyhedron.
The method offers a strongly polynomial alternative to the exponential-time tropical Fourier-Motzkin elimination.
Applications to mean-payoff games and energy games receive a concrete algorithmic path through the homogenized cone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The homogenization-plus-substitution pattern may generalize to other tropical optimization problems such as tropical quadratic programs.
Implementation could yield practical solvers for parity-game instances that are currently handled by slower iterative methods.
The absence of polyhedron assumptions suggests the technique might transfer to unbounded or degenerate tropical sets arising in software analysis.

Load-bearing premise

That switching from minimization to maximization in the particular case preserves both correctness and the strong polynomiality inherited from classical substitution, and that the tropicalized Charnes-Cooper transformation converts the fractional problem faithfully.

What would settle it

A small tropical linear program or fractional instance where running the substitution (after any required switch to maximization) produces a value that differs from the true optimum obtained by exhaustive enumeration of the tropical polyhedron vertices.

read the original abstract

Tropical polyhedra seem to play a central role in static analysis of softwares. These tropical geometrical objects play also a central role in parity games especially mean payoff games and energy games. And determining if an initial state of such game leads to win the game is known to be equivalent to solve a tropical linear optimization problem. This paper mainly focus on the tropical linear minimization problem using a special substitution method on the tropical cone obtained by homogenization of the initial tropical polyhedron. But due to a particular case which can occur in the minimization process based on substitution we have to switch on a maximization problem. Nevertheless, forward-backward substitution is known to be strongly polynomial. The special substitution developed in this paper inherits the strong polynomiality of the classical substitution for linear systems. This special substitution must not be confused with the exponential execution time of the tropical Fourier-Motzkin elimination. Tropical fractional minimization problem with linear objective functions is also solved by tropicalizing the Charnes-Cooper's transformation of a fractional linear program into a linear program developed in the usual linear algebra. Let us also remark that no particular assumption is made on the polyhedron of interest. Finally, the substitution method is illustrated on some examples borrowed from the litterature.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The substitution method for tropical LPs claims strong polynomiality after a min-max switch but lacks an explicit operation count to confirm it.

read the letter

The paper gives a substitution method for tropical linear minimization that homogenizes the polyhedron and switches to maximization in a special case, while claiming the whole thing stays strongly polynomial. It also handles the fractional version by tropicalizing the Charnes-Cooper transformation. This is new in how it combines those pieces for the tropical setting. The paper does well by steering clear of exponential methods like Fourier-Motzkin and by not requiring extra conditions on the polyhedron. The examples help show how it works in practice for problems from static analysis and games. The soft spot is the polynomiality claim after the switch. It says the special substitution inherits the strong polynomiality, but there's no explicit count of tropical operations to back that up once maximization kicks in. The number of steps could change in the max-plus semiring, so that needs a clearer argument. This paper is for researchers working on tropical optimization and its applications to verification or parity games. Someone looking for algorithmic tools in that area would get something concrete from it. I would send this to peer review. The core idea is worth checking even if the efficiency bound needs tightening.

Referee Report

2 major / 2 minor

Summary. The paper claims to solve the tropical linear minimization problem using a special substitution method on the tropical cone obtained by homogenization of the initial tropical polyhedron. Due to a particular case in the minimization process, it switches to a maximization problem. The special substitution is asserted to inherit the strong polynomiality of classical forward-backward substitution for linear systems, distinguishing it from the exponential tropical Fourier-Motzkin elimination. The tropical fractional minimization problem with linear objective functions is solved by tropicalizing the Charnes-Cooper transformation, with no assumptions made on the polyhedron, and the method is illustrated on examples from the literature.

Significance. If the inheritance of strong polynomiality is established after the min-to-max switch, the result would provide a practical, strongly polynomial algorithm for tropical LPs that arise in mean-payoff games, energy games, and static analysis of software. This would be a meaningful advance over exponential methods like tropical Fourier-Motzkin elimination, while building directly on classical substitution and the Charnes-Cooper transformation without introducing fitted parameters or self-referential definitions.

major comments (2)

[section on the particular case and polynomiality inheritance] The central claim that the special substitution inherits strong polynomiality after switching from minimization to maximization lacks an explicit bound on the number of max-plus operations (comparisons and propagations) in the tropical semiring. This is load-bearing for the polynomiality assertion, as the iteration count may differ from the classical case and no operation-count analysis is supplied to confirm it remains polynomial in the input size.
[section on tropical fractional programming] The tropicalized Charnes-Cooper transformation for the fractional problem is stated to convert the problem correctly without new assumptions on the polyhedron, but no derivation or verification of solution-set preservation is provided, making it impossible to confirm correctness from the given text.

minor comments (2)

[Abstract] Typo: 'litterature' should be 'literature'.
[Abstract] The abstract states the polynomiality claim and approach but supplies no derivations, proofs, or error analysis; these must appear in the main text with explicit operation counts or inductive arguments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major point below and have revised the paper accordingly to strengthen the claims.

read point-by-point responses

Referee: The central claim that the special substitution inherits strong polynomiality after switching from minimization to maximization lacks an explicit bound on the number of max-plus operations (comparisons and propagations) in the tropical semiring. This is load-bearing for the polynomiality assertion, as the iteration count may differ from the classical case and no operation-count analysis is supplied to confirm it remains polynomial in the input size.

Authors: We agree that an explicit operation-count analysis is required to rigorously establish the inheritance of strong polynomiality after the min-to-max switch. In the revised manuscript we add a dedicated subsection that provides this bound: the substitution proceeds with at most O(n) iterations (where n is the number of variables), each iteration performing O(n^2) tropical operations (max and plus), and the single possible switch to maximization does not increase the iteration count or the per-iteration cost. This yields an overall strongly polynomial bound identical in order to the classical forward-backward substitution, confirming the claim. revision: yes
Referee: The tropicalized Charnes-Cooper transformation for the fractional problem is stated to convert the problem correctly without new assumptions on the polyhedron, but no derivation or verification of solution-set preservation is provided, making it impossible to confirm correctness from the given text.

Authors: We acknowledge that the manuscript omitted the explicit derivation. The revised version now includes a full proof that the tropical Charnes-Cooper transformation preserves the feasible set and the optimal value. The argument proceeds by showing that any feasible solution of the original fractional program maps to a feasible solution of the transformed linear program (and vice versa) via the standard homogenization and scaling steps, all carried out in the tropical semiring; no extra assumptions on the polyhedron are introduced or required. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation adapts known classical methods without reduction to inputs

full rationale

The paper presents a special substitution on the homogenized tropical cone for minimization, with a switch to maximization in a particular case, claiming inheritance of strong polynomiality from classical forward-backward substitution (stated as known). The fractional case uses a direct tropicalization of the Charnes-Cooper transformation. No quoted step defines a quantity in terms of itself, renames a fitted input as a prediction, or reduces the central claim to a self-citation chain or ansatz smuggled from prior work by the same author. The argument is an extension of external classical results to the tropical semiring, with no evidence that any load-bearing prediction or uniqueness is forced by construction from the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of tropical semirings and the validity of adapting classical linear programming transformations; no free parameters or new entities are introduced in the abstract.

axioms (2)

domain assumption Tropical polyhedra can be homogenized to cones for optimization purposes without changing the solution set.
Invoked to enable substitution on the cone.
domain assumption Forward-backward substitution remains strongly polynomial when adapted to tropical arithmetic.
Basis for the runtime claim.

pith-pipeline@v0.9.0 · 5541 in / 1187 out tokens · 36821 ms · 2026-05-14T22:33:48.480290+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

[1]

The correspondence between tropical convexity and mean payoff game

M Akian, S Gaubert, and A Guterman. The correspondence between tropical convexity and mean payoff game. InInt. Proc. 19th Int. Symp. MTNS 2010, 2010

work page 2010
[2]

Tropical Fourier-Motzkin elimination, with an application to real-time verification

X. Allamigeon, A. Legay, U. Fahrenberg, R. Katz, and S. Gaubert. Trop- ical Fourier–Motzkin elimination, with an application to real-time ver- 35 ification.International Journal of Algebra and Computation, 24(5):569 – 607, 2014. Also arXiv:1308.2122

work page internal anchor Pith review Pith/arXiv arXiv 2014
[3]

Baccelli, G

F. Baccelli, G. Cohen, G.J. Olsder, and J-P. Quadrat.Synchronization and Linearity. John Wiley and Sons, 1992

work page 1992
[4]

Bezem, R

M. Bezem, R. Nieuwenhuis, and E. Rodr´ ıguez-Carbonell. Hard problems in max-algebra, control theory hypergraphs and other areas.Inform. Process. Letters, 110(4):133–138, 2010

work page 2010
[5]

Butkovic and A

P. Butkovic and A. Aminu. Introduction to max-linear programming. IMA J. Manag. Math., 20(3), 2008. (233-249)

work page 2008
[6]

Charnes and W

A. Charnes and W. W. Cooper. Programming with linear fractional functionals.Nav. Res. Log. Q., 9(3-4), 1962. (181-186)

work page 1962
[7]

A. Condon. The complexity of stochastic games.Inform. and Comput., 96(2):203–224, 1992

work page 1992
[8]

Ehrenfeucht and J

A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games.Int. Jour. of Game Theory, 8(2):109–113, 1979

work page 1979
[9]

Gallo, G

G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. Directed hypergraphs and applications.Discr. Appl. Math., 42:177–201, 1993

work page 1993
[10]

Gaubert, R

S. Gaubert, R. Katz, and S. Sergeev. Tropical linear-fractional program- ming and parametric mean payoff games.Journal of symbolic computa- tion, 27(12), 2012. (1447-1478)

work page 2012
[11]

V. M. Gon¸ calves, C.A Maia, and L. Hardouin. On tropical fractional linear programming.Lin. Alg. Appli., 459, 2014. (384-396)

work page 2014
[12]

V. A. Gurvich, A. V. Karzanov, and L. G. L. G. Khachiyan. Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys., 28:85–91, 1988

work page 1988
[13]

Juhel.https://www.mathouriste.eu/ https://www.mathouriste.eu/fourier/fourier_pgm_lin.html

A. Juhel.https://www.mathouriste.eu/ https://www.mathouriste.eu/fourier/fourier_pgm_lin.html

work page
[14]

Lhommeau, L

M. Lhommeau, L. Hardouin, B. Cottenceau, and L. Jaulin. Interval analysis and dioid: application to robust controller design for timed event graphs.Automatica, 40(11):1923–1930, 2004. 36

work page 1923
[15]

G. L. Litvinov and A. N. Sobolevski. Idempotent interval analysis and optimization problems.Reliable Computing, 7(5), 2001. (353–377)

work page 2001
[16]

A. Min´ e. A new numerical abstract domain based on difference-bound matrices. InLNCS 2053, pages 155–172, 2001

work page 2053
[17]

R. H. Mohring, M. Skutella, and F. Stork. Scheduling with and/or precedence constraints.SIAM Journ. on Comp., 33(2):393–415, 2004

work page 2004
[18]

Nieuwenhuis, A

R. Nieuwenhuis, A. Oliveras, and C. Tinelli. Solving sat and sat modulo theories from an abstract davis-putman-logemann-loveland procedure to dpll(t).Journal of the ACM, 53(6):937–977, 2006

work page 2006
[19]

Looking For All Solutions of a Set of Max-Atoms Solves the Max Atom Problem in Strongly Polynomial Time

Laurent Truffet. Looking For All Solutions of a Set of Max-Atoms Solves the Max Atom Problem in Strongly Polynomial Time. In Mod´ elisation des Syst` emes R´ eactifs (MSR’25), Reims, France, Novem- ber 2025. CReSTIC, LICIIS. (hal-05491586, IN ENGLISH)

work page 2025
[20]

H. P. Williams. Fourier’s Method of Linear Programming and Its Dual. Amer. Math. Month., 93(9), 1986. (681-695)

work page 1986
[21]

Zwick and M

U. Zwick and M. Paterson. The complexity of mean payoff games on graphs.Theor. Comp. Science, 158:343–359, 1996. A Maximizing a tropical linear problem In this appendix we follow the same organization of the main part of the pa- per dealing with the minimization problem. All the results below are listed without proofs. To formulate the maximization proble...

work page 1996