Column basis reduction and decomposable knapsack problems

DOI10.1016/J.DISOPT.2009.01.003zbMATH Open1176.90418arXiv0807.1317OpenAlexW2064684117MaRDI QIDQ834182FDOQ834182

Authors: Bala Krishnamoorthy, Gábor Pataki 

Publication date: 19 August 2009

Published in: Discrete Optimization (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

integer programmingsplit disjunctionsbasis reduction

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• Integer programming for classifying orthogonal arrays
• Basis reduction and the complexity of branch-and-bound
• A study of lattice reformulations for integer programming
• Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
• 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

Uses Software

• NTL
• LattE

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)