日時：2025 年 3 月 10 日（月） 13:30–18:00（開場は 13:00 頃）
開催方法：対面およびウェブ会議システム Zoom によるハイブリッド開催
対面会場：国立情報学研究所 (NII) 12 階 1208 号室
講演1
– 講演者：黒岩稜氏（国立情報学研究所）
– 講演題目：Domain-Independent Dynamic Programming：動的計画法に基づく組合せ最適化のための汎用ソルバ
– 講演概要：組合せ最適化問題を解くための実用的な手法として、整数計画法や制約プログラミングといった汎用ソルバが広く用いられている。一方で、状態とその遷移に基づいて問題を解決する手法である動的計画法は 、組合せ最適化における先行研究のほとんどでは、個別の問題に特化したアルゴリズムとして扱われてきた。本研究では、動的計画法モデルとして定式化されてた問題を解く汎用ソルバであるDomain-Independent Dynamic Programming（DIDP）を提案する。本講演においては、PythonライブラリであるDIDPPyを用いてDIDPにおけるモデリング手法を説明したのち、グラフ上の経路探索を用いるソルバのアルゴリズムを解説する。さらに、11のNP困難な組合せ最適化問題のベンチマーク問題集を用いてDIDPソルバを実験的に評価した結果を示す。本研究の実験設定では、複数の問題において、DIDPが商用の整数計画法ソルバであるGurobiと制約プログラミングソルバであるIBM ILOG CP Optimizerの性能を上回る。
講演2
– 講演者：澄田範奈氏（東京科学大学）
– 講演題目：バンディット最大最小効用公平割当
– 講演概要：本講演では，バンディット最大最小効用公平割当問題を導入する．この問題では，加法的な効用をもつエージェントに対して不可分財集合の割当を繰り返し行う．各エージェントの各財への価値はそれぞれ未知の確率分布に従い，各ラウンドでエージェントは受け取った財のそのラウンドでの価値をフィードバックする．目的は，エージェントの中で最小の累積効用を最大化することである．この問題は，競合比解析の文脈において類似した問題に比べて情報の与えられ方が異なる．また，リグレット解析での関連研究では目的関数がラウンドに関して加法的であるが，本講演で扱う目的関数は非加法的である．本講演で，バンディット最大最小効用公平割当問題に対してリグレット保証がほぼ最適なアルゴリズムを提案する．本講演の内容は，原田翼氏（東京科学大学）と伊藤伸志氏（東京大学）との共同研究に基づく．
参加費：無料
参加資格：自由（会員/非会員不問）
参加申込：
– 対面参加：申込不要です。
– オンライン参加：こちらのフォームからお申し込みください
なお、本研究部会の最新情報は研究部会のウェブページでご覧いただけます。
主査：林俊介（法政大学）
幹事：藤井海斗（国立情報学研究所）