A note on tropical linear and integer programs

DOI10.1007/S10957-018-1429-8MaRDI QIDQ1730786zbMATH OpenOpenAlexWikidataFDO

Authors Peter Butkovič

Publication date 6 March 2019

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1709.08983

zbMATH Keywords

dualitytropical linear programmingresiduationtropical integer programming

Mathematics Subject Classification ID

Linear programming (90C05) Optimality conditions and duality in mathematical programming (90C46) Eigenvalues, singular values, and eigenvectors (15A18) Integer programming (90C10) Max-plus and related algebras (15A80) Tropical optimization (e.g., max-plus optimization) (90C24)

Abstract: We present simple compact proofs of the strong and weak duality theorems of tropical linear programming. It follows that there is no duality gap for a pair of tropical primal-dual problems. This result together with known properties of subeigenvectors enables us to directly solve a special tropical linear program with two-sided constraints. We also study the duality gap in tropical integer linear programming. A direct solution is available for the primal problem. An algorithm of quadratic complexity is presented for the dual problem. A direct solution is available provided that all coefficients of the objective function are integer. This solution yields a good estimate of the optimal objective function value in the general case.

Recommendations

• On tropical fractional linear programming
• Tropicalizing the simplex algorithm
• Algebraic solutions of tropical optimization problems
• Abstract tropical linear programming
• New algorithms for solving tropical linear systems

Cites work

• scientific article; zbMATH DE number 3906559 (Why is no real title available?)
• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• A MAX-plus model of ribosome dynamics during mRNA translation
• A characterization of the minimum cycle mean in a digraph
• Applications of max algebra to diagonal scaling of matrices
• Finding a bounded mixed-integer solution to a system of dual network inequalities
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Introduction to max-linear programming
• Linear and combinatorial optimization in ordered algebraic structures
• Max-algebra: The linear algebra of combinatorics?
• Max-linear systems. Theory and algorithms.
• Minimax algebra
• On abstract dual linear programs
• On the integer max-linear programming problem
• On tropical supereigenvectors
• Reducible spectral theory with applications to the robustness of matrices in max-algebra
• Tropical linear-fractional programming and parametric mean payoff games
• Tropical mathematics
• Tropical polyhedra are equivalent to mean payoff games
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings

Cited in

(10)

• Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
• The non-positive circuit weight problem in parametric graphs: a solution based on dioid theory
• On tropical fractional linear programming
• Tropicalizing the simplex algorithm
• The 2-domination number of cylindrical graphs
• Tropical Carathéodory with matroids
• Weak dual residuations applied to tropical linear equations
• Abstract tropical linear programming
• Extremal properties of tropical eigenvalues and solutions to tropical optimization problems
• What Tropical Geometry Tells Us about the Complexity of Linear Programming

This page was built for publication: A note on tropical linear and integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1730786)