今回のチュートリアルで用いる題材 ソルバーによる求解 (OMMX、JijZept Solver)

Pythonによる数理モデリング (JijModeling)

このセクションでは、ジョブショップスケジューリング問題を定式化し、Pythonを用いてモデルを実装する方法を学びます。

Python環境のセットアップ手順

まずはJijZept SDKを利用するための推奨Python環境セットアップ手順を以下に示します。
仮想環境を使うことで、依存関係の衝突を防ぎ、クリーンな開発環境を維持できます。


JijZept IDEをご利用の方へ

JijZept IDE環境ではPythonやパッケージのセットアップは不要です。すぐにチュートリアルを始められます。
詳細はJijZept IDEドキュメントをご覧ください。

Python環境セットアップ

  1. 仮想環境の作成
    Terminal window
    python -m venv .venv
  2. 仮想環境の有効化
    Terminal window
    source .venv/bin/activate
  3. JijZept SDKのインストール
    Terminal window
    pip install "jijzept_sdk[all]"

    このコマンドでJijModeling、OMMX、MINTOなど最適化チュートリアルに必要な全てのパッケージがまとめてインストールされます。

  4. 分析、可視化パッケージのインストール
    Terminal window
    pip install pandas matplotlib

JijModelingとは：コンセプト紹介

JijModelingは、数理最適化問題をPythonを用いて直感的かつ宣言的に記述するためのライブラリです。数理最適化の専門家だけでなく、ソフトウェアエンジニアやデータサイエンティストにとっても、数学的な定式化を自然なPythonコードとして表現できるように設計されています。

JijModelingの主な役割は、人間が理解しやすい形で記述された最適化モデル（決定変数、目的関数、制約条件）を、コンピュータ（最適化ソルバー）が解釈できる形式に変換することです。これにより、複雑な数式を手計算で扱う手間を省き、モデルの構築、検証、再利用を容易にします。

JijModelingの特徴

  • 宣言的な記述: 「何を」最適化したいか（目的関数）、「どのような」条件下で（制約条件）を記述することに集中でき、具体的な求解アルゴリズム（「どのように」解くか）を意識する必要はありません。
  • 明確性と再利用性: モデルの構造がコード上で明確になり、デバッグや変更、他の問題への応用が容易になります。
  • JijZeptエコシステムとの連携: JijModelingで記述したモデルは、OMMX形式での保存・共有や、MINTOでの最適化計算実行とシームレスに連携します。

このセクションでは、JijModelingの基本的な使い方を学び、実際に最適化問題をコードで表現する方法を習得します。既存のJijModelingチュートリアルも詳細なリファレンスとして役立ちますが、このチュートリアルでは、学習パスに沿った段階的な解説と例を提供します。

基本的な使い方：変数、目的関数、制約の定義

JijModelingを使って最適化モデルを構築する基本的な手順を見ていきましょう。以下のように、パラメータ、決定変数、目的関数、制約条件を定義する方法を説明します。 詳細な使い方は、JijModelingチュートリアルを参照してください。 

import jijmodeling as jm


# --- パラメータの定義（例: 重みベクトル） ---
w = jm.Placeholder("w", ndim=1) # 1次元の変数
v = jm.Placeholder("w", ndim=1) # 1次元の変数
N = w.len_at(0, latex="N") # wの長さ (len(w[0]))をNと表示


# --- 決定変数の定義（1次元バイナリ, 整数、連続変数） ---
x = jm.BinaryVar("x", shape=(N,)) # バイナリ変数 (shape=(N,))
y = jm.IntegerVar("y", shape=(N,), lower_bound=0, upper_bound=1000) # 整数変数 (0から1000まで) (shape=(N,))
z = jm.ContinuousVar("z", shape=(N,2), lower_bound=0, upper_bound=10) # 連続変数 (0から10まで) (shape=(N,2))


# --- インデックスの定義 ---
i = jm.Element("i", belong_to=(0, N)) # 0 <= i < N までの範囲をとるインデックス


# --- 問題の定義（最大化） ---
problem = jm.Problem("sample_problem", sense=jm.ProblemSense.MAXIMIZE)


# --- 目的関数の定義 ---
problem += jm.sum(i, v[i] * x[i])


# --- 制約条件の定義 ---
# 例1: Σ_i w[i] * x[i] <= 5
problem += jm.Constraint("select_limit", jm.sum(i, w[i] * x[i]) <= 5)
# 例2: すべてのiについて、x[i] <= 2
problem += jm.Constraint("sum_constraint", x[i] <= 2, forall=[i])

並列ジョブショップスケジューリング問題の定式化、実装

定式化

まずは、並列ジョブショップスケジューリング問題を定式化してみましょう。
以下が対応する目的関数、制約条件、決定変数です。

目的関数 制約条件 決定変数
メイクスパン（全てのジョブが完了するまでの時間）の最小化
  • 各ジョブは1台の機械にのみ割り当てる
  • 各機械の合計処理時間はメイクスパン以下
  • どのジョブをどの機械に割り当てるか（バイナリ変数）
  • メイクスパン

この表と合致するように定式化すると、以下のようになります。

並列ジョブショップスケジューリング問題の数理モデル

  • 決定変数：
    • $x_{im}$：ジョブ$i$を機械$m$に割り当てる場合に1、そうでない場合に0となるバイナリ変数
    • $makespan$：全ての機械の完了時間の最大値（最小化したい目的関数）
  • 目的関数：
    • $\min makespan$
  • 制約条件：
    • 各ジョブは1つの機械にのみ割り当てられる：
      \[\sum_{m=0}^{M-1} x_{im} = 1,\ \forall i\]
    • 各機械の処理時間 $JT_{i}$はmakespan以下：
      \[\sum_{i=0}^{N-1} {JT}_i x_{im} \leq makespan,\ \forall m\]

JijModelingによる実装

上記の数理モデルをJijModelingを用いてPythonで実装してみましょう。以下がそのコード例です。 

import jijmodeling as jm


# --- 1. プレースホルダー（入力データ） ---
# JT[i]: ジョブiの処理時間
JT = jm.Placeholder("JT", ndim=1, description="ジョブiの処理時間")
# N: ジョブ数（JTの長さから自動取得）
N = JT.len_at(0, latex="N", description="ジョブ数")
# M: 機械数
M = jm.Placeholder("M", description="機械数")


# --- 2. インデックス ---
i = jm.Element("i", belong_to=(0, N), description="ジョブのインデックス")
m = jm.Element("m", belong_to=(0, M), description="機械のインデックス")


# --- 3. 決定変数 ---
# x[i, m]: ジョブiを機械mに割り当てるか（バイナリ）
x = jm.BinaryVar(
    "x",
    shape=(N, M),
    description="x[i, m]: ジョブiが機械mに割り当てられると1"
)
# makespan: 全機械の完了時間の最大値
makespan = jm.ContinuousVar(
    "makespan",
    lower_bound=0,
    upper_bound=jm.sum(i, JT[i]),
    description="メイクスパン（全体の完了時間）"
)


# --- 4. 問題定義 ---
problem = jm.Problem("Parallel Machine Scheduling")


# --- 5. 制約条件 ---
# 各ジョブは必ず1台の機械に割り当てる
problem += jm.Constraint(
    "Job_Assignment",
    jm.sum(m, x[i, m]) == 1,
    forall=i,
)
# 各機械の合計処理時間はmakespan以下
problem += jm.Constraint(
    "Max_Time_per_Machine",
    jm.sum(i, JT[i] * x[i, m]) <= makespan,
    forall=m,
)


# --- 6. 目的関数 ---
# メイクスパンを最小化
problem += makespan

このように、数式と似た感覚でJijModelingを用いて数理モデルを定式化することができます。

もしNotebook、あるいはJijZept IDEを使用している場合は、変数名を表示させると数式をレンダリングすることが可能です。

JijModeling Rendering
次へ：ソルバーによる求解 (OMMX、JijZept Solver)