Skip to main content

LPファイルへの書き出し

概要​

JijModelingで問題を作って解いたが実行可能解が得られない場合、モデルが間違っているのかパラメータの調整が間違っているのかは簡単にはわかりません。

そこで、作成した問題を通常の最適化ソルバーが解けるLPファイルの形式に出力する関数としてto_lp_expression() が存在します。

to_lp_expression() では、LPファイルにそのまま書き込める文字列を出力します。

ここでは、to_lp_expression() を使ってJijModelingで定義した問題をCBCソルバーで解いてみます。

問題の作成​

ナップザック問題をJijModelingで実装します。ナップザック問題とは以下のように定義される最大化問題です。

\begin{aligned}
\max &\sum_{i=1}^{N}v_ix_i\\
\mathrm{s.t.}&\sum_{i=1}^{N} w_ix_i \leq W\\
&x_i \in \{0, 1\}, ~\forall i
\end{aligned}

ここで、

‘N‘`N` : アイテム数

‘W‘`W` : ナップザックの容量

‘vi‘`v_i` : アイテム‘i‘`i`の価値

‘wi‘`w_i` : アイテム‘i‘`i`の要領

です。目的関数を ‘−1‘`-1` 倍した最小化問題を、Jij で実装します。

import jijmodeling as jm

# set problem
problem = jm.Problem('knapsack')

# define variables
values = jm.Placeholder('values', dim=1)
weights = jm.Placeholder('weights', dim=1)
W = jm.Placeholder('W')
N = values.shape[0]
x = jm.Binary('x', shape=(N, ))
i = jm.Element('i', N)

# set maximum weight constraint
problem += jm.Constraint("capacity", jm.Sum({i: N}, weights[i] * x[i]) <= W)

# set objective function
obj = - jm.Sum(i, values[i]*x[i])
problem += obj

インスタンスは以下のように定義します。

# set a list of values & weights 
values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
weights = [4, 9, 2, 5, 10, 7, 6, 8, 10, 9]
# set maximum weight
W = 30
instance_data = {'values': values, 'weights': weights, 'W': W}

LPファイルへの変換を行う​

上で定義した問題を通常のソルバーで解ける（通称LPファイル）形に変換します。その際に to_lp_expression() という関数を使用します。

その後、LPファイルとして書き出しを行います。

lp_obj = jm.to_lp_expression(problem, ph_value=instance_data, relax={}, obj_ignore=False, fixed_variables={})

with open("problem_lp.lp", w) as prob_lp:
    prob_lp.write(lp_obj)

ここで to_lp_expression() の引数の詳細は以下の通りです。

  • relax (Dict[str, bool]) : JijModelingで使用できる変数は基本的に整数なので、それを連続緩和したい場合にどの変数を緩和するかを辞書の形で与えます。 {var.label:True} という形です。 複数ある場合は、key-valueを増やします。初期値はFalseです。

  • obj_ignore (bool): 目的関数が二次形式の場合は多々存在するので、目的関数を無視するかどうかのbool値です。 obj_ignore=True とすると、目的関数は定数 0 として出力します。初期値はFalse です。

  • ph_value (dict), fixed_variables (dict): 通常のJijModelingで使用するto_pyquboなどと同じ型です。

CBCソルバーを用いてLPファイルの問題を解く​

ここでは試しに、変数の連続緩和を行い目的関数の上界を得てみましょう。

LPファイルを読み込み、ソルバーを使用するのに python-mip を使用します。

# 連続緩和の指定
relax = {"x":True}
lp_obj = jm.to_lp_expression(problem, ph_value=instance_data, relax=relax, obj_ignore=False, fixed_variables={})

# LPファイルの書き出し
with open("problem_lp.lp", w) as prob_lp:
    prob_lp.write(lp_obj)

from mip import *
m = Model(sense=MINIMIZE, solver_name=CBC)

# LPファイルの読み込み
m.read("prob_lp.lp")
print('model has {} vars, {} constraints and {} nzs'.format(m.num_cols, m.num_rows, m.num_nz))

# CBCソルバーを用いた求解
m.optimize()

# 変数の値の出力
for i in m.vars:
    print(i, " = ", i.x)

# 目的関数値
print(m.objective_value)

# 元の問題の最適値の上界
print(-1 * m.objective_value)

JijModeling上では、Knapsack問題を目的関数に-1倍した最小化問題を考えたので、目的関数値を-1倍した値が元のKnapsack問題の最適値の上界となります。

fixed_variables で固定されている変数は、LPファイルの中では定数として扱われているため、python-mipで定義した問題上の変数 m.vars の中には存在しません。なので別途取得する必要があります。

この関数を使う意義​

Openjij（JijModeling）では様々なソルバーが使用できます。それにも関わらず今回のLPファイルへ出力を行い、CBCなどの通常のソルバーを使用する理由をここでは説明します。

1. JijModelingで実装したモデル（or 問題）が正しいかどうかを確認する​

to_lp_expression() では、JijModelingで実装したモデルがそのままLPファイルとして出力されます。ですので小さい問題サイズで通常のソルバーを用いて問題を解くことで、実装したモデルが正しいかどうかの判断をある程度することができます。

特に解きたい問題の目的関数が二次多項式の場合では、通常のソルバーで解を求めるのが非常に遅くなるケースが多いです。このとき制約式が正しく実装されているか確認したい場合、新たなモデルを作る必要なく目的関数を無視（obj_ignore=True）を指定するだけで、LPファイルを作成することができます。このLPファイルを通常のソルバーで解くことでモデルの正当性をある程度判断することができます。

2. 目的関数の上界・下界を求める​

最適化問題において、上界や下界は問題を解く上で大切な情報となります。以下では最小化問題を考えるとします。

relax={"x":True} と指定して解くことで、最適値の下界を得ることができます。この上でOpenjijで使用できるソルバーを使って問題を解いたときに、そこで得た解の良し悪しをある程度判断することができます。特に、最適値の下界とOpenjijで得た解の目的関数値が一致した場合、その解は最適解となります。

このように上界・下界の情報を仕様することで、解の良し悪しを判断することができます。

注意​

現在Jijmodeling内で定義できる変数Spinはto_lp_expression()の出力が対応していません。現在対応中ですので、今しばらくお待ち下さい。