On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond

DOI10.1137/151002915zbMath1330.90053arXiv1408.3518OpenAlexW1528072933MaRDI QIDQ3457191

Jesús A. De Loera, Raymond Hemmecke, Jon Lee

Publication date: 11 December 2015

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

linear programminginteger programmingaugmentationcircuitGraver basisgraver complexity\(N\)-fold

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05)

Related Items

Quadratic diameter bounds for dual network flow polyhedra, On circuit diameter bounds via circuit imbalances, Solving MIPs via scaling-based augmentation, A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs, Heat-bath random walks with Markov bases, An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, Inapproximability of shortest paths on perfect matching polytopes, A scaling algorithm for optimizing arbitrary functions over vertices of polytopes, Constructing Clustering Transformations, On the Circuit Diameter of Some Combinatorial Polytopes, On the circuit diameter conjecture, A note on the approximability of deepest-descent circuit steps, A polyhedral model for enumeration and optimization over the set of circuits, A Generalized Simplex Method for Integer Problems Given by Verification Oracles, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix, Lower bounds on the graver complexity of \(M\)-fold matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial oracle-time algorithm for convex integer minimization
• The Graver complexity of integer programming
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Nonlinear discrete optimization. An algorithmic theory
• An application of simultaneous diophantine approximation in combinatorial optimization
• Subspaces with well-scaled frames
• Decomposition of regular matroids
• On the computational behavior of a polynomial-time network flow algorithm
• The generalized simplex method
• Test sets for integer programs
• A polynomial time primal network simplex algorithm for minimum cost flows
• Higher Lawrence configurations.
• On the positive sums property and the computation of Graver test sets
• Edges versus circuits: a hierarchy of diameters in polyhedra
• \(n\)-fold integer programming in cubic time
• A bound for the number of different basic solutions generated by the simplex method
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• On Greedy and Submodular Matrices
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• On the Circuit Diameter of Dual Transportation Polyhedra
• Combinatorics and Geometry of Transportation Polytopes: An Update
• Packing and covering with integral feasible flows in integral supply-demand networks
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the foundations of linear and integer linear programming I
• A counterexample to an integer analogue of Carathéodory's theorem
• The Complexity of Generic Primal Algorithms for Solving General Integer Programs
• On sub-determinants and the diameter of polyhedra