@techreport{oai:ipsj.ixsq.nii.ac.jp:00228917,
 author = {長倉, 光輝 and 藤吉, 邦洋 and Koki, Nagakura and Kunihiro, Fujiyoshi},
 issue = {50},
 month = {Nov},
 note = {集合対間配線問題とは，同数のソース端子とシンク端子が与えられ，これらの端子間を任意の組合せで 1 対 1 接続する単層配線問題である．集合対間配線では端子間の配線長やその差を小さくすることが求められる．この配線はプリント基板上のバス配線やエスケープ配線の部分問題として現れる．この問題の最適解を求める手法として，整数線形計画問題（ILP）ソルバを用いた手法と充足可能性問題（SAT）ソルバを用いた手法が提案されている．しかし，従来の SAT ソルバを用いた手法では，配線長の制御のために用いる制約が膨大で，配線領域が大きい場合にはメモリ不足で解けなかった．そこで，本研究では配線領域が大きい問題でも解けるように，従来の SAT ソルバを用いた集合対間配線の改良手法を提案する．, A set-pair routing problem is a single-layer routing problem in which combinations of these pins to be connected by routing is flexible. The problem requires routing in which minimum the longest routing length and the length difference. The set-pair routing appears partially in a printed circuit board (PCB). In addition, several methods have been proposed to find a suboptimal routing solution by using flow graph. Furthermore, two methods have been proposed for finding the optimal routing solution to this problem, one using the integer linear programming (ILP) solver and the other using the satisfiability problem (SAT) solver. However, the conventional method using the SAT solver has a huge number of constraints used to control the routing length, and when the routing area is large, it cannot be solved due to insufficient memory. Therefore, this paper presents an improved routing method for a set-pair routing problem using the SAT solver to solve problems with large routing areas.},
 title = {集合対間配線問題に対するSATを用いた配線手法の改良},
 year = {2023}
}