An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming

DOI10.1287/ijoc.5.2.206zbMath0778.90042OpenAlexW2133857440MaRDI QIDQ4202587

David F. Shallcross, Thomas F. Rutherford, Herbert E. Scarf, William Cook

Publication date: 3 January 1994

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://cowles.yale.edu/sites/default/files/files/pub/d09/d0990.pdf

zbMATH Keywords

polynomial-time algorithmgeneralized basis reduction method

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Column basis reduction and decomposable knapsack problems, Improved branching disjunctions for branch-and-bound: an analytic center approach, Effective lattice point counting in rational convex polytopes, Parametric formulation of the general integer linear programming problem, A study of lattice reformulations for integer programming, Could we use a million cores to solve an integer program?, A generalization of the integer linear infeasibility problem, Thinner is not always better: cascade knapsack problems, Lattice Reformulation Cuts, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, Non-standard approaches to integer programming, A framework for constructing general integer problems with well-determined duality gaps, On the Structure of Reduced Kernel Lattice Bases

Uses Software

• CPLEX