Reducing Combinatorial Explosions in Solving Search-Type 
Combinatorial Problems with Binary Decision Diagram

Hiroshi G. Okuno (NTT Basic Research Laboratories)


We consider finding the complete solutions of combinatorial
problems simultaneously by BDDs (Binary Decision Diagrams)
with the aim of developing a methodology to avoid
combinatorial explosions in building the BDDs.  Since the
order of variables affects the number of nodes in the BDD,
the known problem is to find an optimal variable order that
minimizes the number of nodes.  However, the constraint
order and its associated variable order are important in
reducing combinatorial explosions, which has not been
explicitly pointed out so far.  We propose an algorithm
called Correlation-based Constraint and Variable Ordering
({\bf CCVO}), which computes a constraint and variable order
that reduces the number of maximum nodes.  We also propose
the on-line divide-and-conquer method and some heuristics
for decomposing the problem into a set of subproblems.

With 128 Mbytes of memory, the 12-Queen problem is solved by
the optimal constraint and variable order obtained by CCVO. 
The on-line divide-and-conquer is also used to solve the
13-Queen problem and the 4-order Magic Square.  The on-line
divide-and-conquer is much faster than the off-line version
due to the compact representation of BDD.  Since these
results with BDDs have not been reported before, the
proposed methodology makes it possible to solve larger
problems with the same computing resources.


二分決定グラフによる探索型組合せ問題の解法での組合せ爆発抑制法

奥乃 博 (NTT 基礎研究所)


二分決定グラフ (BDD) で組合せ問題の全解を同時に求めることを
検討する. この問題での課題は, 計算途中で生じる組合せ爆発を避
け, 同じ計算機資源のもとでできるだけ大きな問題が解ける手法を
開発することである.  従来から知られていたBDDの問題点は, 最終
ノード数を最小にする最適変数順序を求めることである. 本稿では, 
組合せ問題にBDDを適用する場合には最大ノード数が重要であるこ
と, および, それが変数順序だけでなく制約組合せ順序の影響を受
けることを指摘する. 次に, 最大ノード数を最小にする制約順序と
変数順序の最適解を見つけるアルゴリズムCCVO を提案する. さら
に, 最大ノード数が大き過ぎて計算ができない場合には, オンライ
ン版分割統治法を使用する解法を提案し, その分割ヒューリスティッ
クを提案する.

これらの手法により, 12-Queens を128MByte主記憶で解くことがで
き, また, 分割統治法により13-Queens と4次の魔法陣を解くこと
ができた. 二分決定グラフでは途中結果がすべて保存されているの
で, オンライン型分割統治法による解法は, オフライン型分割統治
法よりも高速である.