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

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes


We study the existence of integer solutions to max-linear optimization problems. Specifically, we show that, in a generic case, the integer max-linear optimization problem can be solved in strongly polynomial time. This extends results from our previous papers where polynomial methods for this generic case were given.


Original languageEnglish
Pages (from-to)941-963
Number of pages23
JournalJournal of Optimization Theory and Applications
Issue number3
Early online date24 Jun 2014
Publication statusPublished - 2015


  • Max-linear optimization problem, Integer vector, Max-linear system, 15A80