Instance-specific algorithm configuration via unsupervised deep graph clustering
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 num...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2023
|
| Subjects: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|