7. バイナリ変数を含んだ実行可能解の列挙#
7.1. 導入#
数理最適化では最適解や実行可能解を一度の求解で一つ見つける． 一方で組合せ問題など一部の離散数学では解の列挙に興味がもたれることがある． そして実務でも複数の計画を算出することが要求されることがある．
バイナリ変数 (\(0\)-\(1\) 整数変数) を含んだ最適化問題の文脈で「解の列挙」では， no-good cut 条件とよばれる制約条件を検討することになる． これを以下に述べる．
7.2. No-good cut 条件#
今，\(0\) または \(1\) の値をとる次のバイナリ変数がモデルに含まれていたとしよう．
このモデルを求解するか，もしくは既知の結果から各 \(i\) 番目の変数 \(x_i\) について，その実行可能解が \(x^*_i\) だったとする． このとき次の集合を定める．
そして \(\bar{x}_i=1-x_i\) として次の制約条件式を考え，元のモデルに追加する．
これは元の実行可能解が満たせない制約条件である． 何故ならば元の実行可能解に対して左辺第一項は \(0\) で，第二項もまた \(0\) となるからである． 条件を満たすためには，一つ以上の変数が値を反転させなければならない． この制約条件式 (3) のことを no-good cut 条件といい，次の意図を持ってモデルに追加される．
7.3. 効用#
no-good cut 条件 (3) は定義から，少なくとも一つの変数が値を変えることを強制する制約である． これを課すことで得られる解は元の実行可能解から少なくとも一つずれることになるため，無用 (no-good 1和製英語である NG は no-good のことである．) な制約である． また no-good cut 条件によって特定の解を除外できるという意味で，切除平面 (cutting plane) を入れていることにもなっている．
no-good cut 条件を追加したモデルを求解すると，別解または実行不可能の何れかの状態になる． つまり実行不可能な場合には真に無用な切除だったことになる． この cut は no-good ではあるが，他の一般の cut と比較して一つの解を切除しているという点では good である．
実行不可能となるまで，求解の度に得られる実行可能解に対して no-good cut 条件を追加して逐次的に求解すれば， 解の列挙を行うこともできる．
7.4. 例題#
PySIMPLE による no-good cut 条件 (3) の実装例を考えよう． 簡単のため，次の制約条件のみからなる問題の実行可能解の列挙とする．
ここで \(I=\{1,2,3\}\) の場合に PySIMPLE によってモデルを記述すると次のとおりである． 下記のサンプルコードでは求解後に no-good-cut 条件を実行不可能となるまで while ループ内で毎回追加している．
Tip
本項目および「PySIMPLE での制約式の追加」と関連する話題が次で言及されている． https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2305.html#3
PySIMPLE Sample Code
1def optimize(**kwds):
2 from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter
3 I = Set(value=range(1,4))
4 i = Element(set=I)
5 x = BinaryVariable(index=i)
6 p = Problem(name='No-good cut test', type=min)
7 p += Sum(x[i], i) == 1
8 p.solve(**kwds)
9 show(p, x, i)
10 return p,x,i
11
12def show(p, x, i):
13 print('\n[Print]')
14 print(p.status)
15 print(x[i].val == 1)
16
17# ---
18
19from pysimple import NuoptStatus, Sum
20p,x,i = optimize(silent=True)
21i0 = x[i].val == 0
22i1 = x[i].val == 1
23while p.status == NuoptStatus.OPTIMAL:
24 # No-good cut 条件を追加
25 # PySIMPLE での Problem クラスへの制約条件追加時には次のことに注意する．
26 #
27 # - Problem には同じ名前の制約式を追加することはできない．
28 # - 制約式に明示的に名前を付けない場合は自動で命名される．
29 #
30 # 後者において制約式名はその構造 (式の形) から命名されるため，
31 # 命名省略時には while 文中で同じ制約式と認識されてしまう．
32 # このため制約式名の重複を回避するには毎回異なった制約式名をつける必要がある．
33 # サンプルコードでは制約式の数が毎回増加することに着目して，
34 # 制約式数を利用した命名法を採用している．
35 # ref.) https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2305.html#3
36 p += Sum(x[i0]) + Sum(1-x[i1]) >= 1, 'Co' + str(len(p.constraints))
37 print(p[-1]) # 意図した制約式になっているか確認
38
39 # 求解
40 p.solve(silent=True)
41 show(p, x, i)
42 i0 = x[i].val == 0
43 i1 = x[i].val == 1
上記を実行すると次の結果を得る．
Result
1[Print]
2NuoptStatus.OPTIMAL
3(x[i].val==1)[i] in [2]
4Co1:
5x[1]-x[2]+x[3]>=0
6
7[Print]
8NuoptStatus.OPTIMAL
9(x[i].val==1)[i] in [3]
10Co2:
11x[1]+x[2]-x[3]>=0
12
13[Print]
14NuoptStatus.OPTIMAL
15(x[i].val==1)[i] in [1]
16Co3:
17-x[1]+x[2]+x[3]>=0
18
19[Print]
20NuoptStatus.INFEASIBLE
21(x[i].val==1)[i] in []
考える問題の実行可能解は各変数が \(1\) となる場合であるから， 確かに解が列挙されていることがわかる．
上記とは別に集合 \(I_0\) および \(I_1\) を明示的に作らない実装例を次に与える．
PySIMPLE Sample Code
1def optimize(**kwds):
2 from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter
3 I = Set(value=range(1,4))
4 i = Element(set=I)
5 x = BinaryVariable(index=i)
6 p = Problem(name='No-good cut test', type=min)
7 p += Sum(x[i], i) == 1
8 p.solve(**kwds)
9 show(p, x, i)
10 return p,x,i
11
12def show(p, x, i):
13 print('\n[Print]')
14 print(p.status)
15 print(x[i].val == 1)
16
17# ---
18
19from pysimple import NuoptStatus, Sum
20p,x,i = optimize(silent=True)
21while p.status == NuoptStatus.OPTIMAL:
22 # No-good cut 条件を追加
23 p += Sum((1-x[i].val)*x[i]) + Sum(x[i].val*(1-x[i])) >= 1, 'Co' + str(len(p.constraints))
24 print(p[-1]) # 意図した制約式になっているか確認
25
26 # 求解
27 p.solve(silent=True)
28 show(p, x, i)
これは no-good cut 条件 (3) を次のように整理した場合である． 但し \(x_i^*\) は各求解時の \(i\) 番目の変数 \(x_i\) の実行可能解の値を意味し， \(\bar{x}_i=1-x_i\) である．
(5) の左辺第一項は \(x_i^*=0\) のみの項しか残らず，また第二項も \(x_i^*=1\) のみの項しか残らない． よってこれは no-good cut 条件の別表現である．
用語集
参考文献
久保幹夫, 田村明久, and 松井知己. 応用数理計画ハンドブック. 朝倉書店, 2002.
引用書式