第317回部会 (6月8日) の開催案内

第317回 「待ち行列研究部会」

日時：令和6年6月8日 (第2土曜日) 14:00～17:00
場所：ハイブリッド (早稲田大学西早稲田キャンパス&オンライン)

★★★★★★★ 参加申し込みフォーム★★★★★★★
参加形式（現地，オンライン）に関わらず、下記フォームにてお申込みください．
https://forms.gle/Ad5MhWYB5LjZBPQu5
※懇親会への参加人数把握のため、フォームでのお申込みについてよろしくお願いいたします．
★★★★★★★★★★★★★★★★★★★★★★★★

■ 対面参加の方へ：
対面会場は「早稲田大学 西早稲田キャンパス 63号館 1F数学応数会議室」です．
https://www.waseda.jp/top/access/nishiwaseda-campus

■ オンライン参加の方へ:
上記フォームの最終ページから参加登録をお願いいたします．

■ 講師とテーマ

1. 梅谷 俊治 (リクルート)
「実務につなげる数理最適化」

近年、機械学習によるデータ分析の普及に伴い、その結果を基にした意思決定や計画策定を実現する数理最適化が注目されている。 現在、有償・無償を問わず、多くの数理最適化ソルバーが利用可能となり、現実問題の解決手段として急速に普及している。 しかし、企業における数理最適化の専門家は少なく、大学から輩出される人材も限られているため、実務における数理最適化の活用はまだ限定的な範囲に留まっているのが現状である。この課題を解決するために、(1) 実務の各段階における問題解決を支援することを通じて数理最適化の専門家を育成し、基幹事業に数理最適化を活用する枠組みを創出すること、(2)産業や学術の幅広い現実問題に迅速に対応するための基盤技術となる高性能で汎用的な数理最適化ソルバーを開発することを目指して活動している。講演では、これらの取り組みを紹介する。
※ 関連記事: Recruit Data Blog (May 9, 2024) 「実務につなげる数理最適化」 梅谷俊治 ( https://blog.recruit.co.jp/data/articles/practical_optimization/ )

2. 増山 博之*(東京都立大学)、檀 寛成(早稲田大学)、梅谷 俊治(リクルート)
「スケールフリーの呪い: 多スタート法による大規模組合せ最適化の困難さ」

多スタート法は、大規模組合せ最適化問題に対する代表的なメタヒューリスティクスである。一般に、多スタート法による大規模組合せ最適化問題の求解過程においては、初期段階で最良解の目的関数値は急速に改善し、その後、解の改善頻度が極めて小さくなる「定常的な状態」に、比較的早く到達する現象が確認される。本研究の目的は、このような現象を理論的に解析し、理解を深めることである。この目的を達成するために、標準的な多様化機構をもつランダム多スタート（RMS）法に着目し、大規模組合せ最適化における最適値と最良実験値のギャップ（誤差）を詰める困難さを極値理論を用いて解析した。その結果、最適値からの最良実験値の相対ギャップがスケールフリー性を持つことが、数学的に示され、かつ、TSPの大規模インスタンスを対象とした数値実験でも確認できた。本研究ではこの現象を「スケールフリーの呪い」と称する。この「スケールフリーの呪い」を克服するには、最良解の改善効率がRMSと比べて指数関数的に向上した性能を有する多スタート法の開発が必要であり、これは容易なことではない。以上のことから示唆されるのは、「いかにギャップを詰めるか」よりも「いつ計算を止めるか」が重要であり、その判断は、最適値の推定よりも、追加反復による最良実験値の「期待改善率」のような指標に基づいて行うのが効果的だということである。