日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-3

分解定理に基づく線形順序付け問題の発見的解法
静岡大学

安藤和敏

ANDO Kazutoshi(入会申請中)

静岡大学

*杉本達哉

SUGIMOTO Tatsuya02203940

東京理科大学

魚生川矩義

SUKEGAWA Noriyoshi

01013123

はじめに

1.

おいては G(C) は強連結であるか, あるいは, G(C) のV を有限集合とし, m = |V | とする. 線形順序付け

強連結成分にサイズが大きいものが存在するため, 定問題 (Linear Ordering Problem, LOP) とは, 実数行列

理 1.1 によるアルゴリズムの計算時間の短縮は期待でC = (cuv )u,v∈V が与えられたとき, 目的関数

きない. 本研究の目的は, 定理 1.1 が問題サイズの縮小

m−1∑m∑に失敗する問題例に対して, 定理 1.1 で与えられるもの

cσi σji=1 j=i+1と類似する分解によって問題サイズを縮小する発見的解法を提案することである. さらに導入した手法の有を最大化する順列 σ : {1, . . . , m} → V を見出す問題で効性を数値実験によって検証する.

ある. 線形順序付け問題は NP 困難な組合せ最適化問

2.

題であるが, 投入算出表の三角化や個人の選好の集約などの多くの応用を持つ [3].
一般性を失わず線形順序付け問題の入力行列 C =C = (cuv )u,v∈V を線形順序付け問題の入力とする.
任意の γ ≥ 0 に対して γ-レベルグラフ Gγ (C) =(V, Aγ (C)) を,(cuv )u,v∈V は, 非負, かつ, すべての u, v ∈ V に対して

Aγ (C) = {(u, v) | u, v ∈ V, cuv > γ}cuv = 0 または cvu = 0 であると仮定できる. そのような行列 C に対して強多数グラフ G(C) = (V, A(C)) を,A(C) = {(u, v) | u, v ∈ V, cuv > 0}によって定義する. P(C) を強多数グラフ G(C) の強連結成分に対応する V の分割とする. また, P(C) の順序付け (Y1 , . . . , Yl ) は, もし分解定理に基づく発見的解法によって定義する. Gγ (C) の強連結成分に対応する Vの分割を Pγ (C) とし, (Z1 , . . . , Zl ) を Pγ (C) の位相的順序付けとする. そして, 定理 1.1 と同様に各 i = 1, . . . , lに対して LOP(C[Zi ]) の最適解を σ (i) : {1, . . . , |Zi |} →Zi としたとき, V の順列 σ ∗ = (σ (1) , . . . , σ (l) ) は, γ が十分小さければ LOP の良い近似解になることが期待で((u, v) ∈ A(C), u ∈ Yi , v ∈ Yj , i ̸= j) =⇒ i < j

きる. アルゴリズム 1 はこの考えに基づくものである.

が成り立つならば, P(C) の位相的順序付けと呼ばれる.

線形順序付け問題の入力の行列 C = (cuv )u,v∈V に

線形順序付け問題は以下の定理が示すように強多数グ対して, G(C) = (V, A(C)) をその強多数グラフとし,

ラフ G(C) の強連結成分に対応する部分問題に分解でG(C) の各枝 (u, v) の重みを cuv によって定義する. 重みきることが知られている.

付きグラフ G(C) のカットとは, V = V1 ∪V2 , V1 ∩V2 = ∅行列 C を入力とする線形順序付け問題を LOP(C) でであるような非空な点部分集合の順序対 (V1 , V2 ) である.

表す.

∑{cuv | (u, v) ∈ A(C), u ∈ V1 , v ∈ V2 }定理 1.1 (分解定理 [2]) 行列 C を線形順序付け問題のc(V1 , V2 ) =入力とし, (Y1 , . . . , Yl ) を P(C) の位相的順序付けとすを最小にする G(C) のカットは最小カットと呼ばれる.

る. 各 i = 1, . . . , l に対して C の Yi への制限を C[Yi ] とする. LOP(C[Yi ]) の最適解を σ (i) : {1, . . . , |Yi |} → Yiとしたとき, 順列 σ ∗ = (σ (1) , . . . , σ (l) ) は LOP(C) の最適解である.
定理 1.1 によって, 入力行列 C に対してもし強多数

もう一つの発見的解法は G(C) の誘導部分グラフの最小カット計算に基づくものである. これをアルゴリズ
ム 2 に示す.

3.

予備実験

グラフ G(C) がいくつかのより小さい強連結成分に分本論文で導入する二つの発見的解法を Python で実装

解されれば, LOP(C) を解くための各種アルゴリズムのした. ここで, MAXSIZE は 60 に設定し, MAXSIZE 以下の計算時間の短縮が可能になる. しかし, 多くの問題例にサイズの問題を整数計画問題として定式化して PuLP ラ

1

Def level(C,V )入力: 行列 C = (cuv )u,v∈V
相異なる cuv (u, v ∈ V ) の値を20 = γ0 < γ 1 < · · · < γ kとする;

decom(C, V, −1);

3end

5Def decom(D, Z, j)
入力: 行列 D = (duv )u,v∈Z , 整数 j(−1 ≤ j ≤ k)
if |Z| ≤ MAXSIZE thenreturn LOP(D) の厳密解法による解;

7if |V | ≤ MAXSIZE then2return LOP(C) の厳密解法による解;

34end

5else
(V1 , V2 ) ← G(C) の最小カット;

6for i = 1 to 2 do

74

6Def mincut(C,V )入力: 行列 C = (cuv )u,v∈V

18end

9else

σ (i) ← mincut(C[Vi ], Vi );89end

10return (σ (2) , σ (1) );end

1112end

アルゴリズム 2: 最小カットに基づく発見的解法.
表 1: xLOLIB に対する実験結果の一部.

(Z1 . . . , Zl ) を Gγj+1 (D) の強連結成分

10分解の位相的順序付けとする;

for i = 1 to l do

11Instancerel.dev. [%]Time [s]levelmincutlevel

mincutbe75eec 150

6.3

4.6

18.7

1083.0be75np 150
be75oi 150

6.3
3.0

4.3
2.5

348.1
15.3

1546.41275.5

be75tot 150

6.6

4.6

35.9

1272.5stabu1 150

6.8

4.3

127.3

3705.8

アルゴリズム 1: レベルグラフに基づく発見的

stabu2 150

6.3

4.5

878.7

2029.4解法.

stabu3 150

5.7

4.4

235.1

1239.8σ (i) ← decom(D[Zi ], Zi , j + 1);

1213end14

return (σ (1) , . . . , σ (l) );
end

15end

16

イブラリを使用して厳密解を求める. ベンチマーク問題

れらの発見的解法の著しい有効性は認められなかった

xLOLIB (m = 150) の問題例を入力としてこれらのプが, さらなる性能の改善が可能であると思われる.

ログラムを実行した結果の一部を表 1 に示した. 表中で謝辞

rel.dev. は発見的解法による解の目的関数値のこれまでに知られている最良解の目的関数値 ([1]) からの相対的偏差である. 実験に使用した計算環境は，OS: Ubuntu

本研究は JSPS 科研費 18K11180 の助成を受けたものである.

18.04 (64bit), CPU: Intel Core i7-6700 (3.4GHz), メ

参考文献

モリ: 8GB である.

[1] E. Garcia, J. Ceberio and J.A. Lozano:4.

おわりに線形順序付け問題に対する分解定理 (定理 1.1) は, 入力行列の分解によって計算時間の短縮が可能であることを示唆しているが, 分解定理による入力行列のサイズの縮小に失敗する問題例が多く存在する. 本研究ではそのような問題例に対して, 分解定理で与えられる分解Hy-

brid heuristics for the linear ordering problem.
2019 IEEE Congress on Evolutionary Computation (2019), pp. 1431–1438.
[2] K. Hanauer: Linear Orderings of Sparse Graphs.
Dissertation, Fakultät für Informatik und Mathematik, Universität Passau, 2018.と類似する分解によって問題サイズの縮小が可能とな[3] R. Martı́ and G. Reinelt: The Linear Ordering

る発見的解法: レベルグラフを用いるもの, 及び, 最小

Problem: Exact and Heuristic Methods in Combi-カットに基づくものを提案した. 予備実験の結果はこnatorial Optimization (Springer, 2011).