Zenn
Jij Tech BlogPublicationへの投稿
🤖

JijModelingで定義した最適化問題をPRINTEMPSで解く

TG
2024/12/23に公開
数理最適化
scip
jijmodeling
ommx
printemps
tech

この記事はJij Inc. Advent Calendar 2024の23日目の記事です。

はじめに

最近の業務でSCIP（フリーのMIPソルバー）では求解に時間がかかり過ぎる状況に直面し、OSSのメタヒューリスティクスILPソルバーであるPRINTEMPSを利用させて頂く機会がありました。Jijの業務ではモデラーとして弊社が提供するJijModelingを利用しており、本記事では簡単なナップサック問題を例にJijModelingで定義した最適化問題をPRINTEMPSで解く流れを紹介します。本記事で利用するツールは全てOSSもしくは無償のものなので、ご興味を持たれた方はぜひ試してみてください。

PRINTEMPSについて

PRINTEMPSは冒頭でも触れたように、OSSのメタヒューリスティクスILPソルバーです。私はOptimization Nightで知りました。そちらでのスライド資料も置いておきます。分枝限定法ベースのMIPソルバーが苦手なケースを補完できることを目指したソルバーとのことで今回利用させて頂きました。開発者の方、ありがとうございます。

本題

以下、ナップサック問題をJijModelingで定義し、PRINTEMPSで解いていきます。

Python環境の準備

この記事では以下を使用します。

requirements.txt
jijmodeling == 1.10.1
ommx == 1.5.1
ommx-pyscipopt-adapter == 1.5.1

$ pip install -r requirements.txt

JijModelingによる定式化

まずJijModelingでナップサック問題を定式化します。

import jijmodeling as jm

# 定数の定義
v = jm.Placeholder('v', ndim=1, description="value of item")
w = jm.Placeholder('w', ndim=1, description="weight of item")
W = jm.Placeholder('W', description="capacity of knapsack")
N = v.len_at(0, latex="N", description="number of items")

# 決定変数の定義
x = jm.BinaryVar('x', shape=(N,))

# 添字の定義
i = jm.Element('i', belong_to = (0, N))

# 問題の定義
problem = jm.Problem('Knapsack')
problem += - jm.sum(i, v[i] * x[i])
problem += jm.Constraint('weight', jm.sum(i, w[i] * x[i]) <= W)

problem


出力
JijModelingでは数式に近い書き方でモデリングを行うことができ、また画像のように定義した数理モデルをLaTeX表示する機能があります。ナップサック問題はアイテムの重さの合計がW以下という条件のもとでアイテムの合計価値を最大化する問題ですが、今回は目的関数にマイナスを付けて最小化問題として定義しています。

インスタンスデータの準備

以下のようにインスタンスデータを定義しました。対応するjm.Placeholderに値が代入されます。

price = [5000, 7000, 2000, 1000, 4000, 3000]
weight = [800, 1000, 600, 400, 500, 300]
capacity = 2000

instance_data = {'v': price, 'w':weight, 'W': capacity}

SCIPによる求解

まずは厳密ソルバーであるSCIPで今回の問題の最適解を取得しておきます。
JijModelingで定義した問題をSCIPで解くためにJijが提供するOMMXというソフトウェアを利用します。OMMXは数理最適化向けのデータフォーマットであり、OMMXを経由してJijModelingで定義した問題を各種のソルバーで求解することができます。後段でPRINTEMPSでの求解を実施する時もOMMXを利用します。OMMXについてはこちらのリリース記事もご確認ください。

以下、OMMXを利用してSCIPでの求解を行うコードです。

from ommx_pyscipopt_adapter import instance_to_model, model_to_solution

# problem、instance_dataからOMMXのインスタンスを生成
interpreter = jm.Interpreter(instance_data)
ommx_instance = interpreter.eval_problem(problem)

# OMMXのインスタンスからSCIPのモデルを生成
model = instance_to_model(ommx_instance)

# SCIPで最適化
model.optimize()

# SCIPの解をOMMXのSolutionに変換
ommx_solution_by_scip = model_to_solution(model, ommx_instance)

# 結果の表示
display(ommx_solution_by_scip.decision_variables)
print(f'SCIPで求解した時の目的関数値: {ommx_solution_by_scip.objective}')


出力
今回のナップサック問題の最適解は-14,000と確認できました。また決定変数xの値がpandasデータフレーム形式で確認できます。このようにJijModelingで定義した問題をスムーズにSCIPで求解することができます。ここで得られた最適解を後段でのPRINTEMPSによる求解結果と比較することで、正しくPRINTEMPSを使えているかどうかの確認になります。

PRINTEMPSによる求解

次に同じ問題をPRINTEMPSで解いていきます。

OMMXを利用したmpsファイルへの書き出し

mpsファイルで最適化問題をPRINTEMPSに与えるので、JijModelingで定義した問題をmpsファイルに出力します。

ommx_instance.write_mps(f'knapsack.mps.gz')

$ gzip -d -k knapsack.mps.gz

knapsack.mpsというファイルが生成されます。

PRINTEMPSの準備

次にPRINTEMPSを準備していきます。PRINTEMPSの公式ドキュメントはこちらです。こちらの記事も参考になります。これらの内容に従い、スタンドアローンソルバーを準備します。以下に私が実施した手順をまとめておきます。

クローン
$ git clone https://github.com/snowberryfield/printemps.git
ビルド
$ cd printemps  # クローンしてきたリポジトリに移動
$ make -f makefile/Makefile.application

これによりprintemps/build/application/Release/mps_solverという実行可能ファイルが生成されると思います。

PRINTEMPSによる求解

以下のコマンドで求解が実行できます。

$ printemps/build/application/Release/mps_solver knapsack.mps -p printemps/application/dat/option.json

printemps/application/dat/option.jsonはPRINTEMPSソルバーの設定ファイルですが、今回の問題はデフォルト設定のままで問題ないかと思います。求解が完了すると以下の3つのファイルが生成されます。

  • incumbent.json
  • incumbent.sol
  • status.json

incumbent.jsonを確認してみると目的関数値は-14,000でSCIPの結果と一致しており、無事PRINTEMPSで求解することが出来ました。

{ 
    "version": "v2.5.0", 
    "name": "knapsack", 
    "number_of_variables": 6, 
    "number_of_constraints": 1, 
    "is_found_feasible_solution": true, 
    "objective": -1.400000e+04, 
    "total_violation": 0.000000e+00, 
    "variables": { 
        "OMMX_VAR_0": 0, 
        "OMMX_VAR_1": 1, 
        "OMMX_VAR_2": 0, 
        "OMMX_VAR_3": 0, 
        "OMMX_VAR_4": 1, 
        "OMMX_VAR_5": 1
    }, 
    "expressions": {}, 
    "constraints": { 
        "OMMX_CONSTR_0": -2.000000e+02
    }, 
    "violations": { 
        "OMMX_CONSTR_0": 0.000000e+00
    }
}

OMMXのsolution形式への変換

JijModelingで定義した問題をPRINTEMPSで解くという本記事の目的は既に達成されました。しかし実際に数理最適化問題に取り組んでいる時はSCIPの結果とPRINTEMPSの結果を比較することになるので、双方の結果が同じ形式になっていた方が便利です。PRINTEMPSの結果について以下のようにしてOMMXのSolutionに変換することができます。

import json

printemps_solution_path = 'incumbent.json'

with open(printemps_solution_path, 'r') as f:
    printemps_solution = json.load(f)

ommx_solution_by_printemps = ommx_instance.evaluate({
        var.id: printemps_solution['variables'][f'OMMX_VAR_{var.id}']
        for var in ommx_instance.raw.decision_variables
    })

display(ommx_solution_by_printemps.decision_variables)
print(f'PRINTEMPSで求解した時の目的関数値: {ommx_solution_by_printemps.objective}')


出力
SCIPによる最適解と同様の結果が得られていることが確認できます。

最後に

Jijでは数理最適化・量子コンピュータに関連するソフトウェア開発を行っています。
OSSも複数開発、提供しています。Discordのコミュニティへぜひ参加してください！
https://discord.gg/Km5dKF9JjG
また，Jijでは各ポジションを絶賛採用中です！
ご興味ございましたらカジュアル面談からでもぜひ！ご連絡お待ちしております。
数理最適化エンジニア（採用情報）
量子コンピューティングソフトウェアエンジニア（採用情報）
Rustエンジニア(アルゴリズムエンジニア)（採用情報）
研究チームPMO（採用情報）
オープンポジション等その他の採用情報はこちら

Jij Tech Blog
Jij Tech BlogPublication

Discussion