An abstract model for branching and its application to mixed integer programming

Pierre Le Bodic, George Nemhauser

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a (Formula presented.) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.

    Original languageEnglish
    Pages (from-to)369-405
    Number of pages37
    JournalMathematical Programming
    Volume166
    Issue number1-2
    DOIs
    Publication statusPublished - Nov 2017

    Keywords

    • Abstract model
    • Algorithm analysis
    • Branch and bound
    • Computational complexity
    • Mixed integer programming

    Cite this

    @article{f8aece98da784993aac96b60edbb3190,
    title = "An abstract model for branching and its application to mixed integer programming",
    abstract = "The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a (Formula presented.) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.",
    keywords = "Abstract model, Algorithm analysis, Branch and bound, Computational complexity, Mixed integer programming",
    author = "{Le Bodic}, Pierre and George Nemhauser",
    year = "2017",
    month = "11",
    doi = "10.1007/s10107-016-1101-8",
    language = "English",
    volume = "166",
    pages = "369--405",
    journal = "Mathematical Programming",
    issn = "0025-5610",
    publisher = "Springer",
    number = "1-2",

    }

    An abstract model for branching and its application to mixed integer programming. / Le Bodic, Pierre; Nemhauser, George.

    In: Mathematical Programming, Vol. 166, No. 1-2, 11.2017, p. 369-405.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - An abstract model for branching and its application to mixed integer programming

    AU - Le Bodic, Pierre

    AU - Nemhauser, George

    PY - 2017/11

    Y1 - 2017/11

    N2 - The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a (Formula presented.) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.

    AB - The selection of branching variables is a key component of branch-and-bound algorithms for solving mixed-integer programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 “tree” instances where we achieve a (Formula presented.) geometric average time and node improvement over the default rule of SCIP, a state-of-the-art MIP solver.

    KW - Abstract model

    KW - Algorithm analysis

    KW - Branch and bound

    KW - Computational complexity

    KW - Mixed integer programming

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

    U2 - 10.1007/s10107-016-1101-8

    DO - 10.1007/s10107-016-1101-8

    M3 - Article

    VL - 166

    SP - 369

    EP - 405

    JO - Mathematical Programming

    JF - Mathematical Programming

    SN - 0025-5610

    IS - 1-2

    ER -