论文标题
学会加速启发式搜索在线广告中的大规模最大加权B匹配问题
Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising
论文作者
论文摘要
两分B匹配在算法设计中至关重要，并且已广泛应用于经济市场，劳动力市场等。这些实际问题通常具有两个截然不同的特征：大规模和动态，这需要匹配的算法必须定期执行。但是，由于需要无法忍受的运行时间或过多的计算资源，因此现有的精确算法和近似算法通常在此类设置中失败。为了解决此问题，我们提出\ texttt {neusearcher}，该{neusearcher}利用了从以前的实例中学习的知识来解决新的问题实例。具体而言，我们设计了一个多通道图神经网络，以预测匹配边缘权重的阈值，通过该范围可以大大减少搜索区域。我们进一步提出了一种平行的启发式搜索算法，以迭代提高溶液质量，直到收敛为止。开放和工业数据集的实验表明，与最新的近似方法相比，\ texttt {neusearcher}可以加快2到3次的速度，同时实现完全相同的匹配解决方案。
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. These practical problems usually exhibit two distinct features: large-scale and dynamic, which requires the matching algorithm to be repeatedly executed at regular intervals. However, existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. To address this issue, we propose \texttt{NeuSearcher} which leverages the knowledge learned from previously instances to solve new problem instances. Specifically, we design a multichannel graph neural network to predict the threshold of the matched edges weights, by which the search region could be significantly reduced. We further propose a parallel heuristic search algorithm to iteratively improve the solution quality until convergence. Experiments on both open and industrial datasets demonstrate that \texttt{NeuSearcher} can speed up 2 to 3 times while achieving exactly the same matching solution compared with the state-of-the-art approximation approaches.
