Recent years have witnessed rapid advances in the use of neural networks to
solve combinatorial optimization problems. Nevertheless, designing the "right"
neural model that can effectively handle a given optimization problem can be
challenging, and often there is no theoretical understanding or justification
of the resulting neural model. In this paper, we focus on the rectilinear
Steiner minimum tree (RSMT) problem, which is of critical importance in IC
layout design and as a result has attracted numerous heuristic approaches in
the VLSI literature. Our contributions are two-fold. On the methodology front,
we propose NN-Steiner, which is a novel mixed neural-algorithmic framework for
computing RSMTs that leverages the celebrated PTAS algorithmic framework of
Arora to solve this problem (and other geometric optimization problems). Our
NN-Steiner replaces key algorithmic components within Arora's PTAS by suitable
neural components. In particular, NN-Steiner only needs four neural network
(NN) components that are called repeatedly within an algorithmic framework.
Crucially, each of the four NN components is only of bounded size independent
of input size, and thus easy to train. Furthermore, as the NN component is
learning a generic algorithmic step, once learned, the resulting mixed
neural-algorithmic framework generalizes to much larger instances not seen in
training. Our NN-Steiner, to our best knowledge, is the first neural
architecture of bounded size that has capacity to approximately solve RSMT (and
variants). On the empirical front, we show how NN-Steiner can be implemented
and demonstrate the effectiveness of our resulting approach, especially in
terms of generalization, by comparing with state-of-the-art methods (both
neural or non-neural based).

近年来，神经网络在解决组合优化问题方面取得了快速发展。在本文中，我们提出了 NN-Steiner，这是一种新颖的混合神经 - 算法框架，用于计算矩形斯坦纳最小生成树（RSMT），并展示了其在处理复杂示例方面的泛化性和与现有方法的比较效果。