Problem Decomposition (Time-Series)

Problem Decomposition (Time-Series)#

🌐 日本語 | English

Overview#

In real-world problems, a problem can grow large in one particular direction, making a naive solve prohibitively slow. Typical examples include:

  • Planning over time-series data (e.g. energy supply-demand planning — the longer the time horizon, the larger the problem)

  • Planning over a space that is long in one direction (e.g. cutting problems for glass sheets carried on a conveyor)

In such cases, splitting the problem and solving the resulting subproblems can produce a reasonably good solution in a fraction of the computation time. However, implementing such a split usually has to be designed case by case, which takes effort.

JijZept Tools analyzes the mathematical structure held by JijModeling, and uses information such as “this constraint is separable / not separable” to generate the decomposed problems automatically.

Running the decomposition algorithm#

Let’s look at the following example. Consider a simplified production-planning problem.

Given a demand, we produce goods to satisfy it while keeping the cost as low as possible. Concretely, we consider a problem with the following constraints.

import jijmodeling as jm

c = jm.Placeholder("c", ndim=1)
h = jm.Placeholder("h", ndim=1)
d = jm.Placeholder("d", ndim=1, description="demand")
u = jm.Placeholder("u", ndim=1)

s0 = jm.Placeholder("s0")

x = jm.ContinuousVar(
    "x", shape=c.shape, lower_bound=0, upper_bound=100000, description="production"
)
s = jm.ContinuousVar(
    "s", shape=h.shape, lower_bound=0, upper_bound=100000, description="inventory"
)

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{inventory}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{production}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\\end{array}\end{split}\]

Here t corresponds to the time-series index, so planning over a long horizon makes the problem large.

For simplicity, this example uses 10 time steps, but in practice the time series can be much longer.

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)

Next, we specify how to split the time series. The split is given as a list, using conditions on the index to be split, as shown below.

In this case, the problem is split into three subproblems: \(0 \leq t < 3\), \(3 \leq t < 8\), and \(8 \leq t < 10\).

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

The decomposed problems can then be obtained as follows.

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} c_{t} \cdot x_{t} + \sum_{\substack{t = 0\\t \geq 0 \land t < 3}}^{\mathrm{len}\left(c, 0\right) - 1} h_{t} \cdot s_{t} & \\\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{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{{where}} & & & \\& s & 1\text{-dim continuous variable}& \text{inventory}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{production}\\ & & \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} c_{t} \cdot x_{t} + \sum_{\substack{t = 0\\t \geq 3 \land t < 8}}^{\mathrm{len}\left(c, 0\right) - 1} h_{t} \cdot s_{t} & \\\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{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{{where}} & & & \\& s & 1\text{-dim continuous variable}& \text{inventory}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\& x & 1\text{-dim continuous variable}& \text{production}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }100000 & \\\end{array}\end{split}\]

Here, JijZept Tools analyzes the mathematical structure held by JijModeling, classifies the constraints, for example as

  • separable with respect to the specified indices

  • separable with respect to adjacent indices

and generates the decomposed problems accordingly.

Running the following operation automatically:

  • solves each decomposed problem with the method given as callback_for_decomposed_problem, and

  • combines the individual solutions into a solution of the original 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
)

solution.decision_variables_df
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_df
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>

In this way, we can find an optimal combination of inventory and production that satisfies the constraints, while solving the problem in decomposed form.

Contents