組合せ最適化研究室

宋研究室では、経営工学の関連分野で派生する様々な問題に対して、数理的な手法を用いて効率的な解法の開発を行っている。 主に組合せ最適化問題として定式化できる問題を対象としている。 最近は取り組んでいる主なテーマは以下の通りである。

研究紹介

■集団形成ゲーム: 社会において、人間、組織、国などのプレイヤーは集団を形成し、各プレイヤーの選好や集団形成のメカニズムによって社会全体の構造が変化する。この研究では、社会の仕組みのモデル化を行ったうえ、仮想的な社会のシミュレーションや仮説の理論的裏付けを与えるなどを行う。

■スケジューリング: この研究では、製品の組み立て順序、複数の生産ラインへの作業工程の割り当て、学校・交通機関における時間割作成などの問題を対象としている。最近は特に多品種少量生産を目的としたジャストインタイム方式における様々なスケジューリング問題を対象に解法の開発を進めている。

■公平分割問題: 公平分割問題とは、複数のプレイヤー(人間、組織、国など)が共有する単数または複数のもの(財産、施設、資源など)の公平な分配方法に関する研究である。そこで、人間、組織、国などが関わる様々な問題に対して、公平分割問題としての定式化および解法の開発を行っている。

■最適解の高速並列探索: 多くの組合せ最適化問題に対して効率的な解法が発見されておらず、その最適解を求めるため膨大な計算時間を必要とする。そこで、計算時間を短縮するため、最適解の探索という巨大な計算タスクを分割して並列化する手法や分割した計算タスク間で共有すべき情報について研究している。

卒論・修論

game theory
ヘドニックゲームにおける選好の複雑さと安定分割構築について
2018, 修論
game theory
活動選択ゲームにおける集団意思決定に着目した安定割当導出メカニズムの分析
2018, 修論
game theory
ソーシャルネットワークの動的構造変化を考慮した活動選択ゲームとその個人的安定割当について
2018, 卒論
game theory
ヘドニック選好の階層数によるNash 安定分割の存在判定への影響
2018, 卒論
game theory
加法的ヘドニックゲームにおける契約的強コア安定集団構造を導く効果的な逸脱について
2018, 卒論
game theory
敵重視ヘドニックゲームにおけるコア安定集団構造の近似的構成
2018, 卒論
game theory
活動における役割を考慮した活動選択ゲームの提案
2018, 卒論
game theory
無向非循環ネットワークにおける活動選択ゲームの Nash 安定割当について
2018, 卒論
game theory
辺の構築制約付きネットワーク形成ゲームにおける均衡解について
2018, 卒論
network optimization
動的計画法による多目的最短経路と全点間信頼度の並列計算手法の提案
2018, 修論
network optimization
多目的最短経路問題のための拡張ベルマンフォード法の提案
2018, 卒論
network optimization
正方格子グラフの全点間信頼度計算について
2018, 卒論
web application
プログラミング教育支援におけるクラウド型課題提出システムの開発
2018, 卒論
game theory
GAS ゲームにおける安定概念に対する逸脱集合に基づく記述と安定割当判定問題について
2017, 卒論
game theory
ヘドニックゲームの厳密な選好プロファイル空間における安定インスタンスの分布と近傍について
2017, 卒論
game theory
加法的ヘドニックゲームにおける契約的個人安定集団構造を導く効果的な逸脱について
2017, 卒論
network optimization
全点間信頼度最大化のためのネットワーク均衡概念の提案
2017, 卒論
scheduling
タスク選択を考慮した人員配置問題に対する貪欲解法の有効性
2017, 修論
scheduling
並列機械モデルにおける最大待ち時間最小化問題の計算論的分析
2017, 卒論
game theory
GASP における Core 安定な割当の探索アルゴリズムについて
2016, 卒論
game theory
GASP における Core 安定割当存在判定の計算複雑さについて
2016, 卒論
game theory
分離可能ヘドニックゲームにおける契約的安定集団構造の効率的構成方法の提案
2016, 卒論
game theory
逸脱近傍による GASP の契約的安定割当探索について
2016, 卒論
network optimization
一様確率と一様コスト制約下の全点間信頼度最大ネットワークの構造分析
2016, 卒論
scheduling
個別指導塾における受講希望充足度最大化へのアプローチ
2016, 卒論
scheduling
制約プログラミングによる卒業論文発表会プログラム導出法の提案
2016, 卒論
scheduling
合流可能な一様並列機械モデルにおけるメイクスパンの最小化
2016, 卒論
social choice
Consent Group Control における双対性と実行可能性について
2016, 卒論