Lattice based extended formulations for integer linear equality systems

DOI10.1007/S10107-008-0236-7MaRDI QIDQ847838zbMATH OpenOpenAlexFDO

Authors Karen Aardal, Laurence A. Wolsey

Publication date 19 February 2010

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702881, https://ir.cwi.nl/pub/11899

zbMATH Keywords

Frobenius numberInteger widthLattice basis reduction

Mathematics Subject Classification ID

Computer solution of Diophantine equations (11Y50) Linear integral equations (45A05) Integer programming (90C10)

Abstract: We study different extended formulations for the set $X=xinmathbb{Z}^{n}midAx=A{x}^0$ in order to tackle the feasibility problem for the set $X_{+}=Xcapmathbb{Z}_{+}^n$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_{+})$, but rather to reformulate in such a way that the new variables introduced provide good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. For the case that $A$ has one row $a$ we analyze the reformulations in more detail. In particular, we determine the integer width of the extended formulations in the direction of the last coordinate, and derive a lower bound on the Frobenius number of $a$. We also suggest how a decomposition of the vector $a$ can be obtained that will provide a useful extended formulation. Our theoretical results are accompanied by a small computational study.

Recommendations

• Hard Equality Constrained Integer Knapsacks
• Basis reduction and the complexity of branch-and-bound
• Extended formulations for Gomory corner polyhedra
• Lattice reformulation cuts
• scientific article; zbMATH DE number 5165610

Cites work

• A Class of Hard Small 0-1 Programs
• An introduction to the geometry of numbers.
• Coefficient reduction for inequalities in 0–1 variables
• Coefficient strengthening: a tool for reformulating mixed-integer programs
• Combining Problem Structure with Basis Reduction to Solve a Class of Hard Integer Programs
• Equivalent Integer Programs and Canonical Problems
• Equivalent knapsack‐type formulations of bounded integer linear programs: An alternative approach
• Factoring polynomials with rational coefficients
• Hard Equality Constrained Integer Knapsacks
• scientific article; zbMATH DE number 3980484 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
• Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
• Transformation of integer programs to knapsack problems

Cited in

(6)

• Thinner is not always better: cascade knapsack problems
• Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems
• Lattice reformulation cuts
• On the structure of reduced kernel lattice bases
• Counter-cyclical margins for option portfolios
• Computer classification of linear codes based on lattice point enumeration

Describes a project that uses

Uses Software

• XPRESS

This page was built for publication: Lattice based extended formulations for integer linear equality systems

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