nAG最適化コーナー: クリスマス・エディション : キャンディーはどこに隠す？

この記事はnAG最適化コーナー シリーズの一部です。

メリークリスマス！ nAG最適化コーナーシリーズのクリスマス・スペシャル・エディションへようこそ。

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

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

さてここで、モデルが仮に上手くできたとしても、クリスマスツリーとプレゼントで構成される複雑な領域を考慮し、最適化を行う必要があります。 $$\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*}$$ これにより、以下の領域が定義されます。

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

ツリーの中央部分も以下のようにほぼ似たような問題として表現できます。 $$\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*}$$ しかしながら、このままではそれぞれのモデルで領域の一部分のみにフォーカスし、他の部分を無視しなければなりません。これは明らかに私たちの問題に対する良い解決策ではありません！

２つの領域の結合

追加の決定変数を導入することによってツリーの中央と上部の両方を同じモデルに結合可能です。 $\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$となり、常に満たされる状況となり影響を及ぼさなくなります。

それぞれの小領域が３つ不等式により定義されるので、この手法を全ての制約に適用して２つの決定変数$\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$を選択して全ての制約を無視する可能性があります。

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

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

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

最後の仕上げ

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

更に、この方法で完全に分離された領域を作成することも可能です。 例として、クリスマスツリーの下にプレゼントを配置して見ましょう！ するとモデルは以下のようになります: $$\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 で解いてみると…

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

覚えておくと役立つ事

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

このクリスマス／年末年始シーズンが皆様にとって素晴らしいものとなりますように！　来年の１月に予定されている次の nAG最適化コーナーの記事でまたお目にかかることを楽しみにしております。