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

HOME > 論文誌  > JORSJ論文概要 

62-1 62-2 62-3 62-4

JORSJ 62-1

1.
ナップサック共有問題および関連する問題群に対する動的計画法アルゴリズムと完全多項式時間近似スキーム
片岡 靖詞,山田 武夫(防衛大学校)
ナップサック共有問題は,複数のプレーヤが各自の手持ち商品集合からいくつかの商品を選び,1つの共有ナップサックに詰め込む問題であるが,本論文ではその拡張を考察する.目的関数の形状によりいくつかの関連問題が考えられるが,これらを統一的に解く動的計画法に基づく擬多項式時間アルゴリズムを示す.次に,問題を一連の部分問題に分割して得られる近似アルゴリズムを提示する.このアルゴリズムは,動的計画法の適用時に適切なスケーリングを導入することで,ナップサック共有問題および関連する諸問題に対し,完全多項式時間近似スキームを与えることが示される.議論は主に2プレーヤの場合について行っているが,3人以上の場合についても拡張可能である.また,2プレーヤの場合については動的計画法に依拠しない多項式時間近似スキームも付録として付している.
2.
ロジスティック回帰における変数選択に対する混合整数非線形計画法の適用
木村 圭児(九州大学)

木村・脇(2018)は,線形回帰における変数選択のためのAIC最小化問題に対し混合整数非線形計画法を提案し,既存手法よりも高速であることを数値実験で示した.本論文は,ロジスティック回帰におけるAIC最小化問題を扱い,先に述べた手法のテクニック(例えば緩和やヒューリスティクス)はロジスティック回帰の場合でも適用可能であることを示す.ロジスティック回帰の場合,分枝限定法の各部分問題の緩和問題は制約無し凸計画問題となる.この緩和問題を解くために,親問題の緩和解を基に初期実行可能解を生成し,ニュートン法を適用する.実装には,分枝限定法のフレームワークを提供しているSCIPを用いる.数値実験において,区分線形近似を利用した手法と比較し,提案手法の方が高速にAIC最小化問題を解けることを示す.

3.
レベニューマネジメントにおける区別しない複数列を持つ座席位置選択モデル
小笠原 悠,金 正道(弘前大学)

本研究では,顧客の商品に対する選択行動を考慮したネットワークレベニューマネジメントの既存モデルを座席位置に応用し,顧客の座席位置に対する選択肢を制御することで期待利益の最大化を目指す“座席位置選択モデル”という新たなモデルを提案した.本モデルでは複数の列を区別しないことや,複数の料金クラスはそれぞれ独立に到着する等の仮定を用いて定式化を行った.更に最適政策の近似法として,choicebased deterministic linear programming(CDLP)とdecomposition approximation(DCOMP)を本モデルに適用し,数値実験による性能比較を行った.その結果,既存モデルではCDLPよりも高い性能が示されていたCOMPに比べ,本モデルにおいてはCDLPが有効な近似法であることが示唆された.

ページトップへ戻る

JORSJ 62-2

1.
マルチモジュラ関数の基本演算について
森口 聡子,室田 一雄(首都大学東京)
マルチモジュラ関数は,待ち行列や離散事象システム等で使われる離散変数の関数で,離散凸解析の文脈でも基本的な離散凸関数のクラスとして知られている.本論文はマルチモジュラ関数の基本演算(変数の置換やスケーリング,制限や射影など)について考察することを目的とする.特に,マルチモジュラ関数は,変数の順番に連続性を課すという自然な条件下での射影演算については閉じていることや,二つのマルチモジュラ関数の合成積は,マルチモジュラ関数と分離凸関数の合成積という特殊な場合でもマルチモジュラ性を保存しないことを明らかにする.
2.
野球の戦術を最適化するための動的計画アルゴリズム
吉良 知文(群馬大学),稲川 敬介(秋田県立大学),藤田 敏治(九州工業大学)

野球の1試合をマルコフゲームとしてモデル化すると,攻撃側にとって選ぶべきは打撃か盗塁かあるいは犠打か,守備側にとって打者を敬遠すべきか否かと
いった,監督の最適な意思決定を状況別に計算できる.しかし,吉良・稲川(2014)のモデルは非定和ゲームであり(引き分けがある日本プロ野球ルールに起因),均衡勝率の一意性が保証されない.本論文では,約645万状態の有限非定和マルコフゲームとして定式化し,「勝つ確率を最大にする戦略の中から引き分ける確率を最大にする戦略を選ぶ」という辞書式順序の最適応答を考慮することで均衡点勝率の一意性を保証する.均衡勝率と均衡戦略を数秒で計算可能な動的計画アルゴリズムを与える.また,情報の価値の観点から後攻チームの優位性を議論する.さらに,試合中の意思決定を考慮した上での最適打順も導出する.

3.
Ross Recovery Theoremを用いたフォワードルッキングな収益率分布の推定
霧生 拓也(三菱UFJトラスト投資工学研究所),枇々木 規雄(慶應義塾大学)

Ross(2015)により,投資家の効用関数に関する特定の仮定の下で,リスク中立分布から実分布を推定する定理(Recovery Theorem)が示された.この定
理を利用して推定した実分布はフォワードルッキングな性質を持つことから,市場リスク管理やポートフォリオ最適化など,多くの金融の問題への応用が期待される.しかし,推定の過程で非適切問題を解く必要があるため,解がノイズの影響を受けやすく,精度の良い実分布の推定値を得ることは難しい.そこで本研究では,先験情報を考慮して正則化項を設定し,解を安定化する新たな方法を提案する.仮想データを用いた数値分析の結果から,提案方法は先行研究の方法に比べて精度良い推定値を得られることを示す.

ページトップへ戻る

JORSJ 62-3

1.
L1距離制約をもつ分離凸資源配分問題
南川 智都,塩浦 昭義(東京工業大学)
分離凸資源配分問題とは,離散的な資源を複数の活動へ配分することによって,経費・損失を表す分離凸関数を最小にすることを目的とする.本論文では,所与のベクトルと解ベクトルとのL1距離が定数以下,という制約の下での分離凸資源配分問題を考える.まず,単純な分離凸資源配分問題にL1距離制約を追加した問題が,劣モジュラ資源配分問題として定式化できることを示す.この結果から,劣モジュラ資源配分問題を解くための既存のアルゴリズムを利用することで,L1制約付き単純資源配分問題が多項式時間で解けることを示す.さらに,既存のアルゴリズムをL1制約付き単純資源配分問題に特化し,得られたアルゴリズムの計算時間の解析を行う.
2.
放射・環状道路網におけるコードン課金とエリア課金
宮川 雅至(山梨大学)

本論文ではコードン課金とエリア課金の2種類のロードプライシングに対して,課金領域の規模と料金を決定するためのモデルを提案する.コードン課金は課金領域へ流入する交通に課金するのに対し,エリア課金は課金領域内のすべての交通に課金する.まず,放射・環状道路網を有する円盤都市において起終点が一様に分布するときの交通量と料金収入を解析的に導出する.交通は起終点の位置に応じて通過交通,流入交通,流出交通,域内交通に分類する.そして,課金領域の規模と料金が各交通量と料金収入に及ぼす影響を明らかにする.また,通過交通を完全に排除する料金,ならびに料金収入を最大にする料金を求める.最後に,コードン課金に比べてエリア課金の方が,課金領域内の交通量の削減と料金収入の確保のいずれにおいても優れていることを示す.


ページトップへ戻る

JORSJ 62-4

1.
樹木育種に現れる混合整数二次錐計画問題に 対する多面体的手法
Sena Safarina(東京工業大学) Tim J. Mullin(スウェーデン森林研究所) 山下 真(東京工業大学)
樹木育種では,遺伝子の多様性を維持しながら利益 を最大化するような遺伝子型の割合を決定する最適化 問題が重要な問題の一つして認識されている.このう ち,遺伝子の多様性に関する制約は錐最適化理論で研 究が進む二次錐で表現可能であるが,一方で遺伝子型 の割合が均等である場合の用途も実用性があり,混合 整数二次錐計画問題への求解が必要である.しかし, 汎用ソルバーでは計算時間が長時間となり,計算時間 の短縮が重要な課題であった. 本研究では,二次錐を多面体で近似する手法と,二 次錐を複数の3次元の二次錐に分割して切除平面法を 用いる方法を提案している.特に後者は切除平面を解 析的に得られるように設計されており,さらに樹木育 種に現れる行列の疎性を切除平面も保持できることも 示した.数値実験を通して,この手法が汎用ソルバー よりも短時間で求解可能であり,疎性の活用が有効で あることを確認した.
2.
動的パトロールゲームについて
吉良 知文(群馬大学) 神山 直之(九州大学) 穴井 宏和,岩下 洋哲,大堀 耕太郎 (株式会社富士通研究所)

警備員と侵入者の各時点での位置に応じて決まる利 得(総視認度)を,警備員は最大化,侵入者は最小化 するゲームを考える.侵入者の学習能力に応じて3つ のケースを議論する.Case 1:警備員は動的巡回経 路(巡回経路+スケジュール)を選び,侵入者はこれ を完全に学習して動的侵入経路を選ぶ.Case 2:警 備員は動的巡回経路を乱択化し,侵入者はその確率分 布を学習して動的侵入経路を乱択化する.Case 3: 警備員の戦略はCase 2と同様であるが,侵入者は逐 次的に警備員の位置を学習してリルートできる.侵入 者の最適応答を求める問題は,時空間ネットワーク上 の最短経路問題(Case 1・2)とマルコフ決定過程 (Case 3)に帰着される.Case 1~3のシュタッケル ベルグ均衡を求める問題は,それぞれ多項式サイズの 混合整数線形計画問題,線形計画問題,双線形計画問 題に帰着される.


ページトップへ戻る
HOMEに戻る
カレンダー
日 程:2021/10/9(土)
場所:オンライ ン開催
テーマ:地理情 報システム入門
シンポジウム
2021 年春季シンポジウム
開催終了しました。
日 程:2021/3/1(月)
場所:東 京工業大学
(オ ンライン開催)
2021 年秋季シンポジウム
日程:2021/9/15 (水)
場所:九 州大学
(オ ンライン開催)
研究発表会
2021 年春季研究発表会
開催終了しました。
日程:2021/
3/2(月)~3(水)
場所:東 京工業大学
(オ ンライン開催)
2021 年秋季研究発表会
日程:2021/
9/16(水)~17(金)
場所:九 州大学
(オ ンライン開催)
= 会場開催についてのお知らせ=
「新型コロナウイルス感染予防のため、以下について、予め御了承いただけますよう、よろしくお願い 申し上げます。」

● 新型コロナウイルス感染拡大の状況によっては、イベントの開催を中止させていただく場合がございます。 ご来場前に必ず当該イベントのホームページにて開催の有無をご確認下さ い。

●参加者の皆様へのお願い
・発熱、強い倦怠感等の症状がある方は御来場を御遠慮下さい。

・感染予防のため、スタッフはマスクを着用している場合があることを御了承下さい。