Tropical aspects of linear programming

Pascal Benchimol 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
Inria Saclay - Ile de France, CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
Abstract : In this thesis, we present new results on the complexity of classical linear programming on the one hand, and of tropical linear programming and mean payoff games on the other hand. Our contributions lie in the study of the interplay between these two problems provided by the dequantization process. This process tranforms classical linear programs into linear programs over tropical semirings, such as the $\R \cup\{ -\infty\}$ endowed with $\max$ as addition and $+$ as muliplication. Concerning classical linear programming, our first contribution is a tropicalization of the simplex method. More precisely, we describe an implementation of the simplex method that, under genericity conditions, solves a linear program over an ordered field. Our implementation uses only the restricted information provided by the valuation map, which corresponds to the ``orders of magnitude'' of the input. Using this approach, we exhibit a class of classical linear programs over the real numbers on which the simplex method, with any pivoting rule, performs a number of iterations which is polynomial in the input size of the problem. In particular, this implies that the corresponding polyhedra have a diameter which is polynomial in the input size. Our second contribution concerns interior point methods for classical linear programming. We disprove the continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with $3r + 4$ inequalities in dimension $2r + 2$ where the central path has a total curvature which is exponential in $r$. We also point out suprising features of the tropicalization of the central path. For example it has a purely geometric description, while the classical central path depends on the algebraic representation of a linear program. Moreover, the tropical central path may lie on the boundary of the tropicalization of the feasible set, and may even coincide with a path of the tropical simplex method. Concerning tropical linear programming and mean payoff games, our main result is a new procedure to solve these problems based on the tropicalization of the simplex method. The latter readily applies to tropical linear programs satisfying genericity conditions. In order to solve arbitrary problems, we devise a new perturbation scheme. Our key tool is to use tropical semirings based on additive groups of vectors ordered lexicographically. Then, we transfer complexity results from classical to tropical linear programming. We show that the existence of a polynomial-time pivoting rule for the classical simplex method, satisfying additional assumptions, would provide a polynomial algorithm for tropical linear programming and thus for mean payoff games. By transferring the analysis of the shadow-vertex rule of Adler, Karp and Shamir, we also obtain the first algorithm that solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a symmetry property. We establish tropical counterparts of the notions of basic points and edges of a polyhedron. This yields a geometric interpretation of the tropicalization of the simplex method. As in the classical case, the tropical algorithm pivots on the graph of an arrangement of hyperplanes associated to a tropical polyhedron. This interpretation is based on a geometric connection between the cells of an arrangement of classical hyperplanes and their tropicalization. Building up on this geometric interpretation, we present algorithmic refinements of the tropical pivoting operation. We show that pivoting along an edge of a tropical polyhedron defined by $m$ inequalities in dimension $n$ can be done in time $O(n(m+n))$, a complexity similar to the classical pivoting operation. We also show that the computation of reduced costs can be done tropically in time $O(n(m+n))$.
Complete list of metadatas

Cited literature [146 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/tel-01198482
Contributor : Pascal Benchimol <>
Submitted on : Sunday, September 13, 2015 - 3:48:20 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:31 PM
Long-term archiving on : Tuesday, December 29, 2015 - 1:04:31 AM

File

Identifiers

  • HAL Id : tel-01198482, version 1

Collections

Citation

Pascal Benchimol. Tropical aspects of linear programming. Optimization and Control [math.OC]. Ecole Polytechnique, 2014. English. ⟨tel-01198482⟩

Share

Metrics

Record views

445

Files downloads

538