-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン
https://www.msi.co.jp/solution/nuopt/top.html
2024 Vol.2 ( 2024 年 3 月 6 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理最適化パッケージ
Nuorium Optimizer をはじめとして，最適化に関する様々な情報や
ご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> Nuorium Optimizer V26 3 月リリース予定
■ <トピック> 発表案内
■ <セミナー> セミナーのご案内
■ < tips > 使ってみよう PySIMPLE（第 29 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> Nuorium Optimizer V26 3 月リリース予定
******************************************************************
Nuorium Optimizer V26 を 3 月中にリリースする予定です．
V26 では以下の機能が強化されています．
- ソルバ
- 分枝限定法の発見的探索強化
- ハイパースパース単体法 hsimplex の前処理強化
- 重み付き局所探索法 WLS の混合整数計画問題対応
- モデリング言語 PySIMPLE
- 添字グループ情報の利用
- 変数の値固定機能
- 添字付き get メソッド
分枝限定法における発見的探索を強化しました．
特に問題構造を利用した発見的探索の強化を行いました．
これにより，弊社のベンチマークセット（747 問）で 60 秒以内に
実行可能解の求まる数が 85% から 91 % に向上しています．
ハイパースパース単体法（hsimplex）に対して前処理を強化しました．
実務に現れる問題は往々にして除去可能な変数や制約式をもちます．
そのような問題では hsimplex による求解速度の向上が見込めます．
※解法 hsimplex は PySIMPLE からのみ選択可能です
重み付き局所探索法 WLS が，従来扱えるのは整数変数のみの問題まで
でしたが，連続変数を含む問題（混合整数計画問題）に対して解ける
ようになりました．
なお目的関数と制約式が線形である最適化問題に対して適用可能です．
これにより，WLS で扱える問題が飛躍的に拡大しました．
※解法 WLS は PySIMPLE からのみ選択可能です
PySIMPLE の新機能については，今後のメールマガジンの
「使ってみよう PySIMPLE」にて，随時ご紹介いたします．
Nuorium Optimizer V26 の 3 月リリースに向けて鋭意作業中です．
是非ご期待ください！
（藤井 浩一）
******************************************************************
■ <トピック> 発表案内
******************************************************************
3 月 7 日・8 日に筑波大学で開催される日本オペレーションズ・リサーチ
学会 2024 年春季研究発表会にて学会展示と発表をおこないます．
・列挙の方法による market split 問題の解法
* 田中大毅（NTT データ数理システム）
market split 問題とは 0-1 整数変数と等式制約のみを含む整数計画
問題で，数十変数程度の小規模な問題であっても汎用ソルバでは解くことが
極めて難しいことが指摘されています．
実際，整数計画問題のベンチマークセットである MIPLIB に含まれる
pb-market-split8-70-4 という問題は，70 変数 8 制約という小規模な
問題でありながら，2023 年まで実行可能解が存在するか否かは不明でした．
本研究では，分枝限定法とは異なるアプローチにより pb-market-split8-70-4
の実行可能解をすべて求めることに成功したので，そのアルゴリズムに
ついて解説します．
OR 学会では発表だけではなく展示も行っております．
是非展示ブースにお立ち寄りください！
また，3 月 21 日・22 に政策研究大学院大学で開催される研究集会
「最適化：モデリングとアルゴリズム」にて発表をおこないます．
・Steepest-Edge Simplex Algorithms for Quadratic Programming
* 清水翔司（NTT データ数理システム）
藤井浩一（NTT データ数理システム）
Julian Hall (University of Edinburgh)
線形計画問題を解くアルゴリズムの一つに，1947 年に G.B.Dantzig に
よって提案された単体法があります．
単体法は 50/60 年代に二次計画問題に対しても適用できるように拡張
されましたが，その後は，線形計画問題に対する単体法ほど普及して
いないように窺えます．
二次計画単体法には，通常の単体法で扱うよりも大きな方程式系を
扱わなければならないというデメリットがありますが，一方で，
通常の単体法で使用される線形代数の道具立て（LU 分解・更新など）を
そのまま流用でき，スパース性をフルに活用した効率的な実装が
可能であるというメリットがあります．
本講演では，二次計画単体法の概略をお伝えしつつ，通常の線形計画問題に
対する単体法で成功を収めている steepest-edge 規則を二次計画単体法へ
拡張する話をいたします．
・Improving Lower Bounds for Large Scale QAPs
* 藤井浩一（NTT データ数理システム）
小島政和（中央大学）
品野勇治（Zuse Institute Berlin）
Hans D. Mittelmann (Arizona State University)
Sunyoung Kim（梨花女子大学）
大規模二次割当問題(QAP)を解くプロジェクトの進捗状況を報告します．
本発表ではニュートンブラケット法を用いて二重非負緩和（DNN: Double
Non-Negative Relaxation）を用いて QAP の大域的下界を効率よく
求める手法を発表します．
DNN を解く過程で得られる補助的情報と，並列化フレームワーク Ubiquity
Generator (UG) に実装されているチェックポイント機構を組み合わせる
ことにより，大規模な QAP 問題に対して強力な大域的下界を求めることが
可能になります．
この手法により，QAPの標準的なベンチマークであるQAPLIBに含まれる，
最適解が未だ証明されていない問題のいくつかに対して下界を更新した
という成果を報告します．
（藤井 浩一）
******************************************************************
■ <セミナー> セミナーのご案内
******************************************************************
4 月までに開催する無料のセミナーをご紹介します．
新しく企画した【シフトセミナー】や【物流セミナー】も開催しますので，
この機会に是非奮ってご参加ください．
また 3 月にハンズオンセミナーを開催します．
実際に製品を動かしながら受講いただけるセミナーになっております．
年度末のこの機会にご興味のある方は申込いただければと思います．
ぜひこの機会にご参加ください．
[ 勤務シフト作成最適化セミナー (対面)]
2024 年 03 月 19 日（火）13:30～15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-schedule.html
[ 輸送業務の最適化セミナー (Webinar)]
2024 年 03 月 13 日（水）13:30～15:30
詳細とお申込み
https://www.msiism.jp/event/nuopt-logistics.html
[ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー (Webinar)]
2024 年 04 月 05 日（金）13:30～15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-manufacturing-scheduling.html
[ Nuorium Optimizer ハンズオンセミナー (Webinar)]
2024 年 03 月 22 日 (金) 13:30～16:00
詳細とお申込み :
https://www.msiism.jp/event/nuopt-hands-on.html
[ Nuorium Optimizer 紹介セミナー (Webinar)]
2024 年 03 月 14 日 (木) 13:30～15:30
2024 年 04 月 18 日 (木) 13:30～15:30
詳細とお申込み :
https://www.msiism.jp/event/nuopt-introduction.html
（保科 拓紀）
******************************************************************
■ < tips > 使ってみよう PySIMPLE（第 29 回）
******************************************************************
このコーナーでは，Nuorium Optimizer の Python インターフェース
PySIMPLE のエッセンスを紹介していきます．
第 11 回では PySIMPLE でフローネットワークを扱う方法を紹介しました．
今回は更に踏み込んだフローネットワークの扱い方を紹介します．
次のようなフローネットワーク NN を考えます．今回は NN の部分フロー
ネットワーク KK も考えます．N1, K1 は始点，N2, K2 は終点，N, K は
始終点のノードの集合を表します．
C++SIMPLE:
------------------------------------------------------------------
Set N, K;
Set KK(dim=2, superSet=(K,K))="nk1,k k1,k k,nk2 k,k2";
Set NN(dim=2, superSet=(N,N))="n1,n nk1,n n,n2 n,nk2 n1,k1 k2,n2";
NN = NN | KK;
Set N1 = NN.slice(1), N2 = NN.slice(2);
Set K1 = KK.slice(1), K2 = KK.slice(2);
------------------------------------------------------------------
PySIMPLE:
------------------------------------------------------------------
KK = Set(value=[('nk1','k'), ('k1','k'), ('k','nk2'), ('k','k2')])
NN = Set(value=[('n1','n'), ('nk1','n'), ('n','n2'), ('n','nk2'),
('n1','k1'), ('k2','n2')]) | KK
N1, N2 = NN(0), NN(1)
K1, K2 = KK(0), KK(1)
N = N1 | N2
K = K1 | K2
------------------------------------------------------------------
このネットワーク NN を図示すると以下のようになります．矢印は省略して
いますが，おおよそ上から下へ流れます．また KK は nk から右部分です．
┌──────┐
n1 nk1 k1
＼ ／ ＼ ／
n k
／ ＼ ／ ＼
n2 nk2 k2
└──────┘
第 11 回の復習として NN における保存則を記述してみましょう．
C++SIMPLE:
------------------------------------------------------------------
Element nn(set=NN), n1(set=N1), n2(set=N2), n(set=N);
Variable x(index=nn);
Expression x_in(index=n);
Expression x_out(index=n);
x_in[n2] = sum(x[n1,n2], (n1, (n1,n2)<NN)); // ノード n2 の流入量
x_out[n1] = sum(x[n1,n2], (n2, (n1,n2)<NN)); // ノード n1 の流出量
x_in[n] == x_out[n]; // 流入量と流出量は等しい
------------------------------------------------------------------
PySIMPLE:
------------------------------------------------------------------
nn = Element(set=NN)
x = Variable(index=nn)
x_in = Sum(x[nn], nn(0))
x_out = Sum(x[nn], nn(1))
nn_io = Element(set=N1 & N2) # 流入出あり {n, k1, k2, k}
nn_in = Element(set=N2 - N1) # 流入のみ {n2, nk2}
nn_out = Element(set=N1 - N2) # 流出のみ {n1, nk1}
x_in[nn_io] == x_out[nn_io] #
x_in[nn_in] == 0 # x_in[nn(1)>N1] == 0 でも同じ
x_out[nn_out] == 0 # x_out[nn(0)>N2] == 0 でも同じ
------------------------------------------------------------------
今回は部分ネットワーク KK における保存則を考えます．同様に記述して
みましょう．
C++SIMPLE:
------------------------------------------------------------------
Element k(set=K);
x_in[k] == x_out[k];
------------------------------------------------------------------
PySIMPLE(間違い):
------------------------------------------------------------------
kk_io = Element(set=K1 & K2) # {k}
kk_in = Element(set=K2 - K1) # {nk2, k2}
kk_out = Element(set=K1 - K2) # {nk1, k1}
x_in[kk_io] == x_out[kk_io] # kk = Element(set=KK)
x_in[kk_in] == 0
x_out[kk_out] == 0
------------------------------------------------------------------
実は C++SIMPLE ではこれで大丈夫なのですが，PySIMPLE の場合は意図した
制約になりません．実際，ノード k1, k2 は流入・流出ともにあるのですが，
添字 kk_io には k しか含まれません．正しくは次のように記述します．
PySIMPLE(正しい):
------------------------------------------------------------------
kk_io = Element(set=N1 & N2 & K) # {k1, k2, k}
kk_in = Element(set=N2 - N1 & K) # {nk2}
kk_out = Element(set=N1 - N2 & K) # {nk1}
x_in[kk_io] == x_out[kk_io] # x_in[kk_io] == x_out[kk_io]
x_in[kk_in] == 0
x_out[kk_out] == 0
------------------------------------------------------------------
今回のノードの包含関係をベン図にすると，以下のようになります．一般に
K1⊂N1, K2⊂N2 のときに，K1 & K2 と N1 & N2 & K は一致しないことに
注意しましょう．
+-N1-----------+
| +-K1-----+ |
|n1| +----+--+------+
| |nk1| | n| |
| | |k1+-+--+---+ |
| | | |k| | | |
| +---+--+-+k2| | |
| | n| |nk2| |
+------+--+----+ |n2|
| +-----K2-+ |
+-----------N2-+
いかがでしたでしょうか．PySIMPLE は C++SIMPLE のように式を宣言でき
ないこともあり，記述が少し複雑になってしまうこともあります．一方で
添字範囲がどこなのか常に意識することで大味な記述を排除できるとも
いえます．どちらが良いかは難しいですが，添字の動く範囲を気にかけて
おくことは非常に大事です．
実は V26 で追加される機能「添字付き get メソッド」を用いることで
C++SIMPLE と同じように非常に簡潔に記述することができます．
------------------------------------------------------------------
k = Element(set=K)
x_in.get(k) == x_out.get(k)
------------------------------------------------------------------
次回はこちらを含めた V26 新機能の紹介をいたします．どうぞお楽しみに．
第 11 回「フロー問題における保存則の書き方」の内容はこちら:
使ってみよう PySIMPLE（第 11 回）
（池田 悠）
==================================================================
