関連情報

NAG Optimization Corner: クリスマス・エディション
キャンディーはどこに隠す?

[2017年12月掲載ブログ記事翻訳] 
Benjamin Marteau, 数理最適化チーム, Numerical Algorithms Group Ltd (NAG) 

この記事は NAG Optimization Corner シリーズの一部です。

メリークリスマス! NAG Optimization Cornerシリーズのクリスマス・スペシャル・エディションへようこそ。

クリスマスにちなんで、重大な問題を解決する方法をご紹介します。 今回は「サンタのキャンディーを隠すのに最も良い場所を見つける!」という問題を取り上げます。

Optimized Christmas tree with a present

ここでは家族や、友人、そして同僚、及びクリスマスエルフに関する広範な調査を行ったとしましょう。そしてそこから奇跡的にキャンディーの誘引性に関して全員を満足させる非線形モデルを作る事ができたとします。

さてここで、モデルが仮に上手くできたとしても、クリスマスツリーとプレゼントで構成される複雑な領域を考慮し、最適化を行う必要があります。 \begin{equation*} \min_{(x,y)\in クリスマスツリー \ \cup\ プレゼント} F(x,y) \end{equation*} 以下にこのような実行可能領域をモデル化する一つの方法を示したいと思います。

クリスマスツリーを作ろう!

上部から始める

クリスマスツリーの上部分のみに限定すると、この問題はかなり簡単シンプルで、以下の線形制約を受ける非線形最小化問題として表現できます。 \begin{equation*} \min_{(x,y)\in \mathbb{R}^n} F(x,y)\\ \text{s.t. } \left\{ \begin{aligned} x + y &\leq 6\\ -x + y &\leq 6\\ y &\geq 5\\ \end{aligned}\right. \end{equation*} これにより、以下の領域が定義されます。
Top of the tree

そしてこの問題は非線形最適化ソルバーで簡単に解くことができます。 私達はNAGライブラリのソルバルーチン e04wdc を利用しました。 (その際に、開始点はツリーの最上部としました)

Top of the tree

ツリーの中央部分も以下のようにほぼ似たような問題として表現できます。 \begin{equation*} \min_{(x,y)\in \mathbb{R}^n} F(x,y)\\ \text{s.t. } \left\{ \begin{aligned} x + y &\leq 5.5\\ -x + y &\leq 5.5\\ y &\geq 4\\ \end{aligned}\right. \end{equation*} しかしながら、このままではそれぞれのモデルで領域の一部分のみにフォーカスし、他の部分を無視しなければなりません。これは明らかに私たちの問題に対する良い解決策ではありません!

2つの領域の結合

追加の決定変数を導入することによってツリーの中央と上部の両方を同じモデルに結合可能です。 $\delta_K=1 \Rightarrow (x,y) \in K$となるようにそれぞれの小領域$K$にバイナリ変数$\delta_K$を導入します。 一般的にに$ax+by \leq c$の形式の制約においてこのような決定変数$\delta$は、元の不等式を $$ax+by+M\delta \leq M + c$$ (ここで$M$は$ax+by-c$の数量の上限)
に置き換えることによって作成することが可能です。これにより、$\delta=1$の場合は元の不等式が適用され、 $\delta=0$の場合は不等式は$ax+by-c \leq M$となり、常に満たされる状況となり影響を及ぼさなくなります。

それぞれの小領域が3つ不等式により定義されるので、この手法を全ての制約に適用して2つの決定変数$\delta_{top}$と$\delta_{mid} \in \{0,1\}$を導入すると、モデルを以下のように書き換える事ができます: \begin{equation*} \min_{(x,y)\in \mathbb{R}^n} F(x,y)\\ \text{s.t. } \left\{ \begin{aligned} x + y + \delta_{top}M &\leq M + 6\\ -x + y + \delta_{top}M &\leq M + 6\\ y - \delta_{top}M &\geq -M + 5\\ x + y + \delta_{mid}M &\leq M + 5.5\\ -x + y + \delta_{mid}M &\leq M + 5.5\\ y - \delta_{mid}M &\geq -M + 4\\ \end{aligned}\right. \end{equation*} 話しを簡単にするために$M=9$を全ての不等式の境界とします。

ここまでの状態ではまだモデルは未完成で、ソルバが$\delta_{mid}=\delta_{top}=0$を選択して全ての制約を無視する可能性があります。

そこで以下の結合制約を追加して最低1つの制約条件を満たすようにします。$$ \delta_{mid}+\delta_{top} \geq 1 $$

その結果、モデルにバイナリ変数が含まれる事になるため、従来のNLPソルバはもはや適切ではありません。そこで私達はNAGが提供するMINLPソルバh02zkcを利用しました。

Two parts of the tree

ご覧のように、ソルバは両方の小領域を探索し、最小値に収束します。 このソルバは局所ソルバであり、開始点によって、領域内の局所最適解に到達する事に注意してください。

最後の仕上げ

上記の技術は一般化して任意の数の領域を表現することができます。例えばツリー全体のモデルは以下の図が表す二つの(ツリー下部と土台)追加バイナリ変数の導入により実現できます。
Two parts of the tree

更に、この方法で完全に分離された領域を作成することも可能です。 例として、クリスマスツリーの下にプレゼントを配置して見ましょう! するとモデルは以下のようになります: \begin{equation*} \min_{(x,y)\in \mathbb{R}^n} F(x,y)\\ \text{s.t. } \left\{ \begin{aligned} \left. \delta_{top} + \delta_{mid} + \delta_{bot} + \delta_{tr} + \delta_{pr} \geq 1 \right\}\text{binding constraint}\\ \left.\begin{aligned} x + y + \delta_{top}M &\leq M + 6\\ -x + y + \delta_{top}M &\leq M + 6\\ y - \delta_{top}M &\geq -M + 5\\ \end{aligned}\right\}\text{top of the tree}\\ \left.\begin{aligned} x + y + \delta_{mid}M &\leq M + 5.5\\ -x + y + \delta_{mid}M &\leq M + 5.5\\ y - \delta_{mid}M &\geq -M + 4\\ \end{aligned}\right\}\text{middle of the tree}\\ \left.\begin{aligned} x + y + \delta_{bot}M &\leq M + 5\\ -x + y + \delta_{bot}M &\leq M + 5\\ y - \delta_{bot}M &\geq -M + 2.5\\ \end{aligned}\right\}\text{bottom of the tree}\\ \left.\begin{aligned} x - \delta_{tr}M &\geq -M - 0.75\\ x + \delta_{tr}M &\leq M + 0.75\\ y - \delta_{tr}M &\geq -M + 2\\ y + \delta_{tr}M &\leq M + 2.5\\ \end{aligned}\right\}\text{trunk}\\ \left.\begin{aligned} x - \delta_{pr}M &\geq -M - 1\\ x + \delta_{pr}M &\leq M - 0.25\\ y - \delta_{pr}M &\geq -M + 1.8\\ y + \delta_{pr}M &\leq M + 1.3\\ \end{aligned}\right\}\text{present}\\ \end{aligned}\right. \end{equation*}

このモデルをNAGライブラリ関数 h02dac で解いてみると…

その結果キャンディーの隠し場所として最も適しているのはプレゼントの中であるという事が分かりました!
Optimized Christmas tree with a present

覚えておくと役立つ事

非常に簡単な例を説明しましたが、バイナリ変数の導入により、どのようなモデルを表現可能であるかが示されています。 特に不連続な一連の制約は、実際の応用問題ではかなり頻繁に現れるものです。注意する点としては、整数変数を増やすと、その分モデルの複雑さが大きく増加するので、乱用しないようにする事です。

このクリスマス/年末年始シーズンが皆様にとって素晴らしいものとなりますように! 来年の1月に予定されている次の NAG Optimization Cornerの記事でまたお目にかかることを楽しみにしております。

 


本記事は以下の原文(英語)を翻訳したものです。
https://www.nag.co.uk/content/optcorner-christmas-edition

さらに詳しくお知りになりたい場合はお気軽に お問い合わせ 下さい。

Results matter. Trust NAG.

Privacy Policy | Trademarks