4. 求解状態#
4.1. 導入#
最適化計算ではいつでも 最適解 が得られるというわけではなく, また得られなかったとしても単純なエラーというわけでもない.
最適化計算を呼び出す上位側が,求解結果として どのようなことを想定する必要があるかを予め整理しておいて, システムの構築を試みる必要がある.
4.2. 求解状態の種類#
求解によって遷移する状態 (求解状態) には次がある.
最適解 (optimal)
制約条件を満たし,そして最適性が保証されている.但し 最適解 の一意性までは述べていない.
実行可能解 (feasible)
制約条件は満たしているが最適性は保証されていない.許容解とよばれることもある.
緩和解 (relaxed)
整数性の制約条件を満たせなかった.もしくは所与の計算資源では 実行可能解 を探し出せなかった.
実行不可能 問題 (infeasible)
互いに矛盾するモデルもしくはデータが与えられた.
正常中断 (normal)
与えられた計算資源で可能な限り制約充足を行った状態を意味する.
強制的な中断
ユーザによる中断・内部エラーなど
求解状態はこれらの何れかとなる. モデルが仮に固定でも,どのようなデータが入ってくるかは一般にはわからないので, これらについて予め対処できるようにシステムを設計する必要がある.
重要
求解状態の分類はまた同時に最適化計算の利点を暗に伝えている. 数理最適化モデルとして定式化ができれば,少なくとも計算部分のエラーの大部分は予期されるものであり, 加えて 実行不可能 問題の場合であっても,何れかの制約条件式に違反するものとして原因究明対象が明示的に絞られる. これらはシステムの長期的保守に貢献する特徴である.
何故ならば,数十年単位の長期的保守では保守要員が開発時点と比較して変更される可能性が十分にあり, 懸命な努力にもかかわらず,システムの理解や再現環境などがブラックボックス化することはソフトウェア開発では一般に珍しくない. しかし数理最適化モデルとしてシステム開発した場合には,「変数」「制約条件」「目的関数」を通して, 数式として曖昧さなく記述され,その時代ごとのプログラミング言語に依存した知識は可能な限り排除できる. また先に述べたように,問題発生時でも制約条件式間の関係を論理的に解消することで究明できることが多くなる.
これらによりシステムの内部仕様を紐解く負担は,普遍的な数理的素養にのみ依存する部分が多くなって, 保守要員の学習コストを下げることができる.
注釈
最適化計算では目的関数値の最適化ではなく,制約条件式の違反量およびペナルティ値 1ペナルティ値とは重み付きの制約違反量のことである. の最小化を意図した計算をする場合がある. この場合には求解状態は計算資源をすべて使い果たした正常中断 (normal) かエラーの何れかとなる. そして正常中断はあくまですべての計算資源を使い果たしたことを意味するため, 違反量およびペナルティ値がすべて \(0\) となったこととは同値ではない.
4.3. 計算資源について#
計算資源とは具体的には以下に挙げるものであり,計算をするのに必要な資源のことをいう.
計算時間上限
消費メモリ上限
反復回数上限
上下界ギャップ
...
デフォルトで何かしら計算資源が設定されていない限り, 最適化計算では計算させているハードウェアの物理的な計算資源をすべて使用して 最適解 が得られるまで計算する.
最適化計算を行うデータセットに対して,最適解 まで到達するのに必要な計算時間を予め予測することは一般に難しい. 典型的なテストデータセットを準備して,実行時間を計測して大まかな傾向を掴むことはできるので, この傾向と要求される計算資源を天秤にかけて,計算を実行することが理想的である.
所定の計算資源では対応が難しいデータ規模の場合は,モデルの改良や ハードウェア要件 の刷新などを検討するか, 運用面で問題を分割するなど,状況に応じて問題解決方法を模索することになる. その場合でも「変数」「制約条件」「目的関数」のどこで計算資源をよく消費しているかを検討することができ, 問題解決の手がかりとすることができる.
関連
用語集
引用書式