社団法人 日本オペレーションズ・リサーチ学会
ENGLISH
入会申込み お問合わせ
HOME オペレーションズ・リサーチ学会とは 研究活動案内 OR事典Wiki 機関誌 論文誌 会員の方へ
活動概要
会長挨拶
支部紹介
 
HOME  > 論文誌 > 論文概要 


JORSJ 54-1, JORSJ 54-2&3, JORSJ 54-4

JORSJ 54-1

1.
不可分材と貨幣を伴った両側マッチング市場における対安定性
Pairwise Stability in a Two-Sided Matching Market with Indivisible Goods and Money
Yasir Ali and Rashid Farooq (National Univ. of Sciences and Technology, Pakistan)
 

We consider a two-sided matching market in which the traders are partitioned into two sets; the set of sellers and the set of buyers. Each seller owns at most one indivisible good and each buyer owns a certain amount of money. Money is assumed to be an integer variable. Each trader can trade with at most one trader of the opposite side. The marriage model of Gale and Shapley is a special case of our model. We give a constructive proof to show the existence of a pairwise stable outcome.
2.
非平滑な一般化相補性問題の解について
Solution of Nonsmooth Generalized Complementarity Problems
Mohamed Aly Tawhid (Thompson Rivers University Canada)
 

We consider an unconstrained minimization reformulation of the generalized complementarity problem GCP$(f,g)$ when the underlying functions $f$ and $g$ are $H$-differentiable. We describe $H$-differentials of some GCP functions based on the min function and the penalized Fischer-Burmeister function, and their merit functions. Under appropriate semimonotone (${\bf E_0}$), strictly semimonotone (${\bf E}$) regularity-conditions on the $H$-differentials of $f$ and $g$, we show that a local/global minimum of a merit function (or a `stationary point' of a merit function) is coincident with the solution of the given generalized complementarity problem. When specialized GCP$(f,g)$ to the nonlinear complementarity problems, our results not only give new results but also extend/unify various similar results proved for $C^1$, semismooth, and locally Lipschitzian.
3.
密輸量に関する密輸者戦略をもつ取締ゲーム
宝崎隆祐(防衛大学校)
 

本論文は,密輸者と取締者がプレイする多段階の2人ゼロ和取締ゲームを論じている.各ステージにおける密輸者の戦略は密輸量であり,取締者の戦略はパトロールの実施/未実施である.取られた戦略に応じて,プレイの過程で,密輸者の拿捕や密輸成功が確率的に生起する.取締ゲームに関する大半の従来研究では,密輸者戦略を密輸回数制約下での密輸決行/未決行としているが,現実的な観点からは密輸量戦略の方が自然である.論文では,密輸量に応じて生起事象の確率が変化する一般的なケースでの均衡解に対する数値解法アルゴリズムを提案し,また生起確率が固定された場合,その他の特殊なケースに対しては,解析的な均衡解の式を動的計画法により導出した.さらに,これらの理論的成果を数値例に適用し,両プレイヤーの戦略の合理性を分析している.
4.
最小待ち行列選択式MArP/PH/2待ち行列モデルの漸近解析
佐久間 大(東京理科大学)
 

本論文では,到着客が最小の待ち行列に加わる並列型待ち行列モデルを考える.このような待ち行列モデルにおいて,各待ち行列長は互いに相関をもち,一般に定常分布を求めることは難しい.多くの先行研究において,到着時間間隔およびサービス時間が指数分布に従うと仮定し,定常分布の漸近解析が行われてきた.本論文では,到着時間間隔だけでなくサービス時間も指数分布より一般の分布に従うと仮定した並列型待ち行列モデルに対して,定常分布の幾何漸近特性を導いた.
ページトップへ戻る

JORSJ 54-2&3

1.
相補性制約付き数理計画問題の陰的定式化とそのロバスト構造最適化への応用
寒野 善博 (東京大学)
 

構造物を設計する際には,未知の外乱や材料特性のばらつきなどの様々な不確定な要因を含むため,不確定性を考慮した最適設計法を開発することは重要である.不確定な静的外力が作用する構造物のロバスト最適設計問題は,適当な仮定の下で,均衡制約つき数理計画問題(MPEC)として定式化できる.本論文では,このMPECに対して,平滑化Fischer--Burmeister関数を利用した再定式化法を提案する.特に,平滑化パラメータを独立な変数とみなした上で,実行可能解では平滑化パラメータが0となるような等式制約を考慮することが,本定式化の特徴である.ロバスト構造最適化の数値例題を通じて,提案したMPECの再定式化に通常の非線形最適化の解法が適用できることを例証する.
 
2.
典型的制約つきスウィング・オプションの価格付け
田代 雄介 (東京大学)
 

スウィング・オプションはアメリカン型のオプションの一種であり,主にエネルギー市場で取引される.このオプションの保有者は複数回の権利を持ち,権利行使時に取引量を変更できる.本論文では,典型的な制約つきのスウィング・オプション価格を数理計画によって評価する方法を提案する.まず,このオプションにおいて,数種類の変更量によって構成される最適な執行戦略が存在することを示す.そして,この最適戦略を用いて,格子モデル上の価格付け問題を線形計画により定式化する.また,この最適戦略を利用することで,先行研究の評価手法における計算量を削減できることを述べる.さらに,本論文では非完備市場におけるスウィング・オプションの無裁定価格の上下界を求める問題の定式化も行う.
3.
音楽CD市場におけるアーティストのブランド特性分析
住田 潮, 高橋 一樹, 吉井 淳 (筑波大学)
 

本論文は,住田他(2007)の続編であり,CD市場基本モデルを踏襲する.即ち,「ロイヤルティ」と「情報感度」の観点から顧客を類型化し,各顧客の購買・非購買行動を離散時間マルコフ連鎖で表現,推移確率行列を8つのパラメータで構造化し,その期待販売数と実データとの距離を最小にするパラメータ推定により,アーティストのブランド特性を把握することを目指す.前出論文では数値的に期待販売数を求めた為,格子点上での最小化に留まっていた.本論文では,状態確率ベクトルを解析的に表現し,非線形最適化を行うことが可能となった.また,ブランド特性を表現する新たな指標を導入し,より効果的なマーケティング戦略を提案している.なお,本論文が提案する分析アプローチは,CD市場に限らず,一度しか購入されないような商品を扱うあらゆる市場に適用可能である.
4.
不確実状況下での市場品質問題の対策意思決定支援
中津川 実,西川 武一郎、新垣 隆生 ((株)東芝)
 

製造が短期間で行われる近年の電気製品では、製造開始後の市場品質問題を早期に発見し、対策を実施することが重要である。しかし、製造開始直後は修理クレーム数・出荷台数が少ないため推定されるクレーム率の不確実性が大きく、対策実施の意思決定にはリスクが存在する。一方、クレーム数・出荷台数が増えて不確実性が小さくなる将来まで意思決定を延期すると、誤判断を回避できるが対策による改善効果は小さくなる。本稿では、意思決定の延期オプションを考慮した対策実施による市場品質コストの期待値最小化問題を、マルコフ意思決定過程とベイズ統計にもとづく一種の最適停止問題として解く方法を提案する。そして、提案法による品質コスト削減効果、延期オプションの価値評価、市場に複数機種がある場合の対策優先順位評価について議論する。
ページトップへ戻る

JORSJ 54-4

1.
線形順序付け問題に対するラグランジュ緩和と釘付けテスト
鮏川 矩義,山本 芳嗣,張 理遠 (筑波大学)
 


線形順序付け問題は,産業連関分析,重みつき完了時刻の和を最小化する単一機械スケジューリング,複数人の選好をまとめて1つの選好を構成する方法などに応用のあるNP困難な組合せ最適化問題である.本研究では,線形順序付け問題に対するラグランジュ緩和法でのラグランジュ乗数の取り扱いを改良する方法と,通常の釘付けテストを問題の構造を用いて強化する手法を提案し、その性能を数値実験により評価する.
 
2.
二乗和多項式に対する削除法の拡張
脇 隼人,村松 正和 (電気通信大学)
 

本論文では,多項式最適化問題に対する半正定値計画緩和問題の規模を小さくする手法を提案し,この方法が面的縮小法の一種であることを示す.これにより,提案手法で得られる半正定値計画緩和問題が実行可能内点解を持ち,結果として,主双対内点法で解く際に生じる数値的に不安定な振る舞いを取り除くことができるかもしれない.本論文では,いくつかの数値実験を行い提案手法で得られる半正定値計画緩和問題を効率よく解くことができることを実証する.
 
3.
離単体法によって生成される基底解の最大数の下界
北原 知就,水野 眞治 (東京工業大学)
 

北原・水野(2011年)は最小係数規則を採用した主単体法によって生成される異なる実行可能基底解の最大数の上界を導出した.著者らはさらに,得られた上界がタイトであることを示すため,Klee-Mintyの線形計画問題の変種を提案し,最大数の下界を示した.本稿では,このKlee-Mintyの線形計画問題の性質について詳細に述べ,証明する.さらに,単純な線形計画問題の例により,最大数の新しい下界を示す.
 
4.
動的資産配分のためのカーネル法を利用した非線形制御ポリシー
高野 祐一 (東京工業大学)
後藤 順哉 (中央大学))
 

本論文では,非線形制御ポリシーを用いて多期間にわたる動的な資産配分を決定する最適化問題を定式化し,問題求解のための計算手法を提案する.ここで,制御ポリシーとは投資対象資産の過去の収益の関数である.カーネル法を利用することで,非線形関数の中から最適な制御ポリシーを選択する問題は凸2次最適化問題として定式化される.さらに,L1-ノルムを用いた正則化を利用することで問題を線形最適化問題に帰着する.計算実験では,投資対象資産の収益率のシナリオを1期間自己回帰モデルによって生成し,先行研究の手法と比較して我々の提案する投資戦略は良好な運用成績を得られることを示す.
 
5.
頂点容量制約付き有向全域木パッキング問題に対するラグランジュ緩和に基づく列生成法
田中 勇真, 今堀 慎治, 柳浦 睦憲 (名古屋大学)
 

本論文では,頂点容量制約付き有向全域木パッキング問題を扱う.この問題は入力として,有向グラフ,ルート頂点,頂点容量,辺の始点側と終点側それぞれに消費量が与えられる.目的はルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし,有向全域木の各頂点に対する消費量の合計は,与えられた頂点容量を超えてはいけない.この問題はNP 困難である.以前,我々はこの問題に対して2段階の発見的解法を提案した.このアルゴリズムは,1段階目に木の候補を生成し,2段階目に生成したそれぞれの木のパッキング回数を決定する.本論文では,ラグランジュ緩和を用いることで1段階目を改善した.計算実験により,提案アルゴリズムは以前のアルゴリズムより速く木を生成でき,少ない木の候補でもよい解を得ることを確認した.
 
6.
施設位置とサービス開始時刻を同時決定する最大フローカバー型配置問題と首都圏鉄道網における配置分析
田中 健一 (電気通信大学)
 

本論文では,施設におけるサービス提供を時空間領域で決定する,最大カバー型の最適配置問題を提案し,首都圏鉄道網上の配置分析を行う.サービス利用可能者は,就業後に施設に立ち寄り一定時間サービスを受け,ある時刻までに帰宅可能な就業者と定義し,これを最大化する各施設の位置とサービス開始時刻を決定する.開始時刻が,各施設で独立に設定可能な場合(独立開始モデル)と,すべての施設で共通の場合(同時開始モデル)を扱う.二つのモデルを整数計画問題として定式化し,発見的解法を提案する.大都市交通センサスデータをもとに作成したフローデータを用い,首都圏鉄道網上に,一施設を各駅・各開始時刻に配置する状況と,提案解法による複数施設の配置結果を分析する.独立開始モデルでは,異なる時刻にサービスを開始する複数の施設が都心部に配置され,同時開始モデルでは,都心と郊外の大規模駅に分散して配置される結果が得られた.
 
7.
NETAL: 計算機のメモリ階層構造を考慮した高性能ネットワーク解析ライブラリ
安井 雄一郎,藤澤 克樹 (中央大学)
後藤 和茂 (マイクロソフト)
神山 直之 (九州大学)
高松 瑞代 (中央大学)
 

様々な分野においてネットワーク解析に対する期待は高まりを見せているものの大規模な実問題を扱うための計算量が課題とされている.そこでネットワーク解析において重要な最短路問題と中心性指標に対する計算機のメモリ階層構造を考慮した効率的な並列計算手法を提案し,NETAL(NETwork Analysis Library) として実装した.NETAL は,NUMA アーキテクチャを採用した AMD Opteron 6174 などのメニーコアプロセッサ上での効率的な並列実行を実現し,既存の実装と比べ最も高速である.USA-road-d.NY.gr(26万点73万枝) に対し,全対全最短路長を44.4秒,代替経路を考慮した全対全最短路を411.2 秒で求め,9th DIMACS参照実装の 302.7 倍,32.7 倍の性能を示した.また,USA-road-d.USA.gr(2400万点5800万枝) に対して全対全最短路長を 7.75 日間で求めることに成功し,δ-stepping の432.4 倍,9th DIMACS 参照実装の 228.9 倍の性能を示した.中心性指標計算については,GraphCTを用いて18時間要するweb-BerkStanのbetweennessに対し,NETAL はcloseness, graph, stress, betweennessを同時に扱い 1 時間で終了する.さらに,R-MAT グラフに対し SSCA#2 の 2.4-3.7 倍の性能を確認した.
 
ページトップへ戻る
HOMEに戻る
イベントカレンダー
2017年度第1回ORセミナー
日程:
2017年5月13日(土)
場所:
(株)構造計画研究所

2017年度第2回ORセミナー
日程:
2017年6月17日(土)
場所:
(株)構造計画研究所
シンポジウム
2017年秋季シンポジウム
日程:
2017年9月13日(水)
場所:
関西大学
研究発表会
2017年秋季研究発表会
日程:
2017年9月14日(木)-15日(金)
場所:
関西大学