サブロウ丸

Sabrou-mal サブロウ丸

主にプログラミングと数学

flopt 仕様 v0.5.5: 全体構成

これから数回にわたってfloptという私が開発している最適化モデリングツールの構成について紹介したいと思います。具体的な使い方というよりは、その仕様について記録を残すのがメインです。

具体的な使用方法やチュートリアルはこちら。

本稿ではfloptの構成の概要について紹介します。

構成

floptの内部構成はUserSystemSolverの3つのパートに大きく分かれています。

https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20221113/20221113105922.png

floptは最適化問題モデリングツールの側面に加えて、"アルゴリズムやソルバ開発を容易にする" という目標を持っています。モデリングツールを改良したいユーザーはUserの機能のみを見れば良く、ソルバ開発者はSolverの機能のみを見れば良い、ということができるように設計しています。

このそれぞれは独立した記事にまとめているので、上のリンクから参照ください。

この3つの関係性について、実際に問題求解の処理フローをもとに詳しく見ていきましょう。

問題のモデリング → 問題を解く

https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20221002/20221002115235.png

ここでは問題のモデリングから、それを求解するまでの流れを紹介します。まずユーザーはfloptのVariable(変数)とExpression(式)クラスを用いて決定変数や目的変数、制約を表現します。そして、その目的関数や制約をProblemオブジェクトに追加します。

その後、ユーザーの求解指示をトリガーとして、生成された問題(Problem)はSystem部分に渡されます。ユーザーがソルバとしてauto searchを選択していた場合は、Selectorが問題の性質や時間制限などの条件から適切なソルバの選択を行います。

そしてSystemは問題をより一般的な情報に変換してソルバに渡します。具体的にはSolutionという変数ベクトルと目的関数、制約の組です。Solverはそれをもとにより良い解の発見作業を行います。

求解 → ユーザーへ解を提供

https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20221002/20221002114415.png

Solverは求解中に発見した解のregisterを行い、Problemにその情報とログを格納します。ソルバの実行は、基本的にはユーザーが与えた時間制限や試行回数、もしくはソルバ自体の終了条件に従って終了します。 その後、最も良い目的関数値を持つ解をもとに、ユーザーが定義したVariableオブジェクトに変数の値が格納されます。ユーザーはその値を参照することで、最良解を確認したり、事後処理を行うことができるという流れです。もし解が気に入らなければ続きから最適化計算を再開することもできますし、他のアルゴリズムを実行する、ということも可能です。

設計について

重要なのは、Solverの挙動に興味がないユーザーから見れば、ユーザーが問題を定義さえすれば、自身が作成したVariableに良さげな値が魔法のように格納されて返ってくることです。これは人々が最適化モジュールを使用するハードルを激的に下げるはずです。本来であればユーザーは解きたい問題の形式に合わせてソルバやモデリングツールを選択する必要がありますが、それにはまず最適化の知識が必要不可欠ですし、制約の追加や定式化の見直しなどで頻繁に問題のタイプが変わる状況もあるでしょう。floptではそれらに惑わされることなく一貫的に使用できるモデリングツールとして開発しています。

またアルゴリズム開発者にとっては、決定変数、目的関数、制約+アルファの情報が分かっていれば良いので、それのみにアクセスできるようにしています。これはコードの煩雑化を防ぎ可読性を上げるために必要です。また雑務的な機能をSolverのsuper class (BaseSolver)に集約させてコードをクリーンに保てるようにすることで、より良いアルゴリズムの開発の場を提供することを目指します。

まとめ

ここではflopt設計の根幹である3つのパート(User, System, Solver)について求解時の流れをもとにそれぞれの役割を紹介しました。

関連記事

inarizuuuushi.hatenablog.com