用图神经网络加速实例化算法配置，让调参时间从十几秒降到秒级。
Fast instance-specific algorithm configuration with graph neural network
- 用图神经网络替代传统特征提取与聚类，快速确定实例所属类别
- 执行阶段调参时间从十几秒降至亚秒级，总耗时大幅降低
- 适合需要快速响应的工业优化场景，如实时调度与资源分配
组合优化问题在众多工业应用中至关重要，求解速度直接影响效率。提升求解器在不同输入实例上的表现需对每个实例进行参数微调，但该过程耗时且随实例数量增加而加剧。为此提出实例化算法配置（ISAC）方法，包含训练与执行两步：训练阶段从多个实例中提取特征并聚类，为每类实例生成一组通用参数；执行阶段对未知实例提取特征以确定其类别，并应用对应预调参。通常以求解时间（TTS）衡量求解器性能，但ISAC需额外预处理时间。总执行时间 $T_{tot} = TTS + T_{tune}$，其中 $T_{tune}$ 为调参时间。原方法中特征提取（含求解日志统计信息）需数10秒。本文提出使用图神经网络简化特征提取与类别判定，实验表明 $T_{tune}$ 可从数10秒降至亚秒级。
原文摘要 · Abstract (English)
Combinatorial optimization (CO) problems are pivotal across various industrial applications, where the speed of solving these problems is crucial. Improving the performance of CO solvers across diverse input instances requires fine-tuning solver parameters for each instance. However, this tuning process is time-consuming, and the time required increases with the number of instances. To address this, a method called instance-specific algorithm configuration (ISAC) has been devised. This approach involves two main steps: training and execution. During the training step, features are extracted from various instances and then grouped into clusters. For each cluster, parameters are fine-tuned. This cluster-specific tuning process results in a set of generalized parameters for instances belonging to each class. In the execution step, features are extracted from an unknown instance to determine its cluster, and the corresponding pre-tuned parameters are applied. Generally, the running time of a solver is evaluated by the time to solution ($TTS$). However, methods like ISAC require preprocessing. Therefore, the total execution time is $T_{tot}=TTS+T_{tune}$, where $T_{tune}$ represents the tuning time. While the goal is to minimize $T_{tot}$, it is important to note that extracting features in the ISAC method requires a certain amount of computational time. The extracting features include summary statistics of the solver execution logs, which takes several 10 seconds. This research presents a method to significantly reduce the time of the ISAC execution step by streamlining feature extraction and class determination with a graph neural network. Experimental results show that $T_{tune}$ in the execution step, which take several 10 seconds in the original ISAC manner, could be reduced to sub-seconds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。