A note on tropical linear and integer programs

DOI10.1007/S10957-018-1429-8zbMATH Open1436.90102arXiv1709.08983OpenAlexW2899375208WikidataQ128999114 ScholiaQ128999114MaRDI QIDQ1730786FDOQ1730786

Peter Butkovič

Publication date: 6 March 2019

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

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.

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

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

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)

Cites Work

• Max-linear Systems: Theory and Algorithms
• Title not available (Why is that?)
• Linear and combinatorial optimization in ordered algebraic structures
• Minimax algebra
• Tropical polyhedra are equivalent to mean payoff games
• A MAX-plus model of ribosome dynamics during mRNA translation
• Introduction to max-linear programming
• Tropical linear-fractional programming and parametric mean payoff games
• On abstract dual linear programs
• A characterization of the minimum cycle mean in a digraph
• Max-algebra: The linear algebra of combinatorics?
• On tropical supereigenvectors
• Title not available (Why is that?)
• Reducible Spectral Theory with Applications to the Robustness of Matrices in Max-Algebra
• Title not available (Why is that?)
• Applications of max algebra to diagonal scaling of matrices
• Finding a bounded mixed-integer solution to a system of dual network inequalities
• On the integer max-linear programming problem
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings

Cited In (7)

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

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)