Instance-specific algorithm configuration via unsupervised deep graph clustering

• Main Authors: SONG, Wen, LIU, Yi, CAO, Zhiguang, WU, Yaoxin, LI, Qiqiang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Algorithm configuration; Unsupervised graph embedding; Mixed-integer programming; Artificial Intelligence and Robotics; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/8086; https://ink.library.smu.edu.sg/context/sis_research/article/9089/viewcontent/1_s2.0_S0952197623009247_pvoa_cc_by.pdf
• Institution: Singapore Management University

Instance-specific Algorithm Configuration (AC) methods are effective in automatically generating high-quality algorithm parameters for heterogeneous NP-hard problems from multiple sources. However, existing works rely on manually designed features to describe training instances, which are simple numerical attributes and cannot fully capture structural differences. Targeting at Mixed-Integer Programming (MIP) solvers, this paper proposes a novel instances-specific AC method based on end-to-end deep graph clustering. By representing an MIP instance as a bipartite graph, a random walk algorithm is designed to extract raw features with both numerical and structural information from the instance graph. Then an auto-encoder is designed to learn dense instance embeddings unsupervisedly, which facilitates clustering heterogeneous instances into homogeneous clusters for training instance-specific configurations. Experimental results on multiple benchmarks show that the proposed method can improve the solving efficiency of CPLEX on highly heterogeneous instances, and outperform existing instance specific AC methods.