Buchberger algorithm and integer programming
[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.
- On the complexity of smooth projective toric varieties
- Standard pairs and group relaxations in integer programming
- Test sets of integer programs
- Test sets for integer programs
- Gröbner bases of certain zero-dimensional ideals arising in coding theory
- Enumerating polytropes
- An algebraic algorithm for solving parametric integer programs
- Finding multiplies solutions for non-linear integer programming
- Algebraic algorithms for sampling from conditional distributions
- N-solutions to linear systems over Z
- Minimal resolutions of lattice ideals and integer linear programming
- Gröbner bases and triangulations of the second hypersimplex
- An algebraic geometry algorithm for scheduling in presence of setups and correlated demands
- Binomial ideals
- Decomposition of modular codes for computing test sets and Graver basis
- Applying Gröbner basis method to multiparametric polynomial nonlinear programming
- Generating functions and duality for integer programs
- A discrete Farkas lemma
- Alternatives for testing total dual integrality
- The generic Gröbner walk
- Solving thousand-digit Frobenius problems using Gröbner bases
- Sequential importance sampling for multiway tables
- The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
- Test sets for vertex cover problems
- Exact cost minimization of a series-parallel reliable system with multiple component choices using an algebraic method
- Gröbner bases and their application to the Cauchy problem on finitely generated affine monoids
- Representing and solving finite-domain constraint problems using systems of polynomials
- A mathematical programming approach to the computation of the omega invariant of a numerical semigroup
- Gröbner bases of contraction ideals
- scientific article; zbMATH DE number 1163431 (Why is no real title available?)
- Test sets and inequalities for integer programs
- scientific article; zbMATH DE number 782043 (Why is no real title available?)
- scientific article; zbMATH DE number 915924 (Why is no real title available?)
- GRIN: an implementation of Gröbner bases for integer programming
- Solving linear systems of equations over integers with Gröbner bases
- An algebraic approach to integer portfolio problems
- The combinatorics of modeling and analyzing biological systems
- Initial ideals of unimodular integer programs
- Some algebraic methods for solving multiobjective polynomial integer programs
- On the relationship between the value function and the efficient frontier of a mixed integer linear optimization problem
- Computing local minimizers in polynomial optimization under genericity conditions
- Non-standard approaches to integer programming
- Exploring the geometric buchberger algorithm in integer programming
- Toric ideals which are determinantal
- Integer programming with binary and bounded variables via Gröbner bases with applications to multiobjective integer programming
- Computing generating sets of lattice ideals and Markov bases of lattices
- On selection of nonmultiplicative prolongations in computation of Janet bases
This page was built for publication: Buchberger algorithm and integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038746)
