On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond

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

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

Motivated by Bland's linear programming (LP) generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum flow algorithm, we analyze three closely related natural augmentation rules for LP and integer-linear programming (ILP) augmentation algorithms. For all three rules and in both contexts, LP and ILP, we bound the number of augmentations. Extending Bland's "discrete steepest-descent" augmentation rule (i.e., choosing directions with the best ratio of cost improvement per unit 1-norm length, and then making maximal augmentations in such directions) from LP to ILP, we (i) show that the number of discrete steepest-descent augmentations is bounded by the number of elements in the Graver basis of the problem matrix and (ii) give the first strongly polynomial-time algorithm for N-fold ILP. For LP, two of the rules can suffer from a "zig-zagging" phenomenon, and so in those cases we apply the rules more subtly to achieve good bounds. Our results improve on what is known for such augmentation algorithms for LP (e.g., extending the style of bounds found by Kitahara and Mizuno for the number of steps in the simplex method) and are closely related to research on the diameters of polytopes and the search for a strongly polynomial-time simplex or augmentation algorithm.

Original languageEnglish
Pages (from-to)2494-2511
Number of pages18
JournalSIAM Journal on Optimization
Volume25
Issue number4
DOIs
StatePublished - 2015

Keywords

  • Augmentation
  • Circuit
  • Graver basis
  • Graver complexity
  • Integer programming
  • Linear programming
  • N-fold

Fingerprint

Dive into the research topics of 'On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond'. Together they form a unique fingerprint.

Cite this