はじめに

はじめに#

JijModelingとは#

JijModelingは、Python コードを使用して数理モデルを記述するための数理最適化モデラーです。 多項式などを用いて、さまざまな種類の最適化問題を記述することができます。

主な特徴#

1. 数理モデルとパラメータの分離#

JijModeling では、数理モデルの記号的な定義と、入力されるパラメータ（インスタンスデータ）を分離しています。 インスタンスデータは数理モデルにおける決定変数以外の係数などに相当し、数理モデルはインスタンスデータを入力されて初めてソルバーへの入力（インスタンス）へと変換（コンパイル）されます。

記号的に記述された数理モデルに「インスタンスデータ」を入力すると、ソルバーへの入力データ（＝インスタンス）が生成される

図 1 数理モデルにパラメータ（インスタンスデータ）を入力してインスタンスを得る#

このように、JijModeling では個々の数理モデルは個別のインスタンスデータからインスタンスを生成するためのスキーマとして機能し、インスタンスデータのサイズに影響されずに数理モデルを変更することが可能になっています。

2. ソルバーに依存しないモデリング#

JijModeling で記述された数理モデルは、OMMX を経て各種ソルバーに渡される

図 2 JijModeling と OMMX による数理最適化問題の求解の流れ#

JijModeling で定義された数理モデルは、最終的にOMMX Message形式で表現されたインスタンスへとコンパイルされます。 OMMX Message はソルバーに依存しない数理最適化用のデータ交換形式であるため、Jij が提供しているソルバー（JijZeptSolver, OpenJij など）やその他のソルバー（SCIP, Gurobi, FixstarsAmplify など）を自由に切り替えて問題を解くことができます。

3. 型検査による記述の誤りの早期発見#

JijModeling は独自の型システムを搭載しており、添え字の成分数の食い違いなどの誤りを、数理モデルの記述時に発見できるようになっています。 特に、大規模なインスタンスデータを入力する前に間違いを即座に検出することができ、定式化の加速が図られます。

4. 制約条件のパターンの検出機能#

数理最適化ソルバーには、特定の形をした制約条件に対してより高速な求解アルゴリズムを提供しているものがあります。 こうした高速化用の機能は、通常ユーザーが意識的に明示して呼び出す必要があります。 一方、JijModeling は自動でこうした制約条件の存在を検出し、OMMX Message を介してソルバーにその情報を渡すことで、ユーザーの介在なしに自動的に求解を高速化します。 以下の例では、検出機能を有効化しただけで圧倒的な速度改善が見られています。

検出を行わない場合、求解時間が入力サイズに対し自乗または指数オーダーで悪化しているのに対し、制約検出を有効化すると非常に緩やかな線型の変化になっている

図 3 二地区工場配置問題の制約検出による高速化#

5. 数理モデルの \(\LaTeX\) 表示#

JijModeling は非常に強力な\(\LaTeX\)出力機能を備えており、JijZept IDE や Google Colab、あるいは一般の Jupyter Notebook 上で数理モデルの定義を直感的に把握でき、数理モデルが期待通りに構築されているかどうかを迅速かつ対話的に確認できます。 以下は、ナップサック問題の定式化と、その\(\LaTeX\)出力の例です。

import jijmodeling as jm

@jm.Problem.define("Knapsack Problem", sense=jm.ProblemSense.MAXIMIZE)
def knapsack(problem: jm.DecoratedProblem):
    N = problem.Length(description="アイテム数")
    W = problem.Float(description="耐荷重")
    w = problem.Float(shape=N, description="各アイテムの重さ")
    v = problem.Float(shape=N, description="各アイテムの価値")
    x = problem.BinaryVar(shape=N, description="アイテム $i$ をナップサックに入れるときのみ $x_i=1$")

    problem += problem.Constraint(
        "weight",
        jm.sum(w[i] * x[i] for i in N) <= W,
        description="重さの総和が耐荷重を越えない"
    )
    problem += jm.sum(v[i] * x[i] for i in N)

knapsack
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Knapsack Problem}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{v}_{i}\cdot {x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{weight}&\quad \displaystyle \sum _{i=0}^{N-1}{{w}_{i}\cdot {x}_{i}}\leq W\\&\text{重さの総和が耐荷重を越えない}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\&&&\text{アイテム $i$ をナップサックに入れるときのみ $x_i=1$}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{アイテム数}\\&&&\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの価値}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{耐荷重}\\&&&\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの重さ}\\\end{alignedat}\end{array} \end{split}\]

Decorator API による直感的な記法#

JijModeling 2.0.0 から、旧来の記法に相当する Plain API に加えて、@ つきの関数定義（デコレータ）内でのみ利用できる Decorator API と呼ばれる略記法をサポートしています。 これにより、変数名の省略や内包表記による記号的な総和の記述など、より「Python らしい」自然なコード記述が可能になりました。

記述例の比較#

Plain API による記述：

my_problem = jm.Problem("My Problem")
N = my_problem.Length("N")
x = my_problem.BinaryVar("x", shape=N)
my_problem += jm.sum(N.filter(lambda i: i % 2 == 0).map(lambda i: x[i]))

Decorator API による記述：

@jm.Problem.define("My Problem")
def my_problem(problem: jm.DecoratedProblem):
    N = problem.Length()
    x = problem.BinaryVar(shape=N)
    problem += jm.sum(x[i] for i in N if i % 2 == 0)

インストール#

pipを使用している場合、次のコマンドでjijmodelingをインストールできます：

pip install 'jijmodeling>=2.0.0, <3'

uv を利用している場合、以下のようにして依存関係に追加できます：

uv add 'jijmodeling>=2.0.0, <3'

jijmodelingの利用には Python 3.11 以上が必要であることに注意してください。

import jijmodeling
jijmodeling.__version__

'2.0.0'

注意

本ドキュメントのコードを実行する際には、上記のjijmodelingのバージョンと同じものを使うことを強く推奨します。

本ドキュメントの構成#

本ドキュメントは数理最適化問題を JijModeling で解くために必要な情報を提供します。 数理最適化そのものについては、JijZept の資料『数理最適化の基礎』などをご参照ください。 本稿の各章の内容は以下の通りです：

  1. クイックスタート：ナップサック問題の例を通して、JijModeling における数理最適化問題の定式化・求解方法について学びます。使うソルバーにより二つにわかれていますが、JijModeling の利用方法はどちらも同じですので、お好みの方をお読みください。

  2. JijModeling の基本：JijModeling を用いたモデリングの基本構成要素を解説します。

  3. 発展的な話題（近日公開）：JijModeling でより高度な数理最適化モデリングを行うための発展的な機能を紹介します。

  4. リファレンス：JijModeling の詳細な利用方法などについて触れています。

    • jijmodeling API Reference: JijModeling の Python API で利用可能な全関数・クラス等の網羅的なリファレンスマニュアルです。

    • Cheat Sheet: 典型的な制約条件・最適化問題などの JijModeling での定式化例を示した事例集です。

    • JijModeling 2 移行ガイド: JijModeling 1 から 2 への変更点について網羅的に解説した移行ガイドです。旧バージョンからの移行の際に参考にしてください。

  5. リリースノート：JijModeling の各バージョンごとの変更履歴が紹介されています。

目次