Optimization Online


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

Jesús De Loera (deloera***at***math.ucdavis.edu)
Raymond Hemmecke (hemmecke***at***tum.de)
Jon Lee (jonxlee***at***umich.edu)

Abstract: Motivated by Bland's linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using ``discrete steepest-descent augmentations'' (i.e., directions with the best ratio of cost improvement per unit 1-norm length), we show that the number of augmentation steps is bounded by the number of elements in the Graver basis of the problem matrix, giving the first ever strongly polynomial-time algorithm for $N$-fold integer-linear optimization. Our results also improve on what is known for such algorithms in the context of linear optimization (e.g., generalizing the bounds of 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.

Keywords: augmentation, Graver basis, test set, circuit, elementary vector, linear program, integer program, Edmonds-Karp, steepest descent vector, linear program, integer program, Edmonds-Karp, steepest descent

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: SIAM J. Optim., 25(4), 24942511.

Download: [PDF]

Entry Submitted: 08/18/2014
Entry Accepted: 08/18/2014
Entry Last Modified: 12/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society