Learning to branch in mixed integer programming

Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, Bistra Dilkina

    Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

    Abstract

    The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP. Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-valuate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.
    Original languageEnglish
    Title of host publicationProceedings of the Thirtieth AAAI Conference on Artificial Intelligence
    Place of PublicationPalo Alto, California
    PublisherAAAI Press
    Pages724-731
    Number of pages8
    Publication statusPublished - 2016
    EventAAAI Conference on Artificial Intelligence 2016 - Phoenix Convention Center, Phoenix, United States
    Duration: 12 Feb 2016 → 17 Feb 2016
    Conference number: 30th
    http://www.aaai.org/Conferences/AAAI/aaai16.php

    Conference

    ConferenceAAAI Conference on Artificial Intelligence 2016
    Abbreviated titleAAAI 16
    CountryUnited States
    CityPhoenix
    Period12/02/16 → 17/02/16
    Internet address

    Cite this

    Khalil, E. B., Le Bodic, P., Song, L., Nemhauser, G., & Dilkina, B. (2016). Learning to branch in mixed integer programming. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (pp. 724-731). Palo Alto, California : AAAI Press.
    Khalil, Elias B. ; Le Bodic, Pierre ; Song, Le ; Nemhauser, George ; Dilkina, Bistra. / Learning to branch in mixed integer programming. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto, California : AAAI Press, 2016. pp. 724-731
    @inproceedings{794a0a524b414ab59e852cd6a5d5353c,
    title = "Learning to branch in mixed integer programming",
    abstract = "The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP. Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-valuate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.",
    author = "Khalil, {Elias B.} and {Le Bodic}, Pierre and Le Song and George Nemhauser and Bistra Dilkina",
    year = "2016",
    language = "English",
    pages = "724--731",
    booktitle = "Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence",
    publisher = "AAAI Press",

    }

    Khalil, EB, Le Bodic, P, Song, L, Nemhauser, G & Dilkina, B 2016, Learning to branch in mixed integer programming. in Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press, Palo Alto, California , pp. 724-731, AAAI Conference on Artificial Intelligence 2016, Phoenix, United States, 12/02/16.

    Learning to branch in mixed integer programming. / Khalil, Elias B.; Le Bodic, Pierre; Song, Le; Nemhauser, George; Dilkina, Bistra.

    Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto, California : AAAI Press, 2016. p. 724-731.

    Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

    TY - GEN

    T1 - Learning to branch in mixed integer programming

    AU - Khalil, Elias B.

    AU - Le Bodic, Pierre

    AU - Song, Le

    AU - Nemhauser, George

    AU - Dilkina, Bistra

    PY - 2016

    Y1 - 2016

    N2 - The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP. Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-valuate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.

    AB - The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP. Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-valuate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.

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

    M3 - Conference Paper

    SP - 724

    EP - 731

    BT - Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence

    PB - AAAI Press

    CY - Palo Alto, California

    ER -

    Khalil EB, Le Bodic P, Song L, Nemhauser G, Dilkina B. Learning to branch in mixed integer programming. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Palo Alto, California : AAAI Press. 2016. p. 724-731

    Access to Document