Solving MIPs via scaling-based augmentation

Pierre Le Bodic, Jeffrey W. Pavelka, Marc E. Pfetsch, Sebastian Pokutta

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)1-25
    Number of pages25
    JournalDiscrete Optimization
    Volume27
    DOIs
    Publication statusPublished - Feb 2018

    Keywords

    • Augmentation methods
    • Mixed-integer programs
    • Primal methods
    • Scaling

    Cite this

    Le Bodic, Pierre ; Pavelka, Jeffrey W. ; Pfetsch, Marc E. ; Pokutta, Sebastian. / Solving MIPs via scaling-based augmentation. In: Discrete Optimization. 2018 ; Vol. 27. pp. 1-25.
    @article{f9e2266e968246b8b8e5e632a1ca9b01,
    title = "Solving MIPs via scaling-based augmentation",
    abstract = "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.",
    keywords = "Augmentation methods, Mixed-integer programs, Primal methods, Scaling",
    author = "{Le Bodic}, Pierre and Pavelka, {Jeffrey W.} and Pfetsch, {Marc E.} and Sebastian Pokutta",
    year = "2018",
    month = "2",
    doi = "10.1016/j.disopt.2017.08.004",
    language = "English",
    volume = "27",
    pages = "1--25",
    journal = "Discrete Optimization",
    issn = "1572-5286",
    publisher = "Elsevier",

    }

    Solving MIPs via scaling-based augmentation. / Le Bodic, Pierre; Pavelka, Jeffrey W.; Pfetsch, Marc E.; Pokutta, Sebastian.

    In: Discrete Optimization, Vol. 27, 02.2018, p. 1-25.

    Research output: Contribution to journalArticleResearchpeer-review

    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

    VL - 27

    SP - 1

    EP - 25

    JO - Discrete Optimization

    JF - Discrete Optimization

    SN - 1572-5286

    ER -