  


On Augmentation Algorithms for Linear and IntegerLinear Programming: From EdmondsKarp to Bland and Beyond
JesÃºs De Loera (deloeramath.ucdavis.edu) Abstract: Motivated by Bland's linearprogramming generalization of the renowned EdmondsKarp efficient refinement of the FordFulkerson maximumflow algorithm, we discuss three closelyrelated natural augmentation rules for linear and integerlinear optimization. In several nice situations, we show that polynomiallymany augmentation steps suffice to reach an optimum. In particular, when using ``discrete steepestdescent augmentations'' (i.e., directions with the best ratio of cost improvement per unit 1norm 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 polynomialtime algorithm for $N$fold integerlinear 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 polynomialtime simplex or augmentation algorithm. Keywords: augmentation, Graver basis, test set, circuit, elementary vector, linear program, integer program, EdmondsKarp, steepest descent vector, linear program, integer program, EdmondsKarp, 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), 2494–2511. Download: [PDF] Entry Submitted: 08/18/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  