大 規 模 数 理 計 画 の 解 法 に つ い て

23

大 規 模 数 理 計 画 の 解 法 に つ い て 若 林 信 夫

1.序

本 論 文 は大 規 模 な数 理 計 画問 題 の解 法 に おけ る最近 の い くつ か の発 展 を管 理 科 学 の 立場 か ら批 判 的 に検 討 す る こ とを 目的 とす る。

数 理 計 画 法 が経 済 学 の 資源 配分 の数 学 的 解 明か ら出発 し,計 算機 利 用 と密 接 に結 び つ い て1/4世 紀 を経 過 した。 そ の間,資 源 は経 済 学 の カテ ゴ リに と

ど ま らず 全 ゆ る科学 ・技術 の対 象 とす る ものに 拡 大 され た。 対 象 と され るシ ス テ ムは 例 外 な く複 雑 で大 規 模 で あ る。 た とえば,国 民 経 済 シス テ ム,企 業 シ ス テ ム,輸 送 シ ス テ ム,通 信 シス テ ム,計 算 機 シ ス テ ムを考 え てみ る。 こ れ らは,す べ て 多数 の要 素 とそ れ ら要 素 間 の強 い 結 び つ き,構 成 要 素 の多 様 な動 作 制 御,あ るい は そ の シス テ ムの 内外 の処 理 すべ き大 量 の情 報 とい った

さ まざ まな要 因 で 説 明 され よ う。

これ らシ ス テ ムの研 究,設 計,構 築 は,何 らか の意 味 で多 数 の制 約 の も と で 特定 の 目標 を最 適 にす るに は ど うす るか とい うこ とに関 わ ってい る。 い わ ば,数 理 計 画 法 を解 い て い るので あ る。

数学 的 に 厳 密 な 定 式 化 が な され た 資 源 の 合 理 的 配分 の 問 題 で あれ ば, Kuhn‑Tucker条 件 に よ りほ ぼ ル ーチ ン的 に 解 の 特 徴 づ け が 可 能 で あ る。 こ れ は1950年 代 始 め に 知 られ てい た。 しか し 解 の実 現 過 程 に な る と原 理 的 に 解 の存 在 や 収 束 が保 証 され て も,無 限 の 期 間 の 後 に はそ うな るで あ ろ う とい う程 度 の 認識 で あ った。 い いか えれ ば,解 法(算 法)と か 収 束 率 とか 計 算 の 手 間 とい った問 題 が 十 分 考 え られ な か った 。

また,資 源 配分 問 題 が 「教 育 上 の練習 問 題 」 か ら手 を 離 れ て,実 用 的問 題 に な る と必然 的 に大 規 模 構 造 に な る。 こ こに,大 規 模 とは 単 に 変 数や 制 約 式

が 多 くな る(大 次 元化)だ け で は な く,そ れ らの間 の 関連 が特 殊化 され,構 造 は ス パ ー ス(過 疎)性 を 帯 び て くる。 具 体 的 に述 べ よ う。 多数 期 間 に また が る動 学 的 計 画 問 題 は,各 期 の制 約 式 や 変数 をreplicateす るため に ス パ ー ス構 造 とな り,多 数 の事業 部 を もつ多 部 門(多 角)経 営 体 は,特 殊 な ネ ッ ト

ワー タ構造 を もつ サ ブ シス テ ムの階 層 と して スパ ー ス構 造 に な って い る。

大 規模 系 に 加速 す る要 因 は,組 合 わ せ論 的性 格 つ ま り,各 変 数,各 条 件 の 組 合 わ せ が 無数 に あ る こ とに も よ る。 機 械 部 品 の組 立 て,道 順,ス ケ ジ ュー

リン グは や は り資 源 の組 合 わ せ 論 的 な配分 の 枠 内 に あ る。

また,確 率 的 性 格 を有 す る こ とも大 規模 系 に させ る。 不 完 全 に しか知 られ てい な い事 象 は確 率 変 数 と して処 理 し,確i率 模 型 を作 るに して も最 終 的 に解 を 求 め るに は確 定 近 似 しなけ れ ば な らな い た め で あ る。 同 じこ とは,問 題 の 非 線 形 性 を線 形近 似 して解 く場 合 に起 り,や は り大 規 模 化 す る。

要 す るに,大 規 模 系 は 問 題 そ れ 自体 の大 規 模 性 と,解 法 上 仕 方 が な く大 規 模 に な る場 合 が あ る。

さて,数 理 計 画 法 の解 法 を 考 え る さい,ダ ン ツ ィク(G.B.Dantzig)の 単 体 法(SimplexMe七hod)と そ の 変 形 が圧 倒 的 な成 功 を お さめ て きた こ とは 多 言 を要 しない 。線 形 計 画法(LP)に 限 らず2次 計 画 法(QP),非 線 形 計 画 法(NLP)のMAP(MethodofApProximationProgram)版 は,単 体法 を 直接 継 承 して い る し,後 に 述 べ るい くつか の新 解 法 も中途 に お い て単 体 法 の 恩恵 を受 け て い る。

単 体 法 あ るい は数 理 計 画 の殆 どす べ て の解 法 は手 計 算 も可 能 で あ るが,計 算機 の発展 な しに は考 え る こ とが で き ない。P.Wolfe[24]等 に よって 図1 を作 成 す る と,こ の 図か ら数 理 計 画 法 の計 算 機 の処 理 能 力 の 飛躍 的 な発 展 を み る こ とが で き よ う。 もち ろん この要 因 は,計 算機 械 の 発 達 と,計 算技 術 と か プ ロ グ ラ ム技 術 の総 合的 見地 か ら説 明 され ね ば な らな い が 線 形 計 画法(単 体 法)の 計 算 技 術 だ け を とって も次 の よ うな発 展 が あ る。 主 単 体 法 か ら改 訂 単 体法 へ,最 低 の 反 復 回数 を 志 向す るMINIT算 法,基 底 逆 行列 の 積 形 式 か ら逆 行列 の再 逆 転 化 技 法 へ(以 上,記 憶 容量,計 算 の手 間 の観 点 か ら),

̀

大規模数 理計画 の解法 につ いて ²⁵

1,000

計簿

間100 (log)

む95⊥ll←ー1十ーー十‑m蜘㎝㎜

101

計算能力(式数)

60分(8K704)

IBM 22.5分(32K704)

220秒(32K704SP)

●46秒(7090SP)

・28禾 少(7090) の10秒(360)

図1数 理計画と計算機の能力の関係

＼

BartelsandGolubのLU分 解(数 値 の 安 定 性 の 観 点 か ら),あ る い は, ForrestandTomlinら の ス パ ー ス 性 を 考 慮 した 特 殊 な分 解 法,GUB(一 般 化 され た 上 限 法),初 期 基 底 解 を 強 化 す る各 種 の 方 法(た とえ ばScolnikの 解 法[33コ,Chretienneの 解 法)な ど。

しか し直 面 す る 数 理 計 画 問 題 が 大 規 模 に な る に つ れ,始 め か ら単 体 法 の 系 列 に 頼 り き りに な る の は 記 憶 容 量,解 の 精 度,計 算 速 度,計 算 の 手 間 あ る い は これ らを ま とめ た 計 算 の コ ス トの 面 か ら非 効 率 な い し無 理 が 生 じ る。 超 大 型 の 計 算 機 に よ らな くて も 中 型 程 度 の 計 算 機 で 同 程 度 に 大 規 模 な 問 題 が 望 む 精 度 で 解 け る こ とが 一 般 に 望 ま しい 。 そ の た め の工 夫 に は 単 体 法 に か わ る多 数 の 新 案 な り代 替 案,補 完 案 が あ る で あ ろ う([12コ)。 そ の 中 で 逐 次 近 似 の 反 復 解 法 は 有 力 な 方 法 で あ る と思 わ れ る。 計 算 機 が 利 用 可 能 に な る 以 前 か ら,

ソ連 の(ノ ー ベ ル経 済 学 受 賞 者)レ オ ニ ー ド ・カ ン トロ ビ ッチ は 試 み て い る し,最 近 で は,や は り ソ連 の シ ョル,エ ル モ レ フ らの キ エ フ の キ ベ ル ネ テ ィ ク研 究 者 が,欧 米 に 非 微 分 可 能 な 関 数 の 極 値 解 法 を 「輸 出 」 して い る の は 興 味 深 い こ とで あ る。 大 規 模 系 に 応 用 され た 最 近 の 反 復 解 法 は,区 分 的 に ス ム

ー ス な 関 数 が 直 接 現 わ れ た り,問 題 を 縮 約 して 微 分 可 能 で な い 関 数 を 問 題 に す る こ とが 多 い 。 た と え ばF(X)=maxf(X,y)はfが 微 分 可 能 で あ っ て も

シ

F(x)は 微 分 可 能 とは 限 らない(例 えば,F(x)・=max(x+y,x‑y)を 考 え よ)。 そ の場 合,通 常 の傾 斜法 や ペ ナ ル テ ィ関 数 は 若 干 の 修 正 を必 要 とす る。

さ らに,重 要 と思 われ る のは,問 題 を 短絡 して,非 微 分 可 能 な制 約 つ き極 値 問 題 を 扱 う とき,元 の美 しい線 形 性 な り,組 合 わ せ論 的 な性 質 が 強 引 に 消滅 して しまわ な いか とい うこ とで あ る。 結論 的 に は,変 形 に と もな い元 の構 造 が 崩 れ,近 似 解 と しての 役 割 に 追 い や られ る。 しか し大 規 模 系 で は,莫 大 な コス トが かか る とか,何 も得 られ な い よ りは ま しで,そ れ が 許 され るの で あ る。

この論 文 は,数 理 計 画 法 の 「大 規 模性 」 の観 点 か ら,上 述 の現 在 の さ まざ まな動 向 を展 開 し批 判 的 に検 討 す る こ とを 目的 とす る。 そ の構 成 は まず 関 数 に適 当 な次 数 の 微分 可 能性 を仮 定 す る と きの最 適 化 手 法 が展 開 され る。 次 に 大 規 模 問 題 の解法 に 向 い て い る一 般 化 傾 斜 法 を展 開す る。 こ ごまで は反 復 解 法 に も とつ くアル ゴ リズ ムを 中心 に考 え て きた が,最 後 の 節 で は何 らか の ア ル ゴ リズ ムを組 込 ん だ一 般 的 な数 理 計 画 シス テ ム の設 計 ない し利 用 上 の問 題 点 を述 べ る。

一な お

,大 規模 数 理 計 画 の従 来 の 研究 動 向に つ い ては,文 献[6],[8],[14コ が 参 考 に な る。 本 稿 は,こ れ らを さ らに斬 新 な もの に して い る。 また紙 面 の 制 約 上,多 数 の数 値 計 算 の結 果 は別 に報 告 す る予 定 で あ る。

2.大 規 模数 理 計 画 問 題 の解 法

大規 模 数 理 計 画問 題 は次 の よ うな非 線 形 計 画 問 題(最 適 問 題)と して定 式 化 され る。

,minf(x)(1)

m∈X

こ こ で,x=(x1,x2,…,Xn)は,n次 元 ユ ・一 ク リ ッ ド空 間Enに 属 す る ベ ク トル,f(X)は 連 続 な 実 数 値 凸 関 数,Xは 制 約 集 合 で 問 題 に 応 じ種 々の 形 を と り,後 に 特 定 化 す る。 こ こで と くに ノ(κ)に 微 分 可 能 性 を 仮 定 しな い こ と に 注 意 を 要 す る。 た とえ ば,f(x)=maxf(x,y)は,一 般 に 区 分 的 に 凸 な

ン

関数 で あ り,こ の よ うな場 合 に,帰 着,しうる多数 の大 規 模 問 題 を 見 出す こ と

大 規模数理 計画 の解法 につ い て 27

が で き る。

問 題(1)の 解 法 は ・ コ ー シ ー(1874年)の 傾 斜 法 に 遡 る古 い 歴 史 が あ る カ㍉

関 数 ∫(わ に,ス ム ー ス な 関 数 を 仮 定 して い た 。 ス ム ー ス で な い 関 数 の 極 値 問 題 は ソ ビエ トの シ ョル(皿Iop)が1962年 大 規 模 ネ ッ トワ ー ク問 題 を こ の 型 の 極 値 問 題 に 直 して 解 い た こ とに 始 ま る とい わ れ 歴 史 が 新 しい 。 こ の 方 法

は 欧 米 が 輸 入 し,亜 傾 斜(subgradient)法 と よ ん で い る が,本 論 で は ソ ビエ ト風 の 「一 般 化 傾 斜 法 」 を 採 用 し,こ れ を め ぐ る議 論 を 展 開 して い きた い 。

2.1.問 題 の 帰 着

実 際 的 な 大 規 模 数 理 計 画 問 題 は 制 約 式 の 係 数 か らな る制 約 行 列 に 何 らか の 構 造 を も っ て い る。 制 約 式 が 線 形 か 近 似 線 形 化 可 能 な,い わ ば 線 形 構 造 を 想 定 す る場 合 が 多 い 。 以 下,種 々 の 大 規 模 問 題 が(1)に 帰 着 し う る こ と を 丞 す 。

例1.多 数 の 行 を もつ 数 理 計 画 問 題

制 約 式 に 多 数 の 行 を 含 む 大 規 模 数 理 計 画 は 制 約 式 部 分 をMl行 とM2行 の2つ に 分 け て 考 え る。 す な わ ち 線 形 計 画 で あ れ ば,maxdx,s.t.廊 一δ, ASx=・bS,x≧0に な る。 こ こ で,多 面 体P・ ・{xlAsx!=bs,x≧0}は 有 界 と し,

そ の 端 点 をxゴ とす れ ば,多 面 体 の 定 義 か ら,x一 Σλdxd,Σ2d・=1,λ ゴ≧0で

ゴ' あ る 。 よ っ て,

max[Σ(cxV)RdlZl(Ax」)R」 ・=b,Σ λ」=‑1,λ 」≧0}

2、,22・… ・1,ゴ'j

で あ る。 こ の と き,λ 」を 求 め る 問 題 に な った 。 双 対 問 題 は,minカ'b+Po, s.t,P'Ax」+P。 ≦c'x」,η,で ある か らPoを 消 去 す る こ とに よ り,minf(P)

とな る。 こ こ で,f(P)‑max[c'x」‑P'(Ax」 一一b)]で あ る。 基 本 式(1)へ の 帰 着 が 実 現 され た 。maxdxの 代 りにmaxΣ 乃(Adx)(カ は 凹)の よ うな 分 離 型 の 非 線 形 計 画 に つ い て も周 知 の 方 法([刀)で(1)に 帰 着 され うる。 この

こ とは,以 下 の 数 例 に も妥 当 す る。

例2.ブ ロ ッ ク角 状 分 解 型 の 数 理 計 画

ブ ロ ッ ク角 状 分 解 とい うの は,制 約 式 を タ ブ ロ ー形 式 に した と き個 々 の ブ ロ ッ クを カ ッ プ リン グ 式 に よ っ て 統 合 化 した 形 に な っ て い る も の で あ る。 こ

の 型 に 属 す る問 題 は,Dantzig‑Wolfe型 と も い わ れ,経 済 や 企 業 の 分 権 計 画 やHitchcock‑Koopmansの 輸 送 問 題 や 多 品 種 ネ ッ ト ワー ク問 題 が 属 す る。

れ れ

maxΣCi'Xi,s.t.ΣAiXi=bo ,BiXi≦bi,Xi≧0と 表 わ せ る 。 双 対 ラ グ ラ ン ジ ュ

ごコ ユ ざコ 

形 式 は ΣAiXi=boに 対 応 す る 双 対 変 数 ρゴ を も っ て,maxΣCiXi+Pd' (ΣAiXi‑bo),s.t.BiXi≦bi,Stri≧0と 書 け る 。 よ っ て,min{Σmax(CiXi

P,≧oi=1Xi≧ 。

+Pゴ'AiXt):BiXi≦b}を 得 る。 い ま制 約 集 合Pi‑{XilBiXi≦b,}が 有 界 で あ れ ば,線 形 計 画 問 題 の 最 適 解 は 常 に 制 約 集 合 の 端 点 で 起 るか ら端 点 を 疹 初 と

れ

す る と 上 の 問 題 は,minf(P),こ こ で,f(P)=Σmax{CiXi(k)+〆 魂 貌(k)}

P≧Oi=1mi(k)≧0

とな り,(1)へ の帰 着 を 知 る。

例3.双 対 角 状 の分 解型 の数 理 計 画

例2の 双対 版 で,こ の型 に直 接 属 す る問 題 に は多 数 期 間 に わ た る投 資 計 画 問 題 が あ る。

れ

minΣb,'Xi+bo'Y,s.t.Bi'Xi+Ai'ツ ≦o♂(i・‑1,2,…,n),〃i,ツ ≧0

憲=1

上 の 問 題 はP,≧0を 固 定 す る と 制 約 式 の 部 分 がB掘 ≦Oi'・‑Ai'Y(i‑1,2,れ

…,n)・Xi≧0(i・ ・1,2,…,n)と 書 け る か ら,min{max(Σbi'Xi+bo'p,):

y≧0≧Oi=1 あ

B掘 ≦Ci'一 』 か,i==1,2,…,n}と な る 。 制 約 式B掘 ≦Ci'・‑Ai'Yに 対 す る ラ

グ ラ ン ジ ュ 乗 数 を ρ盛 と す る と,上 の{}内 の 双 対 は, max[ΣP,(c,'一 ・4げ)十bo'ツ4)f∠4♂ ≧oノ,Pi≧OJ=1,2,…,n]

Pi

と な る 。 こ こ で 例2と 同 様,制 約 集 合P,={A[P,A,'≧cl,ρ 之o}が 有 界 で あ る と す る 。 そ の と きPiの 端 点 をPi(k),h‑1,2,… と す る と 結 局

minノ(y)た だ し,f(ツ)=・max[2]P,(k)(Ci'‑Ai'ツ)十bo'ツ]

れ

y≧oPi(k)t=1

を 得 る。

例4.確 率 的 計 画 法(不 確 実 性 下 の 二 段 階 計 画 法)

問 題 の 係 数 や 定 数 が 正 確 に は わ か らな い が そ の 確 率 分 布 は 所 与 で あ る,い わ ゆ る確 率 的 計 画 法 を 二 段 階 法(hereandnow)で 解 く と し よ う。

問 題 は,min[ΣCi」Vi+E(x)],s.t.x≧0で あ る 。 こ こ でE(x)は 関 数

i==1

大規模数理計画の解法について ²⁹

sc,(x,ω)の 数 学 的 期 待 値 を 表 わ しg(x,ω)は 問 題:minΣhigi,s・t・z≧0・

D2≧bw‑Axの 解 で あ る 。bwは 確 率 変 数 で あ る 。 い ま,有 限 個 の 値b.(Pt==

1,2,…,h)を と る と す れ ば,上 の 問 題 は

れ ゐ

mil1[1:ci〃i+Σ ク。(Σhieの],S.t.Ax+Dg。 ≧b。

i=1r=1

(7=1,2,…,h),x≧0,2。 ≧O,r=・1,2,…,h と な り 例3の 問 題 群 に 帰 着 す る 。

以 上 種 々 の 大 規 模 数 理 計 画 の(1)へ の 帰 着 を み た の で,次 に こ の 種 の 問 題

の 解 法 に つ い て 考 え る 。 、

2.2.数 学 的 準 備

以 下 で 必 要 と な る 数 学 的 概 念 を 証 明 な し に 述 べ る 。

ス カ ラ ー 積 〈x・ly>〒=Σ 鈴 二地(=x'y)・(ユ ー ク リ ッ ド)ノ ル ム ・llxlト<x・x>巷 ・

̀ロ1

距 離a(x,y)=1匪 一 ッ1,ρ(x,X)=‑inf睡 一 酬 を 定 義 す る 。 y∈x

f(X)がXの 上 の 実 数 値 関 数 で あ る と き,そ の 最 大 値 の 集 合 は{Cl,∈X:

f(),)=・maxf(め}でx∈x あ る。fがxを 含 む あ る 開 集 合Xの 上 で 凸 関 数 で あ る と す る 。 そ の と きOf(X)・ ・{P∈En:<P,y‑‑X>≧f(y)‑f(X),VPt∈X}を

関 数fの 点xで の 一 般 化 微 分(subdifferen七ial)と い い,Pを 一 般 化 傾 斜 (subgradiePt)と い う 。 集 合Of(〃)が1点 ρ か ら な る 必 十 条 件 は,凸 関 数 ∫ が κ の 近 傍 で 有 限 か つ 万 で 微 分 可 能 で あ る こ と で あ る 。 そ の と き,

画 ω 《 霧 ・…,霧)で あ る.こ こで 舞 撫 ∫(方十λθλ)一ノ ∫⑦ 一

<7f(x)・ed>(6ゴ は 第 ブ 要 素 が1他 は0の ベ ク トル)で あ る 。f'(x;),)一

蹴 、吻 〉柵 梱 ㌍ α)で あ り,こ商 の片側方向微係数と

か 餌(〃)の 支 持 関 数 とい う。∫'(絹 θゴ)一砺/∂κゴを ∫'(の で 表 わ す 。(ベ ク ト ル の 転 置 の'と は 文 脈 か ら識 別 さ れ る 。)

大 次 元 の 問 題 や 偏 微 分 を 計 算 す る の が 面 倒 な と き,一 一般 化 傾 斜 法 は 一一回 の 反 復 に 相 当 の 手 間 が 予 想 され る。 そ こで 一 般 化 傾 斜(∫')を 確 率 的 に 選 択 す

る こ とが 勧 め られ る。 た と え ば,

f!(xt)一 急 ∫(xt+4袈)‑f(xt)

とす る。 こ こ でhkは そ の 要 素 が[‑1,1]の 上 で 一 様 に 分 布 す る確 率 ベ ク ト ル で あ る 。 ま た,添 字 ≠は 反 復 段 階 を 表 わ す 。

一 般 化 傾 斜 を2つ の 逐 次 的 な 傾 斜 の 差 の 方 向 に 空 間 を 拡 張 ま た は 縮 小 す る 計 算 方 法 も あ る([27コ 参 照)。 ま た,f(x)==・max(乃(x))の 場 合,一 般 化

'∈ 」

傾 斜f'を 求 め ず に,非 線 形 計 画minv・s・t・f」(x)rV≦0を 解 く こ と も あ る (〔8])が,ゲ ー ム 理 論 か ら 推 察 さ れ る よ う に 大 規 模 向 き で は な い 。

次 に 射 影 演 算 子(projectionoperator)の 概 念 を 導 入 す る 。 点xの 集 合

●Cの 上

へ の 射 影 と はllx‑「Pc(x)ll'・ ・infllx‑yliと な る 点Pc(x)∈Cの こ と

γ∈ σ

で あ る 。 こ こ でCは 閉 凸 集 合,ノ ル ムMiは ユ ー ク リ ッ ド ノ ル ム と す る 。 Pe(X)は 以 下P(X)と 書 い て も 混 同 は な い で あ ろ う 。 そ の と き,次 の 性 質 が 成 り 立 つ 。

[1]ベ ク トルx‑P(x)は,点P(x)でCに 支 持 的(supporting)で

あ る 。 す な わ ち,任 意 のy∈Cに 対 し で,〈x‑P(x)・y‑P(x)〉 ≦0が 成 り た つ 。 も しCが 強 く 凸 で,xeC・Pt≠P(X)・O,∈Cで あ れ ば,≦ は く に 置 き か え ら れ る 。

[2]射 影 演 算 子P(x)は 縮 小 的(contractive)で あ る,す な わ ち, llP(x)・ 一一P(y)il≦lix‑yli。

[3]ilp(x)一 ツli≦llx‑:ソ11

[4]点xか ら 超 平 面h(x)・ ω'x+ωo‑Oへ の 距 離 は 制 約h(x。)===ω'x。+

ωo‑0の も と でVx‑xr[12を 最 小 に す る こ と に よ り 得 ら れ,lh(x)1/Hwnで あ る 。

[5]kxの 超平面 の上一の 射影 はPα)… 辮 叫 こよって与 え ら れ るb

2.3.最 適 問題 の 伝 統 的 解 法一 傾 斜 法一

この節 で は 関 数 ∫(め が 微 分 可 能 で あ る場 合 の最 適 問 題(制 約 な し,制 約 付)に 対 し現 在 どの よ うな方 法 が あ り,大 規 模 計 画 の観 点 か らす る とどの よ

大規模数理 計画 の解法 につ いて ³¹ うな 評 価 が 可 能 で あ る か 簡 単 に 述 べ る。

[制 約 な しの 最 適 化]実 用 段 階 また は経 済 的 に 意 味 の あ る の は 制 約 が あ る 場 合 の 最 適 化 で あ る が,制 約 な しの 最 適 化 は,そ れ 自身 の 発 展 の み な らず 制 約 付 最 適 化 の 手 足 と な っ て い る。'

問 題(1)に 対 し伝 統 的 に 傾 斜 法(gradientmethod)が 採 用 され て き た 。 こ れ は,連 続 的 にi・=cr(t)'d(t),〃(0)==所 与 ま た は 離 散 的 にxt+i・ ・xt+αtdt., が 一所 与 と表 わ され る逐 次 反 復 公 式 に 沿 っ て 進 む 。 こ こで,ὰは ス テ ッ プ

轍 澱 段階画 ま探索方向という・朔@呵 霧 …認 轟

は 騰 の ときZ(‑thth)hf(x‑‑h)で 計 算 され る.囎 法 の手 続 きは,(i)探 索 方 向 の 決 定,(ii)ス テ ップ幅 の 決 定,(iii)収 束 の 判 定 か ら な る。(ii)の αtの 決 定 か ら先 に 述 べ る と,α δ(α>o)はF(α)一 ノ(xt+αdり を 最 小 に す る

よ う決 め られ る の が ふ つ うで フ ィボ ナ ッチ,黄 金 分 割 系 統 ρ も の と 内 挿 系 統 の も の が あ る。 次 に(i)め 探 索 方 向 〆 の 決 め 方 に つ い て 述 べ る。 最 も単 純 な も の は 最 急 降 下(steepestdescent)法 でat‑‑gt‑一 一7f(xt)と す る も の で あ る。 これ は 簡 単 で あ る が ジ グ ザ グ現 象 を 回 避 で きず 収 束 が 悪 い 欠 点 を も つ 。 次 に 共 役 傾 斜(conjugategradient)法 が あ る。 これ は 傾 斜 だ け で な く 以 前 の探 索 方 向 を 考 慮 し

〃一一+亀 朗 一一+誹 覗 み 一'

な る公 式 で 探 索方 向 を きめ る。 共 役 傾 斜 法 は2次 収 束 が可 能 で,記 憶 容量 も 少 な く済 む の で大 規 模 問 題 に は 好 適 で あ る([20コ)。2次 収 束 とな る理 由は共 役傾斜法薩 本的に2次 関数 ∫の 一去 曲+b'x+c(Aは 対称正定値)撮

小 に す る 方 法 で あ る か ら。‑9(x)‑7f(x)=Ax+bよ り 一9(x*)=Ax*+b

=‑O ,よ って 線 形 方 程 式 を 解 く こ と と2次 関 数 の 最 小 化 は 同 値 で あ る 。 問 題 は 収 束 の 速 さ と関 連 す る数 値 の 安 定 性 に あ る。

最 後 に 可 変 計 量(VariableMetric)法 に つ い て 述 べ る 。f(x)が 上 の よ う に2次 関 数 な ら,解 がx*=・‑A‑tbで 結 局,x*=・x‑A'lgと な る 。 こ の と き 逆 行 列A'‑1の 近 似 行 列Hと し て 何 か い い 行 列 を 反 復 的 に も 汐 て く る こ と に

ノ

よ り,収 束 を 速 め よ う と い う の が 可 変 計 量 法 の ア イ デ ア で あ る 。 こ の 方 法 は 共 役 傾 斜 法 の よ う にxoを 任 意 に と り,xt+1‑xt+crtstで 反 復 的 に 改 訂 し て い く。 こ こ で,st‑Htgtで あ り,HtはDFP(Davidon‑Fletcher‑Powell)

法の胎 酬 一碑 齢 讐i罫 瑞 一研 一〃(x・+・)‑7f(x・)VC

よ る 。 現 在 最 も 効 果 的 と い わ れ るOrenのSSVM(Self‑ScalingVariable

M・t・ic)法に よれば 酬 一ト ㌻ 課̀+・ ・V・V・・]rt+li誓1・ここで・

ブー ツ講(1一 φ8)+識 、鰍 一(〆 研 ダ)垂(毒 一 ッ腸)・<伽 〈・

で あ る。

可 変 計 量 法 は 前 の どの 方 法 よ りも 収 束 が速 く,H行 列 に ス パ ー ス行 列 技 法(コ レス キ ー分解 な ど)を 用 い る と非常 に 効果 的 で あ る といわ れ る。 しか し,こ の方 法 は1回 に要 す る 計 算 量 が 多 い うえ に,H行 列 のた め の 記憶 コ ス トが か な り大 きい ので,大 規 模 な 最適 問 題 に は疑 問 で あ る。

[非 負 条件 下 の最 適 化]非 負条 件x≧Oを 明確 に 制 約 式 に 追 加 したmin

T∈x

f(x),x≧0は 経 済 問 題 と して 重 要 で あ る。xがfを 最 小 に す る必 要 条 件 は x+∠ 〃≧oの よ うな す べ て の ∠〃 に 対 してVf(x)∠x≧oと な る こ とで あ る。

または 絢窄 鍼 力繋(1習 のとき である・ したがって・最急 ノ

降 下 の 傾 斜 法 に よ れ ば,次 の よ う に な る 。 い ま,‑Pit・=Pit(x)

一{1観

し1錨 分小 の正 数 かDOf/∂ 」Vi>oの とき'と お くと・ 出鼎

xo≧6か ら 始 ま り,〃1,x2….を 次 の よ う に 生 成 す る 。xtを 与 え た と き ベ

ク トル 腔 一錆 乃(の 藷 と い 塊 κ・畷 に よ り反復 させ る.

ス テ ッ プ 幅 αtは0≦ ὰ≦Lt≡ …sup{α:xt‑‑crgt≧0}でf(」tt一 αtgt)を 最 小 に す る 値 で あ る 。

共 役 傾 斜 法,可 変 計 量 法 に 対 し て も 非 負 条 件 は 同 様 に 考 慮 さ れ る 。 [制 約 付 最 適 化]一 般 的 な 制 約 条 件 を 考 え る た め に 制 約 集 合 をX‑

{x∈En:9(x)≦O・h(x)‑0・ κ≧0}と 具 体 化 す る 。'こ こ にg(x)・ 一(g1(x),̲,

大 規模 数理計画 の解法につい て ³³

9m(x))・h(x)=(h1(x),…,ht(x))は ベ ク トル 関 数 で 凸 関 数(線 形 関 数 を 含 む)と す る。m・n,1は か な り大 き な 正 の 整 数 値 とす る。

この 型 の 非 線 形 計 画 の 解 法 も基 本 的 に は 傾 斜 法 に 属 す る。 そ の理 論 的 成 果

(1)

は 既 に[2]に あ った が,数 値 計 算 の観 点 か らは緩 漫 な 収束 のた めに,あ るい は 制約 な し問 題 の 未発 達 のた め に 殆 ど実 用 化 され なか った 。今 日,計 算 機 利 用 に結 び つ きそ の解 法 に飛 躍 的 発 展 が み られ るが,そ の接 近 に は 制約 式 を 目

く  

的 関 数 と 独 自に 扱 うか,結 合 す る か の2種 類 あ る。 そ して そ の どち らが 優 れ た 解 法 で あ る か は 異 論 が あ る。 有 名 なC『lvilleの 評 価(1970年)は 大 ス テ

●ッ プ の 傾 斜 法 で 前 者 のGRG(GeneralizedReducedGradient)が,後 者 の SUMT(SequentialUnconstrainedMinimizationTechnique)又 は ペ ナ ル テ ィ法 よ りも1.36対0.78で 優 位 を 立 証 した が,そ の 後SUMTに 改 良 を 施 し全 く逆 の 評 価 づ け を 主 張 す る研 究 も あ る ⊂3])。 この 論 争 の 背 後 に は テ ス ト問 題 が 制 限 さ れ て い る こ と(大 規 模 問 題 は な い)や プ ロ グ ラ ム 技 術 も影 響 して い る と思 わ れ る。 大 規 模 処 理 の 見 地 か らはSUMT型 が 収 束 率,計 算 量 の 点 で 劣 って も記 憶 容 量(逆 行 列 を 必 要 と しな い)の 点 で 有 利 と推 測 され る 。 今 後 よ り一 層 の 実 験 の 積 み 重 ね が 必 要 で あ ろ う([32])。

また,主 ・双 対 法 は 主 変 数 と双 対 変 数 を ペ ナ ル テ ィ法 に よ り同時 に 改 善 し て い くも の で 最 も見 込 が あ る。 但 し前 提 と して 双 対 問 題 と双 対 変 数 が 確 定 さ れ て い る こ と を 必 要 とす る。 こ の 方 法 は 問 題(1)に 対 しp@)‑min7(x,の

あ  ゐ

を 得,次 に ρ(の を π に 関 し 最 大 化 す る 。 グ(%の と し て は 数 値 計 算 の 安 定 性 を 増 す た め に ラ グ ラ ン ジ ュ 式 に ペ ナ ル テ ィ項 を 追 加 す る 。y(X,U,r)==

f(X)十 Σ λ(8i(X),Ui,r)こ こ で

R(9・(x)・u…)一{瑠 ㍗8蛋(理1織=諺 ・〉・であ る([2・])e

し た が っ て ま ず(ut,7t)を 与 え,g(X・ 帆 の をX∈Xに 関 し 最 小 化 し

(1)傾 斜 法(勾 配 法)の 経 済 学 的,経 営 学 的 解 釈 と 幾 何 学 的 説 明 は,Arrowand Hurwicz[1コ お よ び 古 瀬[30コ を 参 照 せ よ.

(2)制 約 式 を 目的 関 数 に 結 合 す る こ と に よ り無 制 約 問 題 とす る 場 合,無 制 約 問 題 は 微 分 可 能 な ペ ナ ル テ ィ 関 数 よ り微 分 可 能 で な い 関 数 に す る方 が 有 利 と す る 研 究 が あ る.Conn[5コ 参 照.

xtを 得 る 。 次 に,(ut,rり を 下 の 反 復 法 に よ り 改 訂 し て(ut+1,〆+1)を 得 る 。 こ れ は,f(X),8ゴ(X)が 凸 関 数 で あ れ ば も と の 問 題 の 解 に 収 束 す る こ と が 示 さ れ る 。 要 す る に,,

9(x.u,r)==f(x)+Σ え(9i(x),Ui,r)・Ui≧0

ざ

Xit+1=max[O,x、̀‑tOtSPx(xt・ù・rt)]・i=1・2・ … ・n

{均̀+Lmax[0,U」t‑一 ρtg」(xt)],ク=1,̲,m

〆+i=Ptrt こ こで

t・t>O,ρ ￠→O,ΣP,=:。 。,Σ ρ̀2<。。

で あ る。

2.4.'一 般 化 傾 斜 法

伝 統 的 に は 前 述 の よ うに 微 分 可 能 な 関 数 の 最 適 化 で あ り,主 と して 傾 斜 情 報 を 頼 りに 最 適 値 に 近 付 く も の で あ る。 しか レ大 規 模 な 問 題 に 対 して は,問 題 を2.1.の よ うに 通 常 の 傾 斜 概 念 が 適 用 で き な い 数 理 計 画 に 還 元 した 上 で 解 く方 が 有 利 に な る。

以 下,ソ ビ エ ト流 の 一 般 化 傾 斜 法 と欧 米 の 新 しい 発 展 を 述 べ る。

[ソ ビ エ ト流 の 一 般 化 傾 斜 法]

問 題 はminf(x),x∈C1∩C2,C1⊂Enは 凸 集 合,C2・"{xlgゴ(x)≦0,ブ 驕1,

…,m}で あ る。 こ こで,f(X),8'(X)は 凸 で あ るが 必 ず し も微 分 可 能 で は な い(例 え ば,cuspを 含 む)と す る。

こ の 方 法 は 任 意 の 〃eか ら 出 発 し 次 の 反 復 過 程 か らな り,厳 密 に 収 束 が 証 明 され て い る。

xt+1=Pc(vt+xり1

こ こで,Pσ はC=C、 ∩C2の 上 へ の 射 影 演 算 子,xtは,計 算 され た8ゴ(め の 正 負 に 応 じて 次 の 値 を と る。

鵡 熱::1::1二1∴,

大規模数 理計画 の解法 につい て ³⁵

関 数 の 右 肩 の プ ラ イ ム は 一 般 化 傾 斜,ノ ル ム は ユ ー ク リ ッ ド ノ ル ム,λ εは, ス テ ッ プ 幅 で あ る 。 ス テ ッ プ 幅 λtの 選 び 方 で 収 束 の 緩 急 が き ま る,H.3.

ゆ

皿lop[26]は,limろ 一 〇,Σ λ̀=。 。lR̀>oで 幾 何 収 束 を 証 明 レ,後 に λt+1=

t→o◎t;e

λ̀》凋/σ(σ ≧ 〜/万 で か な り大 き くと る)と す る こ と を 提 案 した 。 しか し, λ̀は 単 純 な 指 数 関 数 で あ る の で 種 々 の 変 形 に よ り 収 束 を 速 め うる(例 え ば

2次 指 数 平 滑)。

ナ

ま た,線 形 不 等 式 の 緩 和 法(RelaxationMethod)に 類 似 し た 以 下 の 公 式 がB.T.nonflK[19]に よ り提 案 さ れ,収 束 を 速 め た 。

∫(κり 一 ∫*xt+1

=κ̀+γt ∫'(の

1げ'(xt)li2

こ こ で,0<γt<2,f*=・minf(x)で あ る 。 一 般 に,f*は 未 知 で あ る の で, 近 似 値fを 設 定 しf(xn)≦fかf(xn)≧f+ε,ε>oに 応 じ そ れ ぞ れf(x"),

1̲‑

7(f+inff(xn))を_π 新 た なfと す る 。

この 方 法 は,乗 算 回 数,記 憶 場 所 も少 くて 済 む 利 点 の 反 面,基 本 的 に 最 急 降 下 で あ る か ら,鳥 か ご ケ ー ス や 峡 谷 ケ ー ス の よ うな 収 束 の速 度 が 心 配 で あ

る。

以 下 の 定 理 は,一 般 化 傾 斜 法 がt番 め の ス テ ッ プ幅 をcrt・・αoαt(a〈1)と 選 べ ば,と に か く有 限 な 長 さで 収 束 す る こ とを 示 す(同 様 な 証 明 法 は[25])。

定 理f(x)はEnの 上 で 定 義 され た 凸 関 数,M*一{)・,∈En:f(y)=max

x∈X

f(X)}幸 φ,d(X,y)=}レ ー ッ{1乏 す る 。{X(S)蕗 を,f(X)に 一 般 化 傾 斜 法 を 適 用 す る こ と に よ り 得 ら れ るx(o)か ら 出 発 す る 点 列 と す る 。 こ こ で ス テ ッ プ 幅 α を 一 定 と す る 。 そ の と き 任 意 のx*∈M*に 対 し て1)f(Af(t))≦f(の, 2)t≦a2(x(。),x*)/α2,お よ び3)a(y,x*)≦ α と な る よ う な)tとyが 存 在

す る 。

証 明)Sxを ルち 一{〉,:f(y)≦f(x),xe、M*}の 支 持 平 面 で あ る と す る 。

鳥

与 え ら れ た 列{x(s)}ζ 一1か ら 点x(「)を 方ω ∈M*,Px・(「)がx*∈M*の5漬 。) の 上 へ の 射 影 と な る よ う 選 ん だ と す る 。 そ の と き,a2(x(「+1),〃*)=:(d(Px'(「),

x*)一 α)2+d2(x(「),x*)‑d2(.Px・(「),x*)‑d2(x(「),x*)一 一2αd(Px・(「),x*)+α2̲

(2)で あ る か ら,次 の2つ の 場 合 が 可 能 で あ る 。1)あ るt<[d2(x(o),x*)/α2]

に 対 し てa(Px・(t),X*)≦ α が 成 り 立 つ 場 合 。 明 ら か にf(X(̀))≦f(Px・(の)で あ る か らs)t・P.・(t)を 選 べ ば 確 か に 定 理 は 成 立 す る 。2)す べ て のt〈[d2 (x(o),x*)/α2]≡mに 対 し て,d(Px・(t)・x*)〉 α の 場 合 。 こ の と き(2)か ら d2(X(t+1),X*)≦a2(X(t),X*)一 α2す な わ ちd2(〆 ω ・κ*)≦ α2よ っ て,t・=m・

躍α)=ッ と お け ば よ い 。(証 明 了)

最 後 に 典 型 的 な 大 規 模 線 形 計 画 で あ る ブ ロ ッ ク 角 状 型 問 題 を 一 般 化 傾 斜 法 に よ っ て 数 値 計 算 し た 結 果 を 述 べ よ う 。

そ の 問 題 の(t+1)段 は 次 の よ う で あ る 。

(i)前 段 で 得 ら れ たx(t)に 対 し て 線 形 計 画(LP) f(X)=max[Σ δ融+〈X,0」 Σ オ%〉]

㍗∈R

を 解 く 。

(ii)反 復 法 に よ りX(t+1)を 生 成 す る

A・(t+・・一…{α 賜

ll三 塁銑}

(iii)停 止 規 則Ix(t+1)一 ・」V(t)1≦ε ま た はlf(x(̀+1))‑f(xり1≦ ε'に よ り ス ト ッ プ さ せ る かt←t+1と し て(i)に 戻 る 。

大 規 模 問 題 を 直 接,単 体 法 に 結 び つ け る の で は な く,上 の よ う に2段 階 に

1

す る こ と に よ り記 憶 容 量 を 小 さ く解 くの は 近 似 解 で 満 足 す る場 合 効 果 的 で あ る。 ミニ コ ン のFORTRANで,LPル ー チ ン を 別 に す れ ば50ス テ ー トメ ン ト以 内 で 書 け,ε 一10‑6に 対 し,t‑100〜120で 収 束 を み た6上 の 問 題 の よ う に 一 般 化 傾 斜 が 簡 単 な 場 合,文 関 数 を 用 い れ ば,'容 易 に(FORTRANで,

2,30行 で)高 速 高 精 度 に 解 が 得 られ る。i [欧 米 の 新 しい 発 展 コ

IBMのWolfe,Karp,Heldら が 一 般 化 傾 斜 法 を 巡 回 セ ー ル ス マ ン問 題 [10],割 当 問 題[11]に 成 功 的 に 適 用 した が,収 束 の 速 度 は ま だ 不 満 で あ っ た 。 一 般 化 傾 斜 法 と 線 形 不 等 式 の 緩 和 法 に よ る 関 連 か ら,そ れ を 発 展 させ

大規模 数理計画 の解法 につい て37 ゆ

て,線 形 不 等 式 の 共 役 傾 斜 法 に 結 び つ け る研 究 が 始 ま った 。 後 者 に は 独 立 に NagarajaandKrishnaの 研 究[18]が あ るが,速 度,反 復 回 数 に お い て10 倍 は 改 善 して い る。Wolfeと 独 立 にIRIAのLemarchalの 研 究[15]も 興 味 が あ る が,数 値 実 験 が 不 足 して い る。

一 般 化 傾 斜 法 を 出発 解 とす るBOX‑STEP法(文 献[16]参 照)も 大 規 模 問 題 の 解 法 と して 発 表 され た 。 原 理 がBranchandBound法 の よ うに 簡 単 で あ る の で 将 来,Wolfeら の 共 役 一 般 化 傾 斜 法 を 出 発 解 とす る よ うな BOX‑STEP法 が 作 られ るか も しれ な い 。

3.数 理 計 画 シ ス テ ム の 開 発,利 用 と そ の 問 題 点

大 規 模 な 数 理 計 画 モ デ ル は 計 算 機 を 利 用 し て 解 を 見 出 す 。 モ デ ル 式 と デ ー タ き え 提 出 す れ ば 解 法 は ブ ラ ッ ク ボ ッ ク ス に し て 望 む 解 が 得 ら れ る こ と は 現 在 の 所,殆 ど 期 待 で き な い 。 前 処 理 と シ ス テ ム の 利 用 に 細 心 の 注 意 が 必 要 に な る 。 既 製 の 製 品 を 利 用 す る に せ よ,こ れ か ら 開 発 な い し 改 訂 ず る に せ よ, い わ ゆ る 「数 理 計 画 シ ス テ ム 」 を 動 か す 過 程 に は 様 々 な 問 題 が 生 じ て く る 。'

こ れ ら 諸 問 題 に つ い て 大 規 模 問 題 の 解 決 と い う 観 点 か ら 一 般 的 な 注 意 を 述 べ よ う 。

ま ず 仮 り に 大 規 模 な 数 理 計 画 パ ッ ケ ー ジ の 利 用 が 可 能 で あ る と す る と 現 時 点 で は ど の よ う な パ ッ ケ ー ジ が 利 用 可 能 で あ ろ う か 。 一 般 の ユ ー ザ は 商 業 用 に 開 発 さ れ た 大 き な 数 理 計 画 シ ス テ ム に ほ 手 軽 に 利 用 す る こ と は 殆 ど 不 可 能 で あ る が,そ の 機 能 等 に つ き 熟 知 し て お く こ と は,家 内 工 業 的 な シ ス テ ム を 開 発 す る 上 で 有 用 で あ る 。 ま た,ど の よ う に 秀 れ た 機 能 を も っ て い る に せ よ,十 分 な 利 用 実 績 が あ り,robustで あ る こ と が,そ の シ ス テ ム の 評 価 と な る こ と も 注 意 す べ ぎ で あ る 。 そ の 点 で,IBMのMPS/360は 十 分 実 績 が

(3)論 文P.Wolfe,"AMethodofConjugateSubgradientsforMinimizing NonDifferentiableFunctions",in:M.L.BalinskiandP.Wolfe,eds., Nondifferentiableo少timixation,MathematicalPrqgrammingS七udy3

(North‑Holland1975),参 照.そ の 紹 介 はMath.Pro97(1974)380‑383 に あ る.

あ り,範 と な っ て き た 。 そ こ でMPS/360を 原 点 に 最 近 の 大 規 模 数 理 計 画 シ ス テ ム の4社(IBM,UNIVAC,BURROUGHS,CDC)の 製 品 を 比 較 す る

と 表4.1の よ う に な る 。 と こ ろ で,MPs/360は,IBM360/370のos/360

の も と で 動 き 最 大8,191行 の 数 理 計 画 を 解 く シ ス テ ム で あ り,主 要 な 機 能 は, OPTIM,PARA,RANGE,TAB,DUAL,REV,FLAG,CRASH,LOADB,

SAVE,PICT,BV,CL,SEP,GEN,REP,SELを 備 え て お り,MIPは,

組 込 ま れ て い な い 。 な お,前 述 お よ び 表 中 の 主 要 機 能 の 略 号 は,次 の 通 り で あ る 。

OPTIM=逆 行 列 の 積 形 式 を 用 い た 主 最 適 化 法,PARA=右 辺 又 は 目的 関 数 の 係 数 の パ ラ メ ー タ 化,RANGE=右 辺 又 は 目的 関 数 の 係 数 の レイ ン ジ ン グ,TAB=

行 列 の 更 新 形 式,DUAL=双 対 最 適 化,REV=2値 行 列 の 改 訂,FLAG=基 底 か ら外 れ た 特 定 の ベ ク トル を キ ー プ,FORCE=基 底 に 入 れ た り出 した りす る特 定 ベ ク トル を 強 制,CRASH=初 期 出 発 基 底 を 確 定,LOADB=ヵ 一 ドや フ ァ イ ル を 通

じ基 底 を ロ ー ド,SAVE=2値 行 列,基 底 再 出 発 情 報 を ス トア,リ ス トア,PICT=

エ ー タ フ ァ イ ル を 含 む 行 列 の 構 造 を コ ン パ ク トな 形 式 に 描 写,OUT=非 線 形 系 に よ り ア ク セ ス で き る フ ァ イ ル 書 式 で 解 を 出 力,BV=有 界 変 数,CL・=個 別 計 画 を 呼 び 許 容 限 界 を セ ッ トし,条 件 を テ ス トす る 制 御 言 語,SEP=分 離 非 線 形 計 画, MIP=混 合 整 数 計 画,GUB=一 般 化 上 界 法,TRANS・=輸 送 問 題,DECOMP=分 解 モ デ ル,GEN・=デ ー タ イ ン プ ッ トか ら の 行 列 生 成,REP・=報 告 書 機 能,SEL=

制 御 文 が 指 定 し た 行 ま た は 列 の 上 で 演 算 す る た め の 選 択 リ ス ト,RED=問 題 の サ イ ズ の 縮 小 化 。

表4.1

使用計算劇 システム名

IBM360/370

UNIVAC1108

B6700

"(バ

ロ ー ス)

CDC6600

MPSX

UMPIRE

TEMPO/6700

OPHELIA

最大 問題 サ イ ズ

16,383行

8,000行 (192K)

8,191行

M讐 欝 曙 繍 能隔

十MIP,RED 十MIP,FORCE,

REDUCE,GUB

‑DUAL 十GEN,REP

‑TAB ,PICT,SEL 1十MIP

10・OOO行ri騰 垂瑠9会L

考

日225ド ル レ ン タ ル 文 献[17]

MIP,GEN

強 力 (Scicon開 発) ALGOL

他 機 種 と の イ ン プ ッ ト交 換 可 MIP強 力 (SIA開 発) (出 典:SIGMAP1974)

大規模数理 計画 の解法 につ い て ³⁹

表4.1か ら現 在MPSXが 世 界 最 大 の シ ス テ ム(規 模,澗 題 サ イ ズ,顧 客 数)で あ る こ とが わ か る と 同 時 に 各 メ ー カ の 多 少 の 変 化 を 読 み と る こ と が で

き る。

な お 日本 の 数 理 計 画 シ ス テ ム で は 日本 電 気 のNEAC‑MPSが 大 き く,SEP (Hadleyの デ ル タ 法)やMIP(Bendersの 双 対 分 割 法 とBalasの 木 探 索) も組 込 ま れ て い る。200行300列20%の 密 度 の ふ つ うの 規 模 の 線 形 計 画 で あ れ ば 約4分 の 実 行 時 間 で 解 が 得 られ る。 日立 のHMPS,富 士 通 のMPS, LIPsは や や 小 さい が,い ず れ もIBMのMPs/360に 類 似 して い る。 国 産 初 の 本 格 的 数 理 計 画 シ ス テ ム とい わ れ るIMPSに つ い て は,[31]を 参 照 さ れ た い 。 中 程 度 の 問 題 な ら ミニ コ ンか ら 各 種 の 数 理 計 画 パ ヅケ ー ジ が 用 意

され て お り利 用 可 能 で あ る(数 理 計 画 シ ス テ ムが 大 き くな る に つ れ,200行 400列 密 度20%が 大 規 模 と い わ れ る時 代 は 去 り,最 近 は1,000行 程 度 な い と 大 規 模 とい わ な くな っ た)。 ま た,プ ログ ラ ミ ン グ の 教 科 書 程 度 以 上 に,よ

く考 え られ た 数 理 計 画 プ ロ グ ラ ムや ドキ ュ メ ン テ ー シ ョ ン も 出 版 され て い る の で ユ ー ザ が シ ス テ ムを 開 肇 す る こ と もで き る。

以 下,こ れ ら の シ ス テ ム の 開 発 な い し利 用 上,問 題 とな っ て くる 一 般 的 な 注 意 を 述 べ よ う。

(1)そ の シ ス テ ム で 何 が で き る か,十 分 な ドキ ュ メ ン テ ー シ ョン は あ る か 。,・

マ ニ ュ ア ル が ほ とん ど な い か,数 冊 に ま た が っ て い て そ の 読 破 に 相 当 の 時 間 を 要 す る場 合 が あ る。 詳 しい ドキ ュ メ ン トと コ ン パ ク トな も の の 両 建 て が 望 ま しい 。 ま た これ らに 十 分 精 通 した 相 談 員 や 指 導 者 が 養 成 され て い る こ と

も重 要 で あ る。

(2)そ の シ ス テ ム の 数 値 計 算 上 の 精 度 。

モ デ ル が 比 較 的 小 規 模 な ら実 用 上 か な り厳 しい 精 度 が 要 求 され る。 十 分 な 精 度 を 得 るに は 倍 精 度 計 算 で,逆 行 列 ル ー チ ン がLU分 解,最 大 ピ ボ ッ ト 方 式 で あ る こ とが 望 ま しい 。 ま た,大 規 模 な ス パ ー ス 行 列 を 扱 うの で ス パ ー

ス性 を 十 分 考 慮 した 処 理 方 式 で あ る こ と(文 献 〔29コ参 照)。 大 規 模 に な れ ば

演 算 回 数 は 増 加 し,そ れ だ け 計 算 の 誤 差 が 多 くな る。 記 憶 容 量,計 算 の 手 間,数 値 安 定 性,丸 め 誤 差 の 問 題 は 注 意 を 要 す る 。

(3)数 理 計 画 シ ス テ ム の 実 用 上 の 問 題 点(1)

(イ)修 正 され た 最 適 性 分 析(PostOptimalityAnalysis:POA,上 述 の RANGE,PARAMな ど)が 可 能 と な る よ う組 込 まれ て い る か 。1題1題 解

い て は100万 円 か か る も の が,POAに よ り10万 円+α で 済 む 。

(ロ)実 用 に お い て は 離 散 モ デ ル(整 数 計 画,混 合 整 数 計 画)が 通 常 の 姿 で あ る の で,こ れ らを 解 くシ ス テ ムに な っ て い るか 。

の 望 む 規 模 の モ デ ル が 解 け る か 。 過 度 に2次 記 憶 を 使 う方 式 よ りも,イ ン コ ア で 解 け る こ とが 望 ま しい 。 これ は,前 記 の2.に 関 連 す る。

⇔ 非 線 形 計 画 の 場 合,数 式 処 理 の 部 分 が 自動 化 さ れ て い るか 。 この 実 用 化 は 殆 どな され て い な い が 自然 科 学 で は 特 に 重 要 な 要 請 で あ る。

㈲ シ ス テ ム が で き る だ げ 機 種 独 立 で あ り 移 植 可 能 で あ る こ と。FORT‑

RAN・ALGOL,PL/1で 書 か れ た シ ス テ ム は か な り機 種 独 立 で 移 植 可 能 で あ るが,必 ず し も 数 理 計 画 に 便 利 な 言 語 で は な い 。(後 に 数 理 計 画 の プ ロ グ ラ ム言 語 で 再 述 。)Landら の[13]はrobustnessとwell‑testの 観 点 か らか な りの 工 夫 が み られ,ま たFORTRANで 書 か れ た 便 利 な シ ス テ ムで あ る。

しか し,CDC6600用 のFORTRANIVで あ る こ とか ら 精 度 や 周 辺 装 置 等 に 十 分 注 意 して 移 植 す る必 要 が あ る。

￠9入 力 と出 力 が 決 定 と判 断 の 材 料 提 供 に 直 接 役 立 つ よ う,会 話 形 式 に な っ て い るか 。 ま た デ ー タ ベ ー ス の概 念 が そ の シ ス テ ム に 組 込 まれ て い る か 。 多 数 の ユ ー ザ が 共 用 で き る デ ー タ フ ァ ィル の ほ か,私 用 の ユ ー ザ フ ァ ィル が 機 密 保 持 で き る程 度 の 環 境 が 与 え られ て い る か 。

(ト)前 処 理 部 分 の 完 備 。 大 規 模 シ ス テ ム は,し ば しば デ ー タが1万 個 も あ る場 合 を 扱 うの で,デ ー タ の 入 力 を 含 む 前 準 備 に 十 分 手 間 を か け る 必 要 が あ る。 デ ー タ エ ラ ー検 査 の 初 等 的 な 技 法 で あ る 各 種 の マ ッチ ン グ 技 法(バ ラ ン ス ・チ ェ ッ ク,サ ム ・チ ェ ッ ク,ロ ジ カル チ ェ ッ ク,制 限 チ ェ ッ ク,桁 数 チ ェ ッ ク)か ら高 級 なPICTURE制 御 文 を 利 用 す る。 さ らに 余 分 な 不 等 式 を

.大 規模数理計画 の解法につ いて41

事 前 に 除 い た り制 約 式 の 矛 盾 を 見 出 す 機 能(前 述 で はRED,PRESOLVER も あ る)を 備 え て い るか 等 々。

これ ら の要 件 を 寸 べ て 満 た す パ ッケ ー ジ は 利 用 な い し開 発 しが た く,一 種 の チ ェ ッ ク ポ イ ン トと し て 銘 記 す る必 要 が あ る。 これ か ら よ り完 成 度 の 高 い 数 理 計 画 シ ス テ ム を 作 ろ う とい う者 に と っ て,さ ら に 追 加 的 に,プ ロ グ ラ ム テ ス ト法 と数 理 計 画 プ ロ グ ラ ム 言 語 の 問 題 に 注 意 を 喚 起 して お こ う。

㈲ プ ロ グ ラ ム テ ス ト法 。

一 旦 プ ロ グ ラ ムが 出 来 た ら,そ の シ ス テ ム の テ ス トの た め に 各 種 の 問 題 を 解 き答 や 解 が 得 られ る ま で の 時 間 に つ い て検 討 を 加 え ね ば な らな い 。 適 当 な 教 科 書 な い し論 文 の 例 題 を 解 くだ け で は 十 分 で な い 。 数 理 計 画 法 の 練 習 問 題 268題 の 問 題 と,解 答 を 編 集 したVajda[23]で す ら問 題 に 偏 りが み られ, 大 規 模 問 題 とい え る もの は な い 。 線 形 計 画 法 の プ ロ グ ラ ム テ ス トで あ れ ば, 輸 送 問 題,割 当 問 題,巡 回 セ ー ル ス マ ソ 問 題,ジ ョ ブ シ ョ ップ ・ス ケ ジ ュ ー

リン グ 問 題 等 の 離 散 型 計 画 問 題 や 非 線 形 計 画 問 題,確 率 計 画 問 題 を,線 形 計 画 法 に 還 元 す る こ と に よ り大 き な 規 模 の 計 画 問 題 が 得 られ そ れ を 利 用 す る こ とが で き る が,一 般 的 に は 問 題 不 足 に な る。 そ こ で 各 種 の デ ー タ に 対 し シ ス テ ム テ ス トを 行 うの に 擬 似 乱 数 列 た とえ ば 合 同 乗 算 型Xn+t・ ・aXn(mod2り を 発 生 し て 利 用 す る こ とが で き る。 こ こ で,16bitマ シ ソ で あ れ ば, a・=181,2b・=32767+1,32bitマ シ ン な らa・ ・16807又 ,65539,b=・32が 用 い られ る。 この 方 法 は,前 述 の 方 法 に 比 べ 手 作 業 に よ る デ ー タ の 誤 入 力 を 介 在 さ せ な い利 点 が あ る。 しか し,得 られ た 答 が ど の程 度 合 致 して い る か 判 断 しが た い 場 合 が 生 じ る欠 点 が あ る。 そ こで,始 め か ら答 が わ か っ て い る 問 題 を 作 り,そ の 問 題 か ら答 を 見 出 し始 め の答 と比 較 す る方 法 が あ れ ば よい 。 与 え られ た 問 題 か ら解 を 得 る過 程 と は 逆 に,若 干 の 情 報(答 と,行 数,列 数, 密 度,尺 度 因 子 な ど)を 与 え,問 題 を 生 成 す る問 題 は,「 逆 数 理 計 画 法 」 と 呼 ぶ こ とが で き る。 こ の 方 面 の 研 究 の 蓄 積 は 非 線 形 計 画 法 に[22コ,線 形 計 画 法 に[4]し か 寡 聞 に して 知 らな い が 〆未 開 拓 の 重 要 な 分 野 で あ ろ う。 簡 単 に 紹 介 す る と 前 者 は ま ず 次 の 問 題 を 想 定 す る:minθ(x)+o'〃,s.t.9i(x)==

'

φi(x)+bt≦0,こ こに θ(x),φi(x)は 微 分 可 能 な 凸 関 数(線 形 も含 む)で あ る。 そ の と き問 題 の 生 成 は,1.最 適 解 と双 対 最 適 解 の 指 定2.相 補 ス ラ ッ ク性 に よ るbiの 選 択,お よび3.Kuhn‑Tucker条 件 に よ るcの 選 択 の3 段 階 よ りな る。

こ の 手 続 きに よ り 得 られ たRosen・ 鈴 木 の 非 線 形 問 題 は テ ス ト問 題 と し て よ く利 用 され て い る。 次 に 後 者 のGLUPPプ ロ グ ラ ム は,線 形 計 画 に 限 られ る が 前 者 ほ ど 自 由 度 が 大 き くな くま と ま っ て い る。 入 力 デ ー タ は 行 と列 の 望 む 個 数,状 態 密 度 す な わ ち 全 要 素 中 の 非 零 要 素 の 割 合,尺 度 因 子S,こ れ に よ りデ ー タが10'"sと10‑sの 間 に 納 ま る,お よ び 解 ベ ク トル た と え ば す べ て1.0で あ る。 数 理 計 画 シ ス テ ム に 備 え て い るGENを 利 用 す る こ と も で き る。 ま た,条 件 の 悪 い ヒル ベ ル ト行 列 を 発 生 で き る よ うに な って い る。

出 力 デ ー タ は 擬 似 乱 数 的 に 行 ご と に 生 成 され る。 こ の プ ロ グ ラ ムはFORT‑

RANで 書 か れ て い る の で 入 出 力 機 器 さ え 指 定 で きれ ば 容 易 に 移 植 可 能 で あ る。

(リ)数 理 計 画 用 プ ロ グ ラ ム 言 語

商 用 の 数 理 計 画 パ ヅ ケ ー ジ は 大 て い ア セ ン ブ ラ で 数 十 万 ス テ ッ プに も な っ て い て 計 算 機 の 負 担 や 処 理 系 を 開 発 す る コス トが か な り 大 き くな っ て い る 。 数 理 計 画 シ ス テ ム の 処 理 系 記 述 の た め に 読 み 易 く 修 正 が 容 易 で 目的 言 語 が 最 適 化 され て い る よ うな 数 理 計 画 向 き の 便 利 な 言 語 が あ れ ば よい 。 そ

の よ うな 試 作 例 がDantzigら の 下(Stanford大 学)で 稼 動 して い るMPL (MathematicalProgrammingLanguage)で あ る。MPLは 大 規 模 系 の 数 理 計 画 法 の 算 法 記 述 を 目的 と して 設 計 され た 高 級 か つ 利 用 者 向 け の プ ロ グ ラ

ム言 語 で あ る(MPLの 紹 介 に つ い て は[28]参 照)。 す な わ ち,ALGOLと

同 じ 基 本 構 造 を も ち 行 列 演 算 や 集 合 演 算 を 数 学 の 記 法 に 近 い 形 で 記 述 で き る よ う設 計 され て い る。 またMPLを 支 援 す るGENや フ ァ イ ル メ カ ニ ズ ム 用 の 特 殊 目的 の 言 語 も 合 わ せ 開 発 され て い る。 しか しな が ら,大 規 模 数 理 計 画 とい うか らに は,始 め か ら単 体 法 向 き の 扱 い を 考 え る の で は な く,異 質 の 要 素 を もづ 逐 次 近 似 型 の 大 規 模 解 法 に 適 応 す る よ うな設 計 を 考 え る べ き で あ