-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン
https://www.msi.co.jp/solution/nuopt/top.html
2024 Vol.3 ( 2024 年 5 月 21 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは,数理最適化パッケージ
Nuorium Optimizer をはじめとして,最適化に関する様々な情報や
ご案内を提供していきます.
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> Nuorium Optimizer V26 の活用例のご紹介
■ <トピック> MSIISM 記事「ソルバの性能評価」のご紹介
■ <イベント> 特別イベント Nuorium Optimization Day 2024 のご案内
■ <セミナー> セミナーのご案内
■ < tips > 使ってみよう PySIMPLE(第 30 回)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> Nuorium Optimizer V26 の活用例のご紹介
******************************************************************
Nuorium Optimizer の最新バージョンである V26 を 3 月下旬にリリース
しました [1].V26 では数理最適化の要となるアルゴリズム部分の機能
強化が多くあり,特に,重み付き局所探索法 WLS(※1)が連続変数に対応
しました.
これによって,混合整数線形計画問題(※2)に対しても WLS が使える
ようになりました.
WLS が混合整数線形計画問題に対して適用できるといっても,全ての問題に
対して良好な性能を発揮できているというわけではありません.
同じく混合整数線形計画問題に対する解法として知られている分枝限定法と
比較すると,分枝限定法の方が短時間で良質な解が得られるような問題も
あります.一方で,分枝限定法が苦手とするような一部の問題に対しては
WLS の方が短時間で良質な解が得られることを確認しています.
例えば,以下の記事で図形を長方形の容器に敷き詰めるような問題において,
WLS の方が短時間で良い解が得られることを確認しています.
Nuorium Optimizer V26 新機能を活用!
重み付き局所探索法を用いた 2D Strip Packing Problem の求解
https://www.msiism.jp/article/nuorium-optimizer-v26-1001.html
他にも,分枝限定法が苦手とするような問題として工場のピーク電力を
削減するような問題 [2] などもあり,社内で性能を確認しているところ
です.
機会がありましたら内容と結果をご紹介したいと思います.皆様もぜひ
V26 の WLS を様々な問題に適用して効果の程をお確かめください.
※1 WLS とは
WLS (Weighting Local Search) は梅谷俊治博士の論文 [3] を参考にして
開発されたメタヒューリスティクス解法です.
アルゴリズムの概要については Nuorium Optimizer のマニュアル [4] を
ご覧ください.
※2 混合整数線形計画問題とは
混合整数線形計画問題は連続変数と整数変数を含み,目的関数と制約式が
全て線形であるような問題です.混合整数線形計画問題はその表現力の
高さから様々な分野に現れる問題です.例えば,複数の車両を使って顧客に
荷物を運ぶ配送計画問題,生産工程を考慮した上で各機械にどのような
順番でジョブを処理させるかを決定するジョブショップまたは
フローショップスケジューリング,働き方改革などから分野を問わず必要と
される能率や効率の良い人員配置などです.
<参考文献>
[1] Nuorium Optimizer 更新情報
https://www.msi.co.jp/solution/nuopt/whatsnew.html
[2] 小熊祐司,工場のピーク電力抑制を目的とした生産設備群の運転
スケジュール最適化
https://www.msi.co.jp/event/file/muc17_402_4.pdf
[3] Umetani, S. (2017). Exploiting variable associations to
configure efficient local search algorithms in large-scale
binary integer programs.
European Journal of Operational Research, 263(1), 72-81.
[4] Nuorium Optimizer V26 マニュアル B.6 重み付き局所探索法WLS
https://www.msi.co.jp/solution/nuopt/docs/manual/html/0B-06-00.html
(石橋 保身)
******************************************************************
■ <トピック> MSIISM 記事「ソルバの性能評価」のご紹介
******************************************************************
数理最適化の技術は日々進化し,新しいアプローチが提案されています.
これらの技術の「性能」をどのように評価すべきかは,意外と奥が深い
問題です.
新たな MSIISM 記事「ソルバの性能評価」では,これまで提案されてきた
数理最適化ソルバの性能指標や機械学習との対比について解説しています.
MSIISM 記事「ソルバの性能評価」
https://www.msiism.jp/article/solver-performance-evaluation.html
ぜひご覧いただけましたら幸いです.
(藤井 浩一)
******************************************************************
■ <イベント> 特別イベント Nuorium Optimization Day 2024 のご案内
******************************************************************
数理最適化を全くご存知ない方や興味を持ち始めた方等を対象に,
数理最適化技術がどのような課題を解決できるのかを事例紹介を
含めて紹介する特別イベントを開催します.
本イベントのテーマは「数理最適化のポテンシャルを知る」です.
ぜひ,本イベントを通じて数理最適化の幅広さと奥深さを知っていただけ
たら幸いです.なお,当日は弊社社員に相談する場としてもご活用
ください.もし具体的な課題や悩みをお持ちの方は,申込フォームに
相談事項をご記載ください.
[日時]
2024 年 5 月 31 日(金)10:30 - 17:30
[講演者]
- 都築電気株式会社
- ライオン株式会社
- 株式会社 NTT データ数理システム
[会場]
コモレ四谷タワーコンファレンス Room F および Studio & Lounge
https://comore-yotsuya.jp/
[参加費]
無料
[スケジュール及び参加申込]
https://www.msiism.jp/event/nuorium-optimization-day2024.html
皆様のご参加をお待ちしております.
(石橋 保身)
******************************************************************
■ <セミナー> セミナーのご案内
******************************************************************
7 月までに開催する無料のオンラインセミナーをご紹介します.
物流や製造,シフトに関する課題に特化したセミナーを実施いたします.
関連しそうなセミナーがございましたら詳細をご確認いただき,
是非セミナーにご参加いただけますと幸いです.
[ 勤務シフト作成最適化セミナー ]
2024 年 05 月 29 日(水)13:30~15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-schedule.html
[ 輸送業務の最適化セミナー ]
2024 年 06 月 13 日(木)13:30~15:30
2024 年 07 月 10 日(水)13:30~15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-logistics.html
[ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー ]
2024 年 07 月 19 日(金)13:30~15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-manufacturing-scheduling.html
[ Nuorium Optimizer 紹介セミナー ]
2024 年 06 月 07 日 (金) 13:30~15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-introduction.html
(保科 拓紀)
******************************************************************
■ < tips > 使ってみよう PySIMPLE(第 30 回)
******************************************************************
このコーナーでは,Nuorium Optimizer の Python インターフェース
PySIMPLE のエッセンスを紹介していきます.
3 月にリリースされた V26 では幾つもの機能拡張や機能追加がされました.
今回はこのうち,添字付き get メソッドについて紹介します.
PySIMPLE で扱う添字付きオブジェクトは範囲外の添字にアクセスすると
通常 KeyError 例外を投げます.
------------------------------------------------------------------
>>> i = Element(value=[1, 2, 3], name='i')
>>> z = BinaryVariable(index=i, name='z')
>>> z[i+1]
KeyError: 'z[(i+1)[i]][4]'
------------------------------------------------------------------
上記の場合,i=3 のときに z[4] にアクセスしているため,KeyError と
なります.一方,V26 で新たに導入された get メソッドでは Python の
辞書における get メソッドのように範囲外にアクセスしても例外とならず,
PySIMPLE においては,0 となります.
モデルを記述する上で頻出である境界値で分岐する制約式を get メソッド
なし・ありで記述してみましょう.
------------------------------------------------------------------
>>> # without get
>>> i1 = i!=1 # i1 in (2, 3)
>>> z[1] >= 1
(z[1]>=1):
z[1]>=1
>>> z[i1] - z[i1-1] >= 1
((z[(i!=1)]-z[((i!=1)-1)[(i!=1)]][(i!=1)])[(i!=1)]>=1):
-z[1]+z[2]>=1
-z[2]+z[3]>=1
>>> # with get
>>> z[i] - z.get(i-1) >= 1
((z[i]-z.get((i-1)[i])[i])[i]>=1):
z[1]>=1
-z[1]+z[2]>=1
-z[2]+z[3]>=1
------------------------------------------------------------------
このように get メソッドを用いることで制約式を二つに分割することなく,
一括して記述することができるようになります.
今度は第 11 回の「フロー問題における保存則の書き方」に登場したフロー
ネットワークの保存則を get メソッドなし・ありで記述してみましょう.
------------------------------------------------------------------
>>> IJ = Set(value=[(1,2),(1,4),(2,3),(3,6),(4,5),(5,2),(5,6)], name='IJ')
>>> ij = Element(set=IJ, name='ij')
>>> x = Variable(index=ij, name='x')
>>> # without get
>>> m = Element(set=IJ(0)&IJ(1), name='m') # m in (2, 3, 4, 5)
>>> Sum(x[ij], ij(0))[m] == Sum(x[ij], ij(1))[m] # 入出力あり
(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 # ij(0)>IJ(1) in (1,)
(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 # ij(1)>IJ(0) in (6,)
(Sum(x[ij], ij(0))[(ij(1)>IJ(0))]==0):
x[3,6]+x[5,6]==0
>>> # with get
>>> k = Element(set=IJ(0)|IJ(1), name='k') # k in (1, ..., 6)
>>> Sum(x[ij], ij(0)).get(k) == Sum(x[ij], ij(1)).get(k)
(Sum(x[ij], ij(0)).get(k)[k]==Sum(x[ij], ij(1)).get(k)[k]):
-x[1,2]-x[1,4]==0
x[1,2]-x[2,3]+x[5,2]==0
x[2,3]-x[3,6]==0
x[1,4]-x[4,5]==0
x[4,5]-x[5,2]-x[5,6]==0
x[3,6]+x[5,6]==0
------------------------------------------------------------------
こちらも制約式を一括して記述することができました.
いかがでしたでしょうか.get メソッドを用いて一括して記述することで,
見た目が簡潔になるだけでなく,その後に式の値を取得したり制約式を削除
したりするなど,制御も簡単になります.
get メソッドは C++SIMPLE には存在しない PySIMPLE オリジナルの文法です.
非常に強力な記述力を持ちますが,一方で全く異なる式を一括して記述する
ことには向いていません.
第 11 回「フロー問題における保存則の書き方」の内容はこちら:
使ってみよう PySIMPLE(第 11 回)
境界条件やフロー保存則の記述テクニックはこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/get.html
get メソッドのマニュアルはこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/api/class.html#pysimple.Variable.get
(池田 悠)
==================================================================