バイナリ線形計画問題

バイナリ線形計画問題#

ここでは、バイナリ線形計画問題のモデル化を見てみましょう。

\[\begin{split} \begin{align} &\max_{x} \sum_i c_i x_i\\ &\mathrm{s.t.}~ \sum_{i}S_{j, i}x_i = b_j,~\forall j\\ &x_i \in \{0, 1\}. \end{align} \end{split}\]

応用#

離散変数を伴う線形計画問題は、混合整数計画問題と呼ばれ、様々な応用があります。 目的関数と制約条件が全て線形であるにもかかわらず、その応用範囲はとても広いことが知られています。 多くの応用例の中でも、代表的なものを以下に示します。

  • 資本予算最適化

  • 倉庫位置決定最適化

問題サイズが極端に大きくない場合、分枝限定法をベースとした線形計画ソルバーは有用です。 もちろん、JijModelingは線形計画ソルバーもサポートします。 ここではJijModelingによるモデル化と、それをもとにしたJijSolverを用いた求解について説明します。

JijModelingによるモデル化#

import jijmodeling as jm

# set problem
problem = jm.Problem('binary_lp', sense=jm.ProblemSense.MAXIMIZE)

# define variables
S = jm.Placeholder('S', ndim=2)
M = S.len_at(0, latex="M")
N = S.len_at(1, latex="N")
b = jm.Placeholder('b', ndim=1)
c = jm.Placeholder('c', ndim=1)
x = jm.BinaryVar('x', shape=(N,))
i = jm.Element('i', belong_to=(0, N))
j = jm.Element('j', belong_to=(0, M))


# Objective
problem += jm.sum(i, c[i]*x[i])

# Constriants
problem += jm.Constraint("eq_const", jm.sum(i, S[j, i] * x[i]) == b[j], forall=j)

problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{binary\_lp} & & \\& & \max \quad \displaystyle \sum_{i = 0}^{N - 1} c_{i} \cdot x_{i} & \\\text{{s.t.}} & & & \\ & \text{eq\_const} & \displaystyle \sum_{i = 0}^{N - 1} S_{j, i} \cdot x_{i} = b_{j} & \forall j \in \left\{0,\ldots,M - 1\right\} \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

Problem(..., sense=jm.ProblemSense.MAXIMIZE)により、目的関数を最大化することで最適化問題を解くことを明記しています。 senseに何も指定しない場合、デフォルトでは目的関数の最小化により問題を解くモードとなります。

len_atは、Jupyter上のLaTeX表示における数式表現をオーバーライドするのに用いることができます。 同様の機能にshapeもあり、これを用いると見た目が綺麗になります。

e.g.

S = jm.Placeholder('S', ndim=2)
M = S.shape[0]
N = S.shape[1]

インスタンスの準備#

次に、問題のインスタンスを設定しましょう。 例として、以下のインスタンスを準備します。

# set S matrix
inst_S = [[0, 2, 0, 2, 0], [1, 0, 1, 0, 1], [1, 2, 3, 2, 1]]
# set b vector
inst_b = [2, 2, 6]
# set c vector
inst_c = [1, 2, 3, 4, 5]
instance_data = {'S': inst_S, 'b': inst_b, 'c': inst_c}
\[\begin{split}S = \left( \begin{array}{ccccc} 0 & 2 & 0 & 2 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 2 & 3 & 2 & 1 \end{array}\right), \quad \mathbf{b} = \left( \begin{array}{c} 2 \\ 2 \\ 6 \end{array}\right), \quad \mathbf{c} = \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \end{array}\right)\end{split}\]

変数名とそのスコープに注意しましょう。 S, b, cのような変数名はJijModelingによるモデル化部分で用いているため、インスタンス準備部分ではこれらの変数名は使うことができません。 これを避けるために、インスタンス準備部分の変数にはinst_のような接頭語を用いています。

JijSolverを用いた求解#

jijsolverを用いて、この問題の解を求めてみましょう。

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

結果と解の確認#

得られた解の確認をしましょう。 jijsolverから得られた解はOMMXという形式で管理されています。 .decision_variables、.objective、そして.constraintsにより、それぞれ決定変数、目的関数値、制約の破れ具合を見ることができます。

# get the information of the result
df = solution.decision_variables
obj = solution.objective
const = solution.constraints

print("Objective value : {}".format(obj))
print(const)

Objective value : 12.0
   equality  value         used_ids      name subscripts description  \
id                                                                     
0        =0    0.0           {1, 3}  eq_const        [0]        <NA>   
1        =0    0.0        {0, 2, 4}  eq_const        [1]        <NA>   
2        =0    0.0  {0, 1, 2, 3, 4}  eq_const        [2]        <NA>   

   dual_variable removed_reason  
id                               
0           <NA>           <NA>  
1           <NA>           <NA>  
2           <NA>           <NA>

最後に、求められた\(x\)を表示してみましょう。

# check the solution
x_result = df["value"].to_list()
print(x_result)

[0.0, 0.0, 1.0, 1.0, 1.0]
Contents