-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2021 Vol.5 ( 2021 年 9 月 15 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> 「最適化読本」のダウンロード始めました ■ <トピック> 数理最適化交流会 2021 のご案内 ■ <トピック> ZIB 主催のワークショップで講演します ■ <トピック> Second International UG Workshop 2021 ■ <セミナー> オンラインセミナーのご案内 ■ < tips > 使ってみよう PySIMPLE（第 14 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> 「最適化読本」のダウンロード始めました ****************************************************************** 最適化に関連する受託案件にかかわり出しておおよそ 10 年が経った頃， 実際やっているのは最適化じゃなくて制約の折り合いを見つけること だから，「数理計画」というのがより当たっているなあとかちょっと 語りたくなってきた頃に「最適化読本」を書く企画を始めました． 軽い気持でちょっと書き始めてみると自分でもいろいろ話したいことが 募ってきて，続編(第二部)まで出すことになりました．それからさらに 10 年あまり，いろいろな方々に手に取って頂けて嬉しい限りです． その最適化読本(一部，二部)が当社メディアサイトの MSIISM からダウン ロードが可能となりました．アドレスはこちら． https://www.msiism.jp/ebook.html シミュレーションや機械学習の読本も同じページからダウンロード できますので，どうかよろしくお願い申しあげます． ちなみに，最初に述べた「「最適化」より「数理計画」」という気持の 方は，当社ホームページの数理計画用語集の「数理計画法」という私が 書いた項目に詰め込まれています． https://www.msi.co.jp/nuopt/glossary/term_095d42c3c6149d3c695df7fb95946600ab7152a5.html 当時はこんな感じでがちがちに技術的な要件を詰めこんだ堅い文章を 書いていたことを思い知らされてすこし恥しくなる次第ですが，読本と いうスタイルを得たことが，私自身の技術的なコミュニケーションの 方法そのものにも影響したような気がしています． 最適化読本のさらなる続編，という感じで始めているのが，MSIISM の 連載ブログ記事，「難しくても使いこなす組合せ最適化」です．読本を 書き始めた頃と驚くほど変わったことも，そして何も変わっていない こともあるなあとしみじみと思いつつ，先日 (3) まで進めました． こちらが (1) のリンクです． https://www.msiism.jp/article/tanabe-combinatorial-optimization1.html 読本の方に書き切れなかった話や，あれから考えが進んだことなど書ける 場を得たのが嬉しいです． こちらの方もどうかよろしくお願い申しあげます． （田辺 隆人） ****************************************************************** ■ <トピック> 数理最適化交流会 2021 のご案内 ****************************************************************** 昨年度は数理最適化交流会 2020 と題したイベントを開催いたしました． アカデミックで活躍されている先生方と実務で活躍されている技術者の 交流を深め，数理最適化の新しい魅力の発見や数理最適化の更なる発展を 願って開催し，大変ご好評いただいたイベントとなりました． 昨年度の発表の様子などは以下のページをご覧ください． https://www.msiism.jp/article/MP-exchange-meeting-2020.html さて，今年もオンラインで数理最適化交流会 2021 を開催いたします． 今年は定員の数も増やすため，より多くの方にご参加いただけるかと 存じます．数理最適化にすこしでもご興味がありましたらぜひお申込み ください． 数理最適化交流会 2021 開催日： 2021 年 10 月 29 日 セミナーページ： https://www.msi.co.jp/nuopt/seminar/mathoptsymposium2021.html ご講演者： 大阪大学 梅谷 俊治 様 関西大学 檀 寛成 様 JR システム 新井 祐一 様・神谷 祐紀 様 当社 多田 明功 参加費：無料 ※参加者多数の場合はお申込みを締め切る場合がございます． （石橋 保身） ****************************************************************** ■ <トピック> ZIB 主催のワークショップで講演します ****************************************************************** 共同研究などでご一緒させて頂いているベルリンの ZIB 研究所にて開催 されるワークショップ 5th ZIB-RIKEN-IMI-ISM MODAL Workshop on Optimization, Data Analysis and HPC in AI にて講演させて頂く機会を頂きました(私の発表は 9/28 18:00 - 18:20 (日本時間))． テーマは最適化プログラムをビジネスアプリケーションに成長させる上で よく起きる事象と考察，といったお話です． 講演プログラム，申し込みは以下のサイトから可能です． オンライン，どなたでも無償で参加可能ですので奮ってご参加ください． http://optimizationworkshop2020.zib.de/ 統計数理研究所，理化学研究所，九州大学マス・フォア・インダストリ 研究所が共催している関係で日本の研究機関からも多数の講演される方が いらっしゃいます． 研究会の会期は 9/27 - 9/30 ．いずれの日も日本時間で 16:00 開始， 21:00 台にて終了で，日本からの参加者にご配慮頂いております． （田辺 隆人） ****************************************************************** ■ <トピック> Second International UG Workshop 2021 ****************************************************************** 分枝限定法並列化フレームワーク UG は ZIB 研究所に所属する品野勇治 博士の開発する分枝限定法並列化フレームワークで，数コアから数万コア までスケーラブルな並列計算を可能とし，チェックポイント機能やレー シング機能（複数のパラメータを競わせる）など並列化に必要な機能も 充実しています．弊社 Numerical Optimizer にも品野博士との共同研究 によりその一部機能が取り込まれています． UG workshop は主に UG ユーザによる並列化及び組合せ最適化についての 講演が行われるワークショップです．第一回目は 2019 年に開催され， 第二回目は 2021/10/1 に開催されます． 日時： 2021/10/1 16:00 - 24:00 （日本時間） 場所：オンライン及び Zuse Institute Berlin（懇親会のみ） 主催者： Zuse Institute Berlin URL： https://ug.zib.de/workshop2021/ ※ 講演は全て英語で行われます． 前回の UG Workshop はベルリンでの開催でしたが，今回はオンライン 参加のため日本からも参加しやすい形になっています．参加無料ですので ご興味ある方は是非ご参加ください．参加は上のホームページから可能です． 以下は講演一覧です． - Yuji Shinano "Progress in parallel MIP solvers instantiated by UG" - Yuji Shinano "UG Version 1.0" - Daniel Rehfeldt "ug[SCIP-Jack,*]: A parallel solver for Steiner tree and related problems" - Koichi Fujii "ParaQapNB : Massively Parallelized DNN-based Branch-and-bound QAP solver" - Nariaki Tateiwa "Configurable Massively Parallel Solver for Shortest Vector Problems" - Stephen J. Maher "Parallel Benders Decomposition" - Ted Ralphs "Assessment of effectiveness of parallel B&B" - Tim Hasler "Tales from the workbench of the HPO Navi project" - Utz Uwe Haus "ParaConcorde" 今回は品野博士自身による解説が最も注目される講演と思いますが， 立岩氏による SVP ソルバの並列化も大変興味深い講演です． UG はそれ以前は分枝限定法のみの並列化にフォーカスしていましたが， こちらの研究をきっかけとして他の組合せ最適化アルゴリズムと組み 合わせることも可能となりました． また Utz Uwe Haus 氏による，著名な巡回セールスマンソルバ Concorde の 並列バージョンの開発についても注目です． （藤井 浩一） ****************************************************************** ■ <セミナー> オンラインセミナーのご案内 ****************************************************************** 定期的に無料のオンラインセミナーを開催しております． ご興味があればぜひご参加ください． 特に，新規開設の「Numerical Optimizer ハンズオンセミナー」では， Python ベースのモデリング言語 PySIMPLE を軸に Numerical Optimizer の基本的な使い方を学ぶことができます． ・日程 [ Numerical Optimizer 紹介セミナー ] 10/14(木) 13:30 - 15:30 11/ 4(木) 13:30 - 15:30 [ Numerical Optimizer ハンズオンセミナー ] 9/29(水) 13:30 - 16:00 10/26(火) 13:30 - 16:00 [ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー ] 11/ 9(火) 13:30 - 15:30 ・詳細とお申込み https://www.msi.co.jp/nuopt/seminar/index.html また，「最適化無料個別相談会」では，最適化についての様々なご相談事を 承っております． 柔軟に対応させていただきますので，nuopt-info@ml.msi.co.jp まで お気軽にお申し込みください． （岸本 祥吾） ****************************************************************** ■ < tips > 使ってみよう PySIMPLE（第 14 回） ****************************************************************** このコーナーでは，Numerical Optimizer の Python インターフェース PySIMPLE のエッセンスを紹介していきます． 3 月にリリースされた V23 では大きく 2 つの機能が追加されました． - 二次計画問題への対応 - メタヒューリスティクスアルゴリズム wcsp/wls の利用 今回はこのうち後者について見ていきましょう． 複数の制約条件を満たす解の組合せを見つける問題を制約充足問題(CSP) といいます．Numerical Optimizer では制約充足問題に対するメタヒュー リスティクスアルゴリズムとして，タブーサーチ法に基づいた wcsp (weighted constraint satisfaction problem) アルゴリズムを V7 から 搭載しています．V23 の PySIMPLE ではこの wcsp の呼び出しが可能と なったうえ，局所探索法に基づく新たなメタヒューリスティクスアルゴ リズム wls(weighting local search) を利用できるようになりました． 技術的な内容は前々回のメールマガジンをご覧ください． wcsp/wls は連続変数を用いることができない，などの制限がありますが， 高速に近似解を得ることができます．そのため，例えば，人員配置，配車 スケジューリング，作業分担表作成，時間割作成などの，「マス目を 埋める」というタイプの問題と相性が良いです． 第 6 回で扱ったシフトスケジューリングの問題を見てみましょう． ------------------------------------------------------------------ m = Element(value='ABCDE') # Man d = Element(value=range(1,8)) # Day s = Element(value=['Day','Ngt','Off']) # Shift p = Problem() x = BinaryVariable(index=(m,d,s)) p += Sum(x[m,d,s], s) == 1, '一日に勤務は一つ' p += Sum(x[m,d,'Day'], m) == 2, '日勤は二人ちょうど' p += Sum(x[m,d,'Ngt'], m) >= 1, '夜勤は一人以上' p += Sum(x[m,d,'Off'], d) >= 1, '一回以上は休み' p += Sum(x[m,d,'Ngt'], d) <= 2, '夜勤は二回まで' d1 = d != 7 p += x[m,d1+1,'Off'] >= x[m,d1,'Ngt'], '夜勤の次の日は代休' p.solve(silent=True) ------------------------------------------------------------------ 上記の例では線形計画問題として求解を行っていますが，これを wcsp で 求解するには solve より前に以下の一行を追加するだけです． ------------------------------------------------------------------ p.options.method = 'wcsp' # アルゴリズムに wcsp を指定(wls も同様) ------------------------------------------------------------------ 特に wcsp は選択関数 Selection を用いることにより効率よく計算を行う ことができます． ------------------------------------------------------------------ #p += Sum(x[m,d,s], s) == 1, '一日に勤務は一つ' p += Selection(x[m,d,s], s), '一日に勤務は一つ' ------------------------------------------------------------------ 選択関数は内部的には複数の 0-1 整数変数を用意する替わりに，一つの 離散変数を用意するため，内部処理が高速化されます．また，wcsp 以外の アルゴリズムでは Sum(…)==1 と解釈されます． もう一つの wcsp/wls の特長として，制約条件の重要度を表現することが できます． ------------------------------------------------------------------ p += Selection(x[m,d,s], s), '一日に勤務は一つ' p += Sum(x[m,d,'Day'], m) == 2, SoftConstraint(10), '日勤回数' p += Sum(x[m,d,'Ngt'], m) >= 1, SoftConstraint(100), '夜勤下限' p += Sum(x[m,d,'Off'], d) >= 1, HardConstraint(), '休み下限' p += Sum(x[m,d,'Ngt'], d) <= 2, SemiHardConstraint(), '夜勤上限' ------------------------------------------------------------------ この例では「一日に勤務は一つ」と「休み下限」は必ず，「夜勤上限」は ほぼ必ず，「日勤回数」と「夜勤下限」はできるだけ守るように指定して います．一般に，HardConstraint は必ず守らなければならない制約， SemiHardConstraint は必ず守らなければならないが違反する可能性のある 制約，SoftConstraint はできれば守って欲しい制約，といった目安をもって おくとよいでしょう． いかがでしたでしょうか．V23 では扱えるアルゴリズムがぐっと増え， Numerical Optimizer の大部分の機能を扱えるようになりました．今後とも PySIMPLE の進化にご期待ください． PySIMPLE でのメタヒューリスティクスアルゴリズムの使い方はこちら: https://www.msi.co.jp/nuopt/docs/v23/pysimple/guide/metaheuristics.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 ==================================================================