Non-standard approaches to integer programming

DOI10.1016/S0166-218X(01)00337-7zbMath1130.90364OpenAlexW2098919194WikidataQ94974383 ScholiaQ94974383MaRDI QIDQ697562

Karen Aardal, Robert Weismantel, Laurence A. Wolsey

Publication date: 17 September 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00337-7

zbMATH Keywords

Gröbner basisInteger programmingAsymptotic group problemAugmentation algorithmsCorner polyhedronLattice basis reductionLenstra's algorithmSubadditivityTest sets

Mathematics Subject Classification ID

Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

A partial enumeration algorithm for pure nonlinear integer programming, Extended formulations for Gomory corner polyhedra, Generating functions and duality for integer programs, Effective lattice point counting in rational convex polytopes, Multivariable Branching: A 0-1 Knapsack Problem Case Study, Could we use a million cores to solve an integer program?, The power of pyramid decomposition in Normaliz, New Bounds for the Integer Carathéodory Rank, Integer programming, Barvinok's counting algorithm and Gomory relaxations., A generalization of the integer linear infeasibility problem, Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems, Relations between facets of low- and high-dimensional group problems, Parameterized complexity of coloring problems: treewidth versus vertex cover, New linearizations of quadratic assignment problems, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, Vectors in a box, On the lattice programming gap of the group problems, Existence of unimodular triangulations — positive results, An improved partial enumeration algorithm for integer programming problems, Valid inequalities based on simple mixed-integer sets, Cover and pack inequalities for (mixed) integer programming

Uses Software

• LiDIA
• NTL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total dual integrality and integer polyhedra
• On the height of the minimal Hilbert basis
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Decomposition of integer programs and of generating sets
• An integer analogue of Carathéodory's theorem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Covering minima and lattice-point-free convex bodies
• On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities
• The b-hull of an integer program
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• Geometric algorithms and combinatorial optimization
• Lattice reduction: a toolbox for the cryptoanalyst
• Hilbert bases, unimodular triangulations, and binary covers of rational polyhedral cones
• Standard pairs and group relaxations in integer programming
• Simultaneous reduction of a lattice basis and its reciprocal basis
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Truncated Gröbner bases for integer programming
• Variation of cost functions in integer programming
• The height of minimal Hilbert bases
• The integral basis method for integer programming
• Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
• Gröbner bases of lattices, corner polyhedra, and integer programming
• On minimal solutions of Diophantine equations
• Some polyhedra related to combinatorial problems
• Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables
• Integer Programming with a Fixed Number of Variables
• A Variant of the Buchberger Algorithm for Integer Programming
• Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's fast signature scheme
• Variable metric relaxation methods, part II: The ellipsoid method
• Neighborhood Systems for Production Sets with Indivisibilities
• Solving low-density subset sum problems
• Minkowski's Convex Body Theorem and Integer Programming
• Sensitivity theorems in integer linear programming
• A Polynomial Algorithm for the Two-Variable Integer Programming Problem
• On the symmetric travelling salesman problem: A computational study
• Production Sets with Indivisibilities, Part I: Generalities
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The Generalized Basis Reduction Algorithm
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the foundations of linear and integer linear programming I
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
• A Convergent Duality Theory for Integer Programming
• An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming
• Normality and covering properties of affine semigroups
• A counterexample to an integer analogue of Carathéodory's theorem
• Block Reduced Lattice Bases and Successive Minima
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A Geometric Buchberger Algorithm for Integer Programming
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• A Simplified Primal (All-Integer) Integer Programming Algorithm
• A primal (all-integer) integer programming algorithm
• FACES OF AN INTEGER POLYHEDRON
• Some continuous functions related to corner polyhedra
• The complexity of theorem-proving procedures
• Computational experience with a group theoretic integer programming algorithm
• Generalized dynamic programming methods in integer programming
• 0/1-Integer programming: Optimization and Augmentation are equivalent