A strongly polynomial method for solving integer max-linear optimization problems in a generic case (Q2349847): Difference between revisions

The paper extends results of \textit{P. Butkovič} and \textit{M. MacCaig} [Discrete Appl. Math. 162, 128--141 (2014; Zbl 1303.90063)] and yields a strongly polynomial method for finding an integer solution of a max-linear optimization problem (IMLOP). First, they introduce basics on max-linear algebra and consider then the solvability of max-linear systems w.r.t. integer solutions. Using oneF(ractional)P(art)-property for the max-linear systems they derive the existence of integer solutions of max-linear systems and give statements about the optimal value and an integer optimal solution of an IMLOP under OneFP. They show that the method belonging to their statements is strongly polynomial. An explicit algorithmic description of the method, as can be found e.g. in their paper [loc. cit.], is not given. A simple numerical example in \(\mathbb Z^4\) shows the reader how a solution of an IMLOP can be found by using the developed statements.