A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 11 Issue 1
Jan.  2024

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
R. Wang, Z. Zhou, K. Li, T. Zhang, L. Wang, X. Xu, and X. Liao, “Learning to branch in combinatorial optimization with graph pointer networks,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 1, pp. 157–169, Jan. 2024. doi: 10.1109/JAS.2023.124113
Citation: R. Wang, Z. Zhou, K. Li, T. Zhang, L. Wang, X. Xu, and X. Liao, “Learning to branch in combinatorial optimization with graph pointer networks,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 1, pp. 157–169, Jan. 2024. doi: 10.1109/JAS.2023.124113

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

doi: 10.1109/JAS.2023.124113
Funds:  This work was supported by the Open Project of Xiangjiang Laboratory (22XJ02003), Scientific Project of the National University of Defense Technology (NUDT) (ZK21-07, 23-ZZCX-JDZ-28), the National Science Fund for Outstanding Young Scholars (62122093), and the National Natural Science Foundation of China (72071205)
More Information
  • Traditional expert-designed branching rules in branch-and-bound (B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems. Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.

     

  • loading
  • [1]
    P. Festa, “A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems,” in Proc. 16th Int. Conf. Transparent Optical Networks, Graz, Austria, 2014, pp. 1–20.
    [2]
    A. Schrijver, “On the history of combinatorial optimization (till 1960),” Handb. Oper. Res. Manage. Sci., vol. 12, pp. 1–68, 2005.
    [3]
    K. Abe, I. Sato, and M. Sugiyama, “Solving NP-hard problems on graphs by reinforcement learning without domain knowledge,” arXiv preprint arXiv: 1905.11623, 2020
    [4]
    E. Yolcu and B. Póczos, “Learning local search heuristics for Boolean satisfiability,” in Proc. 33rd Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, pp. 7992–8003.
    [5]
    Y. Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: A methodological tour d’Horizon,” Eur. J. Oper. Res., vol. 290, no. 2, pp. 405–421, Apr. 2021. doi: 10.1016/j.ejor.2020.07.063
    [6]
    D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, “Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning,” Discrete Optim., vol. 19, pp. 79–102, Feb. 2016. doi: 10.1016/j.disopt.2016.01.005
    [7]
    A. H. Land and A. G. Doig, “An automatic method for solving discrete programming problems,” in 50 Years of Integer Programming 1958–2008, M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, Eds. Berlin, Germany: Springer, 2010, pp. 105–132.
    [8]
    N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman, “Learning combinatorial optimization on graphs: A survey with applications to networking,” IEEE Access, vol. 8, pp. 120388–120416, Jun. 2020. doi: 10.1109/ACCESS.2020.3004964
    [9]
    E. A. Silver, “An overview of heuristic solution methods,” J. Oper. Res. Soc., vol. 55, no. 9, pp. 936–956, May 2004. doi: 10.1057/palgrave.jors.2601758
    [10]
    C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Comput. Surv., vol. 35, no. 3, pp. 268–308, Sept. 2003. doi: 10.1145/937503.937505
    [11]
    H. He, H. Daume III, and J. Eisner, “Learning to search in branch and bound algorithms,” in Proc. 27th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2014, pp. 3293–3301.
    [12]
    E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina, “Learning to branch in mixed integer programming,” in Proc. 30th AAAI Conf. Artificial Intelligence, Phoenix, Arizona, 2016, pp. 724–731.
    [13]
    M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi, “Exact combinatorial optimization with graph convolutional neural networks,” in Proc. 33rd Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, p. 1396.
    [14]
    P. Gupta, M. Gasse, E. B. Khalil, M. P. Kumar, A. Lodi, and Y. Bengio, “Hybrid models for learning to branch,” in Proc. 34th Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2020, p. 1518.
    [15]
    G. Zarpellon, J. Jo, A. Lodi, and Y. Bengio, “Parameterizing branch-and-bound search trees to learn branching policies,” in Proc. AAAI Conf. Artificial Intelligence, 2021, pp. 3931–3939.
    [16]
    O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,” in Proc. 28th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2015, pp. 2692–2700.
    [17]
    I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” in Proc. 5th Int. Conf. Learning Representations, Toulon, France, 2016.
    [18]
    M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč, “Deep reinforcement learning for solving the vehicle routing problem,” arXiv preprint arXiv: 1802.04240, 2018.
    [19]
    H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” in Proc. 31st Int. Conf. Neural Information Processing Systems, Long Beach, USA, 2017, pp. 6351–6361.
    [20]
    A. Mittal, A. Dhawan, S. Manchanda, S. Medya, S. Ranu, and A. Singh, “Learning heuristics over large graphs via deep reinforcement learning,” arXiv preprint arXiv: 1903.03332, 2019.
    [21]
    A. Nowak, S. Villar, A. S. Bandeira, and J. Bruna, “A note on learning algorithms for quadratic assignment with graph neural networks,” arXiv preprint arXiv: 1706.07450, 2017.
    [22]
    C. K. Joshi, T. Laurent, and X. Bresson, “An efficient graph convolutional network technique for the travelling salesman problem,” arXiv preprint arXiv: 1906.01227, 2019.
    [23]
    Z. Li, Q. Chen, and V. Koltun, “Combinatorial optimization with graph convolutional networks and guided tree search,” in Proc. 32nd Int. Conf. Neural Information Processing Systems, Montréal, Canada, 2018, pp. 537–546.
    [24]
    M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau, “Learning heuristics for the TSP by policy gradient,” in Proc. 15th Int. Conf. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Delft, The Netherlands, 2018, pp. 170–181.
    [25]
    W. Kool, H. Van Hoof, and M. Welling, “Attention, learn to solve routing problems,” in Proc. 7th Int. Conf. Learning Representations, New Orleans, USA, 2019.
    [26]
    A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in Proc. 31st Int. Conf. Neural Information Processing Systems, Long Beach, USA, 2017, pp. 5998–6008.
    [27]
    K. Li, T. Zhang, and R. Wang, “Deep reinforcement learning for multiobjective optimization,” IEEE Trans. Cyber., vol. 51, no. 6, pp. 3103–3114, Jun. 2021. doi: 10.1109/TCYB.2020.2977661
    [28]
    A. M. Alvarez, Q. Louveaux, and L. Wehenkel, “A machine learning-based approximation of strong branching,” INFORMS J. Comput., vol. 29, no. 1, pp. 185–195, Jan. 2017. doi: 10.1287/ijoc.2016.0723
    [29]
    C. Hansknecht, I. Joormann, and S. Stiller, “Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem,” arXiv preprint arXiv: 1805.01415, 2018.
    [30]
    V. Nair, S. Bartunov, F. Gimeno, I. Von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraatmadja, P. Wang, R. Addanki, T. Hapuarachchi, T. Keck, J. Keeling, P. Kohli, I. Ktena, Y. J. Li, O. Vinyals, and Y. Zwols, “Solving mixed integer programs using neural networks,” arXiv preprint arXiv: 2012.13349, 2020.
    [31]
    E. Mitchell, “Branch-and-cut algorithms for combinatorial optimization problems,” Handbook of Applied Optimization, vol. 1, no. 1, pp. 65–77, 2002.
    [32]
    A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” ACM Comput. Surv., vol. 50, no. 2, p. 21, Mar. 2018.
    [33]
    P. Geurts, D. Ernst, and L. Wehenkel, “Extremely randomized trees,” Mach. Learn., vol. 63, no. 1, pp. 3–42, Mar. 2006. doi: 10.1007/s10994-006-6226-1
    [34]
    T. Joachims, “Optimizing search engines using clickthrough data,” in Proc. 8th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Edmonton, Canada, 2002, pp. 133–142.
    [35]
    C. J. C. Burges, “From RankNet to LambdaRank to LambdaMART: An overview,” Microsoft Corp., Seattle, USA, Microsoft Research Technical Report MSR-TR-2010-82, 2010.
    [36]
    E. Balas and A. Ho, “Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study,” Combinatorial Optimization I, M. W. Padberg, Ed. Berlin, Germany: Springer, 1980, pp. 37–60.
    [37]
    G. Cornuejols, R. Sridharan, and J. M. Thizy, “A comparison of heuristics and relaxations for the capacitated plant location problem,” Eur. J. Oper. Res., vol. 50, no. 3, pp. 280–297, Feb. 1991. doi: 10.1016/0377-2217(91)90261-S
    [38]
    D. Bergman, A. A. Cire, W.-J. Van Hoeve, and J. Hooker, Decision Diagrams for Optimization. Cham, Germany: Springer, 2016.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(5)  / Tables(9)

    Article Metrics

    Article views (263) PDF downloads(37) Cited by()

    Highlights

    • Traditional B&B methods, which depend on manually-designed branching heuristics, often struggle with adaptability and efficiency across diverse problem scenarios. In contrast, we propose using neural networks to automatically learn these branching heuristics
    • In addition the typical graph features that are commonly explored, global and historical features are designed in this work, providing a more comprehensive and richer representation of the problem state
    • We introduce an innovative model that combines the graph neural network with a pointer mechanism. The graph neural network processes the graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch
    • Our research presents a top-k Kullback-Leibler divergence loss function, specifically designed to train the model to imitate the strong branch heuristic effectively
    • Notably, the proposed method consistently surpasses both expert-crafted branching rules and contemporary machine learning techniques across all tested problems. Once trained, the model demonstrates remarkable generalization abilities, effortlessly adapting to even unseen, larger instances

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return