用图神经网络判断拍卖题是否难解,再选最合适的解法。
Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
- 提取20维结构特征,用轻量MLP预测贪心算法的差距。
- 对难题(如‘鲸鱼-鱼’陷阱结构)的贪心失败率降至0%。
- 适合需要高效选择算法的研究者或系统设计者。
组合拍卖中的赢家确定问题(WDP)是NP难的,现有方法无法可靠预测哪些实例会超越快速贪心启发式算法。机器学习领域虽致力于学习替代求解器,但最新证据表明图神经网络(GNN)在标准基准上常不如调优良好的经典方法。本文提出不同目标:学习预测某实例对贪心分配是否困难,实现实例依赖的算法选择。我们设计了20维结构特征向量,训练一个轻量MLP硬度分类器,预测贪心最优性差距的平均绝对误差为0.033,皮尔逊相关系数0.937,二分类准确率94.7%(跨三个随机种子)。对被识别为困难的实例——即表现出“鲸鱼-鱼”陷阱结构、贪心算法必然失效的情况——部署异构GNN专家,六种对抗配置下优化差距接近0%(贪心为3.75–59.24%)。结合硬度分类器与GNN及贪心求解器的混合分配器,在混合分布上整体差距仅为0.51%。在CATS基准上的诚实评估表明,GNN并未超越Gurobi(0.45–0.71 vs. 0.20差距),这支持了算法选择的框架。学习‘何时’启用昂贵求解器,比学习完全替代它们更可行。
原文摘要 · Abstract (English)
The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to \emph{replace} solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict \emph{when} a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7\% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ${\approx}0\%$ optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24\% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51\% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning \emph{when} to deploy expensive solvers is more tractable than learning to replace them.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。