数理解析研究所講究録
第 1773 巻 2012 年 207-217

207

線形順序付け問題に対するラグランジュ緩和と釘付けテスト
筑波大学システム情報工学研究科

川 矩義 (Noriyoshi Sukegawa) *筑波大学システム情報乙学研究科

張理 遠 (Liyuan Zhang) \dag er

Graduate School of Systems and Information Engineering,
University of Tsukuba
筑波大学システム情報系

山本 芳嗣 (Yoshitsugu Yamamoto) \d ag er

Faculty of Engineering, Information and Systems,
University of Tsukuba

1

はじめに

線形順序付け問題は，有限集合とその集合に属する要素の 1 対比較に対する重みが与えられた下で，重みの総和を最大にする線形順序を求める NP 困難な組合せ最適化問題である．Kemeny の方法，産業連関分析や重み付き完了時刻和最小化 1 機械スケジューリングなどに応用がある．

この問題は 0-1 整数線形計画問題として定式化される．Charon and Hudry [1] は，ラグランジュ緩和を用いた分枝限定法を提案し，乱数に基づく入力例に対し数値実験を行った．ラグランジュ乗数の総数は，素朴に実装すると，問題サイズ の 3 乗に比例するため，大規模な問題に対する実装が困難であることを彼らは指摘$\searrow$

している．

本論文では，ラグランジュ乗数の取り扱いを改良したラグランジュ緩和法を提案し，その性能を数値実験により検証する．また，問題の規模を縮小するための道具として良く知られた釘付けテストを，線形順序付け問
題の構造を用いて強化する方法を提案し，その性能を数値実験により検証する．
本論文の構成は以下のとおりである．2 節で線形順序付け問題を説明し，3 節で 0-1 整数線形計画問題としての定式化を紹介する．4 節で本論文で提案する緩和について説明し，5 節で通常の釘付けテストと本論文で提案する改良釘付けテストについて説明する．6 節で提案する解法について説明をし，7 節でその性能を数値実験により検証する．

2 線形順序付け問題
まず線形順序付け問題の応用例である Kemeny の方法を紹介しよう．項目の集合 $N=\{1,2, \ldots, n\}$ が与えられて， 人の投票者が$K$らの選好順序を，$\sigma_{1},$$\ldots,$$N$$\sigma_{\kappa},$の上の同点を許さない選好順序，(すなわち線形順序) を申告しているとする．彼とする．ここでの目標は，この複数の投票者が持つ選好順序を 1 つの選$\ldots,$$\sigma_{K}$

好順序にまとめることである．

Kemeny [4] で提案された通り，与えられたすべての選好順序に 「近い」 選好順序が最終的な選好順序として選ばれるべきであろう．そこで，ある選好順序が，与えられている複数の選好順序とどの程度近いかを測る-mail: sukega60@sk.tsukuba.ac.jp
e-mail: zhangliyuan120@gmail.com\d ag er
e-mail: yamamoto@sk.tsukuba.ac.jp$*e$\dag er208
ための指標を定義する．まず，準備として，定数$\alpha\in[0,1]$に対し，$c_{ij}^{(1)}:=\alpha|\{\kappa|\sigma_{\kappa}(i)<\sigma_{\kappa}(j)\}|-(1-\alpha)|\{\kappa|\sigma_{\kappa}(i)>\sigma_{\kappa}(j)\}|$$c_{ij}^{(2)}:= \sum_{A^{-=1}}^{K}\alpha[\sigma_{\kappa}(j)-\sigma_{\kappa-}(i)]^{+}-(1-(y)[\sigma_{\kappa}(i)-\sigma_{\kappa}(j)]^{+}$

を定義する．ここで$|\cdot|$$[t]^{+}= \max\{t, 0\}$ とする．定数は対応する集合の位数を表し，$\alpha$は「勝」 と「負」 のどちらを重視するかに依存して決まるものである．
全単射

$\pi$

: $Narrow N$ で最終的な選好順序を表す．すなわち， が最終的な選好順序において$i$ることと $\pi(i)<\pi(j)$

選好順序

$\pi$

が成立することが同値であるとする．先ほど定義した係数において $\pi(i)<\pi(j)$$j$$c_{ij}^{(\nu)}(\nu=1,2)$

より上位であは，最終的なとしたときに，どの程度の同意が得られるかを表している．従って，この値の総和$\sum_{(i,j):\pi(i)<\pi(j)}c_{ij}^{(\nu)}$を最大にする選好順序は，与えられた複数の選好順序に最も近い選好順序とみなすことができる．Kemeny の方法は，以$p^{-}$の最適化問題maximize$\sum_{(i,j):\pi(i)<\pi(j)}c_{ij}^{(\nu)}$(LOP)

subject to

$\pi$

は線形順序

を解き，その最適解を最終的な選好順序とするものである．この最適化問題 (LOP) が本論文で注目する問題
である．

3 定式化
この節では，線形順序付け問題の 0-1 整数線形計画問題としての一般的な定式化をまず紹介し，次に，メモリの節約を考慮した定式化を紹介する．

3.1 0-1 整数線形計画問題
与えられた線形順序$\pi$に対し，すべての順序対 $(i,j)$ について，0-1 変数$x_{ij}$を以下のように定義する．

$x_{ij}=\{\begin{array}{l}1 if \pi(i)<\pi(j)0 otherwise\end{array}$

すると，線形順序付け問題は以下のように定式化される．

maximize(LOP)

subject to$\sum_{(i,j)\in N_{\neq}^{2}}C_{i}jX_{i}j$

for all$X_{i}j\in\{0,1\}$$X_{i}j+xji=1$$X_{i}j+x_{jk}+x_{ki}\leq 2$$(i,j)\in N_{\neq}^{2}$for all
for all $(i,j, k)\in N_{\neq}^{3}$$(i,j)\in N_{\neq}^{2}$(0-1)(反対称性)(推移性)

ここで，$N_{\neq}^{2};=\{(i, j)|i,$ $j\in N,$ $i\neq j\}$$N_{\neq}^{3}:=\{(i,$ $j,$$k)|i,$ $j,$ $k\in N,$ $i\neq j,$ $j\neq k,$ $k\neq i\}$209である．最適化問題 (LOP) は $n(n-1)/2$ 個の等式制約 (反対称性制約) と $n(n-1)(n-2)/3$ 個の不等式制
約 (推移性制約) を持つため，問題サイズ$\searrow$の増加に伴い，非常にたくさんの制約を持っようになることが分かる．従ってこれらの制約をどのように扱うかが，解法を考える上で重要になる．

32 変数削減
反対称性制約を用いて $Xji$ で $i<j$ を満たすものを $1-x_{ij}$ で書き換えることで，以下の等価な最適化問題$(P)$が得られる．

maximizesubject to$(P)$for all $(i,j)\in N_{<}^{2}$$x_{ij}+x_{jk}-x_{ik}\leq 1$

for all $(i,j, k)\in N_{<}^{3}$$-x_{ij}-x_{jk}+x_{ik}\leq 0$

for all $(i,j, k)\in N_{<}^{3}$$(\#_{\lrcorner^{1}=^{J}}1)$$(_{=}^{\#_{\llcorner}}|\lrcorner 2)$

ここで，$\overline{c}_{ij}:=c_{ij}-c_{ji}$$N_{<}^{2}:=\{(i,j)|i, j\in N, i<j\}$$N_{<}^{3}:=\{(i,j, k)|i,j, k\in N, i<j<k\}$である．決定変数が半減し，等式制約が消え，推移性制約が 2 種類に分かれている．本論文では，1 つ目の推移性制約を型 1,2 つ目の推移性制約を型 2 と呼ぶ．また，この書き換えによって目的関数に定数項$\sum_{(i,j)\in N_{<}^{2}}c_{ji}$で表すとすれば，が表れるが，これは省略する．すなわち，最適化問題の最適値をである．以降では，最適化問題 $(P)$ に対する解法について議論する．
$\omega(\cdot)$$\omega(P)+\sum_{(i,j)\in N_{<}^{2}}Cji=\omega(LOP)$

4 緩和
この節では，まず前節の最適化問題 $(P)$ に対するいくつかの緩和を提案し，それらの性質についてまとめる．次に本論文で提案する緩和法について説明をする．

4.1

推移性制約の緩和

まず，最適化問題 $(P)$ において，問題サイズ
ち $U$ と $V$ をそれぞれ$N_{<}^{3}$の増加に伴い急速に増加する推移性制約を緩和する．すなわの適当な部分集合として，以下の制約緩和問題 $(P(U, V))$ を解く．

maximize$(P(U,V))$$n$subject to$\sum_{(i,j)\in N_{<}^{2}}\overline{c}_{ij}x_{ij}$$x_{ij}\in\{0,1\}$

for all $(i, j)\in N_{<}^{2}$$x_{ij}+x_{jk}-x_{ik}\leq 1$

for all $(i, j, k)\in U$$-x_{ij}-x_{jk}+x_{ik}\leq 0$

for all $(i, j, k)\in V$

明らかに，制約緩和問題 $(P(U, V))$ を解いた結果得られる最適解が，偶然すべての推移性制約を満たしている
場合，その解は元問題 $(P)$ の最適解である．

210

42 ラグランジュ緩和$(U, V)$ に特殊な構造が仮定されない限り，一般には依然として解きにくい問題
制約緩和問題 $(P(U, V))$ は，である．そこで，更にこの問題を緩和した問題を解くということが考えられる．本論文では，ラグランジュ緩和を用いる．

型 1 に属するすべての制約に対し非負の乗数$u_{ijk}$を，型 2 に属するすべての制約に対し非負の乗数$v_{ijk}$を導入し，以下のような制約が 0-1 制約のみのラグランジュ緩和問題 $(LR(u, v))$ を解く．

maximize$\sum_{(i,j)\in N_{<}^{2}}\overline{c}_{ij}x_{ij}$$(LR(u,v))$$+ \sum_{(i,j,k)\in U}u_{ijk}(1-x_{ij}-x_{jk}+x_{ik})$$+ \sum_{(i,j,k)\in V}v_{ijk}(0+x_{ij}+x_{jk}-x_{ik})$subject to

簡単のため，どのような$U$$x_{ij}\in\{0,1\}$と$V$

for all $(i,j)\in N_{<}^{2}$を選んでいるかは明記せずに，この最適化問題を単純に $(LR(u, v))$ と書とく．ここで， と はそれぞれ乗数のベクトルを表しており，ラグランジュ$r(u,v)_{ij}$乗数ベクトルと呼ばれる．また，を目的関数における吻の係数とする．ラグランジュ緩和問題$(LR(u, v))$ は，0-1 制約のみの問題であるため，最適解の 1 つ $x(u, v)=(x(u, v)_{ij})_{(i,j)\in}$ 梶は，以下のよう$u$$(u_{ijk})_{(i,j,k)\in U}$$v$$(v_{ijk})_{(i,j,k)\in V}$に計算できる．

(1)$x(u, v)_{ij}=\{\begin{array}{l}1if r(u, v)_{ij}>00 if r(u, v)_{ij}\leq 0\end{array}$

ラグランジュ緩和問題 $(LR(u, v))$ の最適値 $\omega(LR(u, v))$ は元問題 (P) の最適値の上界を与える．

重要な点は，通常のラグランジュ緩和で取り扱うべき乗数の総数が $n(n-1)(n-2)/3$ であったのに対し，本研究で提案するラグランジュ緩和では $|U|+|V|$ だけである点である．もし，うまくての乗数を考慮した場合と同程度の$\}_{-}^{-}$$(U,V)$ を選んで，すべ界を得ることができれば，メモリの節約と計算時間の短縮につながる．

ラグランジュ緩和問題 $(LR(u, v))$ の最適解がすべての推移性制約を満たしていたとしても，制約緩和問題$(P(U, V))$とは異なり，元問題 $(P)$ の最適解であることは必ずしも保証できない [3].

5 釘付けテスト
この節では，問題規模の縮小のために用いる釘付けテストを紹介する．まず，通常の釘付けテストを説明し，次に本論文で提案する釘付けテストを紹介する．

5.1 通常の釘付けテスト
ラグランジュ緩和問題 $(LR(u, v))$ の最適解 $x(u, v)$ から得られる情報を用いて，ある変数が元問題 $(P)$ の最適解において O を取る変数なのかそれとも 1 を取る変数なのかを判別できる．
ある添え字 $(s, t)\in N_{<}^{2}$ について元問題 $(P)$ が $x_{st}=\xi\in\{0,1\}$ となる最適解を持っていたとする．このとき，明らかに，元問題 $(P)$ と $x_{st}=\xi$ なる制約を $(P)$ に追加した問題 $(P|x$ $t=\xi)$ は，それぞれの最適値が一$\omega(P|x_{st}=\xi)=\omega(P)\geq\omega_{1ow}$ が致するという意味で，等価である．元問題 $(P)$ のある下界をとすると，成立する．制約緩和問題 $(P(U, V))$ は元問題 $(P)$ の緩和問題であり，ラグランジュ緩和問題 $(LR(u, v))$ は制。

$\omega_{1ow}$

211
約緩和問題を更に緩和した問題であるので，$\omega(LR(u, v)|x_{st}=\xi)\geq\omega(P(U, V)|x_{st}=\xi)\geq\omega(P|x_{st}=\xi)$,$\omega(LR(u, v)|x_{st}=\xi)\geq\omega_{1ow}$ . が得られる．以上をまとめると以が成立する．よって，
F の補題が得られる．

補題 1. ある定数 $\xi\in\{0,1\}$ に対し，もし $\omega(LR(u, v)|x_{st}=\xi)<\omega_{1ow}$ が成立するならば，元問題 $(P)$ の任$x_{st}=1-\xi$ が成立する．
意の最適解において，ラグランジュ緩和問題 $(LR(u, v))$ を解いて得られる最適解 $x(u, v)$ において $x(u, v)_{st}=0$ が成立したと仮定する．このとき，簡単な計算から以下の関係式が成立することが分かる．
$\omega(LR(u, v)|x_{st}=1)=\omega(LR(u, v))+r(u, v)_{st}$最適解 $x(u, v)$ において $x(u, v)_{st}$ が$x(u, v)_{st}$$0$.

であるので，対応する係数 $r(u, v)_{st}$ は非正である．同様にして，が 1 の場合には以下が成立する．
$\omega(LR(u, v)|x_{st}=0)=\omega(LR(u, v))-r(u, v)_{st}$$r(u, v)_{st}$ は正である．以上をまとめると以下の定理が得られる．
このとき，

定理 2.

$\omega(LR(u, v))-\omega_{1ow}<|r(u, v)_{st}|$ が成立するならば，元問題 $(P)$ の任意の最適解
もし，て，$x_{st}^{*}=x(u, v)_{st}$においが成立する．

定理の条件が成立するとき，決定変数52$x^{*}$$x_{st}$は $x(u, v)_{st}$ に固定されたという．

改良釘付けテスト

いくつかの決定変数が$0$

または 1 に固定されている状況を考える．集合$P_{0}$と$P_{1}$

を，それぞれ前節の釘付け

テストにより O と 1 に固定された決定変数に対応する添え字の集合とする．本論文では，これらの固定された変数の情報と，元問題 $(P)$ が持っ推移性制約を組み合せて，通常の釘付けテストを強化する方法を提案する．
釘付けテストによって固定された変数から次のように有向グラフを定義する．頂点集合を $N$ とし，有向枝集合 $A(P_{0}, P_{1})$ を，$x_{ij}$が 1 に，もしくは$A(P_{0}, P_{1}):=\{(i,$ $j)\in N_{\neq}^{2}|(j,$ $i)\in P_{0}$

定義 3.

と

$P_{0}$

あるとき，は$i$$P_{1}$$j$の祖先，または

$j$

は

$i$

が

$0$

に固定された順序対 $(i,j)$ の集合とする．すなわち，

または $(i,j)\in P_{1}\}$ とする．

が与えられて， の要素$N$$Xj_{i}$

$i$

と $j$

について，有向枝集合$A(P_{0}, P_{1})$

上に

$i$

から

$j$

への有向道が$s$の祖先は任意の子孫であるという．

定義 4. ある決定変数の添え字 $(s, t)\in N_{<}^{2}\backslash (P_{0}\cup P_{1})$ が与えられたとき，以下を定義する．
$S_{1}:=\{s\}\cup\{i\in N|i$ は $s$ の祖先

$\}$

,

$T_{1}:=\{t\}\cup\{j\in N|j$ は

$t$

の子孫

$\}$

$S_{0}:=\{s\}\cup\{i\in N|i$ は $s$ の子孫

$\}$

,

$T_{0}:=\{t\}\cup\{j\in N|i$ 1 は

$t$

の祖先

$\}$

まだ固定されていない決定変数の$t$$x_{st}$を選んで，一時的に 1 に固定してみる．すると，任意のの子孫にとっての祖先となるので，推移性制約から決定変数は以下を満たすことになる．
$x_{ij}=\{\begin{array}{ll}1 for all (i, j)\in(S_{1}\cross T_{1})\cap N_{<}^{2}0 for all (i, j)\in(T_{1}\cross S_{1})\cap N_{<}^{2}\end{array}$

212
決定変数

$x_{st}$

を一時的に

$0$

に固定した場合は以下のようになる．

$x_{ij}=\{\begin{array}{ll}1 for all (i, j)\in(T_{0}\cross S_{0})\cap N_{<}^{2}0 for all (i, j)\in(S_{0}\cross T_{0})\cap N_{<}^{2}\end{array}$

与えられたラグランジュ乗数ベクトル $u$ と$v$$x_{st}=1$ を追加した以下のラグランジュ緩和問題を定義
に対し，

する．

maximize$+ \sum_{(i,j,k)\in U}u_{ijk}(1-x_{ij}-x_{jk}+x_{ik})$$\sum_{(i,j)\in N_{<}^{2}}\overline{c}_{ij}x_{ij}$$(LR(u, v, P_{0}, P_{1})$$+ \sum_{(i,j,k)\in V}v_{ijk}(0+x_{ij}+x_{jk}-x_{ik})$$|x_{st}=1)$subject tofor all $(i, j)\in N_{<}^{2}$$x_{ij}\in\{0,1\}$$x_{ij}=\{\begin{array}{ll}0 for all (i,j)\in(T_{1}\cross S_{1})\cap N_{<}^{2}\cup P_{0}1 for all (i, j)\in(S_{1}xT_{1})\cap N_{<}^{2}\cup P_{1}\end{array}$$x_{st}=1$ という制約を追加した元問題 $(P)$ の子問題の緩和問題になっている．
この問題は，

補題 5. もし $((S_{1}\cross T_{1})\cap N_{<}^{2}\cap P_{0})\cup((T_{1}\cross S_{1})\cap N_{<}^{2}\cap P_{1})\neq\emptyset$ , ならば，元問題 $(P)$ の任意の最適解$x^{*}$について $x_{st}^{*}=0$ が成立する．

証明．ある添え字 $(i,j)$ が集合
変数$x_{ij}$$((S_{1}\cross T_{1})\cap N_{<}^{2}\cap P_{0})\cup((T_{1}\cross S_{1})\cap N_{<}^{2}\cap P_{1})$はラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1})|x_{st}=1)$ において同時に$0$に属したと仮定すると，決定と 1 になる必要がある．よっ$x_{st}=1$ となる元問題 $(P)$ の最適解は存在しないことが分かる．口てこの問題は実行不可能になり，決定変数$x_{st}$

を一時的に

$0$

に固定した場合には，以下のラグランジュ緩和問題と補題が得られる．

maximize$+ \sum_{(i,j,k)\in U}u_{ijk}(1-x_{ij}-x_{jk}+x_{ik})$$\sum_{(i,j)\in N_{<}^{2}}\overline{c}_{ij}x_{ij}$$(LR(u, v, P_{0}, P_{1})$$|x_{st}=0)$$+ \sum_{(i,j,k)\in V}v_{ijk}(0+x_{ij}+x_{jk}-x_{ik})$subject tofor all $(i,j)\in N_{<}^{2}$$x_{ij}\in\{0,1\}$$x_{ij}=\{\begin{array}{ll}0 for all (i, j)\in(S_{0}\cross T_{0})\cap N_{<}^{2}\cup P_{0}1 for all (i, j)\in(T_{0}\cross S_{0})\cap N_{<}^{2}\cup P_{1}\end{array}$

補題 6. もし $((T_{0}\cross S_{0})\cap N_{<}^{2}$ 口 $P_{0})\cup((S_{0}\cross T_{0})\cap N_{<}^{2}\cap P_{1})\neq\emptyset$ , ならば，元問題 $(P)$ の任意の最適解$x^{*}$について $x_{st}^{*}=1$ が成立する．

ラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1})|x_{st}=\xi)$ は，元問題 $(P)$ に $x_{st}=\xi$ なる制約を追加した子問題の緩和問題であるので，以下の補題が得られる．
補題 7. ある定数 $\xi\in\{0,1\}$ と固定されていない決定変数$\xi)<\omega_{1ow}$

$x$

$t$
。

が与えられて，もし $\omega(LR(u, v, P_{0}, P_{1})|x_{st}=$が成立するならば，元問題 $(P)$ の任意の最適解において $x_{st}=1-\xi$ が成立する．

$\omega(LR(u, v))$ とラグランジュ緩和問題の先ほどと同様にして，補題 7 の $\omega(LR(u, v, P_{0}, P_{1})|x_{st}=\xi)$ は，

目的関数の係数を用いて次のように計算できる$\omega(LR(u, v))-\omega(LR(u, v, P_{0}, P_{1})|x_{st}=1-x(u, v)_{st})=\sum_{(i,j)\in A’}|r(u, v)_{ij}|$$x(u, v)_{st}=0$ の場合に $A’$ は，
ここで，$A’=(((S_{1}\cross T_{1})\cap N_{<}^{2}\cup P_{1})\cap\{(i,j)|x(u, v)_{ij}=0\})\cup(((T_{1}\cross S_{1})\cap N_{<}^{2}\cup P_{0})\cap\{(i,j)|x(u, v)_{ij}=1\})$

213$x(u, v)_{st}=1$ の場合に $A’$ は，で与えられ，$A’=(((T_{0}\cross S_{0})\cap N_{<}^{2}\cup P_{1})\cap\{(i, j)|x(u, v)_{ij}=0\})\cup(((S_{0}\cross T_{0})\cap N_{<}^{2}\cup P_{0})\cap\{(i, j)|x(u, v)_{ij}=1\})$

である．最初の部分集合は，ラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1})|x_{st}=\xi)$ において 1 を取るべきである$x(u, v)$ において
のに，

$0$

を取っている決定変数に対応する添え字の集合であり，2 番目の部分集合は，ラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1})|x_{st}=\xi)$ において

$x(u, v)$ において 1 を取ってを取るべきであるのに，いる決定変数に対応する添え宇の集合である．補題 7 とそれに続く $\omega(LR(u, v, P_{0}, P_{1})|x_{st}=\xi)$ の計算方法$0$を改良釘付けテストと呼ぶ．

釘付けテストによっていくつかの変数が固定されてるとき，推移性制約を用いて，更に多くの変数を固定できる．これは，頂点集合を $N$ , 枝集合を$A(P_{0}, P_{1})$とする有向グラフの推移的閉包を作ることで実現できる．

本論文では，改良釘付けテストの前処理として Warshall[6] の方法によりグラフの推移的閉包を作る．

6 提案解法
この節では，本論文で提案する解法について説明する．添え字集合$U$

乗数ベクトルの最適化を行う劣勾配法についてまず説明し，次に， と$U$と $V$ を固定した下で，ラグランジュ$V$の更新方法を説明し，最後にそれらを統合して提案解法の全体像について説明する．

6.1

ラグランジュ双対問題と劣勾配法

ここでは，固定された変数の添え字集合を省略して，ラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1})$ の最
適値 $\omega(LR(u, v, P_{0}, P_{1}))$ をで表す．ラグランジュ双対問題 $(LD)$ は非負のラグランジュ乗数ベクト
ル $(u, v)$ で対応するラグランジュ緩和問題の目的関数値を最小化する問題である．すなわち，$P_{0},$ $P_{1}$$\omega(u, v)$$\omega(u, v)$

minimizesubject to$(LD)$

である．目的関数$\omega(u, v)$$\omega(u, v)$$u,$ $v\geq 0$は区分線形な凸関数であり，微分不可能な点を含む．この問題に対する最も良く知られた解法の 1 つに劣勾配法がある [2].
定義 8.

$(g^{u}, g^{v})$$\omega(\overline{u},\overline{v})+\langle g^{v},$が関数$\omega$の$u-\overline{u}\}+\langle g^{v},$$(\overline{u},\overline{v})\geq 0$における劣勾配であるとは，任意の非負ベクトル $(u, v)$ について
は内積を表す．
が成立することをいう．ここで$v-\overline{v}\}\leq\omega(u, v)$$\langle\cdot,$$\cdot\rangle$

劣勾配の 1 つは以下のように，ラグランジュ緩和問題の最適解から簡単に計算できる．
補題 9. ラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1}))$ の最適解を $x(u, v)$ とする．このとき以下で定義されるベ
クトル $(g^{u}, g^{v})$ は関数$\omega$の $(u, v)$

における劣勾配となる．

$g_{ijk}^{u}:=1-x(u, v)_{ij}-x(u, v)_{jk}+x(u, v)_{ik}$for $(i,j, k)\in U$$g_{ijk}^{v}:=0+x(u, v)_{ij}+x(u, v)_{jk}-x(u, v)_{ik}$for $(i, j, k)\in V$

本論文では以下のルールに従って手元にある乗数ベクトル $(u, v)$ から次の乗数ベクトル $(u^{+}, v^{+})$ を計算

214
する．

$u_{ijk}^{+}$$:= \max\{0,$$u_{ijk}- \mu\frac{\omega(u,v)-\omega_{1ow}}{\Vert(g^{u},g^{v})\Vert^{2}}g_{ijk}^{u}\}$for $(i,j, k)\in U$(2)$v_{ijk}^{+}$$:= \max\{0,$$v_{ijk}- \mu\frac{\omega(u,v)-\omega_{1ow}}{\Vert(g^{u},g^{v})\Vert^{2}}g_{ijk}^{v}\}$

for $(i,j, k)\in V$(3)はユークリッドノルム
はステップサイズを調整するパラメータであり初期値を 2 とする．また
を元問題の最適値を表す．上述の更新ルールにおけるで置き換えると，生成される乗数ベクトルの列がラグランジュ双対問題 $(LD)$ の最適解に収束することが知られている．目的関数値は乗数ベク
トルが更新されたときに必ずしも減少しない．そこで， の初期値を 2 とし，上界の改善に連続して失敗した
回数を数え，5 回に達したならば を半分にする．そして， が 0.005 よりも小さくなったならば終了する．
を固定した t での乗数の最適化が行えるわけだが， とこれにより， との更新をどのように行うか
ここで$\Vert\cdot\Vert$$\mu$$\omega(P)$$\omega_{1ow}$$\omega(u, v)$

$\mu$

$\mu$

$\mu$

$U$

$V$

$V$

$U$

$\grave$の問題が残っている．

62

$U$

と $V$ の更新固定された $U$ と $V$ の下で，劣勾配法におけるステップサイズを調節するパラメータ

とき，今の $U$ と $V$ の下では上界を今以上に改善できる$\overline{p}|$$\mu$が 0.005 を下回った

能性はないと考え， と $V$ を更に拡大する方針を$U$取る．具体的には，劣勾配法が終了した時点で手元にあるラグランジュ緩和問題 $(LR(u, v, P_{0}, P_{1}))$ の最適解
$x(u, v)$ が壊している推移性制約を探して，それらをすべて追加する．

63 提案解法
提案する解法は，劣勾配法と釘付けテストを行う内側のループ (Step2 から 7) と， と

$V$

$U$

を更新する外側のループから構成される．

Step 1 (初期化)(a) 入力である重み行列から各項目$i$} こついて $\sum_{j\in N}c_{ij}-\sum_{j\in N^{Cji}}$ を計算し，この値で降順に並べた線形順序を最初の実行可能解とする．また，その目的関数値を$\omega_{1ow}$とする．

(b) 上で計算した線形順序で隣合うすべての 3 つ組 $(i,j, k)$ に関する推移性制約を初期の $(U, V)$ とし，$larrow 0,$ $\muarrow 2.0,$ $karrow 0,$$(u, v)arrow(O, 0),$

Step 2(ラグランジュ緩和問題 $(LR(u,$ $v,$
(a)

(b)

$P_{0},$$P_{1}))$$P_{0},$ $P_{1}arrow\emptyset,$$\omega_{up}arrow+\infty$

とする．

を解く)

$x(u, v)_{ij}$ を (1) に従い計算する．
目的関数の係数 $r(u, v)_{ij}$ を計算し，$\omega_{up}arrow\min\{\omega_{up}, \omega(LR(u, v, P_{0}, P_{1}))\}$とし，もし$\omega_{up}$$larrow l+1,$ $karrow k+1$ .
が改善されたならば，それ以外のとき， $karrow 0$ とする．
$l,$Step 3(終了条件)(a)

Step 4$\omega_{up}-\omega_{1ow}<\epsilon$が成立する力 1,$k\geq 500$ が成立すれば停止．

( $x(u,$ $v)$ の実行可能解への修正と近傍探索)(a) 各項目$i\ovalbox{\tt\small REJECT}$

こついて $\sum_{i<j}x(u, v)_{ij}+\sum_{i>j}(1-x(u, v)_{ji})$を計算し，この値で降順に並べた線形順序を近傍探索の初期点とする．
(b) 各要素について順位を$\beta$の範囲で上下させて目的関数値が増加する場所を探し，見つかれば解を更新する．局所最適解に至ったとき，$\omega_{up}$Step 5(釘付けテスト)

よりも良い下界が見つかっていれば$\omega_{up}$を更新する．

215
(a)

(b)
(C)

$(\omega_{up}-\omega_{1ow})/\omega_{1ow}<\eta$$P_{0}=P_{1}=\emptyset$$P_{0}$と$k$

が 500 の倍数のとき，のときは通常の釘付けテストを，それ以外のとき，改良釘付けテストを行う．

にそれぞれ$P_{1}$

かつ$0$と 1 に固定された決定変数に対応する添え字集合を入れる．

Step 6( の更新)
$\mu$

(a)

$\mu\leq 0.005$

(b)

もし

$l$

$\muarrow 2.0$ とし Step 8 に行く．
が成立していれば，$\muarrow\mu/2$.
が 5 であれば，Step 7(ラグランジュ乗数ベクトル $(u,$ $v)$ の更新)
(a)$(u, v)$を (2) と$karrow k+1$ とし，Step 2 に行く．
(3) に従って更新．

Step 8(推移性制約の添え字集合$U,$ $V$の更新)(a) $x(u, v)$ によって壊されている推移性制約を探し，すべて $U$ と $V$ に追加する．
(b) 新たに追加された添え字 $(i,j, k)$ について uijk, $v_{ijk}arrow 0$ とし，Step 2 に行く．

7 数値実験
この節では，提案する改良釘付けテストの性能を数値実験により評価する．解法は Java により実装し，実験は CPU: Intel $i3,3.33$ GHz, メモリ

..
.

GAP:

$=\omega_{up}-\omega_{1ow}$$=(\omega_{up}-\omega_{1ow})/\omega_{1ow}$$\%^{UV}:=100(|U|+|V|)/|N_{<}^{3}|,$$\%^{LP}:=100(\omega_{up}-\omega_{up}^{LP})/\omega_{up}^{LP},$である．ここで，と$\omega^{*}$$\omega_{up}^{LP}$, RGAP:

は $(U, V)$$\omega_{up}^{LP}$

2GB の計算機上で行った．以下の数値実験において，,$\%^{PT}:=100(|P_{0}|+|P_{1}|)/|N_{<}^{2}|$,$\%^{*}:=100\omega_{up}/\omega^{*}$

はそれぞれ (LOP) の最適値と(LOP) の線形緩和問題の最適値を表す．また，としてすべての推移性制約を扱ったときのラグランジュ双対問題の最適値と一致する [3]. 以下
を Xpress Optimizer 210106 $(PC:Inteli7,2.80GHz,$

GB memory により計算している．乱数による問題例と実社会から得られた問題例についての実験結果を示す．どの問題例も目的関の実験結果では，$\omega^{*}$と$\omega_{up}^{LP}$

$6$

$)$

数の係数ベクトルが整数であるため，上界値はすべて整数値をとる．したがって提案解法の Step3 の修了条件でとした．他のパラメータについては，$(\beta, \eta, M)=(5,0.01,100,000)$ としている．
$\omega_{up}$$\epsilon:=1$

7.1

乱数による問題例

本論文では，乱数による問題例として Chron and Hudry[1] によって解かれた Median39 と Judge $s100$ を用いた．以 F の実験例では，それぞれ 10 個ずっ問題例を生成している．
問題例 Median39 は， と $Cji$ のどちらか一方はで，もう一方が正となるように構成するものである．こになる確率は等しく 0.5 で，正になる場合には あるいはは，1 から 10 の正整$C_{i}j$

こで，正になる確率と

$0$

$0$

$c_{ji}$$c_{ij}$

数のなかから一様にランダムに選ぶ．実験結果を表 71 に示す．
問題例 Judges100 は，審査員 100 人と候補者 50 人がいる状況を考え，各審査員が候補者も好む確率を 0.5 $+$ 0.35 $(j-i)/(n-1)$ とし，係数
者

$j$

を候補者

$i$

$C_{i}j$

を候補者

$i$

を候補者

$i$

$i$

を候補者

$j$

より

より好む審査員の人数から候補より好む審査員の人数を引いた人数とするものである．実験結果を表 71 に示す．

列 $\%^{LP}$ から，問題例 Median39 と Judges100 のどちらについても，線形緩和問題で得られる上界とほぼ同等の上界が提案解法によって得られている．また，列 % から，短時間で非常に良い下界が見つかっているこ$*$とが分かる．しかしながら，1 つの問題例 (Judges $100d$ ) を除いて，双対ギャップ (GAP) が残ったために最216
適性は保証できなかった．
表1

Median39 の結果

Xpress

提案解法
問題例$Median39a$$Median39b$$Median39c$$Median39d$$Median39e$$Median39f$$Median39g$$Median39h$$Median39i$$Median39j$

GAP
70.00
68.00
44.00
54.00
51.00
83.00
80.00
94.00
71.00
63.00

RGAP
2.4e-22.4e-2
1.5e-2
1.8e-2
1.8e-22.9e-22.8e-23.3e-22.5e-22.2e-2$\%^{PT}$

時間 (秒)

0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00

7.52
7.38
7.46
6.54
7.86
8.60
7.50
8.27
7.41
7.05

1.7e-l1.7e-l8.Oe-2l.le-l8.9e-24.2e-28.2e-2l.le-l9.Oe-2l.le-l%$\overline{\omega^{*}\text{時間}(\text{秒})}$

2898.00
2889.00
2966.00
2958.00
2868.00
2905.00
2900.00
2878.00
2902.00
2860.00

257.40397.60169.80245.00243.00404.001282.702784.70489.20397.90

$*$

99.34
99.72
99.87
100.00100.00
99.72
99.93
99.83
99.90
99.90

表 2Judges100 の結果

提案解法
問題例

Judges $100a$
Judges $100b$$Judgesl00c$

Judges $100d$
Judges $100e$

Judges $100f$
Judges $100g$
Judges $100h$

Judges $100i$
Judges $100j$

72

GAP
25.00
21.00
30.00
0.00
43.00
20.00
10.00
33.00
10.00
60.00

RGAP
4.le-43.4e-44.9e-40.0
7.Oe-43.3e-41.6e-45.5e-41.7e-4
1.Oe-3$Xpre$$\%^{LP}$$\%^{PT}$

3.8e-34.9e-36.4e-30.0
9.4e-3
4.6e-3

58.71
65.45
52.26
91.45
35.84
65.11
75.23
48.99
73.09
11.70

4.le-3l.le-2l.le-3

1.9e-2

時間 (秒)$\omega^{*}$

時間 (秒)

%

12.98
12.26
13.43
9.81
12.93
12.36
12.57
13.98
13.03
14.76

60834.00
61752.00
60598.00
61592.00
61120.00
60220.00
60888.00
60490.00
60400.00
59946.00

118.00102.10111.1085.70
113.70143.70107.60249.70130.40853.80

99.99
99.99
99.97
100.00
99.95
99.97
99.99
99.99
99.99
99.97

$*$

実社会から得られた問題例

問題例 DsumC [5] の目的関数の係数行列は NCAA 大学バスケットボールチームの得点差を基に作られており，60,031 個の 0-1 変数と 13,807,130 本の推移性制約を持つ．実験結果を表 72 に示す．
反復回数はラグランジュ乗数ベクトル $(u, v)$ を更新した回数である．316 回目の反復において最適解が見つかっている．しかしながら，その時点では上界がまだ緩く，2193 回目の反復終了後に双対ギャップ (GAP) が0 になり最適性が証明された．

217
表3

反復回数

$\omega_{up}$1276183.00
500 276219.00
1000 276219.00
1500 276219.00
2000 276219.00
2193 276219.00

8$\omega_{1}$$w$。

276629.00
276221.00
276220.00
276220.00
276220.00
276219.00

GAP
446.00
2.00
1.00
1.00
1.00
0.00

DsumC に対する実験結果$|U|+|V|$$\%^{UV}$

345
10410
10693
10882
11046
11091

0.00
0.08
0.08
0.08
0.08
0.08

$\%^{PT}$

時間 (秒)

0.00
84.68
93.21
94.55
95.21
95.21

0.02
2.48
8.66
13.16
17.36
18.45

$|P_{0}|+|P_{1}|$
$0$

50836
55953
56760
57156
57156

おわりに
本論文では，0-1 整数線形計画問題に定式化した線形順序付け問題に対し，ラグランジュ緩和法と釘付けテストを改善する方法を提案した．大規模な線形順序付け問題を解く際に，通常のラグランジュ緩和法では扱う乗数の個数が非常に多くなるため，それに伴い必要なメモリや劣勾配法にかかる時間も増加するが，提案解法
ではそれらの節約を試みている．数値実験から，提案解法は特に実社会から得られた問題や，実社会の問題例を模した問題例について良い結果を示すことが確認できた．
また，最適解が必要となる場合には，提案した改良釘付けテストによって固定された変数の情報を用いて問題の規模を縮小し，その問題に対し既存の厳密解法を実行するという手段が考えられる．

参考文献[1] I. Charon and O. Hudry, “A branch-and-bound algorithm to solve the linear ordering problem forweighted tournaments“, Drscrete Applied Mathematics 154 (2006) 2097-2116.

[2] M.L. Fisher, “The Lagrangian relaxation method for solving integer programming problems“, Management Science 27 (1981) 1-18.
[3] A.M. Geoffrion, “Lagrangian relaxation for integer programming“, Mathematical Programming Study

2 (1974) 82-114.
[4] J.G. Kemeny and J.L. Snell, Mathematical Models in the Social Sciences, Blaisdell, New York, 1972.

[5] K. Pedings, A.N. Langville and Y. Yamamoto, “A minimum violations ranking method“, to appear

in optimization and Engineering.
[6] R. Sedgewick, Algonthms in, 3rd Edition, Addison-Wesley, Boston, 2002.

$C$