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 proceedingConference PaperResearchpeer-review

    53 Citations (Scopus)

    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
    EditorsDale Schuurmans, Michael Wellman
    Place of PublicationPalo Alto, California
    PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
    Pages724-731
    Number of pages8
    ISBN (Electronic)9781577357605
    Publication statusPublished - 2016
    EventAAAI Conference on Artificial Intelligence 2016 - Phoenix Convention Center, Phoenix, United States of America
    Duration: 12 Feb 201617 Feb 2016
    Conference number: 30th
    http://www.aaai.org/Conferences/AAAI/aaai16.php

    Conference

    ConferenceAAAI Conference on Artificial Intelligence 2016
    Abbreviated titleAAAI 2016
    CountryUnited States of America
    CityPhoenix
    Period12/02/1617/02/16
    Internet address

    Cite this