-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン
https://www.msi.co.jp/solution/nuopt/top.html
2023 Vol.3 ( 2023 年 5 月 29 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理最適化パッケージ
Nuorium Optimizer をはじめとして，最適化に関する様々な情報や
ご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ < コラム > パズルを数理最適化で解く話 第 1 話
■ <セミナー> オンラインセミナーのご案内
■ < tips > 使ってみよう PySIMPLE（第 24 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ < コラム > パズルを数理最適化で解く話 第 1 話
******************************************************************
週刊誌のなかには毎号パズルが掲載されているものがあり，そういった
雑誌を購読していると，職業柄ついつい「このパズルは線形計画問題の
範囲で記述できるのではないか」などと考えてしまいます．
とはいえ，数理最適化（特に線形計画問題）の枠組みで記述できる
パズル問題はそう多くなく，記述できたとしてもデータの準備が大変
だったり求解が困難だったり……．このあたり実務問題と変わらない気が
するのです．
そんなわけで，パズルを数理最適化で定式化しようという試みは意外と
実務向けではないかという思いつきのもと，本コラムが始まりました．
記念すべき第 1 話は「クロスワードパズルを線形計画問題で定式化
できるか？」．
なお第 2 話があるかは未定です．
まず始めにクロスワードパズルについておさらい．碁盤目状の区画の空欄に，
ヒントから推測できる単語の文字でマス埋めていくパズルゲームですね．
ヒントを「ヨコのカギ」や「タテのカギ」などと表現します．
個人的に「ヤ」や「ツ」が「ャ」や「ッ」になったりするのが日本語
クロスワードパズルの面白いところと思っています．
早速ですが私が考えた末たどり着いた結論はこちら．
「記述できなくはないが解く必要がない」
それでは定式化の話をしますが，私個人としては「線形計画問題の定式化」
という言葉は，「変数をどう定義するか」とほとんど同意と考えています．
変数の定義によって，考慮すべき制約条件や目的関数が容易に記述できるか，
記述するために新たな変数が必要か，それとも記述することができないか，
が自ずと定まるからです．
さて，クロスワードパズルの定式化では，変数の定義方法として，
以下の 2 通りの案が浮かびます．
1. パズルの上から i 番目，左から j 番目の空欄に，文字 k が入る場合
1 をとる 0 - 1 変数 x[i,j,k] を用いる
2. m:{タテ,ヨコ} のカギ n に対して，推定した単語の集合 {w1, w2, .. }
のうち w が当てはまる場合 1 をとる 0 - 1 変数 x[m,n,w] を用いる
案 1 は割当問題を基とする定義，案 2 はパターン選択を基とする定義です．
案 2 の定義に「ちょっと待った」と言いたい気持ちをぐっとこらえて案 1 の
定義を考えてみます．
現代仮名遣いの日本語クロスワードパズルで使用する文字は，「あいうえお…」
（「を」も含めておきます）に濁音・半濁音をあわせた 70 文字あります．
すなわち，案 1 の変数 x[i,j,k] の k は 70 通りの値をとり，2 文字の
組合せは単純計算で 4900 通りあります．数えたことはないけれど 2 文字の
単語が 4900 個もあるはずがないので，この時点で案 1 は廃案にすべき
ですが，折角なので制約条件も考えてみましょう．
制約条件を言葉にすると，以下の内容でしょうか．
制約条件: タテ・ヨコのカギに対応する文字の並びが，タテ・ヨコのカギから
推定される単語の 1 つであること．
うーん，これは絶対に四則演算では表現できない．やはり案 1 は廃案ですね．
それでは案 2 の定義を考えてみましょう．
先ほどぐっと飲みこんだ「ちょっと待った」，おそらくは「タテ・ヨコのカギに
対して推定した単語の集合とあるが，それをどう用意するのか？」といった
疑問かと思いますが，線形計画問題の現場では時に非常に都合よい仮定のもと
定式化を進めることがあり，案 2 についても，単語の集合を用意する方法に
ついては後回しにして，制約条件が記述できるか考えてみます．
制約条件を言葉にすると，以下の内容でしょうか．
制約条件: タテのカギに対応する単語とヨコのカギに対応する単語が交わる
マスは同じ文字であること．
例えば，タテのカギ 1 の単語 w1 の 2 文字目と，ヨコのカギ 2 の
単語 w2 の 1 文字目が同じマスである場合，Nuorium Optimizer 的には
sum(w1 の 2 文字目 * x[タテ,1,w1], w1) == sum(w2 の 1 文字目 * x[ヨコ,2,w2], w2)
といった制約式として記述できます．というわけで案 2 による定式化は
可能と言えます．
それでは，後回しにした「タテ・ヨコのカギに対し推定した単語の集合」を
用意する方法について．いろいろ方法は浮かびますが，個人的には頑張って
推定することをお薦めします．正しい単語を推定できるかどうかが
クロスワードパズルの悩みどころであり醍醐味でもあります．
線形計画法で求解できる程度の単語が推定できていれば，それはもうパズルを
解いたも同然でしょう．
ところで，人がクロスワードパズルを解くとき，途中で確定した文字も
単語の推定に用いるため，タテ・ヨコのカギと文字数から推定するよりも
ずっと効率よく推定しています．
実務の場面でも，計算前に必要なデータを全て用意する必要がある
線形計画問題を適用することが，現場の人が逐次的に計画を立てていくよりも
非効率な側面があります．その非効率さが計算結果に悪影響を及ぼすような
場合，多段階に求解する仕組みや専用解法を実装することで，よりよい
結果が得られることを狙います．
実務的なまとめ．
- ある問題を，細かい粒度の割当問題として考えたとき「探索領域に
無駄が大きくなる」「制約式の記述が困難である」といった場合に，
そういった問題が解決された状態から考えると，線形計画問題で
記述・求解できることがあります．
- 1 回の計算で良い結果が得られない場合，熟練者の考え方を参考に，
多段的に解く仕組みや専用解法を構築することがあります．
（中野 雄介）
******************************************************************
■ <セミナー> オンラインセミナーのご案内
******************************************************************
8 月までに開催する無料のオンラインセミナーをご紹介します．
6 月には製造現場の業務改善に向けた数理最適化ソリューションセミナーを
開催します．
本セミナーでは，生産スケジューリングの業務効率化・自動化に向けた
数理最適化ソリューションのご紹介を行います．
7 月には エネルギーマネジメント最適化セミナーを開催します.
数理最適化を用いたエネルギーマネジメントの事例紹介や，
簡単な地域熱供給問題に関して数理最適化を適用したデモを行います．
上記，製造セミナーとエネマネセミナーは次回開催未定ですので，
この機会に是非お申込みください．
また，定例の紹介セミナーとハンズオンセミナーも開催予定です．
ハンズオンセミナーは実際に製品を動かしながら受講いただける
セミナーになっています．こちらもぜひお気軽にご参加ください．
[ 製造現場の業務改善に向けた数理最適化ソリューションセミナー ]
2023 年 06 月 27 日 (火) 13:30～15:30
詳細とお申込み：
https://www.msiism.jp/event/nuopt-manufacturing-scheduling.html
[ エネルギーマネジメント最適化セミナー ]
2023 年 07 月 13 日 (木) 13:30～15:30
詳細とお申込み：
https://www.msiism.jp/event/nuopt-energy-management.html
[ Nuorium Optimizer 紹介セミナー ]
2023 年 06 月 16 日 (金) 13:30～15:30
2023 年 07 月 12 日 (水) 13:30～15:30
2023 年 08 月 30 日 (水) 13:30～15:30
詳細とお申込み：
https://www.msiism.jp/event/nuopt-introduction.html
[ Nuorium Optimizer ハンズオンセミナー ]
2023 年 08 月 04 日 (金) 13:30～16:00
詳細とお申込み：
https://www.msiism.jp/event/nuopt-hands-on.html
（保科 拓紀）
******************************************************************
■ < tips > 使ってみよう PySIMPLE（第 24 回）
******************************************************************
このコーナーでは，Nuorium Optimizer の Python インターフェースである
PySIMPLE のエッセンスを紹介していきます．
今回は実行の度に異なる解を求解させるテクニックを紹介します．
簡単のため，0-1 整数変数 z[1], z[2], z[3] のみを用いた整数計画問題を
考えます．
------------------------------------------------------------------
i = Element(value=[1, 2, 3])
z = BinaryVariable(index=i)
p = Problem()
p += z を用いた制約
p.solve() # 求解
p += ？ # z[1]=z[1].val, .., z[3]=z[3].val を除く
p.solve() # 再求解
p += ？ # z[1]=z[1].val, .., z[3]=z[3].val を除く
p.solve() # 再求解
：
------------------------------------------------------------------
まずは簡単な例から考えてみましょう．例えば，z[1]=1, z[2]=1, z[3]=1
の解のみを除くにはどうすればよいでしょうか．
これは z[1] + z[2] + z[3] が z[1]=1, z[2]=1, z[3]=1 のときに最大値
3 をとることを利用すると「z[1] + z[2] + z[3] <= 2」と記述すればよい
ことに気づくでしょう．
この気づきを応用すると，z の値が 1 以外でも記述することができます．
例えば，z[1]=1, z[2]=0, z[3]=1 を除きたい場合は，z[2] を反転する
ことで，「z[1] + (1-z[2]) + z[3] <= 2」と記述することができます．
一般に z[1]=z[1].val, .. を除きたい場合には次のように記述することが
できます．
------------------------------------------------------------------
Sum(z[i].val*z[i]) + Sum((1-z[i].val)*(1-z[i])) <= len(i.set)-1
------------------------------------------------------------------
また，整理して次のように記述することもできます．
------------------------------------------------------------------
Sum((2*z[i].val-1)*z[i]) <= Sum(z[i].val)-1
------------------------------------------------------------------
したがって，実行の度に異なる解を求解するには次のように記述することが
できます．
------------------------------------------------------------------
while p.status == NuoptStatus.OPTIMAL:
p += Sum((2*z[i].val-1)*z[i]) <= Sum(z[i].val)-1
p.solve() # 再求解
------------------------------------------------------------------
しかし，これを実行すると以下のようなエラーとなってしまいます．
------------------------------------------------------------------
pysimple.error.SimpleError: override constraint '...'
------------------------------------------------------------------
原因が少し分かり辛いですが，これは PySIMPLE 特有の事情が関連して
います．
- Problem には同じ名前の制約式を追加することはできない
- 制約式に明示的に名前を付けない場合は自動で命名される
後者において制約式名はその構造から命名されるため，while 文中で同じ
制約式と認識されてしまっており，これがエラーの原因です．
制約式名の重複を回避するには毎回異なった制約式名をつける必要があり
ます．今回は制約式の数が毎回増加することに着目して，制約式数を利用
してみましょう．
------------------------------------------------------------------
while p.status == NuoptStatus.OPTIMAL:
p += Sum((2*z[i].val-1)*z[i]) <= Sum(z[i].val)-1, str(len(p.constraints))
print(p[-1]) # 意図した制約式になっているか確認
p.solve() # 再求解
#print(z.val) # 毎回異なる解になっているか確認
------------------------------------------------------------------
これで実行の度に異なる解を出力することができます．制約式の出力を
確認してみましょう．
------------------------------------------------------------------
0:
z[1]+z[2]+z[3]>=1
1:
z[1]-z[2]-z[3]>=-1
2:
z[1]+z[2]-z[3]>=0
3:
-z[1]-z[2]-z[3]>=-2
4:
z[1]-z[2]+z[3]>=0
5:
-z[1]-z[2]+z[3]>=-1
6:
-z[1]+z[2]+z[3]>=0
7:
-z[1]+z[2]-z[3]>=-1
------------------------------------------------------------------
冒頭の「z を用いた制約」に制約式を追加すれば，制約を満たしたうえで
実行の度に異なる解を出力することができます．
いかがでしたでしょうか．
PySIMPLE では Python の文法と組み合わせることにより，ちょっとした
仕組みを簡単に実装することができます．
PySIMPLE のマニュアルはこちら:
https://www.msi.co.jp/solution/nuopt/docs/pysimple/index.html
（池田 悠）
==================================================================
