サブロウ丸

Sabrou-mal サブロウ丸

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

flopt 仕様 v0.5.5: Userサイド -- モデリング

本稿ではfloptにおける柔軟で強力なモデリングを支える基盤である変数と式の設計を紹介します。

変数 (Variable)

floptでは1つの変数を1つのオブジェクトで表現します。配列型や行列型の変数VariableArrayもありますが、1つ1つの要素は変数オブジェクトです。変数オブジェクトは(名前、型、下限と上限、値)の情報を持ち、最適化ソルバによる得られた解(Solution)は、変数オブジェクに解の値を設定することでユーザーに還元されます。

変数の生成は下記のAPIで行われ、これらはPuLPモデリングツールのインターフェイスを参考にしています。

Variable(...)  # 一つの変数の生成<br>
Variable.array(...), Variable.matrix(...), Variable.dict(...)  # 複数の変数の生成

floptでは式の簡約化や変数のバイナリ化、など式自体の変形に着目した機能も持つため、問題とは切り離して管理しています。例えばGurobiのインターフェイスでは、まず問題クラスのオブジェクトを作成してから、その問題から変数を作成する仕様(problem. addVar()) ですが、そうはしていないということですね。

式 (Expression)

floptにおける式とは変数同士の四則演算+alphaの繋がりを表現するものです。例えば変数a、b、cに対してa+b+23*a**b+cなどは式です。この式クラスに必要な要件として次を設けます。

  1. 計算性: 変数a、b、cに何か具体的な値を設定したときに3*a**b+cという式の具体的な値を算出する
  2. 解析: a+b+cが一次式で、a**2+b+cがaに対して2次式で、、というように式がどのなタイプなのかを判断する

Expression

floptでの最も基本的な式表現方法で二項演算による実装です。Expressionは(elmA, operator, elmB)の三つ組を持ちます。そして、この二項演算をつなぎ合わせることで複雑な式を表現できます。例えば3*a**b+cを可視化すると下記の計算グラフになります。

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

二項演算の要素がさらに二項演算の結果になっているという再帰的構造を持ちます。この式の値を求める場合は

def value():
    return elmA.value() operator elmB.value()

により変数に設定されている値を用いて再帰的に行われます*1。さて式の値の算出における課題は、演算ごとに計算の優先度があるということです。例えば同じスコープにある積の演算は和の演算よりも先に計算しなければなりません。...といってもこれは結構簡単に解決できて、Pythonに元々実装されている計算順序の機能をそのまま使います。3*a**b+cを計算するときはPython側でa ** bがまず計算されてそれに対応する式オブジェクトが作られます。その次は3*(a**b)に対応する式オブジェクトが作られて、という流れでうまい具合に計算グラフを作成することができます。あとはVariableやExpressionクラスの演算子をオーバーライドしまくれば良いというわけですね。その一部を下記の表に記載しています。

要素 演算 要素 出力クラス
Variable + Variable Expression
Variable + int, float Expression
Variable * Variable Expression
Variable * Expression Expression
Expression + int, float Expression
Expression + Expression Expression
... ... ... ...

例えばExpressionの__add__演算子は下記のように定義されています。中身では式の文字列表現をいい感じにするために、色々簡約化の工夫をしていますね。

    def __add__(self, other):
        if isinstance(other, number_classes):
            if other == 0:
                return self
            return Expression(self, Const(other), "+")
        elif isinstance(other, ExpressionElement):
            if other.isNeg():
                # self + (-other) --> self - other
                return Expression(self, other.elmB, "-")
            else:
                return Expression(self, other, "+")
        return NotImplemented

式の文字列表現とその恩恵

floptでは式の文字列表現は頑張って実現させています。下記のように"x"という名前の変数を用いて式を作成すると、式を表現する文字列もそれに応じて算出されるようにしています。

import flopt
x = flopt.Variable("x")
exp = (x - 1) ** 4 + (x - 2) ** 3 + (x - 3) ** 2
exp.name
>>> '(x-1)^4+(x-2)^3+(x-3)^2'

これは、見栄えが良いのと、ユーザーが式の確認をできるという利点に加えて、次のようなSympyを用いた簡約化(simplifize)と展開(expand)に使用できます。

exp.expand()
>>> x^4-(3*(x^3))+x^2+2*x+2
exp.simplify()
>>> (x-3)^2+(x-2)^3+(x-1)^4

どうです?なかなか良いでしょう?中身は数式処理ライブラリであるSympyのAPIを用いています。式を文字列で与えると、それに対して簡約や展開を行ってくれるAPIを用いています。流れとしては、flopt定義の式を文字列化→Sympyで文字列のまま簡約→文字列からfloptの式への戻し。を行っています。この文字列からflopt式への戻しは組み込み関数のevalを用いて行っています。この関数では文字列を評価するときに引数で渡した文字列と変数のマッチングを表す辞書を渡すとそれに従って文字列評価を行ってくれるので、ここにfloptの変数を渡している。。ということですね。

    def simplify(self):
        """
        Returns
        -------
        Expression
        """
        import sympy

        _locals = {var.name: var for var in self.getVariables()}

        expr = eval(
            str(sympy.sympify(self.getName()).simplify()),
            _locals,
        )
        if isinstance(expr, number_classes):
            expr = Const(expr)
        return expr

単項式と多項式クラス

また、内部では式の解析のために単項式と多項式クラスを用いた式表現をできるようにしています。微分を行える最低限の機能を持つクラスで、これによるユーザー定義の式が一次式なのか二次式なのか、それ以上の次数を持つ多項式なのか、を判断しています。

github.com

CustomExpression

これはユーザーが複雑な式やシミュレーションによるブラックボックス関数を定義するために実装されています。(func, args)のペアを持ちます。

from flopt import *
def f(x, y):
    return x + y

a = Variable("a")
b = Variable("b")
custom_expression = CustomExpression(f, arg=[a, b])

argsには関数の引数を表す変数群です。(ここは将来的には辞書の形で与えることになるかもしれません args={"x": x, "y": y})。これは先の二項演算の要素に指定することができます。要するにcustom_expression + x * yのような式も表現できるということです。

Sum, Prod

これは縮約の一種で複数の変数を入力として一つの値を返す式です。これらはExpressionの再帰の深さを低くするために用意されています。また値を求める処理も再起ではなくなるので若干のパフォーマンス向上も期待されます。

演算のオーバーライド

この変数と式にはモデルリングのために演算のオーバーライドがふんだんにカスタマイズされています。この演算のオーバーライドにより次のような変換が行われます。

  • 変数) + (変数) や (変数) * (式) など(+, -, *, /, %, |)で式(Expression)に変換
  • =, >=, <= で制約(Constraint)に変換 (e.g. a + b <= 3)
  • >>, <<は変数群に変換

まとめ

  • 一つの変数は一つのオブジェクトであり、値をもつ
  • 式は二項演算をベースにした計算グラフにより実現
  • 変数と式の間の演算はその種類に応じて式や制約に変換される

関連記事

inarizuuuushi.hatenablog.com

*1:将来的には再帰を解消したい(再帰の深さによるエラーを避けるため)