Loho G. Combinatorics of Tropical Linear Programming

Berlin: Technische Universität, 2017. — 130 p.A tropical linear inequality is an inequality of the form
min {ai + xi | i ∈ I} ≤ min {a + x | ∈ [d] \ I} ,
where [d] = {1, 2...d} for a natural number d, I ⊆ [d] and a1...ad are elements of the tropical numbers Tmin = R ∪ {∞}. We study systems of tropical linear inequalities and in particular, the algorithmic question of finding a feasible point (x1...xd) ∈ Td min which fulfills all the inequalities in a given system. This is the tropical feasibility problem. Methods to solve this are referred as tropical linear programming. It is a tropical analogue of classical linear programming.