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

HOME > 論文誌  > JORSJ論文概要 


JORSJ 60-1 

JORSJ 60-1

1.
逐次ロジットモデルにおける区分線形近似を利用した特徴選択
佐藤 俊樹 (筑波大学)
高野 祐一 (専修大学)
宮代 隆平 (東京農工大学)
 

本論文では,逐次ロジットモデルの特徴選択問題を扱う.この問題に対して,田中・中川(2014)はロジスティック損失関数を2次近似し,混合整数2次最適化問題による定式化を提案した.しかしながら,2次近似はロジスティック損失関数に対する近似誤差が非常に大きくなってしまうという欠点がある.この欠点を克服するために,本論文ではロジスティック損失関数に対して区分線形近似を適用し,情報量規準に基づく逐次ロジットモデルの特徴選択問題を混合整数線形最適化問題として定式化する.計算機実験の結果,区分線形近似を用いた定式化は,2次近似を用いた定式化よりも良い特徴選択ができることを示した.
2.
Forcing Graph付き最小化ナップサック問題に対する2-近似アルゴリズム
高澤 陽太朗,水野 眞治 (東京工業大学)
 

Carnes and Shmoys(2015)は最小化ナップサック問題に対して2-近似アルゴリズムを提案した.本論文ではこのアルゴリズムを拡張し,Forcing graph付き最小化ナップサック問題(MKPFG)に対して2-近似アルゴリズムを与えた.MKPFGは最小化ナップサック問題に,「ある要素のペアのうちどちらか一方は選ばなくてはならない」という,Forcing制約が追加された問題である.MKPFGは特殊ケースとして頂点被覆問題を含むことからStrongly NP-hardである.以上の結果に加えて,本論文では提案アルゴリズムの一般化を行い,より広いクラスの問題である0?1変数のCovering整数計画問題に対しても新しい近似アルゴリズムを与えた.

3.
モジュラリティ最大化問題に対する切除平面法
伊豆永 洋一 (一般財団法人計量計画研究所)
山本 芳嗣 (静岡大学)
 

与えられたネットワークを密な部分ネットワークに分割するコミュニティ抽出では,NewmanとGirvanによって提案されたモジュラリティと呼ばれる評価関数の最大化を目指す手法が広く知られている.本論文では,モジュラリティ最大化問題を集合分割問題として定式化し,その線形計画緩和問題に対して切除平面法に基づく解法を提案する.提案手法の特徴の一つとして,モジュラリティ最大化問題の異なる定式化に対する緩和問題の構造を利用することにより,切除平面法の各反復で,モジュラリティの上界値が算出可能な点が挙げられる.同時に複数本の切除平面を追加することにより切除平面法の収束の遅さを改善し,標準的なベンチマーク問題を用いた数値実験を実施した結果,提案手法は非常にタイトな上下界値を得ることを確認した.

ページトップへ戻る
HOMEに戻る
イベントカレンダー
 
シンポジウム
 
研究発表会
2017年春季研究発表会
日程:
2017年3月15日(水)-17日(金)
場所:
沖縄県市町村自治会館