Hard Equality Constrained Integer Knapsacks

DOI10.1287/MOOR.1040.0099MaRDI QIDQ5704196zbMATH OpenOpenAlexFDO

Authors Karen Aardal, Arjen K. Lenstra

Publication date 11 November 2005

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://infoscience.epfl.ch/record/149458/files/149458.pdf

zbMATH Keywords

branching on hyperplanesFrobenius numberlattice basis reduction

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) Computer solution of Diophantine equations (11Y50) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 2086933
• On equivalent knapsack problems
• Feasibility of integer knapsacks
• Hardness of approximation for knapsack problems
• On facets of knapsack equality polytopes
• Integrality gaps of integer knapsack problems
• scientific article; zbMATH DE number 2130001
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• Algorithms for some hard knapsack problems
• scientific article; zbMATH DE number 4202023

Cited in

(24)

• Testing integer knapsacks for feasibility
• Thinner is not always better: cascade knapsack problems
• Lattice-based algorithms for number partitioning in the hard phase
• LLL-reduction for integer knapsacks
• The generic Gröbner walk
• An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection
• Feasibility of integer knapsacks
• scientific article; zbMATH DE number 2086933 (Why is no real title available?)
• A Euclid style algorithm for MacMahon's partition analysis
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Lattice reformulation cuts
• On the structure of reduced kernel lattice bases
• Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices
• A study of lattice reformulations for integer programming
• Compressing branch-and-bound trees
• On a variant of the change-making problem
• Compressing branch-and-bound trees
• An algebraic combinatorial approach to Sylvester's denumerant
• Integer programming with binary and bounded variables via Gröbner bases with applications to multiobjective integer programming
• On the power and limitations of branch and cut
• Branching with a pre-specified finite list of k-sparse split sets for binary MIPs
• Column basis reduction and decomposable knapsack problems
• Lattice based extended formulations for integer linear equality systems
• Bounds on the size of branch-and-bound proofs for integer knapsacks

This page was built for publication: Hard Equality Constrained Integer Knapsacks

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