バックナンバー ( 2021 Vol.4 ) 2021 年 8 月 11 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2021 Vol.4 ( 2021 年 8 月 11 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> IFORS 2021 発表予定 ■ <トピック> "The Cutting Plane Game" のご紹介～～入門編～～ ■ <トピック> 出展・発表案内 ■ <セミナー> オンラインセミナーのご案内 ■ < tips > 使ってみよう PySIMPLE（第 13 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> IFORS 2021 発表予定 ****************************************************************** 2021 年 8 月 23 日から 27 日にかけてオペレーションズリサーチの 国際会議の IFORS 2021 に参加し，Numerical Optimizer に関連した 発表を予定しています． IFORS は 3 年ごとに開催され，毎回の参加者は 2000 人を超える大きな 国際会議です．今年は韓国のソウルで開催される予定でしたがオンライン となっています． 私の発表内容は擬コストと並列分枝限定法の話です．最小化問題を仮定す ると，擬コストは分枝後の緩和問題の目的関数値がどれほど上昇するかを 推定する値で，分枝させる変数を選択する上で非常に重要な指標値です． 並列分枝限定法では擬コストの情報を共有メモリの場合は全スレッドで， 分散メモリの場合は全プロセスで共有するとノード数の削減を期待できま す．一方，共有メモリの場合は排他制御が，分散メモリの場合は通信によ るオーバーヘッドが生じるため，必ずしも計算時間を短縮できるとは限り ません．また，並列分枝限定法の設計に依存して適切な共有方法も変わる 可能性もあります． 私の発表では Numerical Optimizer において共有メモリにおける擬コスト の共有方法とその効果について発表します．Numerical Optimizer の並列 分枝限定法は Ubiquity Generator framework (UG) の手法を元にしており， この手法における擬コストの共有方法をいくつか提案し，その効果を計算 実験により確認します． 発表タイトルは Pseudocost sharing in NuOpt です．まだプログラムが 公開されていないため，具体的な日程は不明ですが，参加される方で こちらのタイトルが目に入った方はぜひお立ち寄りください． UG についてはこちらをご覧ください． https://ug.zib.de/index.php （石橋 保身） ****************************************************************** ■ <トピック> "The Cutting Plane Game" のご紹介～～入門編～～ ****************************************************************** 今回は "The Cutting Plane Game" についてご紹介します． これは Gonzalo Munoz 博士（現 O'Higgins 大学 assistant professor） の開発した，整数計画の教育・普及を目的としたゲームです． ゲームはこちらからアクセスできます： http://www.columbia.edu/~gm2543/cpgame.html （2021/08/18 アクセス確認） 本ゲームの目的は，「得られている多面体に対して，切除平面を加える ことによって，可能な限りその整凸包（多面体内の整数点を含む最小の 凸多面体）に近づけること」です． ちょっと難しく聞こえるかもしれませんが，要するにはユーザはどんどん 切除平面を加えることにより与えられた多面体をできるだけ「整える」と いうゲームです． ゲームは全部で 9 面あります．スタート画面から「 ARCADE MODE 」選ぶ とゲームが始まります．真ん中に平面を加えるべき多面体が現れ，右側に は利用できる切除平面の一覧が現れます．各切除平面にあらわれている 数字は「切除平面をつかってよい回数」なので注意しましょう． 切除平面は別名妥当不等式とも呼ばれます．以下の説明をご参考ください． 数理計画用語集・妥当不等式： https://www.msi.co.jp/nuopt/glossary/term_167e2968d79e57b147ffb376f70159d277feacb7.html 切除平面は以下の四つが用意されています． (1) サークルカット (2) ゴモリーカット (3) 横方向スプリットカット (4) 縦方向スプリットカット それぞれを簡単にご説明します． (1) サークルカットは，ユーザがクリックした点にたいして「整数点を 含まない最大の円」を形成し，その円と多面体の共通部分に含まれる 切除平面が加えられます． (2) ゴモリーカットは，まさに整数計画の教科書にあらわれるゴモリー カットですね．多面体の端点をクリックすると発動し端点を切り落とす ような切除平面が加えられます． (3), (4) のスプリットカットは，それぞれ横方向および縦方向に空間を 分割し，分割された空間と多面体の共通集合からえられる切除平面が 加えられます． なかなかメールマガジンだとビジュアル的な説明が難しいですね． 近日中に弊社 MSIISM サイトにて，より詳しく解説した記事を執筆します！ ぜひご参考ください． （藤井 浩一） ****************************************************************** ■ <トピック> 出展・発表案内 ****************************************************************** 今年も多くの学会がオンライン開催されることに伴い Numerical Optimizer もオンライン出展いたします． 日本オペレーションズ・リサーチ学会 2021 年秋季研究発表会＆シンポジウム 開催日：9 月 15 日(水) ～ 9 月 17 日(金) https://orsj.org/nc2021f/ 令和 3 年 電気学会 電力・エネルギー部門大会 開催日：8 月 24 日(火) ～ 8 月 26 日(木) http://ieej-pes.org/pes_2021/ 日本機械学会 2021 年度 年次大会 開催日：9 月 5 日(日) ～ 9 月 8 日(水) https://confit.atlas.jp/guide/event/jsme2021/top スケジューリング・シンポジウム 2021 開催日：9 月 24 日(金) ～ 9 月 25 日(土) http://www.scheduling.jp/symposium/2021/ オンラインではありますが，一部学会ではソフトウェア展示なども行って おります．学会参加の折は是非お立ち寄りください． また以下の学会で発表をいたします． 国際学会「 IFORS 2021 」 開催日：8 月 23 日(月) ～ 8 月 27 日(金) "Pseudocost sharing in NuOpt" *石橋保身（株式会社 NTT データ数理システム） 藤井浩一（株式会社 NTT データ数理システム） 逸見宣博（株式会社 NTT データ数理システム） 国際学会「Operations Research 2021」 開催日：8 月 31 日(火) ～ 9 月 3 日(金) "Solving Challenging Large Scale QAPs with DNN-based Branch-and-bound Method" *藤井浩一（株式会社 NTT データ数理システム） 伊藤直紀（株式会社ファーストリテイリング） Sunyoung Kim（梨花女子大学校） 小島政和（中央大学） Hans Mittelmann（Arizona State University） 品野勇治（Zuse Institute Berlin ） Kim-Chuan Toh（シンガポール国立大学） 大規模な二次割当問題（QAP）を解くプロジェクトの進捗状況を報告します． 本プロジェクトでは，Ubiquity Generator (UG) フレームワークを用いて 実装された並列分枝限定法により QAP を解きます． 下界計算には二重非負緩和に対するニュートン・ブラケット法を採用し， 本講演では分枝ルールや並列化計算の詳細について解説します． QAPLIB の tai30a と sko42 を含むオープンインスタンスを初めて解いた 数値結果も併せて紹介します． 参考： Fujii, Koichi, Naoki Ito, Sunyoung Kim, Masakazu Kojima, Yuji Shinano, and Kim-Chuan Toh. "Solving Challenging Large Scale QAPs." arXiv preprint arXiv:2101.09629 (2021). （藤井 浩一） ****************************************************************** ■ <セミナー> オンラインセミナーのご案内 ****************************************************************** これからも引き続きオンラインセミナーを開催してまいります． 以下にて紹介しておりますセミナーはいずれも無料ですので， ぜひご参加ください． 「Numerical Optimizer 紹介セミナー」では 最適化や Numerical Optimizer の概要を紹介しております． 「エネルギーマネジメント最適化セミナー」や 「Numerical Optimizer 金融工学セミナー」は それぞれのトピックに特化した，より掘り下げた内容となっております． 「最適化無料個別相談会」では，最適化についての様々なご相談事を 承っております． 柔軟に対応させていただきますので，お気軽にお申し込みください． ご参加お待ちしております． ・日程 [ Numerical Optimizer 紹介セミナー ] 8/24 (火) 13:30 - 15:30 9/14 (火) 13:30 - 15:30 [ エネルギーマネジメント最適化セミナー ] 9/ 9 (木) 13:30 - 15:30 [ Numerical Optimizer 金融工学セミナー ] 8/25 (水) 13:30 - 16:30 [ 最適化無料個別相談会 ] 随時開催 ・お申込みページ https://www.msi.co.jp/nuopt/seminar/index.html （佐久間 寛人） ****************************************************************** ■ < tips > 使ってみよう PySIMPLE（第 13 回） ****************************************************************** このコーナーでは，Numerical Optimizer の Python インターフェース PySIMPLE のエッセンスを紹介していきます． 3 月にリリースされた V23 では大きく 2 つの機能が追加されました． - 二次計画問題への対応 - メタヒューリスティクスアルゴリズム wcsp/wls の利用 今回はこのうち二次計画問題の扱い方について見ていきましょう． V22 までの PySIMPLE では制約式と目的関数が線形である，線形計画問題 のみに対応していましたが，V23 では二次の式を扱うことができるように なりました． ------------------------------------------------------------------ >>> i = Element(value=[1, 2], name='i') >>> x = Variable(index=i, name='x') >>> x[i]*x[i] (x[i]*x[i]): x[1]**2 x[2]**2 ------------------------------------------------------------------ また，**2 や pow 関数を使うこともでき，同じ意味となります． ------------------------------------------------------------------ >>> x[i]**2 (x[i]**2): x[1]**2 x[2]**2 >>> pow(x[i], 2) (x[i]**2): x[1]**2 x[2]**2 ------------------------------------------------------------------ SIMPLE では pow 関数を用いると，非線形計画問題扱いとなりますが， PySIMPLE では pow(線形式, 2) は二次の式と解釈されます． 今度は次の例を見てみましょう． ------------------------------------------------------------------ >>> a = Parameter(index=i, value={1: 1, 2: 2}, name='a') >>> a[i]*x[i]*x[i] ((a[i]*x[i])[i]*x[i]): x[1]**2 2*x[2]**2 >>> a[i]*x[i]**2 (a[i]*(x[i]**2)[i]): x[1]**2 2*x[2]**2 ------------------------------------------------------------------ 結果はもちろん同じなのですが，演算子の優先順位の関係で， a[i]*x[i]*x[i] は (a[i]*x[i])*x[i]，a[i]*x[i]**2 は a[i]*(x[i]**2) の順で計算されます．実は，PySIMPLE では変数同士の積は専用の高速化を 行っているため，後者の方がパフォーマンスが良くなります．したがって， a[i]*(x[i]*x[i]) でもパフォーマンスが向上します．このため，PySIMPLE では積極的に **2 を用いた方がよいでしょう． いかがでしたでしょうか．V23 ではこれらの新機能に加え，動作環境の 追加や細かな不具合修正も行われていますので確認してみてください． V23 の PySIMPLE の更新履歴はこちら: https://www.msi.co.jp/nuopt/docs/v23/pysimple/changelog.html （池田 悠） ================================================================== ※ msi-ms@ml.msi.co.jp は送信専用アドレスです。 本メールにそのままご返信いただいてもご回答いたしかねます。 ※ このメールは、弊社ツールのユーザー様、過去に展示会などで お名刺等を頂いたことのある方や 当社に直接お問合せを頂いたことのある方にお送りしています。 ※ バックナンバーはこちらから御覧頂けます。 https://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します。 ※ 今後、ご案内メールが不要な方は、誠にお手数ですが、下記 URL より 「案内停止手続き」をしてくださいますようお願いいたします。 ■ 案内停止はこちらから ■ [都合により本ページでは URL を掲載しておりません] ご登録される情報は、暗号化された通信(SSL)で保護され、プライバシーマークや ISO27001/JIS Q 27001, ISO20000-1, ISO9001の 認証を取得している 株式会社パイプドビッツによる情報管理システム「スパイラル」で安全に管理されます。 上記にアクセスができない場合には「メール不要」と明記の上、 nuopt-info@ml.msi.co.jp までご連絡いただけますと幸いです。 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================