数理最適化: Optimization Night #9

イベント内容

この会について

数理最適化に興味のある人達であつまって、わいわいがやがや議論する会です！

今回はソルバー会ということで、個人でソルバーを作成されている今井さん、小熊さんに、ソルバーの実装に関するお話をしていただきます。後半の議論セッションで、お話いただいた内容をベースにみんなで議論できたらと思います。

今回も株式会社ブレインパッド様の会議室を借りて開催します。 また、株式会社ALGO ARTIS様のご協力により、現地参加の方には飲み物と軽食を準備しています。

現地参加に加え、YouTube Live による配信も行う予定です。 URL は決定次第こちらのページで公開いたします。

質問について

質問は Sli.do にて受け付けます。

• https://app.sli.do/event/pNPh2ktXMat13N7c7x1S3P
• もしくは sli.do で #opt009 と入力

参加対象者

数理最適化・OR等に興味のある方を対象としています。

タイムスケジュール

スケジュールは変更となる可能性があります。ご理解ください。

時間	タイトル	発表者	内容
18:30 -	受付	-	-
18:45 - 18:50	運営より	ohtaman	イントロダクション
18:50 - 18:55	スポンサー枠	株式会社ブレインパッド	-
18:55 - 19:00	スポンサー枠	株式会社 ALGO ARTIS	-
19:00 - 19:40	CDCL による厳密解法を採用した MILP ソルバー	今井さん	実務において数理最適化を活用して課題を解決する際には，課題を解決するために解くべき問題を MILP (混合整数線形計画問題)として定式化し，既存のソルバーを使って解を求めるというアプローチが広く用いられています．多くの MILP ソルバーの実装では分枝限定法が採用されていますが，発表者は CDCL (Conflict Driven Constraint Learning) による厳密解法を採用したソルバーを趣味で開発しています．本発表では，数理最適化とソルバーについて簡単に紹介したのち， CDCL を用いた厳密解法の概要と，分枝限定法・ベンダーズ分解・ SMT (Satisfiability Modulo Theories) ソルバーなどの他の厳密解法との関連について説明します．
19:40 - 20:20	メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発	Yuji Koguma さん	線形整数計画問題は，さまざまな組合せ最適化問題を定式化できる応用性に富んだ問題クラスであり，分枝限定法に基づく高性能なソルバーが多数開発・提供されています。分枝限定法は厳密解法であり，入力されたインスタンスに対して最適解（あるいは実行不可能性の証明）が得られるという利点がありますが，効率的な探索の成否は問題の規模のみならず構造に大きく依存します。他方，実務においては，最適性の証明よりも短時間で良質な実行可能解を求めることが重視されることも多く，そのような場合はメタヒューリスティクスも有力な手法の候補となり得ます。そこで，分枝限定法ソルバーを性能面で補完する汎用的な最適化手段を得ることを目的として，メタヒューリスティクスに基づく汎用線形整数計画ソルバー「PRINTEMPS」を開発し，オープンソースソフトウェアとして公開しています。本講演では，開発したソルバーについて，開発の背景・目的とあわせて紹介したうえで，アルゴリズムの概要，設計・実装のポイント，開発プロセス等について説明します。
20:20 - 20:30	休憩
20:30 - 21:00	議論	sfujiwara & 全員	講演内容を題材に議論します
21:00	解散	-	残りたい人だけ残っていろいろ話しましょう〜

当日の参加方法について

具体的な参加方法は、参加者の方に別途お伝えいたします。

注意事項