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
18 May 1993
0 references
integer programming
0 references
Gröbner basis
0 references
0.8356447815895081
0 references
0.83522629737854
0 references
0.8311745524406433
0 references
0.8012210726737976
0 references
0.7951234579086304
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