入会申込み お問合せ ENGLISH

JORSJ  Vol. 50 No. 4 和文概要  「OR学会創立50周年記念特集号

トップページへ戻ります
「論文誌」トップに戻る

1. 大規模な半正定値計画問題に対するソフトウェア SDPA

藤澤 克樹 (中央大学)、 中田 和秀 (東京工業大学)、  山下 真 (神奈川大学)、  福田 光浩 (東京工業大学)

 半正定値計画問題は幅広い応用を持つ一方、近年では問題のサイズが巨大化しており、内点法アルゴリズムの改良、組合せ最適化手法の組込み、問題の疎性の利用、並列計算の適用などが行われている。著者らのグループでは1995年から半正定値計画問題に対するソフトウェアを開発、評価する研究を行っている。入力問題の様々な特性に対処するために複数のソフトウェアを開発しているが、本論文では主双対内点法を実装した SDPA、並列計算等の適用で大規模な問題に対応した SDPARA、並列計算と行列補完のアルゴリズムを組み合わせた SDPARA-C などのソフトウェアを紹介する。また大規模な問題(量子化学)に対する最新の実験結果やグリッド技術を応用して Web 上からソフトウェアを利用できるようにした SDPA Online Solver
なども紹介していく。

 

2. リコース関数に固定費を含む確率計画問題の解法

椎名 孝之 ((財)電力中央研究所)、 多ヶ谷 有 (キヤノンシステムソリューションズ梶j、 森戸 晋 (早稲田大学)

 確率計画法においては, 制約侵犯への罰金 (リコース関数) を含む費用の期待値を最小化するという 2段階決定モデルがある. 決定変数が連続型である場合, Benders の分解に基づくL-shaped 法が有効である. 決定変数に整数条件を有するとき, 罰金を表すリコース関数は, 非凸関数になるため従来の方法を用いることはできない. 特に単純リコース型の問題に対して, Ahmed et al. (2004)らは, 分枝限定法に基づく解法を示したが, 第2段階における決定変数の値が非負整数に制限されるものであった. そのため, 本論文では現実問題への応用を考慮して, 第2段階の決定変数が正の値をとる場合に, 罰金を生じる確率計画問題を取り扱い,分枝切除法による解法を示す. 分枝操作として, リコース関数が不連続となる点で決定変数のとり得る区間の分割を行い, リコース関数の正確な値を与えるカットを追加する. 数値実験により本手法の有効性が示される.

 

3. リンキング・システムとマトロイド・ペンシル

岩田 覚 (京都大学)

 行列の組合せ論的抽象化として Whitney (1935) に よって導入されたマトロイドは,効率的に解くことの できる組合せ最適化問題に共通の構造として認識され, 今日に至っている.マトロイドと本質的には等価だが, 行列の乗算と類似の演算を直接的に表す離散構造として,Kung (1978) と Schrijver (1979) は,リンキング・システムの概念を提案した. 
一方,同じ大きさの行列の組である行列ペンシルは,動的システムを記述する道具として使用されている.特に,制御理論においては,定数行列による同値変換の下での標準形である Kronecker 標準形が本質的な役割を果たしている.
 本論文は,行集合と列集合を共有するリンキング・ システムの組を,行列ペンシルの組合せ論的抽象化と 捉えて,マトロイド・ペンシルと定義し,その性質を 検討する.特に,行列ペンシルの Kronecker 標準形に 類似した組合せ的な構造を明らかにする.応用として, リンキング・システムの冪乗に関する室田 (1990) の定理に簡潔な別証明を与える.

 

4. グラフとマトロイド中の全域連結集合の列挙

Leonid Khachiyan, Endre Boros, Konrad Borys (Rutgers University, U.S.A.)
Khaled Elbassioni (Max-Planck Institute, Germany)、 Vladimir Gurvich (Rutgers University, U.S.A.)
牧野 和久 (東京大学)

 本論文で,与えられたマトロイド中の極小な全域連結集合の列挙問題を考察する.良く知られているように,マトロイド中の極小な全域集合は,多項式時間遅延で列挙可能であるが,極小な全域連結集合に関しては,何も知られていなかった.本論文で,我々は,この極小な全域連結集合列挙が少なくとも単調な論理関数の双対化問題以上に難しいこと,ならびに,極小な全域連結集合列挙が単調な論理関数の双対化問題に準多項式時間で帰着可能なことを示す.これにより,極小な全域連結集合列挙が逐次準多項式時間で列挙可能
であることを示す.また,グラフ的マトロイドの場合は,逐次多項式時間で列挙できることも示す.

 

5. 辺連結度制約と次数制約を満たすコスト最小多重グラフ構築のための近似アルゴリズム

福永 拓郎、 永持 仁 (京都大学)

 本論文では,節点集合$V$, 2節点間上で定義された辺連結度要求$r$とメトリック辺コスト$c$, 各節点上に定義された次数上下限$a$, $b$が与えられたときに,辺連結度要求を満たし各節点の次数が上下限内に収まるような,$V$上のコスト最小多重グラフを求める問題を考える.我々は,この問題が定数近似アルゴリズムをもつための$r$,$a$,$b$に関する条件について考察した.例えば,$r(u,v)$が全ての2節点$u$, $v$に対し常に2以上であり,$b(v)$が全ての節点$v$について一定である場合は,$(2+2/k)$-近似可能であることを示した.ただし,$k$は$r(u,v)$の最小値である.

 

6. 集合被覆問題に対する緩和法に基づく発見的解法

梅谷 俊治 (電気通信大学)、 柳浦 睦憲( 名古屋大学)

 数理計画法の発展は,困難な組合せ最適化問題の最適解を求める分枝限定法や分枝カット法などの厳密解法だけではなく,良い近似解を求める発見的解法にも大きく寄与してきた.とくに,代表的な組合せ最適化問題の一つである集合被覆問題に対しては,線形計画緩和やラグランジュ緩和を用いた発見的解法が提案されており,乗務員スケジューリングや配送計画において生じる大規模な問題例に対して,最適値からの誤差が1%以下であるような良質な近似解が現実的な計算時間で得られることが知られている.本論文では,集合被覆問題に対して,緩和法を中心とした数理計画の手法に基づく発見的解法を解説する.また,代表的なベンチマーク問題例に対する数値実験を通じて,それらの解法の性能を評価する.

 

7. 二目的食品袋詰め問題に対する動的計画法

軽野 義行 (京都工芸繊維大学)、 永持 仁 (京都大学)、 王 小銘 (京都工芸繊維大学)

 本論文では,自動組合せ計量装置における食品の袋 詰め最適化問題を取り扱う.自動組合せ計量装置はn 台の計量ホッパから構成されており,それぞれのホッパには袋詰めすべき食品が投入され,重さが量られる. ここでは,各ホッパの食品(ピーマン1個や一掴みの スナック菓子など)を品物と呼ぶ.この装置はn個の
品物のうちからいくつかを選んで,それらを一つの袋 に詰める.空になったホッパには新たな品物が投入さ
れ,装置は再びいくつかの品物を選ぶ.このような袋 詰め操作が何度も繰り返される.袋に詰める品物を選
ぶとき,品物の合計重量を目標値に近づける一方で, 選ばれない品物の長期残留を防止することが望まれて
いる.本論文では,これを(静的な)二目的0-1整数 計画問題として定式化し,動的計画法に基づく解法を
与える.また,その最適化による品物の長期残留防止効果を計算実験で確認する.

 

8. マルコフ再生方程式の双対型と単一サーバ待ち行列の漸近解析への応用

三好 直人 (東京工業大学)

 マルコフ再生方程式の双対型を提案する.この双対 型は,従来良く知られている標準型のマルコフ再生方
程式と理論的には等価であるが,最近の確率モデルの 解析にとって有用であることを示す.双対型マルコフ
再生方程式の有用性を示すために,単一サーバ待ち行 列における系内仕事量の定常分布の漸近解析に応用する.ここで,待ち行列への到着過程は可算無限の状態 をもつマルコフ連鎖に支配されているものとする.こ れは,到着過程を支配するマルコフ連鎖が有限個の状 態をもつ場合にこれまで得られている結果の拡張であるが,双対型のマルコフ再生方程式を用いることによって,従来よりも直接的な証明が得られ,拡張も容易になっていることが確かめられる.

 

9. 客の移動を考慮した移動体通信システムのネットワークモデルと積形式解条件

塩田 茂雄、大塚 憲治 (千葉大学)、 町原 文明 (東京電機大学)

 ユーザ数の有限性と移動性を考慮できる移動体通信システムのネットワークモデルとその解析法を提案する.ユーザはポアソン過程に従ってネットワークの外部から到着し,通話状態・非通話状態を繰り返しながら,セルを移動し,いずれネットワークから退去する.本論文では,このモデルに幾つかの修正(積形式解条件)を加えることで,各セルの通話ユーザ数,非通話ユーザ数の同時分布が積形式で表され,各セルのチャネル全塞確率がアーラン損失式で評価できることを示す.積形式解条件は現実には成立しないため,アーラン損失式はチャネル全塞確率のあくまで近似値を与えるものにすぎないが,通常の条件ではその近似精度は充分高いことを数値的に確認する.また,「等価呼量」の概念を導入することで,アーラン損失式に基づくチャネル数設計が可能であることを紹介し,その精度を評価する.

 

10. ストリーム型通信に対する最小アンダーフロールーティング

会田 雅樹、 高野 知佐、 大澤 峻一 (首都大学東京)

 インターネットでは,従来のデータ通信サービスに加えて,音声やライブ映像などのストリーム型サービスが出現している.これらのサービスでは,受信側でパケットを一旦プレイアウトバッファに格納し,ネットワークのパケット遅延を吸収して連続した再生を行う.しかし,ネットワークの遅延が大きいとプレイアウトバッファでの遅延の吸収ができず,再生時にパケットが未到着である「アンダーフロー」が起こりうる.従来のルーティングでは,最短経路問題として平均遅延を最小にする経路を選ぶ方法が一般的であったが,本論文では遅延が予め決められた値を超える確率を最小にする最小アンダーフロー経路を選ぶ方法を考察した.その結果,従来の最短経路の探索方法を繰り返し適用することで最小アンダーフロー経路を探索できることを明らかにし,シミュレーションで効果を確認した.

11. 環境係数を導入したユーザ指向のソフトウェア可用性評価法

得能 貢一、 山田 茂 (鳥取大学)

 本論文では,ユーザ指向のソフトウェア可用性評価法について議論する.まず,開発過程のテスト工程とリリース後の運用段階におけるソフトウェア故障発生事象・修復特性の違いを考慮するために,従前のマルコフ型ソフトウェア可用性モデルに環境係数を導入し,モデルを再構築する.次に,ユーザの使用要求を満足に完了できる性質や度合と定義されるソフトウェアのサービス可用性を評価するための確率モデルを構築する.このモデルより,ユーザの使用特性を加味した3種類のサービス指向型可用性評価尺度を,運用時間およびデバッグ回数の関数として導出する.最後に,導出された評価尺度を用いたソフトウェアのサービス可用性評価の数値例を示し,動作環境の違いを考慮した場合やシステム本体のみの状態を記述した旧来モデルによる評価結果との相違点について考察する.

 

12. 家計に対する多期間最適化モデルと最適保険設計

枇々木 規雄 (慶應義塾大学)

 個人顧客へのファイナンシャル・コンサルティングを行うために、世帯の属性やライフサイクルを考慮した最適な投資戦略や生命保険、火災保険、医療保険の加入保険金額を決定する多期間最適化モデルの構築を行う。本論文では枇々木, 小守林(2006)を拡張し、@病気に伴うキャッシュ・フローの変化と医療保険の導入、A保険金額が一定ではない(逓減型)定期死亡保険のモデル化、B生命保険金額および医療保険金額を時点ごとに決定変数とするモデル化、Cサンプリング・エラーの影響、に対する分析を数値計算によって検証する。死亡保険の受取金額逓減型を含めたモデルや最適受取金額設計モデルは、平準払い保険料を劇的に減少させ、リスクを減らすことができるとともに、期待される富が世帯主の死亡時点に影響を受けにくい死亡保険の最適受取金額を求めることができる有用なモデルであることが分かった。

 

13. 市場価格と整合的なオプション評価法とその適用例

宮崎 浩一 (電気通信大学)

本論文では、市場価格と整合的なオプション評価法に関する全体像及び基本的手法を示したうえで、日本におけるオプション市場への適用例も幾つか与える。まず、市場価格と整合的なオプション評価法の源流として、Breeden and Litzenberger (1978)と Heston (1993)を採り上げ本質的部分を解説する。次に、市場価格との整合性を求めてオプション評価法が、デタミニステック・ボラティリティモデル、ストキャステック・ボラティリティモデル、ジャンプを含むモデルへと広がり発展していく過程を概観する。その際に、著者が上記2つの論文を市場価格と整合的なオプション評価法の源流として位置づけた理由も明らかにする。最後に、日本のオプション市場に対する適用例が数少ないことに配慮して、著者等が行ったNIKKEI225オプション市場への適用例も紹介する。

14. 行列バランシング問題とバイナリAHP

源馬 耕一 (静岡大学)、  加藤 豊 (法政大学)、  関谷 和之 (静岡大学)

 AHPの一対比較行列に対する重要度算出法に固有ベクトル法がある.固有ベクトル法はペロン・フロベニ ウスの定理から無限大ノルム最小化問題として記述 できる.一対比較行列に対する最小χ2乗法は行列 バランシング問題に帰着し,1ノルム最小化問題と してモデル化した.これらノルムの双対関係から両 者を比較した.固有ベクトル法のアルゴリズムとし てはべき乗法が知られているが,最小χ2乗法に対 して行列スケーリングアルゴリズムが存在し,その 大域収束性を保証した.重要度の性質である行優位 性と左右対称性は最小χ2乗法では成立し,固有ベ クトル法では行優位性のみ成立することを示した. さらに,バイナリAHPでの一対比較行列に関して 2つの算出法の相異を解析し,一対比較値のパラメ ータの取り方による順位逆転現象を最小χ2乗法が 起こりにくいことを実証した.

 

15. 二乗距離順序メディアン立地問題

大澤 義明 (筑波大学)、  尾崎 尚也 ((財)鉄道総合技術研究所)、 フランク・プラストリア (ブリュッセル自由大学)
田村 一軌 ((財)鉄道総合技術研究所)

 多くの立地問題を特別な場合として含む順序メディアン立地問題が最近集中的に研究されている。一方で、施設立地は多くの判断基準から検討されなければならない。そこで、本研究では、連続平面上の順序メディアン立地を多目的計画問題として定式化する。ただし、施設までの移動費用として直線距離の二乗距離を用いる。最初に、必ずしも凸ではない一般の2目的計画問題においても、パレート最適場所がボロノイ図で限定でき包絡線により多項式時間内で特定できることを示す。次に、多目的凸計画問題において、パレート最適やトレードオフ曲線が多項式時間で導出できることを証明する。茨城県のデータを用いた計算例も提示する。

 

16. 訪問介護スタッフスケジューリングにおけるスタッフ数の上下限値

池上 敦子 (成蹊大学)、 宇野 綾希 (第一生命情報システム梶j

 訪問介護事業所では,個々の利用者に対して,指定された時間に利用者宅を訪問しサービスを提供する.働ける時間に制約のあるヘルパー達を使って,これらのサービスを確実に提供しなければならないが,様々な制約や要求を満たしながら1ヶ月分の勤務表を作成するには,非常に多くの労力と時間を費やすことになる.そして,1日のヘルパー必要人数を見積もることでさえ難しいと言われている.
この論文では,訪問介護スタッフスケジューリングの数理計画モデルを紹介し,ある1日におけるヘルパー必要人数に関する下限値計算方法を2種類提案する.また,簡単なヒューリスティックアルゴリズムを利用することによって,上限値の計算も行う.上下限値や,計算の際に得られる情報は,詳細な勤務表作成前のヘルパーのアレンジに有効なものであることがわかった.

 

「論文誌」トップに戻る