Learning fine-grained search space pruning and heuristics for combinatorial optimization

被引:0
作者
Juho Lauri
Sourav Dutta
Marco Grassia
Deepak Ajwani
机构
[1] Huawei Research,
[2] University of Catania,undefined
[3] University College Dublin,undefined
来源
Journal of Heuristics | 2023年 / 29卷
关键词
Combinatorial optimization; Machine learning; Maximum clique; Heuristics;
D O I
暂无
中图分类号
学科分类号
摘要
Combinatorial optimization problems arise naturally in a wide range of applications from diverse domains. Many of these problems are NP-hard and designing efficient heuristics for them requires considerable time, effort and experimentation. On the other hand, the number of optimization problems in the industry continues to grow. In recent years, machine learning techniques have been explored to address this gap. In this paper, we propose a novel framework for leveraging machine learning techniques to scale-up exact combinatorial optimization algorithms. In contrast to the existing approaches based on deep-learning, reinforcement learning and restricted Boltzmann machines that attempt to directly learn the output of the optimization problem from its input (with limited success), our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. In addition, our framework uses only interpretable learning models based on intuitive local features and thus the learning process provides deeper insights into the optimization problem and the instance class, that can be used for designing better heuristics. For the classical maximum clique enumeration problem, we show that our framework can prune a large fraction of the input graph (around 99% of nodes in case of sparse graphs) and still detect almost all of the maximum cliques. Overall, this results in several fold speedups of state-of-the-art algorithms. Furthermore, the classification model used in our framework highlights that the chi-squared value of neighborhood degree has a statistically significant correlation with the presence of a node in a maximum clique, particularly in dense graphs which constitute a significant challenge for modern solvers. We leverage this insight to design a novel heuristic we call ALTHEA for the maximum clique detection problem, outperforming the state-of-the-art for dense graphs.
引用
收藏
页码:313 / 347
页数:34
相关论文
共 43 条
  • [21] tf-Darshan: Understanding Fine-grained I/O Performance in Machine Learning Workloads
    Chien, Steven W. D.
    Podobas, Artur
    Peng, Ivy B.
    Markidis, Stefano
    2020 IEEE INTERNATIONAL CONFERENCE ON CLUSTER COMPUTING (CLUSTER 2020), 2020, : 359 - 370
  • [22] Multipoint combinatorial optimization method with a search strategy in higher structure solution space
    Hashimoto, Masatoshi
    Tamura, Kenichi
    Yasuda, Keiichiro
    IEEJ TRANSACTIONS ON ELECTRICAL AND ELECTRONIC ENGINEERING, 2017, 12 : S133 - S134
  • [23] Combinatorial Optimization Method with Search Strategy Based on Hierarchical Interpretation of Solution Space
    Hashimoto, Masatoshi
    Tamura, Kenichi
    Tsuchiya, Junichi
    Yasuda, Keiichiro
    2017 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS (SMC), 2017, : 1862 - 1867
  • [24] Fine-Grained Static Detection of Obfuscation Transforms Using Ensemble-Learning and Semantic Reasoning
    Tofighi-Shirazi, Ramtine
    Asavoae, Irina Mariuca
    Elbaz-Vincent, Philippe
    PROCEEDINGS OF THE 9TH SOFTWARE SECURITY, PROTECTION, AND REVERSE ENGINEERING WORKSHOP 2019 (SSPREW-9), 2019,
  • [25] DL-FHMC: Deep Learning-Based Fine-Grained Hierarchical Learning Approach for Robust Malware Classification
    Abusnaina, Ahmed
    Abuhamad, Mohammed
    Alasmary, Hisham
    Anwar, Afsah
    Jang, Rhongho
    Salem, Saeed
    Nyang, Daehun
    Mohaisen, David
    IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2022, 19 (05) : 3432 - 3447
  • [26] SHAPES: A novel approach for learning search heuristics in under-constrained optimization problems
    Doan, KPV
    Wong, KP
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1997, 9 (05) : 731 - 746
  • [27] Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art
    Karimi-Mamaghan, Maryam
    Mohammadi, Mehrdad
    Meyer, Patrick
    Karimi-Mamaghan, Amir Mohammad
    Talbi, El-Ghazali
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 296 (02) : 393 - 422
  • [28] Prediction of soil degree of compaction based on machine learning: a case study of two fine-grained soils
    Ran, Yuling
    Bai, Wei
    Kong, Lingwei
    Fan, Henghui
    Yang, Xiujuan
    Li, Xuemei
    ENGINEERING COMPUTATIONS, 2024, 41 (01) : 46 - 67
  • [29] A Fine-Grained System Driven of Attacks Over Several New Representation Techniques Using Machine Learning
    Al Ghamdi, Mohammed A.
    IEEE ACCESS, 2023, 11 : 96615 - 96625
  • [30] RETRACTED: A Method of Tracking Visual Targets in Fine-Grained Image Using Machine Learning (Retracted Article)
    Ma, Xiao
    Ye, Yufei
    Chen, Leihang
    Tao, Haibo
    Liao, Cancan
    IETE JOURNAL OF RESEARCH, 2023, 69 (10)