-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2020 Vol.6 ( 2020 年 11 月 11 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 『問題解決力を鍛える！アルゴリズムとデータ構造』 出版記念講演会 開催レポート ■ <トピック> 弊社主催数理最適化交流会 2020 ご報告 ■ <セミナー> オンラインセミナーのご案内 ■ < tips > 使ってみよう PySIMPLE（第 11 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 『問題解決力を鍛える！アルゴリズムとデータ構造』 出版記念講演会 開催レポート ****************************************************************** 弊社の顧問であり，元数理計画部部員でもある大槻氏の著書 『問題解決力を鍛える！アルゴリズムとデータ構造』の出版を記念した 講演会が 10 月 29 日に開催されました． （講演会紹介記事： https://www.msiism.jp/article/otsuki-algorithm-and-data-structure.html） 当初予定していた人数を大幅に上回る方々からの申し込みにより，急遽 申し込み枠を拡大する程の盛況ぶりで，アルゴリズムを専門にしている方 からこれから勉強を始めるという方まで，幅広い層の方にご参加いただき ました． オフラインとオンラインのハイブリッド開催であったため，感染症対策を 十分に行った上で，現地では書籍の即売会とサイン会も併せて実施し， とても盛り上がりのあるイベントとなりました． 講演の内容は，本を書いたモチベーションの説明から始まり，具体的な アルゴリズムの紹介を通じてアルゴリズムを学ぶ意義を解説するもので， 大槻氏のアルゴリズムに対する熱い思いが伝わってくるとともに， 改めて氏のアルゴリズムに対する造詣の深さを感じさせられました． （講演資料はこちらで御覧になれます： https://www.slideshare.net/drken1215/ss-239020647） 大変なご好評をいただき，「もう一度聞きたい」，「もっと詳しく解説 してほしい」などの声も多く寄せられているため，続編や再開催， 講演内容のオンデマンド配信などを現在企画検討中です． 最新の情報については，弊社オウンドメディア MSIISM（https://www.msiism.jp/） にてお知らせしていきますので，楽しみにお待ちください． （松岡 勇気） ****************************************************************** ■ <トピック> 弊社主催数理最適化交流会 2020 ご報告 ****************************************************************** 10 月 30 日に「数理最適化交流会 2020」というイベントをオンライン 開催させていただきました． 当日は 100 名近い方にご参加いただきました． ご参加の方々はまことにありがとうございました． 講演はもちろん，講演後のパネルディスカッションも盛り上がったのが 印象的でした． 「今後の数理最適化の利用シーン」という話題でも 「組み込み環境における最適化」など多様なアイデアが出て，今後の 数理最適化の未来を垣間見た気がいたしました． 詳しい報告は MSIISM にて近日公開予定です！ 楽しみにお待ちください． 今回は開催の都合上，参加人数に上限を設けさせていただきました． 参加したかったにもかかわらずできなかった方にはお詫び申し上げます． ご好評のため来年も類似の企画を検討しておりますので，是非その際は ご参加お待ちしております． （藤井 浩一） ****************************************************************** ■ <セミナー> オンラインセミナーのご案内 ****************************************************************** 12 月 9 日に金融工学セミナーをオンラインで開催いたします． このセミナーでは PySIMPLE を用いて金融工学にかかわるモデルを解く 例をご紹介いたします．オンラインかつ無料のセミナーですので， お気軽にご参加ください． また，金融工学セミナー以外にも定例開催の紹介セミナーとエネルギー マネジメントに特化したセミナーをご用意しています． こちらもぜひご検討ください． ・金融工学セミナー https://msi.hmup.jp/nuopt/seminar/finance 日程とお申込みページ 2020 年 12 月 09 日 (水) 13:30～15:30 https://area34.smp.ne.jp/area/card/26339/8kDJ1F/M?S=lbpftj0lcpb0k ・エネルギーマネジメント最適化セミナー https://msi.hmup.jp/nuopt/seminar/enemanage 日程とお申込みページ 2020 年 12 月 18 日 (金) 13:30～15:30 https://area34.smp.ne.jp/area/card/26339/0kRJAj/M?S=lbpftj0lcne0k ・Numerical Optimizer 紹介セミナー https://msi.hmup.jp/nuopt/seminar/webinar 日程とお申込みページ 2020 年 12 月 08 日 (火) 13:30～15:30 https://area34.smp.ne.jp/area/card/26339/0fr5BG/M?S=lbpftj0lcof0k （石橋 保身） ****************************************************************** ■ < tips > 使ってみよう PySIMPLE（第 11 回） ****************************************************************** このコーナーでは，Numerical Optimizer V21 以降の機能であるモデリング 言語 PySIMPLE のエッセンスを紹介していきます． 今までの連載では SIMPLE と PySIMPLE を比較しながら PySIMPLE の特長を 紹介してきました．今回は PySIMPLE の苦手とする，添字のマッチングに ついて紹介します．ちょっと複雑なのでご注意くださいませ． 物流などで登場するフローネットワークによく見られる保存則を考えます． まずはノード 1, 2, 3, 4 が互いに輸送できる条件で保存則を考えてみま しょう．ネットワークを図示すると以下のようになります． ① ─ ② ｜ × ｜ ③ ─ ④ 保存則，すなわち各ノードでの入力と出力が等しいという制約を SIMPLE で 記述すると以下のようになります． ------------------------------------------------------------------ Set N="1 2 3 4"; Element i(set=N), j(set=N), k(set=N); Variable x(index=(i,j)); sum(x[j,i], j) == sum(x[i,j], j); //sum(x[i,k], i) == sum(x[k,j], j); // これでも同じ ------------------------------------------------------------------ showSystem() 関数で展開を表示させてみると意図通りになっていることが 分かります． ------------------------------------------------------------------ -x[1,1]-x[2,1]-x[3,1]-x[4,1]+x[1,1]+x[1,2]+x[1,3]+x[1,4] == 0 -x[1,2]-x[2,2]-x[3,2]-x[4,2]+x[2,1]+x[2,2]+x[2,3]+x[2,4] == 0 -x[1,3]-x[2,3]-x[3,3]-x[4,3]+x[3,1]+x[3,2]+x[3,3]+x[3,4] == 0 -x[1,4]-x[2,4]-x[3,4]-x[4,4]+x[4,1]+x[4,2]+x[4,3]+x[4,4] == 0 ------------------------------------------------------------------ 次に，一部のノードしか輸送できない条件(疎であるケース)を考えてみま しょう．まずは一旦，すべてのノードに入力と出力があるという条件で 考えることにします． ------------------------------------------------------------------ Set N; Element i(set=N), j(set=N), k(set=N); Set IJ(dim=2, superSet=(N,N)); IJ = "1,4 2,1 2,3 3,6 4,5 5,2 6,5"; Variable x(index=IJ); sum(x[j,i], (j, (j,i)<IJ)) == sum(x[i,j], (j, (i,j)<IJ)); //sum(x[i,k], (i, (i,k)<IJ)) == sum(x[k,j], (j, (k,j)<IJ)); // 同じ ------------------------------------------------------------------ この例ではネットワークに以下のような入出力の関係があります． ① ← ② → ③ ↓ ↑ ↓ ④ → ⑤ ← ⑥ 同様に展開を表示させてみると以下のようになります． ------------------------------------------------------------------ -x[2,1]+x[1,4] == 0 -x[5,2]+x[2,1]+x[2,3] == 0 -x[2,3]+x[3,6] == 0 -x[1,4]+x[4,5] == 0 -x[4,5]-x[6,5]+x[5,2] == 0 -x[3,6]+x[6,5] == 0 ------------------------------------------------------------------ このような制約を PySIMPLE で記述するにはちょっと工夫が必要です． SIMPLE では sum をとった残りの添字が自動的にマッチングするのですが， PySIMPLE で Sum(x[ij], ij(0)) == Sum(x[ij], ij(1)) と記述してしまう と，それができないためです．そこでマッチング用の添字 k を用意すると いう工夫をすることで以下のように記述することができます． ------------------------------------------------------------------ IJ = Set(value=[(1,4), (2,1), (2,3), (3,6), (4,5), (5,2), (6,5)]) ij = Element(set=IJ) x = Variable(index=ij) k = Element(set=IJ(0)|IJ(1)) # k in (1, 2, 3, 4, 5, 6) Sum(x[ij], ij(0))[k] == Sum(x[ij], ij(1))[k] ------------------------------------------------------------------ では，すべてのノードに入出力があるとは限らない場合ではどうでしょうか． 実は SIMPLE では同じ記述で大丈夫なのですが，PySIMPLE ではここから 更にもう一工夫が必要です．以下のようなフローネットワークを考えてみま しょう．先ほどと異なり，①は出力のみ，⑥は入力のみとなっています． ① → ② → ③ ↓ ↑ ↓ ④ → ⑤ → ⑥ ------------------------------------------------------------------ IJ = Set(value=[(1,2), (1,4), (2,3), (3,6), (4,5), (5,2), (5,6)]) ij = Element(set=IJ) x = Variable(index=ij) ------------------------------------------------------------------ PySIMPLE で同じ記述をすると，添字 k が出力のみの①，入力のみの⑥で KeyError となってしまいます．そこで，制約を入出力あり，出力のみ， 入力のみの 3 つに分解することで以下のように記述することができます． ------------------------------------------------------------------ m = Element(set=IJ(0)&IJ(1)) # m in (2, 3, 4, 5) Sum(x[ij], ij(0))[m] == Sum(x[ij], ij(1))[m] # 入出力あり Sum(x[ij], ij(1))[ij(0)>IJ(1)] == 0 # ij(0)>IJ(1) in (1,) Sum(x[ij], ij(0))[ij(1)>IJ(0)] == 0 # ij(1)>IJ(0) in (6,) ------------------------------------------------------------------ ここで，IJ(0) は IJ の一次元目，すなわち始点ノードの集合 (1, 2, 3, 4, 5) を，IJ(1) は終点ノードの集合 (2, 3, 4, 5, 6) であるので， ij(0)>IJ(1) は出力のみのノード IJ(0)-IJ(1)=(1,) に対応する添字です． ------------------------------------------------------------------ (Sum(x[ij], ij(0))[m]==Sum(x[ij], ij(1))[m]): x[1,2]-x[2,3]+x[5,2]==0 x[1,4]-x[4,5]==0 x[2,3]-x[3,6]==0 x[4,5]-x[5,2]-x[5,6]==0 (Sum(x[ij], ij(1))[(ij(0)>IJ(1))]==0): x[1,2]+x[1,4]==0 (Sum(x[ij], ij(0))[(ij(1)>IJ(0))]==0): x[3,6]+x[5,6]==0 ------------------------------------------------------------------ もう一つとして，中間変数を立てるという方法もあります． こちらは数理計画問題として別の問題となってしまうので注意が必要です． ------------------------------------------------------------------ k = Element(set=IJ(0)|IJ(1)) # k in (1, 2, 3, 4, 5, 6) xj = Variable(index=k) xj[ij(1)] == Sum(x[ij], ij(0)) # ij(1) in (2, 3, 4, 5, 6) xj[k>IJ(1)] == 0 # k>IJ(1) in (1,) xi = Variable(index=k) xi[ij(0)] == Sum(x[ij], ij(1)) # ij(0) in (1, 2, 3, 4, 5) xi[k>IJ(0)] == 0 # k>IJ(0) in (6,) xj[k] == xi[k] ------------------------------------------------------------------ いかがでしたでしょうか．PySIMPLE は SIMPLE に比べてより簡潔に記述 できる制約も多い反面，今回のように工夫が必要な部分もあります． 記述方法にお困りの際はご遠慮なくお問い合わせくださいませ． Numerical Optimizer のサポートフォームはこちら: http://www.msi.co.jp/nuopt/user/index.html （池田 悠） ================================================================== ※ このメールは，弊社ツールのユーザー様，過去に展示会などでお名刺 等を頂いたことのある方や当社に直接お問合せを頂いたことのある方 にお送りしています． ※ バックナンバーはこちらから御覧頂けます． https://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後，本メールマガジンやご案内に関するメールが不要な方は，誠に お手数ですが，下記 URL より「案内停止手続き」をしてくださいます ようお願いいたします． ■ 案内停止はこちらから ■ [都合により本ページでは URL を掲載しておりません] ご登録される情報は，暗号化された通信(SSL)で保護され， プライバシーマークや ISO27001/JIS Q 27001, ISO20000-1, ISO9001 の認証を取得している株式会社パイプドビッツによる情報管理 システム「スパイラル」で安全に管理されます． 上記にアクセスができない場合には「メール不要」と明記の上， nuopt-ms@ml.msi.co.jp （このメールに返信で結構です）にメール送付してください． 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================