Publication Type

Journal Article

Version

publishedVersion

Publication Date

10-2023

Abstract

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.

Keywords

Algorithm configuration, Unsupervised graph embedding, Mixed-integer programming

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

Engineering Applications of Artificial Intelligence

Volume

125

First Page

1

Last Page

13

ISSN

0952-1976

Identifier

10.1016/j.engappai.2023.106740

Publisher

Elsevier

Copyright Owner and License

Authors-CC-BY

Creative Commons License

Creative Commons Attribution 3.0 License
This work is licensed under a Creative Commons Attribution 3.0 License.

Additional URL

https://doi.org/10.1016/j.engappai.2023.106740

Download

Share

COinS