Standard pairs and group relaxations in integer programming

DOI10.1016/S0022-4049(99)00009-2MaRDI QIDQ1295785zbMATH OpenOpenAlexWikidataFDO

Authors Serkan Hoşten, Rekha Thomas

Publication date 5 May 2003

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-4049(99)00009-2

zbMATH Keywords

group relaxationsGröbner basesinteger programmingtoric ideals

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10)

Review text

By using the connections between toric ideals and integer programming, the authors give a non-Buchberger algorithm for constructing initial ideals and Gröbner bases of toric ideals. The main tools in giving such an algorithm are standard pair decompositions of standard monomials of a toric initial ideal, localization of such ideals at their associated primes and group relaxations of integer programs. An algorithm is also given for constructing standard pair decompositions. The special case of toric ideals of codimension two is considered, and new results are given on localization of the initial ideals of these ideals at their associated primes.

Recommendations

• Alternative group relaxation of integer programming problems
• The group problem and integer programming duality
• The group-theoretic approach in mixed integer programming
• Group-theoretic method of decomposition methods in integer linear programming
• Relation betwen integer linear vector optimization and multicriteria problems on groups and graphs
• scientific article; zbMATH DE number 4092675
• On the complexity of surrogate and group relaxation for integer linear programs
• Standard pairs for lawrence-type matrices and their applications to several lawrence-type integer programs
• Constrained infinite group relaxations of MIPs
• Semidefinite relaxations for integer programming

Cites work

• A Geometric Buchberger Algorithm for Integer Programming
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Bounds on degrees of projective schemes
• Computing combinatorial decompositions of rings
• Constructions and complexity of secondary polytopes
• Extensions of the Group Theoretic Approach in Integer Programming
• Gröbner bases of lattices, corner polyhedra, and integer programming
• Gröbner bases of toric varieties
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 177867 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 638938 (Why is no real title available?)
• scientific article; zbMATH DE number 967945 (Why is no real title available?)
• Introduction to Toric Varieties. (AM-131)
• Lifting projections of convex polyhedra
• Linear Diophantine equations and local cohomology
• Neighborhood Systems for Production Sets with Indivisibilities
• On the foundations of linear and integer linear programming I
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Sensitivity theorems in integer linear programming
• Some polyhedra related to combinatorial problems
• Syzygies of codimension 2 lattice ideals
• The associated primes of initial ideals of lattice ideals
• The Gröbner fan of an ideal
• The value function of an integer program
• Variation of cost functions in integer programming
• What can be computed in algebraic geometry?

Cited in

(20)

• The toric Hilbert scheme of a rank two lattice is smooth and irreducible.
• An algebraic algorithm for solving parametric integer programs
• The vertex ideal of a lattice.
• On a conjecture of R. P. Stanley. II: Quotients modulo monomial ideals
• Standard pairs for monomial ideals in semigroup rings
• Prime filtrations of monomial ideals and polarizations
• Computing the integer programming gap
• An algorithm for solving parametric integer program
• On rotational symmetries of drawings of coherent periodic graphs
• scientific article; zbMATH DE number 1736031 (Why is no real title available?)
• Uniform bounds on multigraded regularity
• Standard pairs for lawrence-type matrices and their applications to several lawrence-type integer programs
• The structure of group relaxations
• Standard Bigraded Hilbert Functions
• Initial ideals of unimodular integer programs
• Asymptotic degree of random monomial ideals
• Non-standard approaches to integer programming
• Exploring the geometric buchberger algorithm in integer programming
• Integer programming with binary and bounded variables via Gröbner bases with applications to multiobjective integer programming
• Finite filtrations of modules and shellable multicomplexes

This page was built for publication: Standard pairs and group relaxations in integer programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295785)