  Augmentation methods for mixed-integer (linear) programs are a class of
primal solution approaches in which a current iterate is augmented to a better
solution or proved optimal. It is well known that the performance of these
methods, i.e., number of iterations needed, can theoretically be improved by
scaling methods. We extend these results by an improved and extended
convergence analysis, which shows that bit scaling and geometric scaling
theoretically perform similarly well in the worst case for 0/1 polytopes as
well as show that in some cases geometric scaling can outperform bit scaling
arbitrarily. We also investigate the performance of implementations of these
methods, where the augmentation directions are computed by a MIP solver. It
turns out that the number of iterations is usually low. While scaling methods
usually do not improve the performance for easier problems, in the case of hard
mixed-integer optimization problems they allow to compute solutions of very
good quality and are often superior.

Optimization and Control