バイナリ線形計画問題

バイナリ線形計画問題#

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

\[\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によるモデル化と、それをもとにしたJijZeptSolverを用いた求解について説明します。

JijModelingによるモデル化#

import jijmodeling as jm

@jm.Problem.define('binary_lp', sense=jm.ProblemSense.MAXIMIZE)
def problem(problem: jm.DecoratedProblem):
    # define variables
    S = problem.Float(ndim=2)
    M = problem.DependentVar(S.len_at(0))
    N = problem.DependentVar(S.len_at(1))
    b = problem.Float(shape=(M,))
    c = problem.Float(shape=(N,))
    x = problem.BinaryVar(shape=(N,))
    
    # Objective
    problem += jm.sum(c[i] * x[i] for i in N)
    
    # Constraints
    problem += problem.Constraint(
        "eq_const", 
        [jm.sum(S[j, i] * x[i] for i in N) == b[j] for j in M]
    )

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{binary\_{}lp}\\\displaystyle \max &\displaystyle \sum _{i=0}^{N-1}{{c}_{i}\cdot {x}_{i}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{eq\_{}const}&\quad \displaystyle \sum _{i=0}^{N-1}{{S}_{j,i}\cdot {x}_{i}}={b}_{j}\quad \forall j\;\text{s.t.}\;j\in \left\{0,\ldots ,M-1\right\}\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}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}b&\in \mathop{\mathrm{Array}}\left[M;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\c&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\S&\in \mathop{\mathrm{Array}}\left[(-)\times (-);\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}M&=\mathop{\mathtt{len\_{}at}}\left(S,0\right)&\quad &\in \mathbb{N}\\N&=\mathop{\mathtt{len\_{}at}}\left(S,1\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

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

インスタンスの準備#

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

# 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_のような接頭語を用いています。

JijZeptSolverを用いた求解#

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

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

結果と解の確認#

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

# get the information of the result
obj = solution.objective
df = solution.decision_variables_df
const = solution.constraints_df

print(f"Objective value : {obj}")
print(f"Decision variakbles : \n {df}")
print(f"Constraints : \n {const}")

Objective value : 12.0
Decision variakbles : 
       kind  lower  upper name subscripts description substituted_value  value
id                                                                           
0   Binary    0.0    1.0    x        [0]        <NA>              <NA>    0.0
1   Binary    0.0    1.0    x        [1]        <NA>              <NA>    0.0
2   Binary    0.0    1.0    x        [2]        <NA>              <NA>    1.0
3   Binary    0.0    1.0    x        [3]        <NA>              <NA>    1.0
4   Binary    0.0    1.0    x        [4]        <NA>              <NA>    1.0
Constraints : 
    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>
目次