数理システム 最適化メールマガジン

バックナンバー ( 2019 Vol.4 ) 2019 年 7 月 18 日 発行

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  数理システム 最適化メールマガジン  http://www.msi.co.jp/nuopt/
                           2019 Vol.4 ( 2019 年  7 月 18 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

数理システム 最適化メールマガジンでは,数理計画法パッケージ
数理システム Numerical Optimizer をはじめとして,最適化に関する様々
な情報やご案内を提供していきます.

++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ■ <  tips  > 使ってみよう PySIMPLE(第 3 回)
 ■ <トピック> EURO2019 参加ご報告
 ■ <セミナー> 特別セミナーのご案内
 ■ <セミナー> 7 月・8 月体験セミナーのご案内
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

******************************************************************
■ <  tips  > 使ってみよう PySIMPLE(第 3 回)
******************************************************************

このコーナーでは,Numerical Optimizer V21 の新機能であるモデリング
言語 PySIMPLE のエッセンスを紹介していきます.
前回は PySIMPLE に特徴的な条件式の書き方を紹介し,その中で疎集合の
考えに基づく書き方が登場しました.今回はこの点に更に焦点を当てて,
SIMPLE と比較しながら紹介いたします.

前回,最後に紹介した多次元の条件式を用いた書き方を見てみましょう.
ij(0) で条件式 ij の一次元目を取り出しているのがポイントです.

SIMPLE:                            PySIMPLE:
---------------------------------+--------------------------------
Set I="1 2 3"; Element i(set=I); | i = Element(value=[1, 2, 3])
Set J="1 2 3"; Element j(set=J); | j = Element(value=[1, 2, 3])
Variable x(index=(i,j));         | x = Variable(index=(i,j))
Variable y(index=i);             | y = Variable(index=i)
                                 | ij = i<j
x[i,j] >= y[i], i<j;             | x[ij] >= y[ij(0)]
---------------------------------+--------------------------------

これは要素を列挙すると,次のように書くことができます.SIMPLE では
次元が 1 始まり,PySIMPLE では 0 始まりであることに注意してください.

---------------------------------+--------------------------------
Set I="1 2 3"; Element i(set=I); | i = Element(value=[1, 2, 3])
Set J="1 2 3"; Element j(set=J); | j = Element(value=[1, 2, 3])
Variable x(index=(i,j));         | x = Variable(index=(i,j))
Variable y(index=i);             | y = Variable(index=i)
Set IJ(dim=2); IJ="1,2 1,3 2,3"; | ij = Element(
Element ij(set=IJ);              |    value=[(1,2), (1,3), (2,3)])
x[ij] >= y[ij.at(1)];            | x[ij] >= y[ij(0)]
---------------------------------+--------------------------------

両者が同じ意味であることがより分かりやすくなったのではないでしょうか.
実は,このモデルには無駄があります.変数 x は 9 個,変数 y は 3 個を
定義しているのに,実際に使用しているのはその一部だけであるからです.
変数を必要最小限だけ定義するようにモデルを修正してみましょう.

---------------------------------+--------------------------------
Set IJ(dim=2); IJ="1,2 1,3 2,3"; | ij = Element(
Element ij(set=IJ);              |    value=[(1,2), (1,3), (2,3)])
Variable x(index=ij);            | x = Variable(index=ij)
Variable y(index=IJ.slice(1));   | y = Variable(index=ij(0))
x[ij] >= y[ij.at(1)];            | x[ij] >= y[ij(0)]
---------------------------------+--------------------------------

SIMPLE では次のように書くこともできます.

------------------------------------------------------------------
Set I; Element i(set=I);
Set J; Element j(set=J);
Set IJ(dim=2, superSet=(I,J)); IJ="1,2 1,3 2,3";
Variable x(index=IJ);
Variable y(index=i);
x[i,j] >= y[i], (i,j)<IJ;
------------------------------------------------------------------

ここで二次元集合 IJ は二次元集合 I*J(直積) の部分集合となっています.
このように集合の疎(sparse)性に着目することで,無駄な変数や制約式を
省き,より大規模な問題に対応することができるようになります.

次はもう少し難しい例で見てみましょう.以下のような集合分割問題を考え
ます.

- A さんと B さんをテーブルに振り分ける

このモデルの定式化にはいろいろ考えられますが,今回は変数として次の
3 つのテーブルを用意する定式化を考えます.

- テーブル A(A さんのみ)
- テーブル B(B さんのみ)
- テーブル AB(A さんと B さんが同じテーブル)

------------------------------------------------------------------
t = Element(value=['A', 'B', 'AB'])
z = BinaryVariable(index=t)  # テーブル t が採用されれば 1
------------------------------------------------------------------

このとき A さん,B さん各人がいずれか 1 つのテーブルに属するという
制約はどのように記述すればよいでしょうか.
実際に書き下すと次のようにすればいいことが分かります.

------------------------------------------------------------------
z['A']+z['AB'] == 1  # A さんはテーブル A かテーブル AB に振り分け
z['B']+z['AB'] == 1  # B さんはテーブル B かテーブル AB に振り分け
------------------------------------------------------------------

ではこれを一括して記述するにはどうすればよいでしょうか.ポイントは
各人 A, B に対してそれぞれを含む二次元の疎集合を作成することです.
制約式は添字の一次元目が残るため,各人に対して自動展開することにも
注意してください.

SIMPLE:
------------------------------------------------------------------
Set S; Element s(set=S);  // 人
Set T; Element t(set=T);  // テーブル
Set ST(dim=2, superSet=(S, T)); ST="A,A B,B A,AB B,AB";
IntegerVariable z(index=t, type=binary);
sum(z[t], (t, (s,t)<ST)) == 1;
------------------------------------------------------------------

PySIMPLE:
------------------------------------------------------------------
st = Element(value=[('A','A'), ('B','B'), ('A','AB'), ('B','AB')])
z = BinaryVariable(index=st(1))  # st(1) in ['A', 'B', 'AB']
Sum(z[st(1)], st(1)) == 1
------------------------------------------------------------------

いかがでしたでしょうか.多次元の添字から一部を取り出す例は例題集の
p メディアン問題,巡回セールスマン問題,仕事割当問題などでも登場
します.また,今回取り上げたような少し複雑な例はサンプルの数独でも
紹介していますので是非確認してみてください.

PySIMPLE に同梱しているサンプルの解説はこちら:
    https://www.msi.co.jp/nuopt/docs/v21/pysimple/sample.html

                                                 (池田 悠)

******************************************************************
■ <トピック> EURO2019 参加ご報告
******************************************************************

6/23~6/26 にかけてアイルランドのダブリンで開催された EURO2019 に
参加しました.
EURO-k conference はヨーロッパでおこなわれる大規模な Operations 
Research (OR) の学会です.
今年は弊社から Numerical Optimizer を並列化したソルバ ParaNUOPT 
について発表させていただきました.
ParaNUOPT はドイツの Zuse Institute Berlin ご所属の品野勇治博士との
共同研究で開発した並列分枝限定法ソルバです.
発表資料は下記リンクにありますのでご興味ある方は是非ご確認なさって
ください.

   https://www.msi.co.jp/nuopt/download/introduction/module/euro2019.pdf

さて,EURO2019 は OR の学会ということもあり,数理最適化の応用や
実務向けの発表が多くあります.
私が聴いた中で特に興味深かったものは次の話です.

   Luigi De Giovanni, Carlo Lancia, Guglielmo Lulli, 
   Davide Meneghetti.
   A heuristic for the Air Traffic Flow Management Problem based 
   on Data Analytics and Integer Programming

Air Traffic Flow Management は燃料費や飛行機が衝突しないように同じ
セグメントに存在する飛行機の数に制限を設けるなどの制約を考慮して
航空路を制御する問題です.
この話の中でスライドに書かれていた次の言葉がとても印象的でした.

   "that flight plan does not match our preferences" (Airspace users)
   "... sorry, cannot say why!" (Airspace users)

数理最適化として現実の問題を解くには目的関数や制約式を数式で記述
する必要がありますが,人の好みや現場の人が長年培ってきた経験を
数式として漏れなく記述することは難しいものです.
弊社はお客様へのヒアリングとフィードバックを通じてこれを実現して
いますが,他の国でも似たような問題を抱えている点が非常に興味
深かったです.この話では過去のデータから "好み" を学習して最良な
フライトプランを選択する方法で問題を解決しようとしていました.
導入後,Airspace users からどのような言葉が返ってくるのか気になる
ところです.

                                                 (石橋 保身)

******************************************************************
■ <セミナー> 特別セミナーのご案内
******************************************************************

◆最適化&シミュレーションセミナー「製造業向けソリューションのご紹介」
  
本セミナーは最適化とシミュレーションの製造業への活用例を同時に
知っていただける内容になっております.両方のソリューションに
ご興味をお持ちの方,お持ちの課題にどちらのソリューションを
適用すればよいか迷われている方には,最適なセミナーです.

混合しがちな最適化とシミュレーションの違いについても細かくご説明
致します.

また,近年の動向や弊社に頂くご相談内容を踏まえ,数理最適化や
シミュレーションがどのようにビジネスの現場で利用されているのかを,
弊社最適化ソフト開発責任者よりお伝えします.

   ☆   日時:2019 年 7 月 30 日 (火) 14:00~17:00

   ☆   参加費:無料

   ☆   会場:
         (株) NTT データ数理システム セミナールーム
           (東京都新宿区信濃町 35 信濃町煉瓦館 4F)
             https://www.msi.co.jp/msi/location.html

   ☆ 上記セミナーのお申込み・詳細は下記をご覧ください.
             https://msi.hmup.jp/nuopt/seminar/simulation

◆スケジューリングセミナー
  
皆様からの声にお答えして,先日大盛況に終わりました「スケジュー
リングセミナー」を,8 月に開催いたします!
本セミナーではコールセンター業界における大規模スタッフのシフト
スケジューリングや医療・介護現場でのシフトスケジューリングなど,
多様な現場・要望にお応えできるスケジューリングソリューションを
ご紹介いたします.

最適化・数理計画を用いたワークフォースマネジメント(WFM)への
導入事例にご興味がある方,実用的なシフトスケジューリングに
ご興味がある方は是非お気軽にご参加ください.

   ☆   日時:2019 年 8 月 27 日 (金) 15:00~17:00

   ☆   参加費:無料

   ☆   会場:
         (株) NTT データ数理システム セミナールーム
           (東京都新宿区信濃町 35 信濃町煉瓦館 4F)
             https://www.msi.co.jp/msi/location.html

   ☆ 上記セミナーのお申込み・詳細は下記をご覧ください.
             https://msi.hmup.jp/nuopt/seminar/shiftsch

◆PySIMPLE セミナー
  
本セミナーでは Numerical Optimizer V21 の新機能として
実装いたしました Python インタフェース【 PySIMPLE 】を
ご紹介致します.

PySIMPLE を用いたモデリングの例や SIMPLE との表記方法の
違いなど,実際の製品画面をご覧頂きながらご説明いたします.
大変多くのご要望を頂いておりました機能でございます.
奮ってご参加ください.

※新機能紹介を目的とした特別セミナーにつき,
  次回以降の開催の予定はございません.

   ☆   日時:2019 年 8 月 30 日 (金) 15:00~17:00

   ☆   参加費:無料

   ☆   会場:
         (株) NTT データ数理システム セミナールーム
           (東京都新宿区信濃町 35 信濃町煉瓦館 4F)
             https://www.msi.co.jp/msi/location.html

   ☆ 上記セミナーのお申込み・詳細は下記をご覧ください.
             https://msi.hmup.jp/nuopt/seminar/pysimple

皆様のご参加をお待ちしております.

                                                 (山本 和寛)

******************************************************************
■ <セミナー> 6 月体験セミナーのご案内
******************************************************************

---[ Numerical Optimizer 定例セミナー開催日程 ]-------------------

・7 月  19 日 (金) 13:30~17:00 Numerical Optimizer 体験セミナー
                  https://msi.hmup.jp/nuopt/seminar/seminarRegular

・8 月  21 日 (水) 13:30~17:00 Numerical Optimizer 体験セミナー
                  https://msi.hmup.jp/nuopt/seminar/seminarRegular

------------------------------------------------------------------

実際に PC 上で Numerical Optimizer を体験できるセミナーです.
数理最適化ソルバーをお探しの方はもちろんのこと,数理最適化とは
どんなものか知りたい方にもお薦めです.
機能を強化した Excel アドインもご紹介いたします.モデルとデータの
連携を気軽に行いたい方や,解を集計しグラフを書いて分析を行いたい
方にお薦めの機能です.
また,近年の動向や弊社に頂くご相談内容を踏まえ,数理最適化が
どのようにビジネスの現場で利用されているのかを,開発責任者より
お伝えします.

皆様のご参加をお待ちしております.

                                                 (山本 和寛)

==================================================================
※ このメールは,弊社ツールのユーザー様,過去に展示会などでお名刺
   等を頂いたことのある方や当社に直接お問合せを頂いたことのある方
   にお送りしています.
※ バックナンバーはこちらから御覧頂けます.
     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
==================================================================

<< 記事の訂正のお知らせ >>

「使ってみよう PySIMPLE(第 3 回)」の記事内のモデルの記述例
につきまして、以下の誤りがございました。
訂正させていただきますとともに、お詫び申し上げます。

< 3 個目の SIMPLE と PySIMPLE の比較例のうち SIMPLE 部分 >
  (誤)Set IJ(dim=2); IJ="1,3 1,4 2,3";
  (正)Set IJ(dim=2); IJ="1,2 1,3 2,3";

< 3 個目の SIMPLE と PySIMPLE の比較例直後にある SIMPLE の記述例 >
  (誤)Set IJ(dim=2, superSet=(I,J)); IJ="1,3 1,4 2,3";
  (正)Set IJ(dim=2, superSet=(I,J)); IJ="1,2 1,3 2,3";

なお、本ページ内の該当箇所につきましては訂正を行なっております。