TY - JOUR

T1 - Solving MIPs via scaling-based augmentation

AU - Le Bodic, Pierre

AU - Pavelka, Jeffrey W.

AU - Pfetsch, Marc E.

AU - Pokutta, Sebastian

PY - 2018/2

Y1 - 2018/2

N2 - Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a feasible solution is iteratively augmented to a better solution or proved to be 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 identically well in the worst case for 0/1 polytopes, as well as show that in some cases, geometric scaling can outperform bit scaling arbitrarily, leading to the first strong separation between these two methods.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 required iterations is low in most cases. 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.

AB - Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a feasible solution is iteratively augmented to a better solution or proved to be 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 identically well in the worst case for 0/1 polytopes, as well as show that in some cases, geometric scaling can outperform bit scaling arbitrarily, leading to the first strong separation between these two methods.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 required iterations is low in most cases. 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.

KW - Augmentation methods

KW - Mixed-integer programs

KW - Primal methods

KW - Scaling

UR - http://www.scopus.com/inward/record.url?scp=85029880403&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2017.08.004

DO - 10.1016/j.disopt.2017.08.004

M3 - Article

AN - SCOPUS:85029880403

VL - 27

SP - 1

EP - 25

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -