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

バックナンバー ( 2024 Vol.4 ) 2024 年 7 月 17 日 発行

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  数理システム 最適化メールマガジン
                     https://www.msi.co.jp/solution/nuopt/top.html
                           2024 Vol.4 ( 2024 年  7 月 17 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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

++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ■ <トピック> Nuorium Optimizer 事例ご紹介
 ■ <トピック> 発表案内
 ■ <トピック> MSIISM 記事(社員インタビュー)のご紹介
 ■ <イベント> Nuorium Optimization Day 2024 開催報告
 ■ <セミナー> 無料オンラインセミナーのご案内
 ■ <  tips  > 使ってみよう PySIMPLE(第 31 回)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

******************************************************************
■ <トピック> Nuorium Optimizer 事例ご紹介
******************************************************************

2024 年 6 月 7 日に次の事例を公開しました.

・秋田県立大学 システム科学技術学部 木村 寛 様
  「数理最適化ツールを研究室に導入し学生の実践的研究に活用した事例」
  https://www.msiism.jp/article/kimura-akita-pu-nuopt.html

本事例では数理最適化による課題解決の実践的なノウハウを学生に
身につけてもらうことを目的に Nuorium Optimizer を導入いただきました.
具体的には勤務スケジューリングの最適化などにご利用くださり,フリーの
ツールにはない機能や弊社のサポートについてご評価をいただいています.
さらに地元企業との共同研究もされており,学生の育成から地域活性化と
幅広く活動されています.詳細はぜひ上記記事をご覧ください.

本事例の作成にあたり木村先生には大変お忙しい中,インタビューなどを
させていただきました.
この場を借りてお礼を申し上げます.

                                                (石橋 保身)

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

カナダ・モントリオールで開催される国際数理計画シンポジウム
ISMP 2024 にて弊社より二件発表を行います.

「二次計画問題に対する steepest-edge 単体法」
  * 清水翔司 (NTTデータ数理システム)
    藤井浩一 (NTTデータ数理システム)
    Julian Hall (University of Edinburgh)

線形計画問題を解くアルゴリズムの一つに,1947 年に G.B.Dantzig に
よって提案された単体法があります.単体法は 1950~60 年代に二次計画
問題に対しても適用できるように拡張されましたが,その後は,線形計画
問題に対する単体法ほど普及していないように窺えます.
二次計画単体法は,通常の単体法で用いられる線形代数の道具立て
(LU 分解・更新など) をそのまま利用できるため,スパース性を十分に
活かした効率的な実装が可能であるという利点があります.本講演では,
二次計画単体法の概略をお伝えしつつ,通常の線形計画問題に対する
単体法で成功を収めている steepest-edge 規則を二次計画単体法へ拡張
する話をいたします.

"Solving Large-Scale Quadratic Assignment Problems by a Parallelized Lagrangian-DNN-Based Branch-and-Bound"
  * 藤井浩一(NTT データ数理システム)
    小島政和(中央大学)
    品野勇治(Zuse Institute Berlin)
    Sunyoung Kim(梨花女子大学)
    Hans D. Mittelmann (Arizona State University)

二次割当問題(QAP)は,施設に配置場所を割り当てる問題で,各割り当てに
対するコストが二次関数で表現されます.この古典的な組合せ最適化問題は
依然として困難であることが知られており,代表的なベンチマーク QAPLIB の
いくつかのインスタンスはまだ未解決です.
本講演では,Ubiquity Generator フレームワークにより 100,000 以上の
コアを活用することにより,またラグランジアン二重非負錐緩和という
強力な緩和を用いることによって,大規模な QAP を計算する取り組みに
ついて紹介します.発表の中では,いくつかのオープンインスタンスを
初めて解き,またいくつかのインスタンスに対しては下界を更新することに
成功したという計算結果を報告します.

[ 日時 ]
  2024 年 07 月 21 日(日)~ 07 月 26 日(金)

[ 場所 ]
  モントリオール国際会議場

[ 詳細 ]
  学会 HP  https://ismp2024.gerad.ca/

                                                (藤井 浩一)

******************************************************************
■ <トピック> MSIISM 記事(社員インタビュー)のご紹介
******************************************************************

弊社顧問の大槻兼資さんに社員インタビュー記事を作成していただきました.
MSIISM にて公開されておりますので,ぜひご覧ください.
https://www.msiism.jp/article/fujii-t-interview-mathematical-optimization.html

ここでは,記事内で触れられている離散数学に関して簡単に補足したいと
思います.
離散数学というのは順列やグラフといった離散構造を扱う数学の分野です.
数理最適化においても解が離散的な値を取る最適化問題(離散最適化問題)
が扱われており離散数学の対象といえますが,離散数学においては最適化
アルゴリズムだけではなく,数え上げ等の他のアルゴリズムや,離散構造の
もつ数学的な性質そのものにも興味がある印象です.
私自身,学生時代には離散最適化そのものを研究していたわけではないの
ですが,いくつかの離散最適化問題に共通して現れる離散構造の数え上げに
関する研究をしていました.
数え上げアルゴリズム中でサブルーチンとして最適化アルゴリズムを利用
したこともあり,離散数学と離散最適化は深く関連していると感じています.

                                                (藤井 智仁)

******************************************************************
■ <イベント> Nuorium Optimization Day 2024 開催報告
******************************************************************

Nuorium Optimization Day 2024 という名前で, 当社主催の数理最適化に
特化したイベントを 5 月末に開催しました. 

コモレ四谷タワーコンファレンスにてオフラインで開催し, 約 50 名の方に
ご来場いただき盛況の内にイベントを終了することができました. 
イベントでは当社社員やお客様にご講演を通して, テーマの「数理最適化の
ポテンシャルを知る」についてお伝えできたかと思っています. 

来年も開催を考えていますので, 参加のご参考までに今年のイベントでの
講演タイトルを記載します. 

- 都築電気株式会社
「医療現場における数理最適化 患者さんの担当看護師決定支援」

- ライオン株式会社
「数理最適化を用いたスケジューラによる生産計画の自動作成」

- 株式会社NTTデータ数理システム
「数理最適化の適用可能性を探る~業務効率化から業務改革支援まで~」
「Nuorium Optimizer 最新機能と今後の展望」

また, 懇親会でも講演者様や参加者の皆様とコミュニケーションをとる
ことができ, 数理最適化に関する課題感の共有など非常に有意義な情報
共有の場となりました. 

来年の開催に関して, こんな話が聞いてみたい等テーマ案がありましたら, 
是非ご連絡いただければと思います!

                                                (保科 拓紀)

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

9 月までに開催する無料のオンラインセミナーをご紹介します.

製造やエネルギー,シフトの最適化に関して,課題に特化したセミナーを
実施いたします.
ご興味のあるセミナーがございましたら詳細をご確認いただき,是非
セミナーにご参加いただけますと幸いです.

製造セミナーは開催まで時間がないため,お早めにお申し込みください.

[ 勤務シフト作成最適化セミナー ]
  2024 年 09 月 05 日(木)13:30~15:30
  詳細とお申込み : 
    https://www.msiism.jp/event/nuopt-schedule.html

[ エネルギーマネジメント最適化セミナー ]
  2024 年 08 月 28 日(水)13:30~15:30
  詳細とお申込み
    https://www.msiism.jp/event/nuopt-energy-management.html

[ 製造現場の業務改善に向けた数理最適化ソリューション紹介セミナー ]
  2024 年 07 月 19 日(金)13:30~15:30
  詳細とお申込み : 
    https://www.msiism.jp/event/nuopt-manufacturing-scheduling.html

[ Nuorium Optimizer 紹介セミナー ]
  2024 年 08 月 27 日 (火) 13:30~15:30
  詳細とお申込み : 
    https://www.msiism.jp/event/nuopt-introduction.html

[ Nuorium Optimizer ハンズオンセミナー ]
  2024 年 09 月 20 日 (金) 13:30~16:00
  詳細とお申込み : 
   https://www.msiism.jp/event/nuopt-hands-on.html

                                                (保科 拓紀)

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

このコーナーでは,Nuorium Optimizer の Python インターフェース
PySIMPLE のエッセンスを紹介していきます.

3 月にリリースされた V26 では幾つもの機能拡張や機能追加がされました.
今回はこのうち,変数の添字をグループ化する group 属性の使いどころに
ついて紹介します.group 属性で指定された添字グループ情報は,求解の
性能向上のために活用されます.現在は汎用メタヒューリスティクス解法で
ある wls(重み付き局所探索法)において,「割当構造に対する探索性能
向上」のために用いられます.

割当構造とは,物同士の割り当てを意味する整数変数や制約式を意味します.
例えば変数として,「x[j,p]:仕事 j を作業者 p が担当するなら 1,そう
でないなら 0」等が考えられます.割当構造はシフトスケジューリング,
マッチング,レコメンデーション等,実世界の多くの最適化問題に現れます.

wls は,梅谷俊治博士の論文を参考にして開発されたメタヒューリスティクス
解法です.wls では「変数同士の関連性」を自動検出し,求解性能の向上を
図ります.添字グループ機能にて割当構造を明示すると,割当構造に基づく
関連性を用いてさらなる性能向上を目指します.

それでは実際に,PySIMPLE マニュアルの仕事割当問題を題材として group
属性を指定してみましょう.ソースコードはマニュアル内の以下のページを
ご参照ください.

https://www.msi.co.jp/solution/nuopt/docs/pysimple/_modules/sample/reidaishu.html#p2133_jobassign3

以下のとおりに p2133_jobassign3 関数を呼び出すことで,解法として
wls を指定できます.

------------------------------------------------------------------
p2133_jobassign3(method=Options.Method.WLS)
------------------------------------------------------------------

p2133_jobassign3 関数内で 0-1 整数変数 x を定義している部分に,
添字グループの指定を追記してみましょう.

------------------------------------------------------------------
    x = BinaryVariable(index=jp)
    x.group = 0  # 添字グループの指定(追加コード)
------------------------------------------------------------------

以上の修正にて,変数 x[j,p] が「0 番目の添字 j(仕事)と 1 番目の
添字 p(作業者)の割り当てを表す変数」であることが wls へ伝達されます.
再度 p2133_jobassign3 関数を呼び出してみましょう.添字グループの
情報が伝達されていることが,求解ログの次の箇所にて確認できます.
仕事の個数 8,作業員の人数 5,これらの割り当てを表す変数の個数 35 が
出力されています.

------------------------------------------------------------------
 # Assignment Labels (V1,V2,E) = (8, 5, 35)
------------------------------------------------------------------

今回の小規模な例では,添字グループの指定有無で最終的な目的関数値は
変化しませんが,問題規模が大きくなるにつれて結果に変化が生じます.
実際に,類似問題である一般化割当問題のうち作業者が 50 人以上の問題
設定にて,添字グループの指定により最終的な目的関数値が改善することが
確認されています.

最後に,添字グループの指定が wls の求解へいかに影響を及ぼすのか,
一例を説明します.局所探索法では,解に対して「近傍操作」と呼ばれる
微小変化を繰り返すことで制約違反量や目的関数値の改善を図ります.
添字グループを指定することで,wls では特殊な近傍操作「スワップ操作」を
積極的に用いるようになります.

「スワップ操作」について説明します.いま,2 つの仕事 j1, j2 と 2 人の
作業員 p1, p2 に着目し,探索途中の解が x[j1,p1] = 1,x[j1,p2] = 0,
x[j2,p1] = 0, x[j2,p2] = 1 だとします.この状況は,仕事と作業員の割当
関係として以下のとおりに図示できます.

j1 ─ p1
j2 ─ p2

スワップ操作ではこの解に対して,以下の図のとおりに割り当てを交換する
微小変化を与えます.

j1    p1
   ×
j2    p2

各仕事に対する人数制限や各作業員に対する仕事数制限が制約条件である
ことを考えると,スワップ操作は,制約条件の充足を維持しながら目的関数
値を改善する良い近傍操作であることが期待できます.wls では添字グループの
情報に基づきスワップ操作などの有望な近傍操作を追加することで,より
良い解への到達を図ります.

いかがでしたでしょうか.割当構造は実世界の多くの問題に現れる離散構造で,
局所探索法の研究においても近傍操作にこだわる価値が高いことが知られて
います.お手元の最適化問題に近しい構造がある場合,ぜひ group 属性を
お試しください.

group 属性の詳細はこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/api/class.html#pysimple.Variable.group

解法 wls の詳細はこちら:
https://www.msi.co.jp/solution/nuopt/docs/manual/html/0B-06-00.html

性能評価に用いた一般化割当問題の詳細はこちら (OR-Library):
https://people.brunel.ac.uk/~mastjjb/jeb/orlib/gapinfo.html

                                                (神谷 俊介)
==================================================================