The Complexity of Generic Primal Algorithms for Solving General Integer Programs

DOI10.1287/moor.27.4.681.305zbMath1082.90072OpenAlexW2137614705MaRDI QIDQ5704103

Andreas S. Schulz, Robert Weismantel

Publication date: 11 November 2005

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

Full work available at URL: https://doi.org/10.1287/moor.27.4.681.305

zbMATH Keywords

computational complexityinteger programmingcombinatorial optimizationprimal algorithmsaugmentation problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ Solving MIPs via scaling-based augmentation ⋮ On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming ⋮ \(N\)-fold integer programming ⋮ Influence of the normalization constraint on the integral simplex using decomposition ⋮ Unnamed Item ⋮ A Generalized Simplex Method for Integer Problems Given by Verification Oracles ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization