graver basis – Optimization Online

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

Published: 2014/08/18, Updated: 2015/12/07

(Mixed) Integer Linear Programming, Linear Programming augmentation, circuit, edmonds-karp, elementary vector, graver basis, integer program, linear programming, steepest descent, steepest descent vector, test set

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 … Read more

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

Published: 2012/07/04

Raymond Hemmecke

Matthias Köppe

Robert Weismantel

(Mixed) Integer Nonlinear Programming augmentation algorithm, graver basis, n-fold integer programs, polynomial-time algorithm, proximity, stochastic integer programming, stochastic multi-commodity flow

We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more