日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

解集合プログラミングを用いた配電網問題の解法に関する一考察
山田 健太郎

湊 真一

番原 睦則

配電網問題は求解困難な組合せ最適化問題の一種である．配電網問題は，トポロジ制約と電気制約を満たしつつ，電力の損失を最小にするスイッチの開閉状態を求めることが目的である．トポロジ制約のみの配電網問題は，与えられた連結グラフと根と呼ばれるノードから根付き全域森を探索する部分グラフ探索問題 (根付き全域森問題) に帰着できる．本稿では，解集合プログラミング (ASP) を用いた根付き全域森問題の解法について述べる．考案した ASP
符号化は，根付き全域森問題の連結制約を ASP の個数制約で表現することにより，基礎化後のルール数を少なく抑えるよう工夫されており，大規模な問題に対する有効性が期待できる．また，配電網における障害時の復旧予測への応用を狙いとし，根付き全域森問題の 2 つの実行可能解が，局所的な変形による遷移だけで互いに移りあえるかを問う “解の遷移問題” への拡張についても述べる．最後に，実用規模の問題を含む問題集を用いた実験結果について報
告する．

SS1

SS2

1 はじめに電力網の構成制御は，エネルギーの節約や安定した電力供給を支える重要な研究課題である．電力網は，

s1

s2

c1

高電圧で発電所と変電所を結ぶ送電網と，低電圧で変c2

c3

電所と家庭や工場といった需要家を結ぶ配電網に分類される．配電網は変電所と需要家との間で構成される

s3

s4

電力供給ネットワークであり，その構成技術はスマー
トグリッドや，災害時の障害箇所の迂回構成などを支える重要な基盤技術である．

s5

s6

s7

c4

c5

図1

c6

配電網問題の例

配電網問題は，供給経路に関するトポロジ制約と，電流・電圧に関する電気制約を満たしつつ，電力の損る．電気制約は，供給経路の各区間で許容電流を超え失を最小にするスイッチの開閉状態を求めることが目ないこと，電気抵抗による電圧降下が許容範囲を超え的である [4]．トポロジ制約は，短絡 (供給経路上のないことを保証する．本稿ではトポロジ制約のみの配ループ，複数の変電所と結ばれる需要家) と停電 (変電網問題を対象とする．

電所と結ばれない需要家) が発生しないことを保証す

トポロジ制約のみの配電網問題の例を図 1 に示す．
この例は，2 つの変電所 {SS1 , SS2 }，7 個のスイッ

A Study on Solving Power Distribution Network
Problem with Answer Set Programming.
Kentaro Yamada, Mutsunori Banbara, 名古屋大学大学院情報学研究科, Graduate School of Informatics,
Nagoya University.
Shin-ichi Minato, 京都大学大学院情報学研究科, Graduate School of Informatics, Kyoto University.

チ {s1 , . . . , s7 }，6 つの需要家 {c1 , . . . , c6 } から構成
されている．■ は閉じたスイッチ，□ は開いたスイッチを表している．配電網問題の実行可能解は閉じたス
イッチの集合で表すことができる．この例は実行可能
解 {s1 , s3 , s5 , s7 } を表している．需要家 {c1 , c2 , c4 }

根付き全域森問題 インスタンス

変換器- ASP ファクト - ASP システム - 根付き全域森問題の解ASP 符号化(論理プログラム)
図2

提案アプローチの構成図

は変電所 SS1 から，需要家 {c3 , c5 , c6 } は変電所 SS2

また，配電網における障害時の復旧予測への応用を

から電力を供給され，トポロジ制約を満たしているこ狙いとし，根付き全域森問題の 2 つの実行可能解が，とがわかる．

局所的な変形による遷移だけで互いに移りあえるか

配電網問題は求解困難な組合せ最適化問題の一種を問う “解の遷移問題” への拡張を行なった．この遷であり，これまでフロンティア法を用いた解法等が提移問題を解くには，複数の根付き全域森問題を繰り返案されている [6]．トポロジ制約のみの配電網問題は，し解く必要がある．しかし，各問題中の制約の大部分与えられた連結グラフと根と呼ばれる特殊なノードは共通であるため，ASP システムが同一の探索空間

から，根付き全域森を求める部分グラフ探索問題にを何度も調べることになり，求解効率が低下するとい帰着できることが知られている [7]．以降，この問題

う問題点がある．この問題を解決するために，マルチを根付き全域森問題と呼ぶ．

ショット ASP 解法を用いた実装を提案する．この解解集合プログラミング (Answer Set Programing;

法は，ASP システムが同様の探索失敗を避けるため

ASP [1] [3] [5] [8]) は，論理プログラミングから派生しに獲得した学習節を (部分的に) 保持することで，無たプログラミングパラダイムである．ASP 言語は，

駄な探索を行うことなく，制約を追加した論理プログ

一階論理に基づく知識表現言語の一種であり，論理プ

ラムを連続的に解くことができる．そのため，求解性

ログラムは ASP のルールの有限集合である．ASP シ

能の向上が期待できる．

ステムは論理プログラムから安定モデル意味論 [3] に提案アプローチの有効性を評価するために，DNET

基づく解集合を計算するシステムである．近年，SAT(Power Distribution Network Evaluation Tool) †1

立され，制約充足問題，プランニング，システム生物に公開されている問題集と，Graph Coloring and its
Generalizations †2 に公開されているグラフ彩色問題

学，時間割問題，システム検証など様々な分野への実を基に生成した根付き全域森問題を用いて，実行実用的応用が急速に拡大している [2]．

験を行なった．その結果，改良符号化は，基本符号化

ソルバーの技術を応用した高速な ASP システムが確

本稿では，解集合プログラミングを用いた根付き全と比較して，より多くの問題をより高速に解くこと

域森問題の解法について述べる．提案アプローチでができた．また，改良符号化は辺数 (スイッチ数) がは，まず与えられた問題インスタンスを ASP のファ

40,000 個を超える問題も解いており，大規模問題に

クト形式に変換した後，ASP ファクトと根付き全域

対する ASP の有効性が確認できた．

森問題を解くための ASP 符号化と結合した上で，高解の遷移問題については，DNET で公開されてい速 ASP システムを用いて解を求める (図 2 参照)．

る実用規模の問題 (fukui-tepco) をベースとした問題

根付き全域森問題を解く ASP 符号化 (論理プログ

集を用いて実験を行った．その結果，マルチショットラム) として，基本符号化と改良符号化の 2 種類を考ASP 解法は，通常の解法と比較して，平均で 3.3 倍案した．特に，改良符号化は，根付き全域森問題の連の高速化を実現し，マルチショット ASP 解法の優位

結制約を ASP の個数制約で表現することにより，基礎化後のルール数を少なく抑えるよう工夫されており，大規模な問題に対する有効性が期待できる．

†1 https://github.com/takemaru/dnet†2 https://mat.tepper.cmu.edu/COLOR04/

r1

r3
s1

c1

c2

s3

s4
s6

c4

図3

s2

c5

s7

r1

c3

c1

s5

s3

c6

c4

r3
s1

c2

c3
s5

c5

s7

r1

根付き全域森問題の入力例

c1

c6

r3
s1

c2

c3

性が確認できた．
本稿の構成は以下の通りである．2 節で根付き全域
森の定義を示し，3 節で解集合プログラミングの説明

s3

s4

c4

c5

s7

c6

を行う．4 節で根付き全域森問題の ASP 符号化を示
し，5 節で根付き全域森問題を遷移問題へ拡張を行う．

図4

根付き全域森の出力例 (2 つ)

6 節で評価実験とその考察を述べ，最後に，7 節で本稿をまとめる．

みとなる場合を表している．

2 根付き全域森問題

3 解集合プログラミング

根付き全域森は以下のように定義される [7]．

ASP の言語は，一般拡張選言プログラムをベース

定義. グラフ G = (V, E) と，根と呼ばれる V 上のとしている [5]．本稿では，説明の簡略化のため，そノードの集合が与えられたとする．このとき，G 上のサブクラスである標準論理プログラムについて説の根付き全域森とは，以下の制約を満たす G の部分明する．以降，標準論理プログラムを単に論理プログ

′

′

′

グラフ G = (V, E ), E ⊆ E である．
′

1. G はサイクルを持たない．(非閉路制約)
2. G′ の各連結成分は，ちょうど 1 つの根を含む．
(根付き連結制約)

ラムと呼ぶ．
論理プログラムは，以下の形式のルールの有限集合である．

a0 :- a1 , . . . ,am , not am+1 , . . . ,not an .

G を求める部分グラフ探索問題を根付き全域森問

ここで，0 ≤ m ≤ n であり，各 ai はアトム，notはデフォルトの否定 †3 ，“,” は連言を表す．“:-” の題と呼ぶ．

左側をヘッド，右側をボディと呼ぶ．“.” はルールの本稿では，与えられたグラフ G から，根付き全域森′

根付き全域森問題の入力例となるグラフを図 3 に終わりを表す終端記号である．ルールの直観的な意味示す．図 3 は，図 1 で示した配電網に対応しており，

は，「a1 , . . . , am がすべて成り立ち，am+1 , . . . , an の

需要家 {c1 , . . . , c6 } は，ノードに対応し，スイッチ

それぞれが成り立たないならば，a0 が成り立つ」で{s1 , . . . , s7 } は，辺に対応する．また，図中の色付きある．ボディが空のルール (すなわち a0 :- .) をファ

ノード {r1 , r3 } は変電所と直接繋がっている需要家をクトと呼び，“:-” を省略することができる．

意味しており，根に対応している．
根付き全域森の例を図 4 に示す．根付き全域森は，ヘッドが空のルールを一貫性制約と呼ぶ．

:- a1 , . . . ,am , not am+1 , . . . ,not an .

各連結成分が必ずちょうど 1 つの根をもつ木構造を

例えば，一貫性制約 “:- a1 ,a2 .” は，「a1 と a2 が両方同形成することで，非閉路制約と根付き連結制約を満た時に成り立つことはない」を意味し，“:- a1 , not a2 .”す．図 4 の上側は，図 1 の配電網問題の解に対応しは，「a1 が成り立つならば，a2 も成り立つ」を意味ている．また，根付き全域森問題には解が複数存在し†3 失敗による否定とも呼ばれる．述語論理で定義される
否定 (¬) とは意味が異なる．

得る．例えば，図 4 の下側は，ある連結成分が根のnode(1). node(2). node(3). node(4). node(5). node(6).

1 %% solution candidates
2 { inForest(X,Y) } :- edge(X,Y).

root(1).

root(3).

3
4 %% reachabilityedge(1,2).

edge(1,4). edge(2,5).

edge(3,6).

edge(4,5). edge(5,6).

edge(2,3).

5 reached(R,R) :- root(R).
6 reached(X,R) :- reached(Y,R), inForest(Y,X).
7 reached(X,R) :- reached(Y,R), inForest(X,Y).

コード 1

根付き全域森問題 (図 3) のファクト表現

8
9 %% acyclicity constraint
10 :- root(R),する．

ASP 言 語 に は ，組 合 せ 問 題 を 解 く た め に 便 利

11

not 1 #sum{ 1,X:reached(X,R) ;12-1,X,Y:inForest(X,Y),reached(X,R),reached(Y,R)

13

} 1.

な 拡 張 構 文 が 用 意 さ れ て い る ．そ の 代 表 的 な も

14の が選 択 子と個 数 制 約で あ る ．例 え ば ，選 択 子

15 %% rooted connectivity constraint“{a1 ; . . . ;an }.” を ファク ト と し て 書 く と ，「アト

16 :- node(X),not reached(X,_).

17 :- reached(X,R1), reached(X,R2), R1 < R2.

ム集合 {a1 , . . . , an } の任意の部分集合が成り立つ」
コード 2

を 意 味 す る ．個 数 制 約 は 選 択 子 の 両 端 に 選 択 可

根付き全域森問題の基本符号化

能 な 個 数 の 上 下 限 を 付 け た も の で あ る ．例 え ば ，“:- a0 , not lb {a1 ; . . . ;an } ub.” と 書 く と ，「a0

1 %% solution candidates

が 成 り 立 つ な ら ば ，a1 , . . . , an の う ち ，lb 個 以 上

2 { inForest(X,Y) } :- edge(X,Y).

ub 個 以 下 が 成 り 立 つ 」を 意 味 す る ．ま た ，重 み

3付き個数制約 (#sum) も用意されている．例えば，“:- a0 , not lb #sum {w1 :a1 ; . . . ;wn :an } ub.” と書くと，「a0 が成り立つならば，a1 , . . . , an のうち

4 %% reachability
5 reached(R,R) :- root(R).
6 reached(X,R) :- reached(Y,R), inForest(Y,X).
7 reached(X,R) :- reached(Y,R), inForest(X,Y).
8

真となるアトムの重み和が lb 個以上 ub 個以下であ

9 %% acyclicity constraint

る」を意味する．項 wi は重みを表す．

10 :- root(R),ASP システムは，与えられた論理プログラムから，安定モデル意味論 [3] に基づく解集合を計算するシステムである．本稿では，高性能かつ高機能な ASP
システムとして世界中で広く使われている clingo †411

not 1 #sum{ 1,X:reached(X,R) ;12-1,X,Y:inForest(X,Y),reached(X,R),reached(Y,R)

13

} 1.

14
15 %% rooted connectivity constraint
16 :- node(X), not 1 { reached(X,R) } 1.

を使用する．clingo を含め最新の高速 ASP システム
は，グラウンダーを用いて変数を含む論理プログラム

コード 3

根付き全域森問題の改良符号化

を変数を含まない論理プログラムに変換 (基礎化) したのち，ASP ソルバーを用いて解集合を計算する方のファクト表現をコード 1 に示す．この問題は，ノー式が主流となっている．

ド 6 個，根ノード 2 個，辺 7 個から構成され，それぞれ，アトム node/1，root/1，edge/2 によって表

4 根付き全域森問題の ASP 符号化されている．例えば，ファクト edge(1,2). は，ノー

本節では，根付き全域森問題の入力と制約を論理プ

ド 1 とノード 2 が隣接していることを表す．

ログラムとして表現する方法について述べる．

ASP ファクト形式. 根付き全域森問題の入力 (図 3)

基本符号化. 根付き全域森問題の ASP 符号化を
コード 2 に示す．2 行目のルールは，各辺 (X,Y) に対して，解の候補となるアトム inForest(X,Y) を導入す

†4 https://potassco.org/

る．この inForest(X,Y) は，辺 (X,Y) が根付き全域森

t = 0 (スタート状態)
r1

t=1
r3

s1

c1

c2

c3

s3

s5

c4

c5

r1

s7

r3

c1

⇒

c6

c2

s2

s3

c3
s5

c4

c5

s7

c6

⇓
r1

r3

c1

c2

s2

c3

s6

c5

c1

s7

c6

t = 3 (ゴール状態)
図5

r3
c2

s2

⇐

s4
c4

r1

c3
s5

c4

s6

c5

s7

c6

t=2

根付き全域森遷移問題 (遷移制約 d = 2) の解の一例に含まれることを意味する．各ノードの到達可能性は規模な問題に対する求解性能が低下する可能性があ

5〜7 行目のルールで表される．アトム reached(X,R)

る．この問題を解決するために考案した改良符号化

は，ノード X は根 R から到達可能であることを意味

をコード 3 に示す．基本符号化との違いは，根付き連する．5 行目のルールは，各根ノードは自分自身か結制約を ASP の個数制約で表している点である (16ら到達可能であることを表す．6〜7 行目のルールは，

行目)．グラフのノード数を n，根ノード数を r とし

ノード Y が根ノード R から到達可能であり，かつ，辺て，根付き連結制約の基礎化後のルール数を比較する(X,Y) が全域森に含まれるならば，ノード X も R からと，基本符号化が n(1 + r C2 ) 個なのに対し，改良符到達可能であることを表す．

号化は n 個と少なく抑えることができる．これによ

非閉路制約は 10〜13 行目のルールで表される．こり，大規模な問題に対する有効性が期待できる．

のルールは，各連結成分のノード数と辺数の差が 1 になること (木の性質) を，ASP の重み付き個数制約を

5 遷移問題への拡張使って表している．根付き連結制約は 16〜17 行目の配電網の構成制御における障害時の復旧予測への応ルールで表される．16 行目のルールは，各ノードは用を狙いとし，ある初期配電網構成 (スタート状態)

少なくとも 1 つの根から到達可能であることを表しから目的配電網構成 (ゴール状態) へのスイッチの切ている (at-least-one 制約)．17 行目のルールは，各替手順を求める遷移問題を考える．各ステップ t で切ノードは高々1 つの根から到達可能であることを表し

替可能なスイッチの個数を d 個以下に制限し，最短ている (at-most-one 制約)．これら 2 つの一貫性制約

ステップ長での切替手順を求めることが目的である．

により，各ノードはちょうど 1 つの根から到達可能でトポロジ制約のみを考える場合，この配電網の遷移あることが強制される．

問題は，根付き全域森問題とその 2 つの実行可能解

改良符号化. 基本符号化は，根付き全域森問題の制が与えられたとき，ある解から他のもう一つの解へ約を ASP のルール 7 個で簡潔に表現できる．しかし，根付き全域森の制約を満たしながら移る “解の遷移問

根付き連結制約を表す at-most-one 制約の基礎化後

題” に帰着できる．各ステップ t で変更可能な辺の数のルール数は，根ノード数の 2 乗に比例するため，大を d 個以下に制限し (遷移制約)，最短ステップ長で

1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

1 %% timestep

2 #program base.

2 t(0..t).

3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

3

4 %% start

4 %% start
5 :- not inForest(X,Y,0), init_Forest(X,Y).

667 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

7 %% goal
8 :- not inForest(X,Y,t), goal_Forest(X,Y).

10 %% timestep

10 %% solution candidates
11 { inForest(X,Y,T) } :- edge(X,Y), t(T).

13 %% solution candidates

13 %% reachability
14 reached(R,R,T) :- root(R), t(T).
15 reached(X,R,T) :- reached(Y,R,T), inForest(Y,X,T), t(T).
16 reached(X,R,T) :- reached(Y,R,T), inForest(X,Y,T), t(T).

14 { inForest(X,Y,t) } :- edge(X,Y), t(t).
1516 %% reachability
17 reached(R,R,t) :- root(R), t(t).

1718 %% acyclicity constraint

not 1 #sum {1,X:reached(X,R,T);

21-1,X,Y: inForest(X,Y,T),

22

reached(X,R,T),

23

reached(Y,R,T)

24

18 reached(X,R,t) :- reached(Y,R,t), inForest(Y,X,t), t(t).
19 reached(X,R,t) :- reached(Y,R,t), inForest(X,Y,t), t(t).

19 :- root(R), t(T),

} 1.

25
26 %% rooted connectivity constraint
27 :- node(X), t(T), not 1 { reached(X,R,T) } 1.

20
21 %% acyclicity constraint
22 :- root(R), t(t),23

not 1 #sum {1,X:reached(X,R,t);24-1,X,Y: inForest(X,Y,t),25

reached(X,R,t),26

reached(Y,R,t)

27

} 1.

28

28
29 %% transition constraint
30 dist(X,Y,T) :inForest(X,Y,T), not inForest(X,Y,T-1), t(T), T>0.

32 dist(X,Y,T) :33

11 t(t).
12

12

31

8 #program step(t).
9 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

920

5 :- not inForest(X,Y,0), init_Forest(X,Y).

inForest(X,Y,T-1), not inForest(X,Y,T), t(T), T>0.

34 :- t(T), not #sum{ 1,X,Y:dist(X,Y,T) } d.

29 %% rooted connectivity constraint
30 :- node(X), t(t), not 1 { reached(X,R,t) } 1.
3132 %% transition constraint
33 dist(X,Y,t) :34

inForest(X,Y,t), not inForest(X,Y,t-1), t(t), t>0.

35 dist(X,Y,t):-

コード 4

全域森遷移問題のシングルショット符号化

36

inForest(X,Y,t-1), not inForest(X,Y,t), t(t), t>0.

37 :- t(t), not #sum{ 1,X,Y:dist(X,Y,t) } d, t>0.
38の変更手順を求めることが目的となる．この遷移問題
を根付き全域森遷移問題と呼ぶことにする．
図 3 の根付き全域森問題とその 2 つの実行可能解か

39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
40 #program check(t).
41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
42 %% goal
43 :- not inForest(X,Y,t), goal_Forest(X,Y), query(t).

ら構成された根付き全域森遷移問題の解の一例を図 5に示す．各ステップ t で変更可能な辺の数を d = 2 以

コード 5

全域森遷移問題のマルチショット符号化下に制限している．この解のステップ長は 3 であり，スタート状態 (t = 0) からゴール状態 (t = 3) まで，の解が存在するかを判定し，存在する場合はその解を根付き全域森の制約を満たしながら遷移しているこ

返す論理プログラムである．根付き全域森問題の改良とがわかる．

符号化 (コード 3) からの拡張点は以下の通りである．

シングルショット符号化. 根付き全域森遷移問題のASP 符号化をコード 4 に示す．この符号化は，与えられた根付き全域森遷移問題に対して，ステップ長 t• 新しくステップを表すアトム t(T) を導入，
• 改良符号化の各アトムにステップを表す項 T を引数として追加，• スタート状態とステップ 0，ゴール状態とステッ
プ t を対応させるルールを追加，• 遷移制約を表すルールを追加．

check(t) パートには，プログラムの終了条件を記述する．ここでは，ゴール状態とステップ t の対応を記述する (43 行目)．なお，t がインクリメントされる

1 行目の t(0..t). は，t(0)., t(1).,. . . t(t). に展と，一つ前の不要になった終了条件は，query(t) の開され，各ステップの識別子を表す．定数 t はステッ

真偽を動的に操作することにより無効化される．

プ長を表す整数値であり，実行時に与えられる．
スタート状態はファクト init_Forest/2 の集合で

6 実行実験

与えらる．5 行目のルールは，スタート状態とステッ

提案アプローチの有効性を評価するために，節 4

プ 0 での根付き全域森が一致することを強制する．同と節 5 の符号化に基づくソルバーを開発し，実行実様にして，8 行目のルールは，ゴール状態とステップ験を行った．

t での根付き全域森が一致することを強制する．
遷 移 制 約 は 30〜34 行 目 の ル ー ル で 表 さ れ る ．

根 付 き 全 域 森 問 題. ベ ン チ マ ー ク と し て は ，DNET †5 で公開されている配電網問題 3 問，おdist(X,Y,T) はステップ T-1 とステップ T の間でよび，Graph Coloring and its Generalization †6 でルールは，各ステップ T において，状態が変化した辺

公開されているグラフ彩色問題を基に生成した 82
問 †7 を使用した．ベンチマーク問題 (計 85 問) の規の数が d 以下であることを保証する．

模は，ノード数 11〜1406，辺の数 16〜49629，根ノー

辺 (X,Y) に変化があったことを意味する．34 行目のマルチショット符号化. シングルショット符号化は，

ド数 1〜281 である．ASP システムには clingo-5.4.0

根付き全域森問題の改良符号化 (コード 3) の自然な

(trendy) を使用し，問題 1 問あたりの制限時間は 1

拡張になっている．この符号化を用いて遷移問題を解時間とした．実験環境は，Mac mini，3.2 GHz Intel

くには，ステップ長 t を増やしながら，複数の問題をCore i7，64GB メモリである．

繰り返し解く必要がある．しかし，各問題中の制約の基本符号化と改良符号化の比較結果を図 6 に示す．

大部分は共通であるため，ASP システムが同一の探

この図はカクタスプロットと呼ばれ，縦軸が CPU 時

索空間を何度も調べることになり，求解効率が低下す

間，横軸が解けた問題数を表す．グラフが下に寄るほるという問題点がある．

どより高速に，右に寄るほどより多くの問題を解いた

この問題を解決するために，ASP システム clingo

ことを意味する．図 6 より，改良符号化は，基本符のマルチショット ASP 解法を適用する．この解法は，号化と比較して，より多くの問題を高速に解いている

ASP システムが同様の探索失敗を避けるために獲得ことがわかる．

した学習節を (部分的に) 保持することで，無駄な探表 1 は，解けた問題数を，ベンチマーク問題に含ま索を行うことなく，制約を追加した論理プログラムをれる辺の数で分類したものである．改良符号化は，辺連続的に解くことができる．そのため，求解性能の向の数が 40,000 を超えるような問題も解けており，大上が期待できる．

規模な問題に対する有効性が確認できた.

ASP システム clingo のマルチショット ASP 解法

根付き全域森遷移問題. ベンチマークとしては，ライブラリを用いた符号化をコード 5 に示す．このDNET で公開されている実用規模の配電網問題 (fukui-

符号化は，base，step(t)，check(t) の 3 つのパー

tepco，ノード数 432，根ノード数 72) をベースにしトから構成される．まず，base パートに，ステップ

た．この問題の実行可能解から，スタート状態を 5

t=0 で満たすべき制約を記述する．ここでは，スタート状態とステップ 0 の対応を記述する (5 行目)．次に，step(t) パートには，各ステップ t において満たすべき制約を記述する．ここでは，根付き全域森の制約と遷移制約を記述する (11〜37 行目)．最後に，†5 https://github.com/takemaru/dnet†6 http://mat.tepper.cmu.edu/COLOR04/†7 グラフ彩色問題 127 問の中から，連結グラフで辺の数が 50,000 以下である 82 問を使用した．根については全ノードの 1/5 をランダムに選んで使用した．

図6
表1

基本符号化 (コード 2) と改良符号化 (コード 3) の比較

基本符号化 (コード 2) と改良符号化 (コード 3) の比較 (解けた問題数)

辺の数

問題数

基本符号化

改良符号化

1

〜

1000

30

30

30

1001

〜

4000

20

20

20

4001

〜

7000

11

9

10

7001

〜

10000

8

4

6

10001

〜

20000

9

2

5

20001

〜

30000

2

1

2

30001

〜

40000

1

0

0

40001

〜

50000

4

0

2

85

66

75

計

つ，ゴール状態を 6 つ，をランダムに選び，それらを均で 3.3 倍の高速化を実現している．これにより，根組み合わせた計 30 問の根付き全域森遷移問題を生成付き全域森遷移問題に対するマルチショット ASP 解した．ASP システムと実験環境は上と同じである．

法の優位性が確認できた．

シングルショット符号化 (コード 4) とマルチショッ
ト符号化 (コード 5) の比較結果を表 2 に示す．左か

7 おわりに

ら順に，問題名，解を求めるまでのステップ長，シン

本稿では，根付き全域森問題とその解の遷移問題

グルショット符号化とマルチショット符号化のそれぞについて，解集合プログラミング技術を用いた解法

れの CPU 時間 (秒)，マルチショット符号化を 1 としを提案した．根付き全域森問題を解く 2 種類の ASPたときのシングルショット符号化の比率を示している．

符号化を考案した．特に，改良符号化は，根付き全域

マルチショット符号化は，シングルショット符号化と森問題の連結制約を ASP の個数制約で表現すること比較して，すべての問題をより高速に解いており，平により，基礎化後のルール数を少なく抑えるよう工夫

表2

シングルショット符号化 (コード 4) とマルチショット符号化 (コード 5) の比較結果

問題名

ステップ長 t

シングルショット (秒)マルチショット (秒)比率 (シングル/マルチ)

s1 g608

50.09825.6591.952

s1 g70847.17724.981

1.889

s1 g80843.19315.8522.725

s1 g908

48.98422.9832.131

s1 g100

6

20.964

4.709

4.452

s10 g60

6

21.947

5.132

4.277

s10 g70843.84016.2902.691

s10 g806

21.156

4.887

4.329

s10 g906

21.276

5.324

3.996

s10 g100845.70417.6972.583

s20 g60

6

21.202

4.973

4.263

s20 g70

4

9.890

2.699

3.664

s20 g808

48.47316.3352.967

s20 g9010

107.938

64.441

1.675

s20 g100848.47317.8942.709

s30 g60

6

21.189

5.287

4.008

s30 g70

4

9.901

2.735

3.620

s30 g80

621.884

5.223

4.190

s30 g90

4

9.979

2.658

3.754

s30 g100850.34418.8452.671

s40 g60

8

44.63714.2543.132

s40 g70

6

21.334

4.795

4.449

s40 g80845.202

14.0993.206

s40 g906

21.710

5.119

4.241

s40 g1006

21.299

5.666

3.759

s50 g60

4

10.021

2.726

3.676

s50 g70

6

21.291

4.718

4.513

s50 g806

21.163

6.503

3.254

s50 g9010108.29965.3521.657

s50 g100

4

9.934

2.700

3.679

平均比率

3.337

されている．解の遷移問題については，マルチショッ

続的に解くことができる．DNET の問題集，および，

ト ASP 解法を利用して解く方法を提案した．この方Graph Coloring and its Generalizations の問題を元法は，ASP システムが同様の探索失敗を避けるために生成した問題集を用いた実験の結果，大規模な根付に獲得した学習節を (部分的に) 保持することで，無き全域森問題に対する改良符号化の有効性，遷移問

駄な探索を行うことなく，制約を追加した問題を連

題に対するマルチショット ASP 解法の優位性が確認できた．今後の課題としては，配電網問題の電気制約を，背景理論付き ASP (ASP Modulo Theories) を用いて実装することが挙げられる．

参 考 文 献[1] Baral, C.: Knowledge Representation, Reasoning
and Declarative Problem Solving, Cambridge University Press, 2003.
[2] Erdem, E., Gelfond, M., and Leone, N.: Applications of ASP, AI Magazine, Vol. 37, No. 3(2016),
pp. 53–68.
[3] Gelfond, M. and Lifschitz, V.: The Stable Model
Semantics for Logic Programming, Proceedings ofthe Fifth International Conference and Symposiumon Logic Programming, MIT Press, 1988, pp. 1070–
1080.

[4] 林泰弘, 川崎章司, 松木純也, 松田浩明, 酒井重和, 宮崎輝, 小林直樹: 分散型電源連系配電ネットワークの標準解析モデルの構築とネットワーク構成候補の多面的評価
手法の開発, 電気学会論文誌, Vol. 126, No. 10(2006),
pp. 1013–1022.
[5] 井上克巳, 坂間千秋: 論理プログラミングから解集合
プログラミングへ, コンピュータソフトウェア, Vol. 25,
No. 3(2008), pp. 20–32.
[6] 井上武, 高野圭司, 渡辺喬之, 川原純, 吉仲亮, 岸本章
宏, 津田宏治, 湊真一, 林泰弘: フロンティア法による電力網構成制御, オペレーションズ・リサーチ, Vol. 57,
No. 11(2012), pp. 610–615.
[7] 川原純, 湊真一: グラフ列挙索引化技法の種々の問
題への適用, オペレーションズ・リサーチ, Vol. 57,
No. 11(2012), pp. 604–609.
[8] Niemelä, I.:
Logic Programs with Stable
Model Semantics as a Constraint Programming
Paradigm, Ann. Mathematics and Artificial Intelligence, Vol. 25, No. 3–4(1999), pp. 241–273.