Non-standard approaches to integer programming

DOI10.1016/S0166-218X(01)00337-7zbMATH Open1130.90364DBLPjournals/dam/AardalWW02OpenAlexW2098919194WikidataQ94974383 ScholiaQ94974383MaRDI QIDQ697562FDOQ697562

Authors: 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

Recommendations

• scientific article; zbMATH DE number 5165610
• scientific article; zbMATH DE number 2159271
• An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming
• scientific article; zbMATH DE number 3896667
• scientific article; zbMATH DE number 549930

zbMATH Keywords

Integer programmingAsymptotic group problemAugmentation algorithmsCorner polyhedronLattice basis reductionLenstra's algorithmSubadditivityTest setsGröbner basis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

Uses Software

• LiDIA
• NTL

This page was built for publication: Non-standard approaches to integer programming

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