A strongly polynomial method for solving integer max-linear optimization problems in a generic case

DOI10.1007/s10957-014-0596-5zbMath1323.65067OpenAlexW2084234177WikidataQ59409787 ScholiaQ59409787MaRDI QIDQ2349847

Marie MacCaig, Peter Butkovic

Publication date: 18 June 2015

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

Full work available at URL: https://doi.org/10.1007/s10957-014-0596-5

zbMATH Keywords

numerical exampleexistence of solutioninteger optimal solutioninteger max-linear optimization probleminteger max-linear systemoneF(ractional)P(art)-propertystrongly polynomial method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Max-plus and related algebras (15A80)

Related Items (2)

Constrained integer fractional programming problem with box constraints ⋮ Approximating the volume of tropical polytopes is difficult

Cites Work

• Tropical linear-fractional programming and parametric mean payoff games
• On the integer max-linear programming problem
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• A characterization of the minimum cycle mean in a digraph
• Minimax algebra
• The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
• On integer eigenvectors and subeigenvectors in the max-plus algebra
• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Introduction to max-linear programming
• Max-linear Systems: Theory and Algorithms
• Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A strongly polynomial method for solving integer max-linear optimization problems in a generic case