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

バックナンバー ( 2020 Vol.4 ) 2020 年 8 月 6 日 発行

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

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

++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ■ <トピック> メディアサイト MSIISM  始めました
 ■ <トピック> 出展・発表案内
 ■ <セミナー> オンラインセミナーのご案内
 ■ <  tips  > 使ってみよう PySIMPLE(第 9 回)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

******************************************************************
■ <トピック> メディアサイト MSIISM  始めました
******************************************************************

数理科学を使った問題解決を仕事としている我々の立場から,
様々な手法の特徴および現状の進展度合い,技術の「使いどころ」,
弊社パッケージや受託の事例,関連情報などを広く発信するための
メディアサイト MSIISM (エム・エス・アイ・イズム)を立ちあげました.
アドレスは以下でございます.

   https://www.msiism.jp

数理最適化(私も連載記事「難しくても使いこなす組合せ最適化」を
始めました)や幅広くデータ分析や機械学習,シミュレーションといった
話題を取り上げており,鮮度の良い情報を揃え,繰り返し訪れて頂ける
サイトを目指して努力します.

ご愛顧頂ければ幸いでございます.

                                                 (田辺 隆人)

******************************************************************
■ <トピック> 出展・発表案内
******************************************************************

今年は多くの学会がオンライン開催されることに伴い, 
Numerical Optimizer もオンライン出展いたします.

  令和 2 年 電気学会 電力・エネルギー部門大会
    開催日:9 月 9 日(水) ~ 9 月 11 日(金)
    

  スケジューリング・シンポジウム 2020
    開催日:9 月 17 日(木) ~ 9 月 18 日(金)
    http://www.scheduling.jp/symposium/2020/

オンラインではありますが,学会参加の折は是非お立ち寄りください.

電気学会 電力・エネルギー部門大会では以下の発表も行います.

「発電機起動停止計画問題のための切除平面の改良と分枝限定法の並列化に
ついて」
  *藤井浩一(NTT データ数理システム)
   石橋保身(NTT データ数理システム)

電力系統の計画・運用の問題である起動停止問題に対して,混合整数計画
として定式化し分枝限定法を適用することが有効であることが知られて
いるが,特に混合整数丸め不等式と呼ばれるクラスの切除平面を用いる
ことが重要です.
既存の不等式生成アルゴリズムを改良することにより,起動停止問題の
計算が高速化されることを示します.また Numerical Optimizer で実装
されている二種類の並列計算を紹介し,その効果を起動停止問題に対して
論じます.

以下の学会で発表をいたします.

研究集会「数理最適化の理論・アルゴリズム・応用」
  開催日: 8 月 24 日(月) ~ 8 月 25 日(火)
「集合分割問題に対する重みつき局所探索法の改良」
  *中村健吾(NTT コミュニケーション科学基礎研究所)
   藤井浩一(NTT データ数理システム)
   石橋保身(NTT データ数理システム)
   神谷俊介(NTT データ数理システム)
   梅谷俊治(大阪大学)

集合分割問題とは,係数が 0 または 1 である等式制約を含んだ整数
線形計画問題です.集合分割問題は交通機関乗組員スケジューリングや
車のルーティング等の応用をもつ一方等式制約を含むため,時には
実行可能解の発見すら苦労するような難しい問題クラスです.
大規模な問題でも短い時間で比較的良い実行可能解を得るために,
梅谷博士による局所探索に基づいた発見的解法が提案されています.
本講演ではこの手法にさらなる改良を加え大多数のインスタンスについて
従来の解法が改善できたことを報告します.
なお本発表の内容は発表者が NTT データ数理システムにてインターン中に
行ったものです.

参考:
Umetani, Shunji. "Exploiting variable associations to configure
efficient local search algorithms in large-scale binary integer
programs." European Journal of Operational Research 263.1 (2017):
72-81.

Gleixner, Ambros, et al. MIPLIB 2017: Data-Driven Compilation of the
6th Mixed-Integer Programming Library. Technical report, Optimization
Online, 2019.

                                                 (藤井 浩一)

******************************************************************
■ <セミナー> オンラインセミナーのご案内
******************************************************************

弊社では今年 4 月からオンラインセミナー (Webinar) を開催しています.
ご来社が難しい遠方の方々の参加も多く,参加者からは「知りたかった
内容が聞けて役にたった」と大変ご好評いただいております.
8 月からは火曜日に開催していた Numeriacl Optimizer 紹介セミナーを他
の曜日にも開催いたします.定例会議が理由で今まで参加し辛かった方も
ぜひお申込みください.
また,エネルギーマネジメント最適化セミナーや製造現場向けの数理最適
化セミナーといった特別セミナーも開催予定です.どれも無料のオンライ
ンセミナーなので,普段の業務とは違う分野で数理最適化がどのように使
われているかを知る良い機会かと存じます.お気軽にご参加ください.

・日程
  8/18 (火) Numerical Optimizer 紹介セミナー     13:30 - 15:30
  8/27 (木) エネルギーマネジメント最適化セミナー 13:30 - 15:30
  9/7  (月) Numerical Optimizer 紹介セミナー     13:30 - 15:30
  9/15 (火) 製造現場の業務改善に向けた数理最適化
            ソリューション紹介セミナー
            ~生産スケジューリングを中心に~     13:30 - 15:30
  9/25 (金) Numerical Optimizer 紹介セミナー     13:30 - 15:30

・Numerical Optimizer 紹介セミナーの詳細とお申込みはこちら
    https://msi.hmup.jp/nuopt/seminar/webinar

・エネルギーマネジメント最適化セミナーの詳細とお申込みはこちら
    https://msi.hmup.jp/nuopt/seminar/enemanage

・製造現場の業務改善に向けた数理最適化ソリューション紹介セミナーの
  詳細とお申込みはこちら
    https://msi.hmup.jp/nuopt/seminar/manufacture

                                                 (石橋 保身)

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

このコーナーでは,Numerical Optimizer V21 以降の機能であるモデリング
言語 PySIMPLE のエッセンスを紹介していきます.
今回は Sum 関数の範囲に多次元の添字を用いたときの挙動を整理しておき
ましょう.

まずは基本となる Sum 関数の範囲が一次元の添字で構成されている場合の
挙動です.
PySIMPLE 独自の仕様として,第二引数を省略した場合はすべての範囲に
ついての和が計算されます.目的関数には添字を含むことができないため,
この仕様は便利です.

------------------------------------------------------------------
>>> from pysimple import *
>>> i = Element(value=[1,2], name='i')
>>> j = Element(value=[3,4], name='j')
>>> x = Variable(index=(i,j), name='x')
>>> Sum(x[i,j], i)
Sum(x[i,j], i):
x[1,3]+x[2,3]
x[1,4]+x[2,4]
>>> Sum(x[i,j], j)
Sum(x[i,j], j):
x[1,3]+x[1,4]
x[2,3]+x[2,4]
>>> Sum(x[i,j], (i,j))
Sum(x[i,j], (i,j)):
x[1,3]+x[1,4]+x[2,3]+x[2,4]
>>> Sum(x[i,j])
Sum(x[i,j], (i,j)):
x[1,3]+x[1,4]+x[2,3]+x[2,4]
------------------------------------------------------------------

続いて,範囲に二次元の添字を用いた場合です.
SIMPLE では sum(y[i,j], (i, (i,j)<IJ)) となる記述を,PySIMPLE では
Sum(y[ij], ij(0)) とより簡潔に記述することができます.
先ほどの例と比較してみると理解しやすいでしょう.

------------------------------------------------------------------
>>> ij = Element(value=[(1,3), (1,4), (2,3)], name='ij')
>>> y = Variable(index=ij, name='y')
>>> Sum(y[ij], ij(0))
Sum(y[ij], ij(0)):
y[1,3]+y[2,3]
y[1,4]
>>> Sum(y[ij], ij(1))
Sum(y[ij], ij(1)):
y[1,3]+y[1,4]
y[2,3]
>>> Sum(y[ij], ij)
Sum(y[ij], ij):
y[1,3]+y[1,4]+y[2,3]
>>> Sum(y[ij])
Sum(y[ij], ij):
y[1,3]+y[1,4]+y[2,3]
------------------------------------------------------------------

また,範囲は (ij(0), ij(1)) のように重複がなければ問題ありませんが,
(ij(1), ij(1)) や (ij(1), ij) のように重複を含む場合は ValueError が
投げられます.

------------------------------------------------------------------
>>> Sum(y[ij], (ij(0), ij(1)))
Sum(y[ij], (ij(0),ij(1))):
y[1,3]+y[1,4]+y[2,3]
>>> Sum(y[ij], (ij(1), ij(1)))
ValueError: duplicate Element in range of Sum(*, (ij(1),ij(1)))
>>> Sum(y[ij], (ij(1), ij))
ValueError: duplicate Element in range of Sum(*, (ij(1),ij))
------------------------------------------------------------------

最後に,オブジェクトが二次元の添字の一部を添字にもつ場合を見てみま
しょう.

------------------------------------------------------------------
>>> z = Variable(index=ij(0), name='z')
>>> Sum(z[ij(0)], ij(0))
Sum(z[ij(0)], ij(0)):
z[1]+z[2]
z[1]
>>> Sum(z[ij(0)], ij(1))
Sum(z[ij(0)], ij(1)):
2*z[1]
z[2]
>>> Sum(z[ij(0)], ij)
Sum(z[ij(0)], ij):
2*z[1]+z[2]
>>> Sum(z[ij(0)])
Sum(z[ij(0)], ij(0)):
z[1]+z[2]
z[1]
------------------------------------------------------------------

Sum(z[ij(0)]) は Sum(z[ij(0)], ij) ではなく Sum(z[ij(0)], ij(0))
と解釈されることに注意しましょう.
実は Sum(obj) は Sum(obj, obj.index) のエイリアスとなっています.

------------------------------------------------------------------
>>> Sum(z[ij(0)], z[ij(0)].index)
Sum(z[ij(0)], ij(0)):
z[1]+z[2]
z[1]
------------------------------------------------------------------

いかがでしたでしょうか.
Sum 関数は多次元の添字と組み合わせることで実に様々な制約を表現する
ことができます.具体的なケースは次回以降の連載でお伝えできればと思い
ます.

Sum 関数のドキュメントはこちら:
    https://www.msi.co.jp/nuopt/docs/v22/pysimple/api/function.html#pysimple.func.Sum

                                                 (池田 悠)

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