サブロウ丸

サブロウ丸

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

flopt 仕様 v0.5.5: Systemサイド -- 問題解析とソルバ選択

本稿ではfloptのSystemサイドである問題(Problem)の解析やソルバ選択について記載します。

問題解析とは?

本稿では問題解析をユーザーが定義した問題がどのタイプの最適化問題に属するのかを機械的に判断すること、とします。floptでは柔軟なモデリングにより様々な最適化問題の表現が可能ですが、この問題解析により下記のようなことが実現できます。

ユーザーが定義した問題を

  1. ユーザーが指定したソルバで求解可能かを判断する
  2. 求解可能なソルバを提示する
  3. 求解可能でかつ、その問題を解くのに適しているソルバを提示する
  4. 他の問題形式に変換する

最適化問題のタイプ分け

さてここでは、最適化問題をどのようにタイプ分けするのか?をまず見ていきます。

最適化問題

  1. 決定変数
  2. 目的関数
  3. 制約

の3つの要素からなります。すなわち、ある最適化問題のタイプは (決定変数、目的関数、制約) の3つ組で決まります。例えば線形計画(LP) であれば (連続変数, 線形, 線形) で、混合整数線形計画(MIP) であれば (連続変数+離散変数, 線形, 線形) と表せます。

例えば連続変数+離散変数(Number)は連続変数(Continuous)を含むより広いタイプであるように、それぞれの要素には包含関係があります。それを  \mathrm{Continuous} \leq \mathrm{Number} のように大小関係の記号で表現することにします。そして先ほどの3つ組についても、要素の包含関係から自然に導かれる包含関係を適用します。

 (V_1, O_1, C_1) \leq (V_2, O_2, C_2) \iff (V_1 \leq V_2) \land (O_1 \leq O_2) \land (C_1 \leq C_2)

例えば LP  \leq MIP であり、これはMIPはLPを含むより広いタイプの問題であるということを表しています。(すなわちある問題がLPであれば、その問題はMIPでもあるということですね)

上記の大小関係は実装上は例えばある  V (決定変数のタイプ)について  V_a \leq V \Longrightarrow V_a \in V{\rm .expand()}を満たすようにV.expand()を定義しており、  \{V_a\} \subset V {\rm .expand()} により大小関係を判定しています。具体的にはexpandは flopt/constants.py で定義されています。

さてさて、最適化問題ソースコードでは flopt/solvers/auto_search/selector.py で定義されてあり、一部を抜き出すと

# ---------------------------------------------
#   Optimization Class Definitions
# ---------------------------------------------

# MIP
mip = {
    "Variable": VariableType.Number,
    "Objective": ExpressionType.Linear,
    "Constraint": ExpressionType.Linear,
}

# ising
ising = {
    "Variable": VariableType.Binary,
    "Objective": ExpressionType.Quadratic,
    "Constraint": ExpressionType.Non,
}

# QP
qp = {
    "Variable": VariableType.Continuous,
    "Objective": ExpressionType.Quadratic,
    "Constraint": ExpressionType.Linear,
}

...

こんな感じでそれぞれの最適化問題が3つ組で定義されています。またユーザーが作成した問題も

prob = Problem()
...
prob.toProblemType()

(flopt/problem.pyを参照)

を実行することで、ユーザーが定義した問題を(決定変数、目的関数、制約)のタイプの3つ組Pに変換します。ここで先ほどの関係を用いて、ある最適化問題のタイプQに対し  P \leq Q であればユーザーが定義した問題がその最適化問題Qに属する、ということが分かります。これがfloptにおける問題解析のコアです。 いわば静的な情報である最適化問題のタイプとユーザーが定義する動的な情報であるProblemモデリングという要素を一つの3つ組の形式でどちらも表現できるというのが素晴らしくて、それにより判定もシンプルになっています。

さらに嬉しいことにソルバの求解可能な問題もこの3つ組で表現することができて、ユーザーが定義した問題Pがソルバが求解可能な問題クラスQに対し、 P \leq Q であればそのソルバは問題Pを解ける、、ということも分かります。

構成要素

floptの中では、最適化問題やソルバが求解可能な問題を正確に表現するために、決定変数のタイプや式のタイプについて次のような要素を用意しています。

決定変数

  • Continuous(連続変数)
  • Integer(整数変数)
  • Binary(バイナリ変数)
  • Spin(スピン変数)
  • Permutation(順列変数)

さらにこれらを要素とするNumberとAnyというタイプも用意しています。それぞれが包含する要素は以下の通りです。

Integer Number Any
Continuous
Integer
Binary
Spin
Permutation

Linear Quadratic Polynomial Any
Custom
Const
Linear
Quadratic
Polynomial
BlackBox

数式解析

数式解析とはユーザーが定義した式が線形なのか二次式的なのかを判定するものです。前回の記事 flopt 仕様 v0.5.5 Userサイド -- モデリング - サブロウ丸 で紹介したように、式は基本的は計算グラフの形で管理されます。この形は変数の値から具体的な式の値を計算したり、勾配を計算したり、というのは得意でできますが、式全体を見る必要がある数式的な理解は難しいのです。

そこでfloptでは式解析のためにPolynominal(多項式)クラスを用意しています。ここでは計算グラフから多項式を生成して、それをもとに式が線形であるか、などを判断します。 flopt/polynomial.py at main · nariaki3551/flopt · GitHub

アルゴリズム割り当て

さて、ユーザーが定義した問題がどのタイプの最適化問題に属するかが上記の処理により分かるようになりました。これによりユーザ定義の問題をどのソルバで解けるのかが分かるようになります。次は求解可能なソルバが複数ある場合にどのソルバが適しているかが分かれば最高です。

今回は、問題のクラス、問題の特徴量、および求解条件を与えると、何か一つのソルバを返すようなモデル を用いてソルバ選択を行なっています。問題のクラスごとにそのようなモデルを学習させ、モデルの入力は、問題の特徴量として変数の個数、求解条件として時間制限の2つを用いました。ここはもっとこだわれるポイントで、例えば変数同士の関係性なども特徴量として考えられます。

学習用の訓練データは問題のクラスごとに、変数の個数を[2, 1000]から、求解時間を[2, 120]秒からランダムに選択して問題を生成し、その問題を全てのソルバで求解します。そして得られた解の目的関数値が最良値よりも1e-5位内のソルバを正解ソルバとしました。要するに一つの問題に対して正解ソルバが複数あるということですね。これで問題と求解条件の特徴量と正解ソルバが紐づけられた訓練データが得られるので、あとはそれを用いて学習するだけです。7:3 で訓練データと検証データに分け、scikit-learnの学習apiを用いて学習を行い、最も検証データによる正解精度が良いモデルを採用しています。

下記では訓練後の結果のみを紹介します。

nonlinear

連続変数のみからなる制約なし非線形問題用に学習したモデルの結果です。

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

nonlinear with mixed integer variable

整数制約を含む制約なし非線形問題用に学習したモデルの結果です。

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

ising

ising問題用に学習したモデルです。訓練データはポートフォリオ最適化の形式のものを用いています。

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

ご覧の通り、マダラ模様になっていますね。良い特徴量空間であれば正解ソルバ領域も滑らかになっているはず。。。ということはまだ良い特徴量空間があるのではないか?ということが示唆されます。