-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/
2021 Vol.1 ( 2021 年 1 月 13 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理計画法パッケージ
数理システム Numerical Optimizer をはじめとして，最適化に関する様々
な情報やご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> 新年のご挨拶
■ <トピック> Numerical Optimizer V23 3 月リリース予定
■ <セミナー> 新機能紹介セミナーのご案内
■ < tips > 使ってみよう PySIMPLE（第 12 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> 新年のご挨拶
******************************************************************
数理科学は，現実世界を数理モデルとして表現するところに特徴が
あります．
いろいろな現象や仕組みをモデル化してゆく作業は自由で楽しい．
でも，そこからどんな帰着が現れるのかがわからない怖さもある．
だからモデルを「解く」という作業が必要になります．
結果の「数字」が与えてくれるインサイトの大きさは測り知れず，
先の見えない作業に道筋を付けてくれます．
最適化モデルとして表現された世界での探索を肩代りして，
その様相を具体的に提示するのが最適化ソルバー Numerical Optimizer の
役割ですが，モデリング言語 PySIMPLE の機能増強や新アルゴリズムの
実装など，今年の新バージョン V23 も，速く結果を求めるだけではなく，
数理モデルを改良してより正しい理解に迫ろうとするみなさまに
広く供することができればと願っております．
本年もどうかよろしくお願い申しあげます．
（田辺 隆人）
******************************************************************
■ <トピック> Numerical Optimizer V23 3 月リリース予定
******************************************************************
Numerical Optimizer V23 を 3 月中にリリースする予定です．
V23 では以下の機能が強化されています．
- モデリング言語 PySIMPLE を強化
- タブーサーチを用いた重み付き制約充足問題への対応
- QP(二次計画問題)への対応
- 新アルゴリズム wls を搭載
- 整数計画問題に対する近似解法
- PySIMPLE 経由でご利用可能
wls (weighting local search, 重み付き局所探索法) は，整数計画問題に
対する近似解法です．整数変数間の結びつきを表現するデータ構造「隣接
リスト」を活用し，制約条件が複雑な問題に対しても手際よく実行可能解を
見つけます．本アルゴリズムは大阪大学の梅谷俊治先生の下記の論文を参考
に開発しております．技術的内容にご興味のある方はご覧ください．
S. Umetani: Exploiting variable associations to configure
efficient local search algorithms in large-scale binary integer
programs. Eur. J. Oper. Res., Vol. 263, pp. 72-81, 2017.
wls は整数計画問題の中でも，すべての係数が 0 か 1 である制約式（0-1
制約式）を多くもつ最適化問題に対して特に高い性能を発揮します．
0-1 制約式は航空や鉄道スタッフの従業員スケジューリングなど多くの
場面で現れます．
また 2 次の目的関数やソフト制約（優先度の低い制約）も扱えるため，
さまざまな場面で使用可能です．類似アルゴリズムである wcsp とは例えば
以下の使い分けが考えられます．
- selection として表現できる制約条件が多い --> wcsp
- 0-1 制約式が多い --> wls
さて，V23 において wls は PySIMPLE 経由でのみご利用いただけます．
使い方は簡単で，次のようにアルゴリズムを指定するだけです．
--------------------------------------------------------------
# アルゴリズムを指定
problem.options.method = "wls"
--------------------------------------------------------------
ここでは例として，以下のプログラムを実行してみます．
--------------------------------------------------------------
"""サンプル(目的関数・変数・制約)"""
from pysimple import Problem, BinaryVariable, IntegerVariable
problem = Problem(name="wlsサンプル")
# 変数
x = BinaryVariable()
y = IntegerVariable(lb=-1, ub=3)
z = BinaryVariable()
# 目的関数
problem += x - 2 * y + 3 * z
# 制約条件
problem += x + z == 2
problem += 3 * x + 2 * y - z <= 0
# アルゴリズムを指定
problem.options.method = "wls"
# 求解
print(problem)
problem.solve()
--------------------------------------------------------------
結果は以下のとおりになりました．最適解 (x, y, z) = (1, -1, 1) が
得られています．
=================================================
# Obj = 6
# (Hard/Soft) Penalty = 0 / 0
# Elapsed Time(s) = 0.000283957 / 0.145244
# Iterations = 3 / 10000
=================================================
以上をもって wls のご紹介といたします．ご覧のとおりアルゴリズムは
簡単に切替可能なので，wcsp など他のアルゴリズムと併せお気軽にお試
しください．
PySIMPLE の新機能については，具体的なサンプルを次回以降の連載にて
ご紹介する予定です．
V23 のご紹介は以上です．現在はリリースに向けて鋭意作業中ですので，
お手元に届くまでもうしばらくお待ちください．
（神谷 俊介）
******************************************************************
■ <セミナー> 新機能紹介セミナーのご案内
******************************************************************
Numerical Optimizer V23 の魅力をたっぷりお伝えするセミナーを開催
いたします．PySIMPLE の豊富なデモや wls のアルゴリズムの話など，
メルマガでは紹介しきれない内容もございます．ご興味のある方はぜひ
お申込みください．もちろん，無料のオンラインセミナーとなっています
ので遠方の方もお気軽にご参加ください．
2/26 (金) https://area34.smp.ne.jp/area/card/26339/52wyHD/M?S=lbpftj0lcsh0mjrjp
3/9 (火) https://area34.smp.ne.jp/area/card/26339/d1DGe3/M?S=lbpftj0lcsi0mjrjp
また，通常の紹介セミナーも開催しています．大変ご好評いただいて
いますので，ご都合の良い時にふらっとご参加くださいますと幸いです．
1/22 (金) https://area34.smp.ne.jp/area/card/26339/93D1Ie/M?S=lbpftj0lcse0mjrjp
2/25 (木) https://area34.smp.ne.jp/area/card/26339/H50SKf/M?S=lbpftj0lcsf0mjrjp
3/17 (水) https://area34.smp.ne.jp/area/card/26339/5cQmde/M?S=lbpftj0lcsg0mjrjp
（石橋 保身）
******************************************************************
■ < tips > 使ってみよう PySIMPLE（第 12 回）
******************************************************************
このコーナーでは，Numerical Optimizer V21 以降の機能であるモデリング
言語 PySIMPLE のエッセンスを紹介していきます．
今回は数理計画問題の連続緩和問題を PySIMPLE で扱う方法について紹介
します．
(混合)整数線形計画問題に対して，整数変数を実数変数にすることを連続
緩和(実数緩和)といい，連続緩和した問題を元の問題(主問題)の連続緩和
問題といいます．連続緩和問題は線形計画問題となるため，主問題に比べて
容易に解を求めることができます．そのため，例えば，求解に時間がかかる
問題や，実行不可能な問題に対して，何らかの解を出すことができます．
また，連続緩和問題の重要な性質として，(最小化問題の場合，)その解は
主問題の下界を与えます．すなわち，"何らかの解"は主問題の下界である
ことが保証されています．例として PySIMPLE で記述された次の問題を
考えてみましょう．
------------------------------------------------------------------
i = Element(value=[1, 2])
x = IntegerVariable(index=i, lb=0, ub=5)
p = Problem()
p += 6*x[1] + x[2] >= 12
p += 4*x[1] + 6*x[2] >= 24
p += 180*x[1] + 160*x[2]
p.solve()
------------------------------------------------------------------
この問題の最適解は x[1]=2, x[2]=3 のときに目的関数値 840 となります．
一方で，連続緩和問題では x[1]=1.5, x[2]=3 のときに目的関数値 750 と
なっており，840 >= 750(下界)となっています．
さて，この数理計画問題の主問題・緩和問題を制御するにはどうすれば
よいでしょうか．例えば，上記の数理計画問題を関数化して引数で制御
してみましょう．
------------------------------------------------------------------
def problem(relax: bool):
i = Element(value=[1, 2])
if relax:
x = Variable(index=i)
else:
x = IntegerVariable(index=i)
：
------------------------------------------------------------------
これで，problem(relax=False) とすれば主問題が，problem(relax=True)
とすれば緩和問題になります．また，PySIMPLE では IntegerVariable は
Variable(type=int, …) の糖衣構文であるので，もっと簡潔に次のように
記述することができます．
------------------------------------------------------------------
def problem2(vtype):
i = Element(value=[1, 2])
x = Variable(index=i, type=vtype)
：
------------------------------------------------------------------
これで，problem2(vtype=int) とすれば主問題が，problem2(vtype=float)
とすれば緩和問題になります．
今度は「主問題の結果が最適解でなかったら緩和問題を解く」という制御を
してみましょう．
------------------------------------------------------------------
p = problem2(vtype=int) # 戻り値は Problem
p.solve()
if p.status != NuoptStatus.OPTIMAL:
prelax = problem2(vtype=float) # 緩和問題
prelax.solve()
------------------------------------------------------------------
一見，良さそうですが，もっと効率的に扱う方法があります．この制御方法
では，problem2 関数 2 回分の時間がかかってしまいます．PySIMPLE では
変数の type を動的に変えることができるため，次のように記述することが
できます．
------------------------------------------------------------------
i = Element(value=[1, 2])
x = IntegerVariable(index=i) # Variable(index=i, type=int) と同じ
p = Problem()
：
p.solve()
if p.status != NuoptStatus.OPTIMAL:
x.type = float # 変数の type を連続変数に動的に変更
p.solve() # 緩和問題を求解
------------------------------------------------------------------
いかがでしたでしょうか．このように PySIMPLE では数理計画問題を扱う
ことに特化した様々な機能があります．
PySIMPLE における連続緩和のドキュメントはこちら:
https://www.msi.co.jp/nuopt/docs/v22/pysimple/guide/relax.html
（池田 悠）
==================================================================
※ このメールは，弊社ツールのユーザー様，過去に展示会などでお名刺
等を頂いたことのある方や当社に直接お問合せを頂いたことのある方
にお送りしています．
※ バックナンバーはこちらから御覧頂けます．
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（第 12 回）」の記事内のモデルの記述例
につきまして、以下の誤りがございました。
訂正させていただきますとともに、お詫び申し上げます。
< 最初の PySIMPLE で問題を記述した部分 >
（誤）p += 4*x[i] + 6*x[2] >= 24
（正）p += 4*x[1] + 6*x[2] >= 24
なお、本ページ内の該当箇所につきましては訂正を行なっております。
