-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン
https://www.msi.co.jp/solution/nuopt/top.html
2025 Vol.2 ( 2025 年 3 月 19 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理最適化パッケージ
Nuorium Optimizer をはじめとして，最適化に関する様々な情報や
ご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> ゼロサプレス型二分決定図（ZDD）のご紹介
■ <トピック> Excel アドインの PySIMPLE 対応について
■ <トピック> 発表報告
■ <トピック> 展示会出展のご案内
■ <セミナー> 無料オンラインセミナーのご案内
■ < tips > 使ってみよう PySIMPLE（第 35 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> ゼロサプレス型二分決定図（ZDD）のご紹介
******************************************************************
最適化問題，特に組合せ最適化問題を解く手法は様々です．
分枝限定法のような最適解を求める厳密解法もあれば，局所探索法の
ような短時間に良い解を求めることを目的とした近似解法もあります．
本トピックでは組合せ最適化問題を解く手法としてゼロサプレス型
二分決定図（ZDD）をご紹介します．
なお，本トピックは弊社イベントでご発表いただいた [1] の内容を
元に執筆しています．
ZDD は組合せ最適化問題を解く手法と言いましたが，より正確には
組合せの性質を持つデータを効率良く圧縮して表現するデータ構造の
ことです．厳密な定義を省いて説明すると，中学や高校で確率を求める
際に「樹形図」を書きました．数十通り以上になるとノートには書き
きれないほどの巨大な樹形図が出来上がりますが，ZDD ではその樹形図
が小さく圧縮して書ける，というものです．具体的な例や視覚的な図は
[1] をご覧ください．
最適化問題の制約条件を満たす解を ZDD として保持することで
「目的関数値が最小となる解を取得する」といった解の検索を高速に
行うことができます．また，解が圧縮されて ZDD として保持されて
いるため，複数の解を取得することも可能です．特に後者のような
特徴は「ユーザーの好みが単一の目的関数で表現できない問題」に
対してとても有効です．例えば [1] ではマンションの間取りについて，
ユーザーが与えた条件を元に ZDD を用いて高速に間取りを絞り込む
といった事例を紹介しています．
とても強力な手法である ZDD ですが，弱点もあります．解を圧縮する
という性質から，そもそも解を圧縮できないような問題には不向きです．
また，混合整数線形計画問題のような連続変数を含むような問題には
そのまま適用できません．最適化問題を解く際にはどのような手法が
良いかの見極めが重要です．
最後に宣伝になりますが，弊社はお客様からご依頼いただきましたら
ZDD のようなアルゴリズムの開発も行います．実際にお客様から
「最先端アルゴリズムの実装に必要な資質を備える，重要なパートナー」
とご評価いただきました [1]．何か難しそうな問題があればぜひ一度
弊社にご相談ください．
[1] 西野正彬（NTTコミュニケーション科学基礎研究所）,
"組合せ爆発を乗り越える最先端アルゴリズム技術とその実装",
https://www.msi.co.jp/event/conference/uc2021/lp/pdf/msi2021_1_4.pdf
（石橋 保身）
******************************************************************
■ <トピック> Excel アドインの PySIMPLE 対応について
******************************************************************
ご好評いただいている Excel アドインですが，Nuorium Optimizer V27
より従来のモデリング言語 C++SIMPLE に加えて，対応言語に PySIMPLE が
加わりました！
C++SIMPLE と同様，PySIMPLE で記述したモデルを記述をすると，変数・
パラメータが Excel に反映されます．
ユーザは，直感的に Excel のデータを最適化モデルの入力にすることが
でき，また最適化結果も Excel 上に表示することができます．
V27 の Excel アドインでは，複数のモデルを Excel 上で管理する機能も
増強されています．
さらにパワーアップした Excel アドインを，是非お試しください！
（藤井 浩一・村山 昇）
******************************************************************
■ <トピック> 発表報告
******************************************************************
以下の学会にて発表を行いました．
■ 日本オペレーションズ・リサーチ学会 2025 年春季研究発表会
開催日：3 月 6 日(木) ～ 3 月 7 日(金)
https://orsj.org/nc2025s/conference/
・Feasibility Jump の Nuorium Optimizer への導入（*富塚，藤井）
高速に実行可能解を求める LP-free ヒューリスティクスである
Feasibility Jump (FJ) について，Nuorium Optimizer への導入に際して
行った工夫を解説しました．ペナルティ重みの更新式の修正，非有界変数への
対応，repair 機能との結合について説明し，MIPLIB 2017 の Benchmark
セットやジョブショップスケジューリング問題に対する計算性能の向上を
示しました．発表後にも，さらなる改良として一度に jump する変数の
個数や方法，FJ の得手不得手な問題構造について議論させていただきました．
・混合整数線形計画問題に対する重み付き局所探索法（*神谷，藤井，石橋）
重み付き局所探索法 (WLS) について，Nuorium Optimizer V26 および
V27 での機能拡張を解説しました．連続変数に対応するための近傍操作の
修正や，並列化による初期解・探索パラメータの振り分け，スレッド間の
通信を活用した探索の多様化について説明し，MIPLIB 2017 の
Benchmark セットや Open インスタンスに対する数値実験の結果を示しました．
具体的には，並列化により実行可能解の発見速度や解の質が改善し，
Open インスタンスでは 3 つのインスタンスで既知の最良解を更新したことを
報告しました．質疑応答や発表後には，近傍操作のアイデアや，連続変数への
対応方法について，より詳細な議論が行われました．
■ 日本オペレーションズ・リサーチ学会 2025 年春季シンポジウム
開催日時 3 月 5 日(水) 13:30 ～ 17:20
https://orsj.org/nc2025s/symposium/
「海外 OR の最前線」というテーマで行われるパネルディスカッションにて
藤井浩一がパネリストとして参加しました．当日はアメリカ・ヨーロッパ・
日本における OR に対する観点や教育の違いについてディスカッションが
ありました．とりわけ興味深かったのは，アメリカにおける OR の教育が，
単なる座学ではなく実社会への検証も含めている点で，実務に根差した
OR を指向していることを感じました．
当日の様子は，機関誌「オペレーションズ・リサーチ」 8 月号
（ 2025 年 8 月 1 日刊行予定）に掲載される予定とのことです．
■ 日本機械学会 生産システム部門研究発表講演会 2025
開催日：3 月 3 日(月) ～ 3 月 4 日(火)
https://www.jsme.or.jp/msd/102_kouen25-6
・汎用メタヒューリスティクス解法 WLS の紹介と実務問題への応用
（*神谷，藤井，石橋）
重み付き局所探索法 (WLS) について，製造業における実務問題への
適用可能性を中心に解説しました．中規模・大規模のジョブショップ
スケジューリング問題や 2D Strip Packing Problem において，WLS が
分枝限定法よりも優れた性能を示す一方で，動的ロットサイズ決定問題では
分枝限定法が優れることを確認し，両手法の協調による数理最適化
パッケージの展望を示しました．特に，ジョブショップスケジューリング
問題では，ジョブ数 20 以上，機械台数 15 台以上の規模における性能や，
フレキシブル性（作業を行う機械を選べる追加設定）を加えた場合でも
高い性能を維持できることを示しました．2D Strip Packing Problem
については，MSIISM に掲載しておりますので，ぜひご覧ください．
https://www.msiism.jp/article/nuorium-optimizer-v27-1.html
質疑応答や発表後には，問題規模の実用性やアルゴリズムのシンプルさに
関心をもっていただき，汎用解法の可能性拡大について活発な議論が
行われました．
（神谷 俊介・藤井 浩一・富塚 健志）
******************************************************************
■ <トピック> 展示会出展のご案内
******************************************************************
当社は AI・業務自動化展にて展示を行います．
弊社のソリューションやパッケージの紹介を行いますので，
もし会場にお越しの際は弊社ブースにもお立ち寄りください．
展示会概要
名称 : Japan DX Week AI・業務自動化展
場所 : 東京ビッグサイト
期間 : 2025 年 4 月 23 日(水)～4 月 25 日(金)
https://www.japan-it.jp/hub/ja-jp/visit/ai.html
（保科 拓紀）
******************************************************************
■ <セミナー> 無料オンラインセミナーのご案内
******************************************************************
4 月までに開催する数理最適化に関連する無料のオンラインセミナーを
ご紹介します．
年度の切り替わり時期でもあるので，Nuorium Optimizer の紹介セミナーや
ハンズオンセミナーを実施いたします．
ご興味のあるセミナーございましたら詳細をご確認いただき，
是非セミナーにご参加いただけますと幸いです．
[ Nuorium Optimizer 紹介セミナー ]
2025 年 4 月 10 日（木）13:30～15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-introduction.html
[ Nuorium Optimizer ハンズオンセミナー ]
2025 年 4 月 16 日（水）13:30～16:00
詳細とお申込み
https://www.msiism.jp/event/nuopt-hands-on.html
（保科 拓紀）
******************************************************************
■ < tips > 使ってみよう PySIMPLE（第 35 回）
******************************************************************
このコーナーでは，Nuorium Optimizer の Python インターフェース
PySIMPLE のエッセンスを紹介していきます．
今回は選択関数 Selection に伴う，次元を落としたオブジェクト作成の
方法について紹介します．
以下では変数 z[i,j] は Selection 制約のため，各 i について
z[i,j].val=1 となる j が存在します．
------------------------------------------------------------------
>>> i = Element(value=[1, 2, 3], name='i')
>>> j = Element(value=['X', 'Y'], name='j')
>>> z = BinaryVariable(index=(i,j), name='x')
>>> p = Problem()
>>> p += Selection(z[i,j], j)
>>> p.solve(silent=True)
<NuoptStatus.OPTIMAL: 1>
>>> ij = z[i,j].val>0
>>> z[ij].val
z[1,'X'].val=1
z[2,'Y'].val=1
z[3,'Y'].val=1
------------------------------------------------------------------
これを i をキーとしたオブジェクトとして扱いたい場合にはどうすれば
よいでしょうか．
以下では z[i,j].val>0 を満たす (i,j) の組合せ ij を用いることに
より，i をキー，対応する j を値とするパラメーター a を作成して
います．
------------------------------------------------------------------
>>> a = Parameter(index=i, name='a')
>>> a[ij(0)] = ij(1)
>>> a
a[1]='X'
a[2]='Y'
a[3]='Y'
------------------------------------------------------------------
更に a は一度に Parameter(index=i, value=dict(ij.set)) と記述する
ことも可能です．
Selection で和をとった後に残る添字(上記では i)が多次元の場合でも
同様の方法で扱うことができます．
では，和をとる添字(上記では j)が多次元だった場合はどうすればよいで
しょうか．
以下では z[i,j,k] を (j,k) で Selection をとっているため，各 i に
ついて z[i,j,k].val=1 となる (j,k) の組が存在します．
------------------------------------------------------------------
>>> i = Element(value=[1, 2, 3], name='i')
>>> j = Element(value=['A', 'B'], name='j')
>>> k = Element(value=['X', 'Y'], name='k')
>>> z = BinaryVariable(index=(i,j,k), name='z')
>>> p = Problem()
>>> p += Selection(z[i,j,k], (j,k))
>>> p.solve(silent=True)
<NuoptStatus.OPTIMAL: 1>
>>> ijk = z[i,j,k].val>0
>>> z[ijk].val
z[1,'A','Y'].val=1
z[2,'B','X'].val=1
z[3,'B','Y'].val=1
------------------------------------------------------------------
Parameter は一次元の値しかとることができないため，このような場合，
j 部分を担当するパラメーター aj と，k 部分を担当するパラメーター ak
に分割することで，i をキーとしたオブジェクトとして扱うことができる
ようになります．
このようにすることで (j,k) の組合せが欲しい場合には aj[i] と ak[i]
と記述できます．
------------------------------------------------------------------
>>> aj = Parameter(index=i, name='aj')
>>> aj[ijk(0)] = ijk(1)
>>> aj
aj[1]='A'
aj[2]='B'
aj[3]='B'
>>> ak = Parameter(index=i, name='ak')
>>> ak[ijk(0)] = ijk(2)
>>> ak
ak[1]='Y'
ak[2]='X'
ak[3]='Y'
>>> Printf('{}: {}, {}', i, aj[i], ak[i])
1: A, Y
2: B, X
3: B, Y
------------------------------------------------------------------
更に aj, ak はそれぞれ Parameter(index=i, value=dict(ijk(0,1).set))，
Parameter(index=i, value=dict(ijk(0,2).set)) と記述することも可能です．
いかがでしたでしょうか．今回は特に真新しい機能は紹介していませんが，
上手く発想をすることで添字のまま操作ができることが実感できたのでは
ないでしょうか．
Selection 関数の説明はこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/selection.html
Selection 関数の API マニュアルはこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/api/function.html#pysimple.func.Selection
（池田 悠）
==================================================================
