-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン https://www.msi.co.jp/nuopt/ 2022 Vol.6 ( 2022 年 11 月 29 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ Nuorium Optimizer をはじめとして，最適化に関する様々な情報や ご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 書籍「最適化アルゴリズム （原題: Algorithms for Optimization）」刊行のご案内 ■ <セミナー> オンラインセミナーのご案内 ■ < tips > 使ってみよう PySIMPLE（第 21 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 書籍「最適化アルゴリズム （原題: Algorithms for Optimization）」刊行のご案内 ****************************************************************** 12 月 23 日に，弊社メンバーが翻訳を担当した書籍「最適化アルゴリズム」が 共立出版様より発売されます．こちらはスタンフォード大学准教授の Mykel J. Kochenderfer 氏とその弟子である Tim A. Wheeler 氏による共著 "Algorithms for Optimization" (MIT Press, 2019) の翻訳本となります． 微分の説明から始まり，1 次法や 2 次法，線形計画問題といった基本的な 内容はもちろんのこと，多目的最適化や代理モデル，不確実性下の最適化や 複合領域最適化など，幅広い話題を扱っています． 各トピックに対して，様々なアルゴリズムをプログラミング言語 Julia に よる実装例付きで紹介しているのが本書の特徴です． 学部生や院生の方だけでなく，研究者の方や実務家の方にもオススメの 一冊ですので，是非書店でチェックしてみてください！ 書籍情報はこちらから閲覧できます： https://www.kyoritsu-pub.co.jp/book/b10024250.html （松岡 勇気） ****************************************************************** ■ <セミナー> オンラインセミナーのご案内 ****************************************************************** 1 月までに開催する無料のオンラインセミナーをご紹介します． 1 月には製造系のスケジューリングに関するセミナーを開催します． 数理最適化とは何か，という基本的なところから入りますので， どなたもお気軽にご参加ください． また、定例の紹介セミナーとハンズオンセミナーも開催予定です． ハンズオンセミナーは実際に製品を動かしながら受講いただける セミナーになっています． こちらもぜひお気軽にご参加ください． [ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー ] 2023 年 01 月 25 日 (水) 13:30～15:30 詳細とお申込み：https://www.msiism.jp/event/nuopt-manufacturing-scheduling.html [ Nuorium Optimizer 紹介セミナー ] 2022 年 12 月 16 日 (金) 13:30～15:30 詳細とお申込み：https://www.msiism.jp/event/nuopt-introduction.html [ Nuorium Optimizer ハンズオンセミナー ] 2022 年 12 月 07 日 (水) 13:30～16:00 詳細とお申込み：https://www.msiism.jp/event/nuopt-hands-on.html （保科 拓紀） ****************************************************************** ■ < tips > 使ってみよう PySIMPLE（第 21 回） ****************************************************************** このコーナーでは，Nuorium Optimizer の Python インターフェースである PySIMPLE のエッセンスを紹介していきます． 今回は多次元の添字を使うことによる，疎なモデルの書き方をみていきます． 疎なモデルとして扱うことにより，無駄な変数や制約式が減り，より大きな 問題を解くことができるようになったり，高速化が期待できます． まずは，簡単な輸送問題を例に考えてみましょう． - 倉庫 d と顧客 c が複数ある - 倉庫には取扱上限 upper が存在する - 顧客には需要量 lower が存在する - 輸送コスト cost がかかる - 総輸送コストを少なくしたい この問題を単純に PySIMPLE で実装すると次のようになります． ------------------------------------------------------------------ d = Element(value=uppervalue.keys()) # 倉庫 c = Element(value=lowervalue.keys()) # 顧客 # 倉庫から顧客への輸送コスト cost = Parameter(index=(d,c), value=costvalue) upper = Parameter(index=d, value=uppervalue) # 倉庫取扱量上限 lower = Parameter(index=c, value=lowervalue) # 顧客需要量下限 z = Variable(index=(d,c), lb=0) # 倉庫から顧客への輸送量 prb = Problem() prb += Sum(z[d,c], c) <= upper[d], '倉庫取扱量上限' prb += Sum(z[d,c], d) >= lower[c], '顧客需要量下限' prb += Sum(cost[d,c]*z[d,c]), '総輸送コスト' # 目的関数 prb.solve() ------------------------------------------------------------------ ここで輸送コストは単位あたりの輸送費とし，(倉庫，顧客) ごとに決まると します．そのため入力データ costvalue は以下のようになります． ------------------------------------------------------------------ costvalue = {('d1', 'c1'): 30, ('d1', 'c2'): 20, ('d1', 'c3'): 9999, ('d1', 'c4'): 9999, ('d2', 'c1'): 25, : } ------------------------------------------------------------------ 9999 としているのは実際には輸送が発生しない経路に対するダミーの値 です．大きな値を入力しておくことで輸送が発生し辛くしています． このように現実問題ではすべての輸送経路を考慮する必要はなく，実際に 輸送する経路はごく一部であるケースも多いでしょう． このような場合，すべての経路を用意しておくことは変数・制約式の数を 無駄に増やしてしまうため，大きな問題が解けなかったり，速度が遅く なってしまいます． そこで必要最小限の経路のみを定義することにより効率的なモデルを記述 することができます．PySIMPLE では倉庫から顧客への二次元の添字 dc を 用いることで疎なモデルを表現することができます． ------------------------------------------------------------------ # 倉庫と顧客の疎な添字 dc = Element(value=costvalue.keys()) # 倉庫から顧客への輸送コスト cost = Parameter(index=dc, value=costvalue) upper = Parameter(index=dc(0), value=uppervalue) # 倉庫取扱量上限 lower = Parameter(index=dc(1), value=lowervalue) # 顧客需要量下限 z = Variable(index=dc, lb=0) # 倉庫から顧客への輸送量 prb = Problem() prb += Sum(z[dc], dc(1)) <= upper[dc(0)], '倉庫取扱量上限' prb += Sum(z[dc], dc(0)) >= lower[dc(1)], '顧客需要量下限' prb += Sum(cost[dc]*z[dc]), '総輸送コスト' # 目的関数 prb.solve() ------------------------------------------------------------------ 添字 (d,c) の代わりに dc を用いることで経路のある部分だけを表現する ことができました．倉庫 d や顧客 c の一方のみを指定したい場合は dc(0)， dc(1) と記述します．次元は 0 始まりであることに注意しましょう． また，costavlue は必要部分だけ記述すればよいので次のようになります． ------------------------------------------------------------------ costvalue = {('d1', 'c1'): 30, ('d1', 'c2'): 20, ('d2', 'c1'): 25, : } ------------------------------------------------------------------ 輸送のありえる経路が全ての組合せの 20% だった場合，変数の 8 割が削減 されたことになります． いかがだったでしょうか． 疎なモデルを用いて効率的なモデルを記述する方法は特にネットワーク系の 問題で威力を発揮します．他にも例えばスケジューリング問題では考慮する 必要のないマスをあらかじめ除いておくこともできます． その他の高速化のコツは第 7 回でも取り上げましたので是非ご覧ください． 高速化 TIPS はこちら: http://www.msi.co.jp/nuopt/docs/v24/pysimple/guide/speedup.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 データ数理システム << 数理システム Nuorium Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================