問題分割アルゴリズム

問題分割アルゴリズム#

概要#

実際の問題において、特定の方向に対し問題が大規模になることで、愚直な求解で時間がかかってしまうケースがあります。具体例としては以下のようなケースがあります。

時系列データに対する計画 (エネルギー需給計画など, 時系列を長く取ればとるほど問題の規模が増大)
特定の方向に長い空間を持つ計画 (ベルトコンベアで運ばれるガラスの板取り問題など)

このようなケースの場合、問題を分割してそれぞれの部分問題を解くことにより、ある程度妥当な解を大幅に計算時間を短縮して解くことができますが、そのような分割を行うための実装はケースごとに考慮する必要があり、手間がかかる場合が多いです。

JijZept Toolsでは、JijModelingの持つ数式構造を解析し、この制約は分離可能である、または分離不可能であるといった情報を利用し、自動で分割された問題を生成する機能を持っています。

問題分割アルゴリズムの実行#

以下の例を見てみましょう。単純化した生産計画の問題を考えます。

需要が与えられた際に、その需要を満たすために極力コストを抑えつつ生産を行う問題です。具体的には、以下のような制約条件を持つ問題を考えます。

import jijmodeling as jm
c = jm.Placeholder("c", ndim=1)
h = jm.Placeholder("h", ndim=1)
d = jm.Placeholder("d", ndim=1, description="需要量")
u = jm.Placeholder("u", ndim=1)

s0 = jm.Placeholder("s0")

x = jm.ContinuousVar("x", shape=c.shape, lower_bound=0, upper_bound=100000, description="生産量")
s = jm.ContinuousVar("s", shape=h.shape, lower_bound=0, upper_bound=100000, description="在庫")

t = jm.Element("t", belong_to=c.shape[0])

problem = jm.Problem("production planning")

problem += jm.sum([t], c[t] * x[t] + h[t] * s[t])

problem += jm.Constraint(
    "match_demand", s[t - 1] + x[t] - s[t] == d[t], forall=(t, t >= 1)
)
problem += jm.Constraint("upper limit of production", x[t] <= u[t], forall=t)
problem += jm.Constraint("initial stock", s[t] == s0, forall=(t, t == 0))
problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{production planning} & & \\& & \min \quad \displaystyle \sum_{t = 0}^{\mathrm{len}\left(c, 0\right) - 1} \left(c_{t} \cdot x_{t} + h_{t} \cdot s_{t}\right) & \\\text{{s.t.}} & & & \\ & \text{initial stock} & \displaystyle s_{t} = s0 & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t = 0 \right\} \\ & \text{match\_demand} & \displaystyle s_{t - 1} + x_{t} - s_{t} = d_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 1 \right\} \\ & \text{upper limit of production} & \displaystyle x_{t} \leq u_{t} & \forall t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \\\text{{where}} & & & \\& s & 1\text{-dim continuous variable}& \text{在庫}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{生産量}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\\end{array}\end{split}\]

ここで、tが時系列のインデックスに相当するため、長時間の生産計画を考えると問題規模が大きくなります。

この例では簡単のために、時刻のインデックスを10としますが、実際にはより長い時系列を考えることができます。

instance_data = {
        "c": [1, 2, 3, 4, 3, 2, 1, 3, 2, 5],
        "h": [2, 3, 4, 5, 3, 2, 1, 3, 2, 5],
        "d": [8, 5, 4, 5, 3, 2, 1, 3, 2, 5],
        "u": [10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
        "s0": 10,
    }

interpreter = jm.Interpreter(instance_data)

続いて、どのように時系列を分割するかを与えてあげます。分割の方法は、以下のように分割したいインデックスを用いてリストで指定します。

このケースでは、\(0 \leq t < 3\), \(3 \leq t < 8\), \(8 \leq t < 10\)の3つの部分問題に分割しています。

separable_forall = [
    [(t, (t >= 0) & (t < 3))],
    [(t, (t >= 3) & (t < 8))],
    [(t, (t >= 8) & (t < 10))],
]

ここで、分割された問題を次の方法で取得できます。

from jijzepttools.modeling.algorithm.series_decomposition.series_decomposition import (
    decompose_problem,
    solve,
)
decomposed_problem = decompose_problem(problem, separable_forall)

decomposed_problem[0]

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{production planning\_0} & & \\& & \min \quad \displaystyle \sum_{\substack{t = 0\\t \geq 0 \land t < 3}}^{\mathrm{len}\left(c, 0\right) - 1} \left(c_{t} \cdot x_{t} + h_{t} \cdot s_{t}\right) + \sum_{\substack{t = 0\\t \geq 3 \land t < 8}}^{\mathrm{len}\left(c, 0\right) - 1} \left(c_{t} \cdot x_{t} + h_{t} \cdot s_{t}\right) & \\\text{{s.t.}} & & & \\ & \text{initial stock\_A\_0} & \displaystyle s_{t} = s0 & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t = 0 \land t \geq 0 \land t < 3 \right\} \\ & \text{initial stock\_B\_0} & \displaystyle s_{t} = s0 & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t = 0 \land t \geq 3 \land t < 8 \right\} \\ & \text{match\_demand\_A\_0} & \displaystyle s_{t - 1} + x_{t} - s_{t} = d_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 1 \land t \geq 0 \land t < 3 \right\} \\ & \text{match\_demand\_B\_0} & \displaystyle s_{t - 1} + x_{t} - s_{t} = d_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 1 \land t \geq 3 \land t < 8 \right\} \\ & \text{upper limit of production\_A\_0} & \displaystyle x_{t} \leq u_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 0 \land t < 3 \right\} \\ & \text{upper limit of production\_B\_0} & \displaystyle x_{t} \leq u_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 3 \land t < 8 \right\} \\\text{{where}} & & & \\& s & 1\text{-dim continuous variable}& \text{在庫}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{生産量}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\\end{array}\end{split}\]

decomposed_problem[1]

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{production planning\_1} & & \\& & \min \quad \displaystyle \sum_{\substack{t = 0\\t \geq 3 \land t < 8}}^{\mathrm{len}\left(c, 0\right) - 1} \left(c_{t} \cdot x_{t} + h_{t} \cdot s_{t}\right) + \sum_{\substack{t = 0\\t \geq 8 \land t < 10}}^{\mathrm{len}\left(c, 0\right) - 1} \left(c_{t} \cdot x_{t} + h_{t} \cdot s_{t}\right) & \\\text{{s.t.}} & & & \\ & \text{initial stock\_A\_1} & \displaystyle s_{t} = s0 & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t = 0 \land t \geq 3 \land t < 8 \right\} \\ & \text{initial stock\_B\_1} & \displaystyle s_{t} = s0 & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t = 0 \land t \geq 8 \land t < 10 \right\} \\ & \text{match\_demand\_A\_1} & \displaystyle s_{t - 1} + x_{t} - s_{t} = d_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 1 \land t \geq 3 \land t < 8 \right\} \\ & \text{match\_demand\_B\_1} & \displaystyle s_{t - 1} + x_{t} - s_{t} = d_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 1 \land t \geq 8 \land t < 10 \right\} \\ & \text{upper limit of production\_A\_1} & \displaystyle x_{t} \leq u_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 3 \land t < 8 \right\} \\ & \text{upper limit of production\_B\_1} & \displaystyle x_{t} \leq u_{t} & \forall t \in \left\{t \in \left\{0,\ldots,\mathrm{len}\left(c, 0\right) - 1\right\} \mid t \geq 8 \land t < 10 \right\} \\\text{{where}} & & & \\& s & 1\text{-dim continuous variable}& \text{在庫}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{生産量}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\\end{array}\end{split}\]

ここで、JijZept Toolsにより、JijModelingの持つ数式構造を解析し、

指定したインデックスに対して分割可能である
隣接したインデックスに対して分割可能である

のように制約を分類し、分割された問題を生成しています。

以下のような操作を行うと、

分割された問題をそれぞれ callback_for_decomposed_problem に指定した方法で解く。
それぞれの解を結合して、元の問題の解を得る

操作を自動で行います。

from ommx.v1 import Instance, Solution
from ommx_pyscipopt_adapter import OMMXPySCIPOptAdapter
def callback_for_decomposed_problem(instance: Instance) -> Solution:
   return OMMXPySCIPOptAdapter.solve(instance)

solution = solve(problem, interpreter, separable_forall, callback_for_decomposed_problem)

/home/runner/work/JijZeptTools/JijZeptTools/.venv/lib/python3.10/site-packages/ommx_pyscipopt_adapter/adapter.py:30: UserWarning: linked SCIP 9.02 is not recommended for this version of PySCIPOpt - use version 9.2.1
  self.model = pyscipopt.Model()

solution.decision_variables

	kind	lower	upper	name	subscripts	description	substituted_value	value
id
0	continuous	0.0	100000.0	x	[0]	<NA>	<NA>	0.0
1	continuous	0.0	100000.0	x	[1]	<NA>	<NA>	0.0
2	continuous	0.0	100000.0	x	[2]	<NA>	<NA>	0.0
3	continuous	0.0	100000.0	x	[3]	<NA>	<NA>	4.0
4	continuous	0.0	100000.0	x	[4]	<NA>	<NA>	3.0
5	continuous	0.0	100000.0	x	[5]	<NA>	<NA>	2.0
6	continuous	0.0	100000.0	x	[6]	<NA>	<NA>	4.0
7	continuous	0.0	100000.0	x	[7]	<NA>	<NA>	0.0
8	continuous	0.0	100000.0	x	[8]	<NA>	<NA>	7.0
9	continuous	0.0	100000.0	x	[9]	<NA>	<NA>	0.0
10	continuous	0.0	100000.0	s	[0]	<NA>	<NA>	10.0
11	continuous	0.0	100000.0	s	[1]	<NA>	<NA>	5.0
12	continuous	0.0	100000.0	s	[2]	<NA>	<NA>	1.0
13	continuous	0.0	100000.0	s	[3]	<NA>	<NA>	0.0
14	continuous	0.0	100000.0	s	[4]	<NA>	<NA>	0.0
15	continuous	0.0	100000.0	s	[5]	<NA>	<NA>	0.0
16	continuous	0.0	100000.0	s	[6]	<NA>	<NA>	3.0
17	continuous	0.0	100000.0	s	[7]	<NA>	<NA>	0.0
18	continuous	0.0	100000.0	s	[8]	<NA>	<NA>	5.0
19	continuous	0.0	100000.0	s	[9]	<NA>	<NA>	0.0

solution.constraints

	equality	value	used_ids	name	subscripts	description	dual_variable	removed_reason
id
0	=0	0.0	{10}	initial stock	[0]	<NA>	<NA>	<NA>
1	=0	0.0	{1, 10, 11}	match_demand	[1]	<NA>	<NA>	<NA>
2	=0	0.0	{2, 11, 12}	match_demand	[2]	<NA>	<NA>	<NA>
3	=0	0.0	{3, 12, 13}	match_demand	[3]	<NA>	<NA>	<NA>
4	=0	0.0	{4, 13, 14}	match_demand	[4]	<NA>	<NA>	<NA>
5	=0	0.0	{5, 14, 15}	match_demand	[5]	<NA>	<NA>	<NA>
6	=0	0.0	{16, 6, 15}	match_demand	[6]	<NA>	<NA>	<NA>
7	=0	0.0	{16, 17, 7}	match_demand	[7]	<NA>	<NA>	<NA>
8	=0	0.0	{8, 17, 18}	match_demand	[8]	<NA>	<NA>	<NA>
9	=0	0.0	{9, 18, 19}	match_demand	[9]	<NA>	<NA>	<NA>
10	<=0	-10.0	{0}	upper limit of production	[0]	<NA>	<NA>	<NA>
11	<=0	-10.0	{1}	upper limit of production	[1]	<NA>	<NA>	<NA>
12	<=0	-10.0	{2}	upper limit of production	[2]	<NA>	<NA>	<NA>
13	<=0	-6.0	{3}	upper limit of production	[3]	<NA>	<NA>	<NA>
14	<=0	-7.0	{4}	upper limit of production	[4]	<NA>	<NA>	<NA>
15	<=0	-8.0	{5}	upper limit of production	[5]	<NA>	<NA>	<NA>
16	<=0	-6.0	{6}	upper limit of production	[6]	<NA>	<NA>	<NA>
17	<=0	-10.0	{7}	upper limit of production	[7]	<NA>	<NA>	<NA>
18	<=0	-3.0	{8}	upper limit of production	[8]	<NA>	<NA>	<NA>
19	<=0	-10.0	{9}	upper limit of production	[9]	<NA>	<NA>	<NA>

これにより、制約を満たす在庫と生産量の最適な組み合わせを、問題を分割した上で求めることができます。

問題分割アルゴリズム

Contents

問題分割アルゴリズム#

概要#

問題分割アルゴリズムの実行#