Buchberger algorithm and integer programming (Q4038746)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 177867
Language Label Description Also known as
default for all languages
No label defined
    English
    Buchberger algorithm and integer programming
    scientific article; zbMATH DE number 177867

      Statements

      0 references
      0 references
      18 May 1993
      0 references
      integer programming
      0 references
      Gröbner basis
      0 references
      Buchberger algorithm and integer programming (English)
      0 references
      [For the entire collection see Zbl 0758.00016.] The problem of finding solutions in non-negative integers for a system of linear equations with integer coefficients can be translated to a subalgebra membership problem. Thus solutions can be found by computing the Gröbner basis of a certain binomial ideal (i.e. an ideal generated by term differences). The authors first describe this algorithm. The solution \(X_ T\) obtained by this algorithm depends on the term order \(T\) chosen for the Gröbner basis computation. Then they prove: if the given system has a minimal solution with respect to a linear cost function, then there is a term order \(T\) (which can be found explicitly) such that \(X_ T\) is a minimal solution. Finally the authors give some remarks that help to simplify the computations and discuss several examples.
      0 references

      Identifiers