数理解析研究所講究録 1477 巻 2006 年 73-82

73

多目的割当問題のミニマックス最適化
防衛大学校情報工学科
防衛大学校情報工学科

ウィーラユット
山田 武夫

*

・

ノムシリ (VEERAYUTH Nomsiri)(YAMADA Takeo)
Department of Computer Science,
The National Defense Academy

要旨 : We are concerned with a variation of the assignment problem, where theassignment costs differ under different scinarios. We give a surrogate relaxation
approach to derive a lower bound as well as an upper bound quickly, and showthat the pegging test known for a0-1 programm ing problem is also applicable to this problem. Next, we discuss how the com putation time for pegging
can be drastically shortened by taking the special structure of the assignment
into account Firtally, through numerical experiments we show that the developed method finds upper and lower bound of high accuracy in relatively small
CPU time, and also solve larger instances to optimality faster than conventional

methods.
Keywords : assignment problem, robust optimization, pegging test,
combinatorial optimization

1. はじめに割当問題 (
仕事ある.

$\mathrm{A}\mathrm{P}$:assignment problem)[1] は与えられた$J=\{1, \ldots, n\}$$\mathrm{A}\mathrm{P}$$n$

人の学生 $I=\{1, \ldots, n\}$ を

$n$

個の

に割り当てるとき, 割り当てにともなうコストの総和を最小化する問題での解法としては, ハンガリー法 $[9, 11]$ が良く知られているが, スケーリング技法などを取り入れた,

多項式時間や強多項式時間のアルゴリズムも開発されている.

本研究では, これに対してシナリオが $K$ 個あり [ 」, シナリオ のときに, 学生 を仕事であるとする. 割り当て $x=(x_{ij})$ による総コストは, シナリオカに割り当てるコストが$k$$7^{\eta}$$\mathrm{i}$$j$$c_{\iota j}^{k}$

$k$

であれば

(1)

$z^{k}(x):= \sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^{k}x_{\dot{\mathrm{z}}j}$であるが, 本稿では, これらの最大のものを最小化する, 多目的割当問題のミニマックス最適化 (MMAP: mini-max assignment problem)[18] を考える.

MMAP:
mimrrnzesubject to$\sum_{j=1}^{n}x_{ij}=1$$\sum_{i=1}^{n}x_{ij}=1$,$\mathrm{i}=1,2,$,$j=1,2,$$x_{ij}\in\{0,1\}$$*\mathrm{y}\mathrm{a}\mathrm{I}\mathrm{n}\mathrm{a}\mathrm{d}\mathrm{a}@\mathrm{n}\mathrm{d}\mathrm{a}.$ac.j$\mathrm{p}$(2)$1 \leq k\leq K\mathrm{n}\mathrm{a}\mathrm{x}\{\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^{k}x_{ij}\}$,$\forall \mathrm{i},j$$\ldots,$$\ldots,$

$n$

(3)

$n$

(4)
(5)

74

MMAP は区分的に線形な凸関数を目的関数とする組合せ最適化問題で, 目的関数をくと, 下のようにも書くことができる.
MMAP

’

$v$

と置

:
minimize(6)$v$

subject to$\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}^{k}x_{ij}\leq v$,$k=1,2,$$\ldots,$

(7)

$K$

(3), (4) $(5)$
この問題は, 線形の混合整数計画問題であるので, ある程度のサイズの問題までは NUOPTや XPRESS-MP[13] などの商用ソフトで解くことができる.

AP と異なり, MMAP は NPP 困

難 [6] である.
$\mathrm{A}\mathrm{P}$は人員割当, 機械スケジューリング問題のような様々な状況で応用される. MMAP は

Kouvelis-Yu[7] によって定式化され, NP\sim 困難であることが証明された. そして, 小さい問題を解決した $(n\leq 40, K\leq 30)$ . 榊原ら [18] はシナリオ数 $K$ が 2 で,の値が 200 までの問題について近似解を求める方法を発表している. Cimen[3] はトルコの軍隊の人員割当に MMAPを応用した.
本研究では, 代理制約緩和と近似解法により良い上下界値が得られ, これに釘付けテストを$n$適用すると問題を (大幅に) 縮小できることを示す. さらに, MMAP に対する釘付けテストの効果を高めるため改善釘付けテストを新たに考案する. この方法によって通常の釘付けテス
トを用いたときに比べ, 計算時問が大幅に短縮される. その結果,
までのサイズの$n=1\mathrm{O}\mathrm{O}\mathrm{O}$

問題を厳密に解くことが可能となる.

2. 上界値と下界値
2.1

代理制約緩和$\lambda=(\lambda_{1}, \lambda_{2}, \cdots’\lambda_{K})$を$\sum_{k=1}^{K}\lambda_{k}=1$,$\lambda_{k}\geq 0$(8)$(k=1,2, \ldots, K)$を満たす任意のベクトルとし,(9)$\overline{c}_{j},(\lambda)=\sum_{k=1}^{K}\lambda_{k}c_{ij}^{k}$

と置くと,

SMMAP

MMAP の代理制約緩和により下を得る.
$(\lambda)$:
minimizesubject to$\lambda\in R_{+}^{K}$(10)$\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{c}_{ij}(\lambda)x_{ij}$(3), (4), (5)を固定すると, SMMAP(\lambda ) は通常の割当問題でハンガリー法などにより効率的に解くことができる, その最適解を量$(\lambda)$, 最適目的関数値を$\underline{z}(\lambda)$とすると,$\underline{z}(\lambda)$

は任意の

75

$\lambda\geq 0$

で MMAP の下界値を与える.

劣勾配法によって

また,を最大とする$\underline{z}(\lambda)$$\lambda^{\uparrow}$と$\underline{z}(\lambda)$は$\lambda$$-z:=\underline{z}(\lambda\dagger)$に関して区分的に線形な凹関数となり,が得られる. 以下.

$\underline{z}$を最良の下界値とすると, 次が示される.

命題 1

(i)

$\lambda\in R_{+}^{K}$

関数値をを固定すると,$z^{\star}$とすると,$\underline{z}(\lambda)$

は MMAP の一つの下界値を与える.

これらの間には下の関係が成立する.
(11)$z^{\star}\geq\underline{z}(\lambda)$

(ii)
(iii)

$\underline{z}(\lambda)$$\lambda$は,$\lambda$

MMAP の最適目的に関して区分的に線形な凹関数である.

において,$\underline{z}(\lambda)$が微分可能なら$\underline{z}^{k}(\lambda)$$\frac{\partial\underline{z}(\lambda)}{\partial\lambda_{k}}=\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i\mathrm{j}}^{k}\underline{x}_{ij}=$

任意の\lambda に対し, 前に述べたように$\underline{z}(\lambda)$

は MMAP の下界値を与えるが,(12)

この値はできるだ

け大きい方が望ましい. このために, 劣勾配法 (subgradient method) $[12, 17]$ を導入する. こを意味する.
こで劣勾配とは, (12) を成分とするベクトルが微分不可能な点を有するという点を除い
また, ここでいう劣勾配法とは, 目的関数
$g:=\text{ }\underline{z}(\lambda)/\partial\lambda=(\underline{z}^{k}(\lambda))$$\underline{z}(\lambda)$て通常の勾配法と同じで, 次のように与えられる.

劣勾配法

ここで,

$\lambda+\alpha d$が条件 (8) を満足するために,$d$としては $g$ を超平面$\lambda_{1}+\lambda_{2}+\cdots+\lambda_{K}=1$に射影して$d:=g-\overline{g}1$

をとる.

ここに
$\overline{g}=\sum_{k=1}^{K}g_{k}/K$

である.
は,

これが実際に$\underline{z}(\lambda)$の増加方向であることは, 次のように証明できる. $K.–2$ の場合

劣勾配法ではなく, 2 分探索法を用いる.

78

22

上界値

代理制約緩和において, 最適な

様々な
行可

書き,

を求めるための劣勾配法 (あるいは 2 分探索法) において,

で SMMAP(\lambda ) を繰り返し解いたが,$\lambda$$\mathrm{A}\mathrm{F};_{\mathrm{b}}^{\mathrm{b}}\text{解}$$\lambda^{\mathrm{t}}$でもあるので,$\lambda\dagger$$\text{目}$

的関数値を得るまでに得られた$8\mathrm{M}\mathrm{M}\mathrm{A}\mathrm{P}(\lambda)$$1\leq k\leq K\mathrm{m}\mathrm{a}\mathrm{x}\{z^{k}(\underline{x}(\lambda))\}$$\overline{z}(\lambda)$は$z^{*}$の最適解の$\text{上界}$$\underline{x}(\lambda)$

は MMAP の実値を与える.

$$ れを$\overline{z}(\lambda)$のうち, 最小のものを MMAP の上界値 2 とする.

3. 釘付けテスト
0-1 計画問題の釘付けテスト

3.1

SMMAP(\lambda ) は標準的な割当問題なので, 制約条件 (5) は非負条件 $x_{ij}\geq 0$ と改めてよい.
この線形計画問題を解いた時の最適字引きを$z$$=$$\underline{z}+\sum_{j\in N}\alpha_{0j}y_{j}$

,

(13)

$=$

$\overline{b}_{i}$$y_{B(i)}+ \sum_{j\in N}\alpha_{ij}y_{j},$$i=1,2$ , ..., $2n-1$(14)とすると, 最適性の定義より$\alpha_{0_{J}}\geq 0$$0\leq\overline{b}_{i}\leq 1$

ここに,

$N$

,
,

は非基底変数の添字集合で,$\forall j\in N$$\mathrm{i}=1,2,$$B(\mathrm{i})$は$\mathrm{i}$$\ldots,$

(15)

,

$m+n$

.

(16)

番目の基底変数の添字を表す. また, 最適性の条件より (15) である.

と置くと, 最適解

$PU_{s}:= \min\{\frac{-\alpha_{0j}}{\alpha_{i(\epsilon)j}}|j\in N,$$\alpha_{i(s)j}<0\}(1-\overline{b}_{i(s)})$(17)$PL_{s}:= \min\{\frac{\alpha_{0j}}{\alpha_{i(\mathrm{s})j}}|j\in N,$$\alpha_{i(s)j}>0\}(\overline{b}_{i(\epsilon)})$(18)$(x_{j}^{*})$

において次が成立する [10].

定理 1$\mathrm{P}$の最適解$x^{*}=(x_{j}^{\star})$において(i) x、が非基底変数の場合$\mathrm{o}_{0s}.>\overline{z}-\underline{z}$(ii)$x_{s}$

であれば, $x_{s}^{*}=0$(19)であれば, $x_{s}^{*}=0$

(20)

であれば,

(21)

が基底変数の場合$PU_{s}>\overline{z}-\underline{z}$$PL_{\mathit{8}}>\overline{z}-\underline{z}$$x_{\mathrm{s}}^{*}=1$

77

MMAP の釘付けテスト

32

割当問題 (2)$\sim\langle 5$) は 0-1 計画問題であるが, (5) を連続緩和して$x_{ij}\geq 0$,$\forall i,$$j$と置きかえても良いことが知られている [1]. これは普通の線形計画問題であるので, 市販の,あるいはフリーの線形計画ソフト [5] を用いて解くことができる. しかし, 割当問題についてはその特殊構造を利用した, より効率的な解法がいくつか提案されている. 本節では, その中から最も基本的なハンガリー法 [$9|$について述べる. 上の線形計画問題の双対問題はDAP:
maximizesubject toとなる. ベクトルの対 $p=(p_{i})$ ,(22)$\sum_{i=1}^{n}p_{i}+\sum_{j=1}^{n}qj$$p_{i}+qj\leq c_{ij}$$q=(q_{j})$,$\forall \mathrm{i},j$は, (23) を満たすとき, 双対可能解という.

で, 節点集合 $V_{1}=\{1,2, \ldots, n\},$ $V_{2}=\{1’, 2’, \ldots, n’\}$ と,ここ等号が成り立つ枝だけからなる集合$A(p, q)=\{(\mathrm{i}, j’)|p_{i}+q_{j}=c_{ij}\}$を持つ 2 部グラフを $H(p, q)$ とする. このとき, 線形計画法の双対性から $H(p, q)$ が完全$\text{マ}$$\backslash \backslash J$

チングを持つとき, そのマッチングが割当問題の解となる [2].

2 部グラフ $H(p, q)$ の左側節点の部分集合$U\subseteq V_{1}$が縮小であるというのは, $|U|>|N(U)|$に接するものの集合である.
次の定理は結婚定理, または Hall の定理として知られている [1].

であることをいう. ただし,

$N\langle U$) は$V_{2}$

の節点で,

$U$

定理 2
$H(p, q)$が完全マッチングを持つことの必要十分条件は $H(p, q)$ は縮小を含まないことである.

ハンガリー法では, 適当な双対可能解 $(p, q)$ から出発し, グラフ $H(p, q)$ 中に縮小がある力 ‘
どうか調べ, それがある場合には, (22) が増加するように $(p, q)$ を修正する.

$H(p, q)$ に縮小が含まれないようになるまでこれを反復することにより, 割当問題の解が得られる.
$M$ に対応
ところで, SMMAP(\lambda ) に前節の釘付けテストを適用するには, 最適マッチング
する最適単体表が必要である. これは, ハンガリー法の結果から次のように復元することができる. まず, 次の事実に注意する.
命題 2

在する.

(ii) 上の全域木に含まれる変数は$\mathrm{S}\mathrm{M}\mathrm{M}\mathrm{A}\mathrm{P}(\lambda^{\uparrow})$$H(p, q)$ が連結グラフでない場合には,

このとき,

$p,$

$q$

の最適基底を与える.

を修正して $H(p, q)$ が連結となるようにできる.

$H(p, q)$ の全域木に対応する変数の集合 $B$

非基底変数の集合は

$N$

と記す.

が最適単体表の基底変数の集合とする.

78

33

改善釘付けテスト

最初の単体表を$Bx_{B}+Nx_{N}=1$$c_{B}x_{B}+c_{N}x_{N}=z$と記し, 最適解において対応する単体表が$x_{B}+\overline{A}x_{N}$$\overline{c}x_{N}$であるとする.

$\overline{c}$$\overline{A}$c- の各成分が,$=$$\overline{b}$$z$

一$\overline{z}$この場合$\overline{A}$

で,

$=$

$\alpha_{ij},$$\alpha_{0j}$,$=$$B^{-1}N$$=$$\mathrm{c}_{N}-\mathrm{c}_{B}B^{-1}N$$\overline{b}=B^{-1}1$,$\overline{z}=c_{B}B^{-1}1$に相当する.

A- を求める必要があるが, 互の大きさはここで, 定理 1 の (ii) を適用するには,$(2n-1)\mathrm{x}$

この要素をすべて計算するのは非常に負担が大きい. しかし, 割当問題の特殊性から, この部分を次のように改善することができる.
の係数行列のユニモジュ
連続緩和問題の最適解に対応する基底形式を考える. SMMAP
ラー性から最適単体表では下が成立する.
$(n^{2}-2n+1)$ で,$n$が大きい場合,$(\lambda^{\uparrow})$$\in${-1, 0, 1},$\in${0, 1}(25)$N^{+}:=\{j\in N|\alpha_{0j}>\overline{z}-\underline{z}\}$(26)$N^{-}:=\{j\in N|\alpha_{0j}\leq\overline{z}-\underline{z}\}$

(27)

Clij
$\overline{b}_{i}$(24)$\forall j\in N$

そこで,とすると, 次の定理を示すことができる.

定理 3

(i)

$\overline{b}_{i}=1$の場合$PL_{i}>\overline{z}-\underline{z}\Leftrightarrow\{j\in N^{-}|\alpha_{ij}=1\}=\emptyset$(ii)$\overline{b}_{i}=0$の場合$PU_{i}>\overline{z}-\underline{z}\Leftrightarrow\{j\in N^{-}|\alpha_{ij}=-1\}=\emptyset$

証明: (i) (24) より,$PL_{i}= \min\{\alpha 0\mathrm{i}|\alpha_{ij}=1, j\in N\}=\min\{PL_{i}^{+}, PL_{i}^{-}\}$$PL_{i}^{+}= \min\{\alpha 0j|\alpha_{ij}=1, j\in N^{+}\}$

り,$PL_{i}^{+}>\overline{z}-\underline{z}$. ただし,と $PL_{i}^{-}= \min\{\alpha_{0j}|\alpha_{\dot{x}j}=1, j\in N^{-}\}$ である.

(26) よであるから, 明らかに $PL_{i}>\overline{z}-\underline{z}\Leftrightarrow\{j\in N^{-}|\alpha_{ij}=1\}=\emptyset$ . このようにして (i) が証明された. (ii) も同様$\bullet$

この定理の重要な含意は以下の事実である. すなわち, 釘付けテストを実行する際に必要となるのは非基底変数に対応する行列互のすべてではなく, N- に含まれる列のみで, このが成り立てば, 基底変数を 0 または 1 に固定すN- 部分について,$x_{N}$$\{j\in N^{-}|\alpha_{i\mathrm{j}}=\pm 1\}=\emptyset$

ることができる.

79

以上により,$\overline{A}=(\alpha_{ij})$の $(n^{2}-2n+1)$ 列すべてでなく,$\alpha 0j>\overline{z}-\underline{z}$である列のみ計算すれば良いが, 通常このような列は非基底変数全体比べ, はるかに少数なので, 釘付け時間は大幅に短縮される.

4. 数値実験41

実験計画

シナリオ数 $K$ を 2\sim 16, 商品数 を 200\sim 1000 の範囲で実験を行う. 最初に, 基準コスを $0<\delta<1$ である定数として, シナリ
を $[1,1000]$ の間に一様独立な乱数で発生し,
ト$n$$\delta$$c_{ij}^{0}$オ$j_{\dot{v}}$のときの割当コストを次のように決める.
$c_{ij}^{k}$$\delta$:$[(1-\delta)c_{ij}^{0}, (1+\delta)c_{ij}^{0}]$の整数一様乱数

は割当コストのシナリオ間での相関の度合いを制御するパラメータで,の場合を考える.
上下界値と釘付けを計算するプログラムは 言語で作成し, 実験はが強い. 以下では$\delta$

二

0.3,$\delta=0.6,$$\delta$$\delta=0.9$$\mathrm{I}\mathrm{B}\mathrm{M}$$\mathrm{C}$

MODEL270 (CPU :POWER 3- 垣 SMP 2WAY,

42が小さい程相関$375\mathrm{M}\mathrm{H}\mathrm{z}$$\mathrm{R}\mathrm{S}/6000\mathrm{S}\mathrm{P}44$) 上で行う.

上下界値と釘付け結果と 2 は下界値と上界値
表 1, 表 2, 表 3 はそれぞれの ごとの実験結果を示す. ここで,が得られるまで
は gap の欄に表している. lassign \iota よを表し, これらのギャップ
は 1 に固定された変数の数を表しており,に割当問題 SMMAP(\lambda ) を解いた回数である.
と上下界値はつまり未定の変数の数を示している.
$n’$ は固定されずに残った変数,$\delta$$\underline{z}$$\lambda^{\{}$$(=\overline{z}-\underline{z})$$\mathrm{f}\mathrm{i}\mathrm{x}_{1}$$\lambda^{\uparrow}$$\mathrm{C}\mathrm{P}\mathrm{U}_{1}$の計算時間,$\mathrm{C}\mathrm{P}\mathrm{U}_{2}$

年忌体表の復元と釘付のテストに要した時間である. また, すべての行はランダムに発生した 10 例題についての平均値である,
表 1: 上下界値と釘付け $(\delta=0.3)$$\overline{\frac{Kn\underline{z}\overline{z}\mathrm{g}\mathrm{a}\mathrm{p}\#\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{x}_{1}n’\mathrm{C}\mathrm{P}\mathrm{U}_{1}\mathrm{C}\mathrm{P}\mathrm{U}_{2}}{22001459.11464.04.96.189.8355.80.10.2}}$

2.2

600
1000

1328.41132.9

13306

600
1000

1340.11146.71133443311
1149.1

3.0
2.4

600
1000

1351.6 1357.9
1155.61159.3

6.3
3.7

600
1000

13548
1160

5.9

167.3
275.4

1427.83627.91.4

1563.9

11.0
27.5

2.1
10.2

4.0
1135.32.45.4$\overline{42001483.91490.06.144.262.3409.50.90.2}$
411
33.3

166 .1294.3$296\mathrm{S}.7$

2.1

4.1

$\overline{82001487.01496.69.651.235.4593.41.50.2}$
38.1
35.1

31.3
73.8

2992.44763.6

13.9
38.9

1.9
11.5

$\overline{162001505.41516.911.558.125.3698.42.90.2}$
1360.7 5.91164.94.4

646

292
47.2

2876.05440.9

35.9
83.9

2.0
8.4

$\ovalbox{\tt\small REJECT} 5$$5^{\gamma}.0$$\sim$

80

表 2: 上下界値と釘付け $(\delta=0.6)$$\overline{\frac{Kn\underline{z}\overline{z}\mathrm{g}\mathrm{a}\mathrm{p}\#\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{x}_{1}n’\mathrm{C}\mathrm{P}\mathrm{U}_{1}\mathrm{C}\mathrm{P}\mathrm{U}_{2}}{22001384.21393.29.06.163.2581.80.10.2}}$26
6.51252 .9 1255 .5
33
6.21000 103651039.8
200 . 1449 .7 1462.6 12.9
32.0
7.9
37.0
600 1314.4 1322.3
4.6
3631000 1113.1 1117 .7
200 1484.9 1506.9 220
50 .4
49.9
600 1349 .4 1364.0 14.6
1000 1145 .7 115408351.3
200 150381530.2 26.4
582
600 1373.2 1388.2 15.06481000 1167.6 1178.5 10.9
65 .7

600

4

8

16

表 3: 上下界値と釘付け

3016
332.8
20.9
31.4
59.7
8.4
9.7
3.2
2.7
1.2
0.7

1381.94546 .5
782 .136890
5658 .7
1202.36187 .7
9706 .3
1398.46329.1
12428.9

16

0.9

4.7
06
9.8
30 .9
1.5
18 .1
560
2.9
36 .1
1080

5.2
0.2
2.0
10.2
0.2
2.3
11 .5
0.2
1.9
9.8

$(\delta=0.9\rangle$$\overline{\frac{Kn\underline{z}\overline{z}\mathrm{g}\mathrm{a}\mathrm{P}\#\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{x}_{1}n’\mathrm{C}\mathrm{P}\mathrm{U}_{1}\mathrm{C}\mathrm{P}\mathrm{U}_{2}}{22001195.81204.99.17.547.\mathrm{S}679.40.10.2}}$

600

989 .77890
1353.71191 .9

1000
200
600
1000
200
600
1000

17.0
1433.00.2
2.6127911301.422.345.4009144616.4
1091.7 1104.1 12.4
54.3
0014171060 .988
1485.2 1531.8 46661 .4
0.200226193.1
1319.7 1344.1 24.4
20
61 .7
00
9894 .3
34.4
113221149 .7 17 .5
54.9
00 19176.6
90 .5
7.6

600
1000
4

$200$

8

16

999.4
1.6
9.7
6.9
48 .5
5207.0
5.4
793.3
4.3
6445 .3
7.4 229.1
101383029.3
51.6
3.9
15976
1202.5 10635.717.1
4899 .3
9.3
1010.0 10.9
3123313066725 .7
1468.3 35.3
1.6
53.8
03
1804.8

999.1

2.5
10.2
0.2
22

以上の結果から, 次のことが分かる.

・代理制約緩和法により, かなり精度の良い近似解が短時聞で得られる.
目的関数値 (下界値 で代用) は とともに減少し, $K$ の増加とともに増加する. これ.
.
$\text{・}$$\underline{z}$$n$は, 問題 MMAP の性格から予想されることである.

の増加にともなって, 上下界値の計算時間が増大する.

の増加にともなの増加はさほど顕著でない.
とともに増大するが, $K,$ の増は・最適単体表の復元と釘付けに要する時聞加による影響はさほど大きくない.
釘付けテストにより, 問題はきわめて大幅に縮小される.
$n,$ $K$う$(\mathrm{C}\mathrm{P}\mathrm{U}_{1})$$\delta$$\mathrm{C}\mathrm{P}\mathrm{U}_{1}$$(\mathrm{C}\mathrm{P}\mathrm{U}_{2})$$n$$\delta$

8 \dager

XPRESS-MP による直接解法

43の二値について例題をランダ A に 10 題発生した. ここで, XPRESS-MP は DELLK.
) 上で動かして実験を行う. 計算はタイムリミット
DIMENSION 8400 (Pentium(R)4を CPU 時間 600 秒として打ち切ったが, 図 1 には 600 秒以内に 10 例題がすべて解けたケー$\delta,$$n$$3.40\mathrm{G}\mathrm{H}\mathrm{z}$スについてのみ, 平均をグラフ化した 3$\delta=0.3$

り,の場合でもシナリオ数が 8 以上となると XPRESS-MP では解き難い問題が多くなではシナリオ数 $K$ , 商品数 がかなり小さいケースでないと難しいこと$\delta=0.6,$ $\delta=0.9$

$n$

が分かる.

44

釘付けテスト経由の厳密解法

MMAP の厳密解法について数値実験を行う. 実験計画は第 4 章と同様にそれぞれの に対し, $n=200\sim 1000$ までの範囲で行い, 各ケースについて 10 題をランダムに生成して平均値を計測した. 解法としては上下界値を求め, 第 3 章の (改良された) 釘付けテストによって聞題を縮小して XPRESS-MP で解く. この方法を以降「釘付け経由の厳密解法」 と呼ぶ.
$\delta$

350$\delta--0\mathit{3}$.

300$\mathrm{K}--4_{1}8.18$

300$\delta=03060B\mathrm{K}--4$$\delta=0306$
$[$

250

$\wedge 250$$\wedge 2\alpha\}$$-’\sim$$\overline{\supset}150\mathrm{L}$$\mathrm{i}\mathrm{a}_{2\mathfrak{W}}\supset 0\overline{\mathrm{f}}.\mathrm{L}|50100$$\{\begin{array}{l}*.\prime...*...\iota\cdot........\end{array}$$[_{*}.\cdot.\cdot \mathrm{r}’.*$

50
0$\mathrm{o}10050\mathrm{D}$$\mathrm{o}\mathrm{o}" \mathrm{o}\mathrm{o}\sim\alpha\subset \mathrm{c}$$\mathrm{o}\mathrm{o}" \mathrm{o}\mathrm{o}\sim\infty \mathrm{o}\mathrm{o}\infty \mathrm{o}\mathrm{o}\underline{\mathrm{o}\mathrm{o}\mathrm{o}}$$\mathrm{o}\mathrm{o}\sim\varpi 0\vee\circ\circ\Phi\infty \mathrm{o}\mathrm{o}\underline{\mathrm{o}\mathrm{o}\mathrm{o}}$$\mathrm{o}\mathrm{o}"\sim \mathrm{o}\mathrm{o}\Phi\circ\circ\infty \mathrm{o}\mathrm{o}\underline{\mathrm{o}\mathrm{o}\mathrm{o}}$$\mathrm{n}$– \llcorner t 掻解法 .

$.’\cdot$.1 案手法\phi 一直接解法 $..*\cdots$ 提案手法

図 1: XPRESS-MP による直接解法と釘付けテスト経由の厳密解法

以上の結果から, 次のことが分かる.

釘付けテストを経由する方法は解ける問題のサイズ $(K, n)$ がかなり大きくなり, 同じサイズの問題では計算時間が数倍から数十倍速くなっている.

・直接解法に比べ,.

相関パラメータとシナリオ数が大きい場合は, 釘付け経由の方法でもかなり問題が解き
難くなる.

5. 結論
本観究では多目的割当問題のミニマックス最適化 (MMAP) を定式化し, その解法を検討した. 主な成果は以下のとおりである.

82

.
.
.

MMAP に代理制約緩和と劣勾配法 (あるいは 2 分探索法) を適用し, 上下界値を得る
アルゴリズムを実現した.
代理制約緩和問題が (連続型の) 割当問題となることから, 最適単体表を復元することにより通常の 0-1 計画問題に適用される釘付けテストが MMAP にも適用可能であることを示した.
が大きい場合, 普通の釘付けテストで計算すると膨大な計算時悶がかかるので, それ$n$に対処するために改善釘付けテストを提案した.
・種々のサイズとタイプの例題について数値実験を行い, 上の方法の評価を行った. 以上
が 200 から 1000 までの MMAP が数分の計算時間で解けるようになった.
の結果,
$n$

このように, 釘付けテストにより一般に問題が大幅に縮小されるが, 例えば

数$n=1\mathrm{O}\mathrm{O}\mathrm{O}$でも変の数は 100 万個なので, このうち 99 万個が固定されたとしても, 残った 1 万変数の問題$x_{ij}$

を XPRESS-M$\mathrm{P}$で解くことは困難である. そこで, 今後の課題として, 縮小された問題を商用ソルバーで解くのでなく, 専用のアルゴリズムを構築して解くなどの対処法が考えられる.

参考文献
K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algonthms, and Applications, Prentice Hall, Englewood Criffs, 1993.

[1]$\mathrm{R}$[2]$\mathrm{V}$

Chvatal, Linear Programming, Freeman and Company, San Francisco, 1983.

[3] Z. Cimen, A multi-objective decision support rnodel for the Turkish arrreed forces personnel
assignrnent system, M.S thesis, Air Force Institute of Technology, Wright-Patterson Air Force
Base, $2001$ .
[4] Fisher,[$\mathrm{x}\mathrm{H}\mathrm{i}$.

$\mathrm{M}$$3\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{r}\mathrm{e}\mathrm{r}$. The Lagrangian Relaxation Method for Solving Integer Programming, “SHtbsre FZrvekUjit$\mathrm{e}\mathrm{s}\mathrm{r}\mathrm{p}\mathrm{r}\mathrm{a}\mathrm{e}\mathrm{r}\mathrm{s}88$it”$\mathrm{g},$$OR/MS$ Today 26(1999), 64-Sl[6] M. R. Garey, D. S. Johnson: Cornputevs and Intractability: A Guide to the Theory of NPCompleteness, Freeman and Company, Sap Francisco, 1989.
[S] P. Kouvelis, G. Yu, Robust Discrete Optirnization and Its Applications, Kluwer, Dordrecht,

1998.

. B. KrZRsj, “Ot
it tree IPgrspY
IuateR }Proc. $Amer\tau can$ Math. Society, $7(1956)$ , 48-50.

[$\mathrm{b}\mathrm{H}\mathrm{F}$[$9\mathrm{H}\mathrm{H}$$\mathrm{t}\mathrm{Y}\mathrm{e}$$\mathrm{R}$$\mathrm{s}\mathrm{t}\mathrm{t}$$\mathrm{s}\mathrm{t}$$\mathrm{g}$[10]. . KZYt , “ Ye HZt gsrist 8 etYH ffl
Quaterly, $2(1955),$ 83-9S.
$\mathrm{G}$$\mathrm{t}\mathrm{Y}\mathrm{e}\mathrm{s}$$\mathrm{q}$$\mathrm{R}$Fflgt 8 et$Comb\mathrm{i}nato\tau xal$

[13]$\mathrm{L}$”$\mathrm{t}\mathrm{Y}\mathrm{e}$trsveJjit$\mathrm{t}\mathrm{p}\mathrm{r}\infty.\mathrm{e}8,$”

Rjeffl st$\mathrm{g}$$\mathrm{p}\mathrm{r}\infty.\mathrm{e}8,’$’

Naval Research Logistics

M. Nauss, $Paramet_{tZC}$ Integer Prograrnrning, Univ Missouri Press, Columbia,[11] C. H. Papadimitriou, K. Steiglitz,
Prentice Hall, Englewood Cliffs, 1982.
[12]

I$\mathrm{M}\mathrm{I},$$19\mathrm{S}9$.

Optimization: Algonthrns and Complenty,

A. Wolsey, Integer Prograrnrning, John Wiley & Sons, New York, 1998.
, 2005.
PRESS-MP, http:$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{d}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}.\mathrm{c}\mathrm{o}\mathrm{m}$茨木俊秀, 組合せ最適化 0 分枝限定法を中心として, 産業図書,, 1983.

$\lceil.14]\overline{\prime f\backslash \mathrm{i}}*(\#\ovalbox{\tt\small REJECT},$$\mathrm{i}15|$$\#\mathrm{E}_{\square }^{\Leftrightarrow}\dashv \mathscr{L}_{\mathfrak{B}}^{=}\ovalbox{\tt\small REJECT} l\mathrm{b}- 4\#\mathrm{f}\mathrm{f}\mathrm{i}\beta \mathrm{E}i\Xi \mathrm{f}\mathrm{f}\mathrm{i}k\mathrm{q}_{1_{\mathit{4}\llcorner\backslash l\mathrm{i}\text{し}T}^{\backslash }},$$\mathrm{g}\mathrm{g}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$今野浩
A-7 , 鈴木久敏 (編), 整数計画法と組合せ最適化, 日科技連,, 1982.
$\mathbb{S}t_{\square }^{\epsilon},$$\ovalbox{\tt\small REJECT}*\mathfrak{M}(\ovalbox{\tt\small REJECT}),$$\mathrm{g}\Re_{\mathrm{n}}^{-}\approx \mathrm{F}\mathrm{u}\not\in \text{と}\ovalbox{\tt\small REJECT}\exists_{\mathfrak{Q}}^{\mathrm{A}}\#\ovalbox{\tt\small REJECT} \text{適}l\mathrm{b},$$\mathrm{E}\exists\#\square \mathrm{f}\mathrm{f}\mathrm{i}\ovalbox{\tt\small REJECT}$

今野浩, 整数計画法, 産業図書, 1981.

$\lfloor 1\ulcorner 6]\mathrm{A}\neg \mathrm{S}\mathrm{P}-,$$\not\in \mathscr{L}\mathbb{H}_{\Xi}^{\cong}$$\mathrm{g}\text{数}\overline{\underline{\cong}}+\mathrm{F}\mu \mathrm{f}\mathrm{f}\mathrm{i},$久保幹雄, 田村明久, 松井知己 (編), 応用数理計画ハンドブック, 朝倉書店,, 2002.

$\lceil 1\mathrm{q}\mathrm{A}\mathrm{f}\mathrm{f}\mathrm{f}\mathrm{i}\#\mathbb{R},$$\mathrm{f}\mathrm{f}\mathrm{l}\hslash \mathrm{t}\Re p_{4},7_{\mathrm{A}^{\mathrm{Y}}}’\#\mathrm{f}\mathrm{f}\mathrm{i}\Xi(\ovalbox{\tt\small REJECT}),$$r_{\llcorner\backslash \mathrm{f}\mathrm{f}\mathrm{l}\mathrm{f}\mathrm{l}\ovalbox{\tt\small REJECT}_{\mathrm{p}}^{-}*\text{画}r\backslash \sqrt[\backslash ]{}\mathrm{b}^{\theta}7\mathit{1}i^{r},\mathfrak{F}\ovalbox{\tt\small REJECT}_{\mathrm{H}}^{\yen}\mathrm{E}}\backslash \iota$

榊原静, 中森眞理雄, ベクトルコストによる割当て問題について, 日本 OR 学会春季研究発表会,,.
2-D-5、東京農工大,$\lfloor 18]\mathrm{f}\#\ovalbox{\tt\small REJECT} F,$$\zeta \mathrm{f}^{1}\Phi_{\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}}^{\Leftrightarrow},$$\wedge^{\backslash }p\text{ト}J\iota r\supset 7_{\backslash }\text{ト}\mathrm{t}^{-}\llcorner B;\text{る_{}\mathrm{p}}^{3|l^{\backslash }4\text{て}5\mathrm{f}\mathrm{f}\mathrm{i}\ovalbox{\tt\small REJECT}\mathrm{F}_{\mathrm{L}}^{-}\supset \mathrm{t}^{1^{\vee}}T}.,$$\mathrm{H}18.3.1\mathrm{S}$$\mathrm{B}\text{本}$$\neq^{M_{-}\mathrm{A}}\mathrm{Z}\mathrm{g}\not\equiv \mathrm{f}\mathrm{f}\mathrm{l}\mathrm{f}\mathrm{l}\not\cong \text{表_{}\mathrm{I}}^{\mathrm{A}}$