Column basis reduction and decomposable knapsack problems

DOI10.1016/J.DISOPT.2009.01.003MaRDI QIDQ834182zbMATH OpenOpenAlexFDO

Authors Bala Krishnamoorthy, Gábor Pataki

Publication date 19 August 2009

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.1317

zbMATH Keywords

integer programmingsplit disjunctionsbasis reduction

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Abstract: We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b' <= Ax <= b, x in Z^n with b' <= AUy <= b, y in Z^n, where U is a unimodular matrix computed via basis reduction, to make the columns of $AU$ short and nearly orthogonal. The reformulation is called rangespace reformulation. It is motivated by the reformulation technique proposed for equality constrained IPs by Aardal, Hurkens and Lenstra. We also study a family of IP instances, called decomposable knapsack problems (DKPs). DKPs generalize the instances proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra, and Cornuejols et al. DKPs are knapsack problems with a constraint vector of the form $pM+r,$ with $p>0$ and $r$ integral vectors, and $M$ a large integer. If the parameters are suitably chosen in DKPs, we prove 1) hardness results for these problems, when branch-and-bound branching on individual variables is applied; 2) that they are easy, if one branches on the constraint $px$ instead; and 3) that branching on the last few variables in either the rangespace- or the AHL-reformulations is equivalent to branching on $px$ in the original problem. We also provide recipes to generate such instances. Our computational study confirms that the behavior of the studied instances in practice is as predicted by the theoretical results.

Recommendations

• scientific article; zbMATH DE number 1973871
• An Improved Knapsack Solver for Column Generation
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• scientific article; zbMATH DE number 3926634
• A column generation method for the multiple-choice multi-dimensional knapsack problem
• On \(k\)-column sparse packing programs
• Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem
• Problem reduction heuristic for the 0-1 multidimensional knapsack problem
• Algorithms to approximate column-sparse packing problems
• scientific article; zbMATH DE number 6850331

Cites work

• scientific article; zbMATH DE number 3156817 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A Class of Hard Small 0-1 Programs
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• A hierarchy of polynomial time lattice basis reduction algorithms
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A primal all-integer algorithm based on irreducible solutions
• An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming
• Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices
• Chvátal closures for mixed integer programming problems
• Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
• Computing the Continuous Discretely
• Decomposition of integer programs and of generating sets
• Disjunctive Programming
• Effective lattice point counting in rational convex polytopes
• Equivalent Integer Programs and Canonical Problems
• Factoring polynomials with rational coefficients
• Hard Equality Constrained Integer Knapsacks
• Hard Knapsack Problems
• Integer Programming with a Fixed Number of Variables
• Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
• Minkowski's Convex Body Theorem and Integer Programming
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• On Lovász' lattice reduction and the nearest lattice point problem
• On the separation of split cuts and related inequalities
• Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
• The Generalized Basis Reduction Algorithm
• Trivial integer programs unsolvable by branch-and-bound

Cited in

(14)

• Thinner is not always better: cascade knapsack problems
• Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Integer programming for classifying orthogonal arrays
• Basis reduction and the complexity of branch-and-bound
• Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
• A study of lattice reformulations for integer programming
• On the structure of reduced kernel lattice bases
• Multivariable Branching: A 0-1 Knapsack Problem Case Study
• Lattice-based algorithms for number partitioning in the hard phase
• Sparse recovery with integrality constraints
• Lattice reformulation cuts
• An Improved Knapsack Solver for Column Generation
• Analysis of integer programming algorithms with \(L\)-partition and unimodular transformations

Describes a project that uses

Uses Software

• LattE
• NTL

This page was built for publication: Column basis reduction and decomposable knapsack problems

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