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

HOME > 論文誌  > JORSJ論文概要 

JORSJ 62-1

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が有効な近似法であることが示唆された.

ページトップへ戻る
HOMEに戻る
イベントカレンダー
2019年度第1回ORセミナー
『Python言語によるビジネスアナリティクス』
日程:
2019/5/18(土)
場所:
(株)構造計画研究所 本所新館
参加申込人数が定員に達したため、申込受付を終了しました(2019/4/9)
シンポジウム
2019年秋季シンポジウム
日程:
2019/9/11(水)
場所:
東広島芸術文化ホールくらら
研究発表会
2019年秋季研究発表会
日程:
2019/9/12(木)-13(金)
場所:
東広島芸術文化ホールくらら