7. バイナリ変数を含んだ実行可能解の列挙 #

7.1. 導入 #

数理最適化では最適解や実行可能解を一度の求解で一つ見つける．一方で組合せ問題など一部の離散数学では解の列挙に興味がもたれることがある．そして実務でも複数の計画を算出することが要求されることがある．

バイナリ変数 (\(0\)-\(1\) 整数変数) を含んだ最適化問題の文脈で「解の列挙」では， no-good cut 条件とよばれる制約条件を検討することになる．これを以下に述べる．

7.2. No-good cut 条件 #

今，\(0\) または \(1\) の値をとる次のバイナリ変数がモデルに含まれていたとしよう．

(1)#\[\{x_i \in \mathbb{B} \}_{i\in I}\]

このモデルを求解するか，もしくは既知の結果から各 \(i\) 番目の変数 \(x_i\) について，その実行可能解が \(x^*_i\) だったとする．このとき次の集合を定める．

(2)#\[\begin{split}I_0 &= \{i\in I\mid x^*_i = 0 \}, \\ I_1 &= \{i\in I\mid x^*_i = 1 \}\end{split}\]

そして \(\bar{x}_i=1-x_i\) として次の制約式を考え，元のモデルに追加する．

(3)#\[\sum_{i\in I_0} x_i + \sum_{i\in I_1} \bar{x}_i \geq 1\]

これは元の実行可能解が満たせない制約条件である．何故ならば元の実行可能解に対して左辺第一項は \(0\) で，第二項もまた \(0\) となるからである．条件を満たすためには，一つ以上の変数が値を反転させなければならない．この制約式 (3) のことを no-good cut 条件といい，次の効用の意図を持ってモデルに追加される．

no-good cut 条件 (3) は定義から，少なくとも一つの変数が値を変えることを強制する制約である．これを課すことで得られる解は元の実行可能解から少なくとも一つずれることになるため，無用 (no-good ¹ ¹和製英語である NG は no-good のことである．) な制約である．また no-good cut 条件によって特定の解を除外できるという意味で，切除平面 (cutting plane) を入れていることにもなっている．

no-good cut 条件を追加したモデルを求解すると，別解または実行不可能の何れかの状態になる．つまり実行不可能な場合には真に無用な切除だったことになる．この cut は no-good ではあるが，他の一般の cut と比較して一つの解を切除しているという点では good である．

実行不可能となるまで，求解の度に得られる実行可能解に対して no-good cut 条件を追加して逐次的に求解すれば，解の列挙を行うこともできる．

7.3. 整数変数の場合 #

変数 \(x\) が整数変数の場合についても， no-good cut 条件を同様に「ある特定の実行可能解と一致しないこと」を強制する制約として定式化できる．しかしバイナリ変数の場合と異なり，各変数が多値をとるため，単純な線形不等式一つでその点のみを排除することはできない．このため，補助変数を導入した拡張定式化を用いることが一般的である．

代表的な定式化として，[1] から，次の二つの考え方を紹介しよう．

\(L1\) 距離による定式化
論理的な OR 条件による定式化

但し，何れも整数変数 \(x_i\) は上限 \(U_i\) と下限 \(L_i\) が与えられているものとする．

(4)#\[L_i \leq x_i \leq U_i, \quad \forall i\in I\]

7.3.1. \(L1\) 距離による定式化 #

まず，元の実行可能解 \(x^*\) との距離に着目し，少なくとも一つの変数が異なることを，次の \(L1\) 距離で表す方法が考えられる．

(5)#\[\sum_{i\in I} |x_i - x_i^*| \geq 1\]

これは「すべての成分が一致する場合のみ左辺が \(0\) となる」ことを利用したものであり，それを許さない制約式として機能する．但し，絶対値は線形ではないため，各 \(i\) について非負整数変数 \(z_i\in\mathbb{Z}_{\geq0}\) とバイナリ変数 \(\delta_i\in\mathbb{B}\) を導入し，次の線形化を施す必要がある．

(6)#\[\begin{split}\sum_{i\in I} z_i &= 1, \\ z_i &\leq x_i - x_i^* + M_i\delta_i, \quad \forall i\in I, \\ -z_i &\geq x_i - x_i^* - M_i(1-\delta_i), \quad \forall i\in I\end{split}\]

ここで，整数変数 \(x_i\) の上下限から，次の Big M を仮定した．

(7)#\[M_i = U_i - L_i, \quad i\in I\]

上記の定式化では，\(\delta_i=0\) の場合は \(z_i\leq x_i-x_i^*\) であり，\(\delta_i=1\) の場合は \(-z_i\geq x_i-x_i^*\) を意味している．つまり，\(\delta_i\) は \(0\) と \(1\) で，差 \(x_i-x_i^*\) がそれぞれ正と負の違いを判別しているインジケータ変数である．

なお，特に最適解が上限または下限に張り付いている場合には，違いを生む値としてはそれぞれ差 \(x_i-x_i^*\) が負と正に限られるため，インジケータ変数を用いる必要がない．つまり，\(x_i^* = U_i\) の場合は \(z_i = -(x_i-x_i^*)\)， \(x_i^* = L_i\) の場合は \(z_i = x_i-x_i^*\) へと，インジケータ変数を用いて書かれた二種の不等式をその \(i\) について置き換えればよい．

以上のように，この定式化は「一致からのずれ」を量的に測る形になっている点に特徴がある．

7.3.2. 論理的な OR 条件による定式化 #

別の見方として，「少なくとも一つの成分で値が異なる」という次の論理条件を直接表現する方法がある．

(8)#\[\bigvee_{i\in I} (x_i \neq x_i^*)\]

これを線形制約で表現するために，各 \(i\) について次の意味を持ったバイナリ変数 \(y_i, z_i\in\mathbb{B}\) を導入しよう．

\(y_i = 1\) かつ \(z_i = 1\) は常に成立しない
\(y_i = 1\) ならば \(x_i < x_i^*\)
\(z_i = 1\) ならば \(x_i > x_i^*\)

(8) とこれらの意味に従うよう，順に次の線形な制約を課す．

(9)#\[\begin{split}\sum_{i\in I} (y_i + z_i) &\geq 1, \\ y_i + z_i &\leq 1, \quad \forall i\in I, \\ x_i &\leq (x_i^* - 1) y_i + U_i(1-y_i), \quad \forall i\in I, \\ x_i &\geq (x_i^* + 1) z_i + L_i(1-z_i), \quad \forall i\in I\end{split}\]

これにより，「少なくとも一つの成分で不一致」を強制することができる．以上のように，この定式化は論理条件を元に定式化を図っている点に特徴がある．

7.4. 例題 #

PySIMPLE による no-good cut 条件 (3) の実装例を考えよう．簡単のため，次の制約条件のみからなる問題の実行可能解の列挙とする．

(10)#\[\sum_{i\in I} x_i = 1\]

ここで \(I=\{1,2,3\}\) の場合に PySIMPLE によってモデルを記述すると次のとおりである．下記のサンプルコードでは求解後に no-good-cut 条件を実行不可能となるまで while ループ内で毎回追加している．

Tip

本項目および「PySIMPLE での制約式の追加」と関連する話題が [2] で言及されている． https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2305.html#3

PySIMPLE Sample Code

def optimize(**kwds):
    from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter
    I = Set(value=range(1,4))
    i = Element(set=I)
    x = BinaryVariable(index=i)
    p = Problem(name='No-good cut test', type=min)
    p += Sum(x[i], i) == 1
    p.solve(**kwds)
    show(p, x, i)
    return p,x,i

def show(p, x, i):
    print('\n[Print]')
    print(p.status)
    print(x[i].val == 1)

# ---

from pysimple import NuoptStatus, Sum
p,x,i = optimize(silent=True)
i0 = x[i].val == 0
i1 = x[i].val == 1
while p.status == NuoptStatus.OPTIMAL:
    # No-good cut 条件を追加
    # PySIMPLE での Problem クラスへの制約条件追加時には次のことに注意する．
    # 
    # - Problem には同じ名前の制約式を追加することはできない．
    # - 制約式に明示的に名前を付けない場合は自動で命名される．
    # 
    # 後者において制約式名はその構造 (式の形) から命名されるため，
    # 命名省略時には while 文中で同じ制約式と認識されてしまう．
    # このため制約式名の重複を回避するには毎回異なった制約式名をつける必要がある．
    # サンプルコードでは制約式の数が毎回増加することに着目して，
    # 制約式数を利用した命名法を採用している．
    # ref.) https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2305.html#3
    p += Sum(x[i0]) + Sum(1-x[i1]) >= 1, 'Co' + str(len(p.constraints))
    print(p[-1]) # 意図した制約式になっているか確認

    # 求解
    p.solve(silent=True)
    show(p, x, i)
    i0 = x[i].val == 0
    i1 = x[i].val == 1

上記を実行すると次の結果を得る．

Result

[Print]
NuoptStatus.OPTIMAL
(x[i].val==1)[i] in [2]
Co1:
x[1]-x[2]+x[3]>=0

[Print]
NuoptStatus.OPTIMAL
(x[i].val==1)[i] in [3]
Co2:
x[1]+x[2]-x[3]>=0

[Print]
NuoptStatus.OPTIMAL
(x[i].val==1)[i] in [1]
Co3:
-x[1]+x[2]+x[3]>=0

[Print]
NuoptStatus.INFEASIBLE
(x[i].val==1)[i] in []

考える問題の実行可能解は各変数が \(1\) となる場合であるから，確かに解が列挙されていることがわかる．

上記とは別に集合 \(I_0\) および \(I_1\) を明示的に作らない実装例を次に与える．

PySIMPLE Sample Code

def optimize(**kwds):
    from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter
    I = Set(value=range(1,4))
    i = Element(set=I)
    x = BinaryVariable(index=i)
    p = Problem(name='No-good cut test', type=min)
    p += Sum(x[i], i) == 1
    p.solve(**kwds)
    show(p, x, i)
    return p,x,i

def show(p, x, i):
    print('\n[Print]')
    print(p.status)
    print(x[i].val == 1)

# ---

from pysimple import NuoptStatus, Sum
p,x,i = optimize(silent=True)
while p.status == NuoptStatus.OPTIMAL:
    # No-good cut 条件を追加
    p += Sum((1-x[i].val)*x[i]) + Sum(x[i].val*(1-x[i])) >= 1, 'Co' + str(len(p.constraints))
    print(p[-1]) # 意図した制約式になっているか確認

    # 求解
    p.solve(silent=True)
    show(p, x, i)

これは no-good cut 条件 (3) を次のように整理した場合である．但し \(x_i^*\) は各求解時の \(i\) 番目の変数 \(x_i\) の実行可能解の値を意味し， \(\bar{x}_i=1-x_i\) である．

(11)#\[\sum_{i\in I} \bar{x}_i^*\cdot x_i + \sum_{i\in I} x_i^*\cdot \bar{x}_i \geq 1\]

(11) の左辺第一項は \(x_i^*=0\) のみの項しか残らず，また第二項も \(x_i^*=1\) のみの項しか残らない．よってこれは no-good cut 条件の別表現である．

バイナリ変数を含んだ実行可能解の列挙

目次

7. バイナリ変数を含んだ実行可能解の列挙 #

7.1. 導入 #

7.2. No-good cut 条件 #

7.2.1. 効用 #

7.3. 整数変数の場合 #

7.3.1. \(L1\) 距離による定式化 #

7.3.2. 論理的な OR 条件による定式化 #

7.4. 例題 #