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

From MaRDI portal
Revision as of 02:29, 11 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
A strongly polynomial method for solving integer max-linear optimization problems in a generic case
scientific article

    Statements

    A strongly polynomial method for solving integer max-linear optimization problems in a generic case (English)
    0 references
    18 June 2015
    0 references
    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.
    0 references
    integer max-linear optimization problem
    0 references
    integer max-linear system
    0 references
    strongly polynomial method
    0 references
    existence of solution
    0 references
    oneF(ractional)P(art)-property
    0 references
    integer optimal solution
    0 references
    numerical example
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references