-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン
https://www.msi.co.jp/solution/nuopt/top.html
2026 Vol.5 ( 2026 年 9 月 18 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理最適化パッケージ
Nuorium Optimizer をはじめとして，最適化に関する様々な情報や
ご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> ブラックボックス最適化モジュールのリリース予告
■ <トピック> Feasibility Pump 2.0 のご紹介
■ <イベント> OR セミナー「数理最適化の考え方とモデリング：
AI 時代に求められる最適化エンジニアの役割とは？」開催
■ <トピック> 定式化技法集「スラック緩和」のご紹介
■ < tips > 使ってみよう PySIMPLE（第 43 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> ブラックボックス最適化モジュールのリリース予告
******************************************************************
2026 年 9 月 29 日に Nuorium Optimizer の新機能 ブラックボックス
最適化モジュール をリリースいたします．
ブラックボックス最適化とは，目的関数の数式や勾配を利用せず，
評価値を基に最適解を探索する手法です．
次の記事は本モジュールで解くことができる問題の一例です．
参考：ブラックボックス最適化による偏微分方程式の逆問題解析
https://www.msiism.jp/article/black-box-optimization.html
今後，本モジュールの具体的なユースケース等をメルマガや MSIISM で
発信していきます．
ご期待いただき，リリースまでもうすこしお待ちください．
（田中 大毅）
******************************************************************
■ <トピック> Feasibility Pump 2.0 のご紹介
******************************************************************
混合整数計画問題を解く分枝限定法というアルゴリズムにおいては，
「実行可能解（制約式を満たす解）」を早期に見つける，ということは
とても重要です．
分枝限定法自体の収束を早くする，という点もありますが，何よりも実務に
おいて「現場で使える解」が得られ，安心に使えるためです．このため
分枝限定法には様々なヒューリスティクスが実装されています．
その一つが，Feasibility Pump([1])です．このアルゴリズムは以下の
ような考えで動きます．まず，整数制約を除いた LP 緩和を解くと，
制約式を満たすが整数ではない点が得られます．これを最寄りの整数に
丸めれば，今度は整数だが制約を破る点が得られます．そこで，丸めた点に
もっとも近い LP 実行可能点を求め，それをふたたび丸める．この往復を
繰り返し，「制約を満たす領域」と「整数条件を満たす領域」の間を
行き来しながら，両者が交わる点へと少しずつ解を近づけていきます．
さて，2026 年 3 月リリースの Nuorium Optimizer V28 （ 28.1.0 ）では，
この手法の改良を行いました．一つは，Feasibility Pump 2.0([2])と
呼ばれる拡張です．
従来の丸め操作を，制約伝播（constraint propagation）を用いた
変数固定へと置き換えたものです．
これにより，従来は整数変数が 0-1 変数の場合にのみ対応していましたが，
一般整数変数を含む問題にも適用できるようになりました．
あわせて，直線探索機能([3])も実装し，緩和解のみではなく，
直線上の点も丸め候補として加える改良を行いました．
この改良を適用したところ，起動運転停止計画（Unit Commitment）
問題で，従来実行可能解を見つけることが難しいインスタンスに対して
数分で実行可能解を発見するようになりました．
この改良された Feasibility Pump は分枝限定法のデフォルトで動作
します．実行可能解の発見にお困りの問題がございましたら，ぜひ
Nuorium Optimizer V28 をお試しください．
[1] Fischetti, Matteo, Fred Glover, and Andrea Lodi.
"The feasibility pump." Mathematical Programming 104,
no. 1 (2005): 91-104.
[2] Fischetti, Matteo, and Domenico Salvagnin.
"Feasibility pump 2.0." Mathematical Programming Computation 1,
no. 2 (2009): 201-222.
[3] Boland, Natashia, Andrew Eberhard, Faramroze Engineer,
Matteo Fischetti, Martin Savelsbergh, and Angelos Tsoukalas.
"Boosting the feasibility pump." Mathematical Programming
Computation 6, no. 3 (2014): 255-279.
（藤井 浩一・逸見 宣博）
******************************************************************
■ <イベント> OR セミナー「数理最適化の考え方とモデリング：
AI 時代に求められる最適化エンジニアの役割とは？」開催
******************************************************************
今年の 11 月に開催される，OR 学会主催の OR セミナーにて弊社メンバーが
登壇します．イベントでは数理最適化モデリングの基礎から始め，生成 AI
の活用までを含めた実践的な話題をお伝えする予定です．
日時: 2026 年 11 月 28 日（土） 10:00～17:00
会場: NTT データ 豊洲センタービル 36 階
（※オンライン配信はございません）
定員: 80 名
申し込み期限: 11 月 13 日(金) ※ 定員になり次第締め切りとなります
イベント詳細: https://orsj.org/?p=9976
イベントプログラム
1. AI 時代に求められる数理最適化の考え方
2. 数理最適化モデリングの基礎
3. 数理最適化モデリングの実践テクニックと理論
4. 数理最適化×生成 AI の現在と今後の展望
5. 問題構造の把握と問題分割
6. 実務で使える数理最適化の考え方とその実践
数理最適化の活用や生成 AI との連携にご興味がある方は，
是非ご参加ください！
（松岡 勇気）
******************************************************************
■ <トピック> 定式化技法集「スラック緩和」のご紹介
******************************************************************
今回は，定式化技法集の中から「スラック緩和」を紹介します．
数理最適化モデルを作成していると，
「制約条件をすべて入れたら実行不可能になってしまった」
「どの条件が厳しすぎるのか分からない」
という場面に出会うことがあります．
実務のモデルでは，納期，在庫，設備能力，人員数，作業時間など，
さまざまな条件を同時に満たす必要があります．一つ一つの条件は自然に
見えても，すべてを組み合わせると，解が存在しない場合があります．
このようなときに役立つ考え方の一つが，今回紹介するスラック緩和です．
なお，スラック緩和は弊社における呼称であり，一般に広く定着した用語
ではない事にご留意ください．
# そもそも定式化技法集とは
定式化技法集は，計算機での求解を念頭に置いた，実践的な数理最適化の
定式化，すなわちモデリングのための用語解説やテクニックをまとめた
ドキュメントです．
数理最適化では，現実の業務課題を，変数・制約条件・目的関数として
表現する必要があります．しかし，単に数式として書くだけでなく，
計算機で実際に解きやすい形にすることも重要です．
定式化技法集では，そのような実践的なモデリングのヒントが紹介
されています．
# スラック変数とは
スラック変数，あるいは余裕変数とは，不等式を等式に置き換えるために
導入する中間変数です．
たとえば，次のような不等式を考えます．
------------------------------------------------------------------
2x + 3 <= 7
------------------------------------------------------------------
この不等式は，非負変数 s を用いて，次のように書き換えることが
できます．
------------------------------------------------------------------
2x + 3 + s = 7
s >= 0
------------------------------------------------------------------
このときの s がスラック変数です．
この例では，s は左辺と右辺の「余裕」を表しています．つまり，制約に
対してどれだけ余裕があるかを，変数として明示的に表していると
見ることができます．
スラック変数は，線形最適化問題を標準形に直す際にも用いられる基本的な
考え方です．
# 「スラック緩和」では何を紹介しているか
「スラック緩和」の記事では，制約式に補助的な非負変数を導入する
ことで，その制約条件を緩和するテクニックが紹介されています．
たとえば，本来は
必要量を必ず満たす
という制約を書きたい場合でも，現実にはどうしても満たせないことが
あります．
このとき，制約を満たせなかった量を表す変数を追加しておくと，
どの条件をどの程度満たせなかったか
を確認できるようになります．
つまり，スラック変数は，単に数式変形のための変数ではなく，
モデルがなぜ実行不可能になるのかを調べるための手がかり
としても使うことができます．
# このテクニックが重要な理由
数理最適化モデルが実行不可能になったとき，単に「解がありません」と
言われるだけでは，何を直せばよいか分かりません．
たとえば，勤務計画で必要人数を満たせない場合，「どの日の，
どの時間帯で，何人足りないのか」が分かると，原因を調べやすく
なります．
生産計画で需要量を満たせない場合も，「どの製品が，どの程度不足
しているのか」が分かれば，設備能力，原材料，納期など，どこを
見直すべきか考えやすくなります．
このように，スラック変数を導入することで，実行不可能な状態を，
分析可能な情報として扱えるようになります．
# 実務での利用イメージ
私自身も，計画作成系のモデルで，必要量や上限制約を完全には満たせない
ケースを扱う際に，この考え方を用いることがあります．
たとえば，人員計画や生産計画のような問題では，業務上は「必ず
満たしたい」とされている条件であっても，入力データの状況に
よっては，すべてを同時に満たすことが難しい場合があります．
そのような場合に，スラック変数を導入しておくと，
どの制約が問題になっているのか
どの程度条件を緩和すれば解が得られるのか
を確認しやすくなります．
これは，モデルのデバッグだけでなく，関係者に対して「なぜ計画が
成立しないのか」を説明する際にも役立ちます．
# モデルを「解く」だけでなく「理解する」ために
数理最適化では，モデルを作ってソルバーに渡せば終わり，という
わけではありません．
実際には，得られた結果を確認し，制約条件や入力データを見直し
ながら，業務に合うモデルへ調整していくことが重要です．
その意味で，スラック変数は，モデルを解きやすくするためだけでなく，
モデルのどこに無理があるのかを理解するための技法
ともいえます．
大規模なモデルや，制約条件が多いモデルを扱っていて，
なぜ実行不可能になるのか分からない
どの条件を見直せばよいか分からない
と感じたときには，ぜひ「スラック緩和」の記事を参考にしてみてください．
このように，定式化技法集には，実務で数理最適化モデルを作成する際に
役立つ魅力的な記事が多数掲載されています．皆さんもぜひ，
モデル作成時のヒントとして活用してみてください．
# 参考リンク
- 定式化技法集
https://www.msi.co.jp/solution/nuopt/docs/techniques/index.html
- スラック緩和
https://www.msi.co.jp/solution/nuopt/docs/techniques/articles/slack.html
- スラック変数とソフト制約関数
https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/slacksoftconstraint.html
（加瀬 力）
******************************************************************
■ < tips > 使ってみよう PySIMPLE（第 43 回）
******************************************************************
このコーナーでは，Nuorium Optimizer の Python インターフェース
PySIMPLE のエッセンスを紹介していきます．
今回はスラック変数のソフト制約関数 SoftConstraint による書き換えに
ついて紹介します．第 6 回，第 14 回で登場したシフトスケジューリング
問題を元に，今回は一日分のシフトを決めるとしましょう．
------------------------------------------------------------------
m = Element(value='ABCDE') # Man
s = Element(value=['Day','Ngt','Off']) # Shift
work = Parameter(index=s, value={'Day': 8, 'Ngt': 6}) # 勤務時間
require = Parameter(index=s, value={'Day': 2, 'Ngt': 2}) # 必要人数
x = BinaryVariable(index=(m,s)) # 人 m にシフト s を割り当てるか
------------------------------------------------------------------
シフトごとに勤務時間と一日分の必要人数が与えられています．
ここで value で与えられていないシフト Off(=休み)はともに 0 である
ことに注意しましょう．
今回の目標は勤務時間の平準化制約を記述することです．平準化制約は
全員の勤務時間をできるだけ同じにしたい，という要望なので，厳密な
等式制約としては書けなそうです．必要人数を満たすことを前提とする
と，勤務時間の平均値を目指せばよさそうです．
------------------------------------------------------------------
workave = Sum(require[s]*work[s])/len(m.set) # 勤務時間平均値
------------------------------------------------------------------
記述方法の 1 つとしてスラック変数を用いた方法があります．スラック
変数は違反量(>0)を変数に押し付けますが，平準化制約の場合，正側にも
負側にも違反する可能性があるため，両辺にスラック変数が必要になります．
------------------------------------------------------------------
slack1 = Variable(index=m, lb=0) # 勤務時間平均値からの違反量(-)
slack2 = Variable(index=m, lb=0) # 勤務時間平均値からの違反量(+)
p = Problem()
p += Selection(x[m,s], s), '人 m のシフトは一つ'
p += Sum(x[m,s], m) >= require[s], 'シフト s の必要人数を満たす'
p += Sum(work[s]*x[m,s], s) + slack1[m] == workave + slack2[m], '勤務時間平準化'
p += Sum(slack1[m] + slack2[m]), 'slack'
p.solve(silent=True)
print(p.result.method, p.status, p.objective.val)
# simplex NuoptStatus.OPTIMAL slack.val=6.0000000000000036
------------------------------------------------------------------
スラック変数を目的関数に組み入れることで，勤務時間をできるだけ
平均値に近づけることができます．
スラック変数を用いた記述は基本となる考え方であり，多くのモデリング
言語でも同様の記述ができます．
第 14 回に登場したソフト制約関数 SoftConstraint を用いると，平準化
制約をスラック変数を用意することなく書き換えることができます．
------------------------------------------------------------------
p = Problem()
p += Selection(x[m,s], s), '人 m のシフトは一つ'
p += Sum(x[m,s], m) >= require[s], 'シフト s の必要人数を満たす'
p += Sum(work[s]*x[m,s], s) == workave, SoftConstraint(1), '勤務時間平準化'
p.options.method = Options.Method.WLS
p.solve(silent=True)
print(p.result.method, p.status, p.result.softPenalty)
# wls NuoptStatus.FEASIBLE 6.000000000000002
------------------------------------------------------------------
このような書き換えは一般に可能ですが，正側にも負側にも違反する等式
制約の書き換えとは相性がよいです．また，スラック変数を用いた記述では
目的関数に追加する必要があり，変数のスコープが大きくなる点も解消
されています．
ソフト制約は求解アルゴリズム MILP/WCSP/WLS のいずれでも使用可能ですが，
WCSP の場合，アルゴリズムの特性上，小数部分が切り捨てられ，結果が
変わることがあるのでご注意ください．
また，上記の制約のみでは勤務時間平準化を優先すべく，必要人数を超えた
出勤が発生してしまいます．こちらは別に回避する仕組みが必要でしょう．
いかがでしたでしょうか．
スラック変数を用いた記述は基本となる考え方ですが，制約式や目的関数に
混在することで煩雑になりがちです．ソフト制約関数を用いることで，制約と
違反量を分離した記述が可能になります．
マニュアル版はこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/slacksoftconstraint.html
第 6 回「pandas を用いた結果表の出力」の内容はこちら:
https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2001.html#6
第 14 回「メタヒューリスティクスアルゴリズムの使い方」の内容はこちら:
https://www.msi.co.jp/solution/nuopt/mailmagazine/backnumber2109.html#6
ソフト制約関数 SoftConstraint の使い方はこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/weightedconstraint.html#softconstraint
ソフト制約関数 SoftConstraint の API はこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/api/function.html#pysimple.constraint.SoftConstraint
（池田 悠）
==================================================================
