# Distributed Optimization for Supply Chain Planning for Multiple Companies Using Subgradient Method and Consensus Control

Naoto Debuchi, Tatsushi Nishi, Ziang Liu

► To cite this version:

Naoto Debuchi, Tatsushi Nishi, Ziang Liu. Distributed Optimization for Supply Chain Planning for Multiple Companies Using Subgradient Method and Consensus Control. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2022, Gyeongju, South Korea. pp.216-223, 10.1007/978-3-031-16411-8_27. hal-04768952

HAL Id: hal-04768952

https://inria.hal.science/hal-04768952v1

Submitted on 6 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Distributed optimization for supply chain planning for multiple companies using subgradient method and consensus control

Naoto Debuchi, Tatsushi Nishi, and Ziang Liu

Graduate School of Natural Science and Technology, Okayama University, 3-1-1 Tsushima-naka, Kita-ku, Okayama City 700-8530, Japan
nishi.tatsushi@okayama-u.ac.jp

**Abstract** With recent liberalization and enlarging of trade among companies, it is necessary to generate an optimal supply chain planning by cooperation and coordination of supply chain planning for multiple companies. Without sharing sensitive information such as costs and profit among competitive companies. A distributed optimization can solve the optimization problems with limited information. A distributed optimization method using subgradient and consensus control methods has been proposed to solve continuous optimization problems. However, conventional distributed optimization methods using subgradient and consensus control methods cannot be applied to the supply chain planning for multiple companies including 0-1 decision variables. In this paper, we propose a new distributed optimization method for solving the supply chain planning problem for multiple companies by subgradient method and consensus control. By branch-ing the cases 0-1 variables, an optimal solution can be obtained by the enumera-tion. A method to reduce the computational effort has been developed in the pro-posed method. From numerical experiments, it is confirmed that we can obtain an optimal solution by the reduction of the computation.

**Keywords:** Distributed optimization, Supply chain planning, Subgradient method, Consensus control

## 1 Introduction

With liberalization and enlarging of trade among companies, coordination of supply chain planning becomes more complex. Therefore, it is necessary to create optimal supply chain planning by cooperation and coordination of supply chain planning for multiple companies. In the optimization processes, companies should share their sensitive information to optimize a supply chain planning. However, it is desirable to create a supply chain planning without sharing sensitive information such as costs and profit among competitive companies. Therefore, in this study, we propose a distributed optimization method that can solve the optimization problems with limited information. Distributed optimization methods have been studied widely. In the conventional dis-
tributed optimization methods, the subgradient method [1], [2] and the consensus con-
trol [3] have been used. Subgradient method is one of the optimization methods, which
obtain a better solution by moving a decision variable towards the direction of subgra-
dient. Consensus control is that all decision variables agree with the same state by shar-
ing information [4], [5], [6]. In recent study, the method using both subgradient method
and consensus control [7], [8], [9] has been proposed. An optimization model of supply
chain planning for multiple companies is proposed in [10]. In [10], an augmented La-
grangian decomposition method is used to solve the problem. The performance of the
algorithm is compared with that of Lagrangian relaxation and the penalty function
method. These methods can obtain an approximate solution of optimization problems.
On the other hand, the distributed optimization method in [7] can obtain an optimal
solution of convex continuous optimization problems. In this study, we solve supply
chain planning for multiple companies by the method based on the method in [7]. Since
the method in [7] cannot be applied to an optimization problem including 0-1 decision
variables, we propose a new method which can obtain an optimal solution by branching
the cases of 0-1 variables. The proposed method can obtain an optimal solution of op-
timization problems by the enumerations without using a commercial solver.

## 2 Supply chain planning for multiple companies

Supply chain planning for multiple companies is explained in this section. The objec-
tive of this problem is to determine the daily trade volume of multiple arrival companies
and shipping companies. Each company has a preferred trade volume of each product
each day, and it costs a shortage and excess cost when a trade volume has shortage or
excess towards preferred trade volume. If the trade volume differs in consecutive days,
it costs a trade dividing cost. When each company carries out a trade, it costs a trade
implementation cost. This problem needs to meet four constraints: an arrival volume
and a shipping volume of products must be equal, prescribed trade volume must be
traded, they cannot trade over the upper limit per day, and they can trade only one type
or fewer types in each day. We formulate this problem in two ways. The one is formu-
lation including only continuous variables by omitted 0-1 variables. The another is the
formulation as 0-1 mixed integer programming problem, including 0-1 variables as an
original supply chain planning for multiple companies.

Fig. 1 shows an example of supply chain planning for multiple companies. In this ex-
ample, there are two arrival companies A, B and two shipping companies C, D. Prod-
ucts are two types, the one is blue and the another is yellow. Time period is ten days.
The numbers in Fig. 1 indicate each company’s trade volume in each day. This supply
chain planning meets a constraint which an arrival volume and a shipping volume of
products must be an equal and a constraint which companies can trade only one type or
fewer types in each day. Trade dividing cost is incurred when the trade volume differs
in consecutive days, for example days 1-2 of company D.
<figure><img src="image_3.png" /><figcaption>Fig. 1. An example of supply chain planning for multiple companies</figcaption></figure>

We define sets, constants, and variables of supply chain planning for multiple companies for formulation.

### Sets

$Z_d$: A set of arrival companies

$Z_s$: A set of shipping companies

$P$: A set of products

### Constants

$s_i^{max}$: An upper limit of product i's trade volume

$m_i$: A product i's prescribed trade volume

$D_{i,t}^c$: A company c's preferred trade volume of product i on day t

$\beta_{i,t}^c$: A company c's coefficient of a shortage and excess cost of product i on day t

$e_i^c$: A company c's coefficient of a trade dividing cost of product i

$d_{i,t}^c$: A company c's coefficient of a trade implementation cost of product i on day t

### Variables

$S_{i,t}^c$: A company c's trade volume of product i on day t

$X_{i,t}^c$: A 0-1 variable indicates company c's trade dividing of product i on day t

$Y_{i,t}^c$: A 0-1 variable indicates company c's presence or absence of trade of product i on day t

## 2.1 Formulation including only continuous variables

$$ \min \sum_{c \in Z_d} \sum_{i \in P} \sum_{t} \{ \beta_{i,t}^c |D_{i,t}^c - S_{i,t}^c| \} \quad (2.1) $$

subject to

$$ \sum_{c \in Z_d} S_{i,t}^c = \sum_{c \in Z_s} S_{i,t}^c \quad (2.2) $$

$$ \sum_{t} S_{i,t}^c = m_i \quad (2.3) $$

$$ S_{i,t}^c \leq s_i^{max} \quad (2.4) $$
(2.1) is an objective function that minimizes the total trade costs. Trade dividing costs and trade implementation costs are not considered in this formulation. (2.2) is a constraint ensuring that an arrival volume and a shipping volume of products must be equal. (2.3) is a constraint which state that the trade volume must be traded. (2.4) is a constraint which companies cannot trade over the upper limit per day. A constraint that companies can trade only one type or fewer types in each day is not considered in this formulation.

## 2.2 Formulation including 0-1 variables

$$ \min \sum_{c \in Z_d \cup Z_s} \sum_{i \in P} \sum_{t} \{ \beta_{i,t}^{c} | D_{i,t}^{c} - S_{i,t}^{c} | + e_{i}^{c} X_{i,t}^{c} + d_{i,t}^{c} Y_{i,t}^{c} \} \quad (2.5) $$

subject to

$$ \sum_{c \in Z_d} S_{i,t}^{c} = \sum_{c \in Z_s} S_{i,t}^{c} \quad (2.6) $$

$$ \sum_{t} S_{i,t}^{c} = m_i \quad (2.7) $$

$$ S_{i,t}^{c} \leq s_{i}^{\max} \quad (2.8) $$

$$ \sum_{i \in P} Y_{i,t}^{c} \leq 1 \quad (2.9) $$

$$ X_{i,t}^{c} = \begin{cases} 1 & (S_{i,t}^{c} \neq S_{i,t-1}^{c}) \\ 0 & (S_{i,t}^{c} = S_{i,t-1}^{c}) \end{cases} \quad (2.10) $$

$$ Y_{i,t}^{c} = \begin{cases} 1 & (S_{i,t}^{c} > 0) \\ 0 & (S_{i,t}^{c} = 0) \end{cases} \quad (2.11) $$

(2.5) is an objective function that minimizes the total trade costs. (2.6) is a constraint which an arrival volume and a shipping volume of products must be equal. (2.7) is a constraint ensuring that prescribed trade volume must be traded. (2.8) is a constraint which companies cannot trade over the upper limit per day. (2.9) is a constraint which companies can trade only one type or fewer types in each day. (2.10) is a 0-1 variable which shows the dividing of trade. (2.11) is a 0-1 variable which shows the implementation of trade.

## 3 Solution of the optimization problems including only continuous variables

We use the distributed penalty primal-dual subgradient algorithm (DPPDS algorithm) proposed in [7]. Algorithm 1 shows the DPPDS algorithm.
$$v_x^i(k) = \sum_{j=1}^{N} a_j^i x^j(k) \quad (3.1)$$

$$v_\mu^i(k) = \sum_{j=1}^{N} a_j^i \mu^j(k) \quad (3.2)$$

$$v_\lambda^i(k) = \sum_{j=1}^{N} a_j^i \lambda^j(k) \quad (3.3)$$

$$x^i(k+1) = P_x[v_x^i(k) - \alpha(k)S_x^i(k)] \quad (3.4)$$

$$\mu^i(k+1) = v_\mu^i(k) + \alpha(k) [g(v_x^i(k))]^+ \quad (3.5)$$

$$\lambda^i(k+1) = v_\lambda^i(k) + \alpha(k) |h(v_x^i(k))| \quad (3.6)$$

$$S_x^i(k) = D_{fi}(v_x^i(k)) + \sum_{\ell=1}^{m} v_\mu^i(k) [D_{g\ell}(v_x^i(k))]^+ + \sum_{s=1}^{v} v_\lambda^i(k) |D_{hs}(v_x^i(k))| \quad (3.7)$$

**Algorithm1 DPPDS algorithm**

1: **Given** initial variables $x^i(0), \mu^i(0), \lambda^i(0)$ for each agent $i$, $i = 1, \dots, N$; set $k = 1$

2: **repeat**

3: For $i = 1, \dots, N$, each agent $i$ computes (3.1) ~ (3.3)

4: For $i = 1, \dots, N$, each agent $i$ computes (3.4) ~ (3.7)

5: **Set** $k = k + 1$

6: **until** a predefined stopping criterion (e.g., $k = 1000$) is satisfied.

7: computes $z = f(x(k))$

(3.1) ~ (3.3) indicate consensus control. Each company updates the variables by sharing variables with other companies. (3.4) ~ (3.7) are the updating equations of variables to optimal solution by subgradient method. An optimal solution can be obtained by enough times of updates of variables by consensus control and subgradient method.

## 4 Applying to the optimization problems including 0-1 variables

In this study, we apply the DPPDS algorithm to supply chain planning for multiple companies by branching the cases 0-1 variables and regarding them as continuous variables. There are two 0-1 variables which must be considered in this problem, $X_{i,t}^c$ and $Y_{i,t}^c$. For branching $X_{i,t}^c$ value, we add a constraint which the trade volume $S_{i,t}^c$ must be equal to $S_{i,t-1}^c$ when $X_{i,t}^c = 0$. For branching $Y_{i,t}^c$ value, we add a constraint which the
trade volume $S_{i,t}^c$ must be zero when $Y_{i,t}^c = 0$. We don't add a constraint when $X_{i,t}^c = 1$ or $Y_{i,t}^c = 1$. We obtain an optimal solution by obtaining the solution of the optimization problems of each case and comparing the value of the objective function. However, in some cases branched by $Y_{i,t}^c$ value does not satisfy the constraint that can trade only one type or fewer types in each day. To satisfy this constraint, we choose a type of products which can be traded in each day. Algorithm 2 shows the exhaustive search algorithm of a supply chain planning for multiple companies by using the DPPDS algorithm.

<caption>**Algorithm2** Exhaustive search algorithm</caption>

1: **Given** initial variables $X_{i,t}^c = 1, Y_{i,t}^c = 1$; for $c = 1, \dots, n, i = 1, \dots, p, t = 1, \dots, h$
2: **repeat**
3: &nbsp;&nbsp;&nbsp;&nbsp;flg = 0
4: &nbsp;&nbsp;&nbsp;&nbsp;computes $Z_{i,t} = Y_{i,t}^1 + \dots + Y_{i,t}^n$; for $i = 1, \dots, p, t = 1, \dots, h$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** more than two of $Z_{i,t} \ge 1$; for $t = 1, \dots, h$ **then** flg = 1
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** flg = 0
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $X_{i,t}^c = 0$; for $c = 1, \dots, n, i = 1, \dots, p, t = 1, \dots, h$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;adds constrains $S_{i,t}^c = S_{i,t-1}^c$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $Y_{i,t}^c = 0$; for $c = 1, \dots, n, i = 1, \dots, p, t = 1, \dots, h$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;adds constrains $S_{i,t}^c = 0$
11: &nbsp;&nbsp;&nbsp;&nbsp;computes $z$ by **Algorithm1**
12: &nbsp;&nbsp;&nbsp;&nbsp;**if** $z < \text{total cost}$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;total cost $\leftarrow z$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S_{i,t}^c \leftarrow S_{i,t}^c(k)$; for $c = 1, \dots, n, i = 1, \dots, p, t = 1, \dots, h$
15: &nbsp;&nbsp;&nbsp;&nbsp;changes value of $X_{i,t}^c, Y_{i,t}^c$ one by one; for $i = 1, \dots, p, t = 1, \dots, h$
16: **until** $X_{i,t}^c = 0, Y_{i,t}^c = 0$; for $c = 1, \dots, n, i = 1, \dots, p, t = 1, \dots, h$

$Z_{i,t}$ indicates product $i$ which can be traded on day $t$ and product $i$ can be traded when $Z_{i,t} \ge 1$. $S_{i,t}^c$ is a tentative optimal solution and total cost is a value of the objective function by $S_{i,t}^c$' value. We omit the cases not satisfying the constraint which companies can trade only one type or fewer types in each day in line 4, 5. Tentative optimal solution is updated if we obtain a better solution in line 12 ~ 14. We compute the cases from all $X_{i,t}^c$ and $Y_{i,t}^c$ are 1 to all $X_{i,t}^c$ and $Y_{i,t}^c$ are 0.

In this algorithm, we confirm that an optimal solution is derived. However, the number of computations becomes much larger. Therefore, we have to omit the computation of the cases overlapping constraints with other cases or not being able to obtain a feasible solution.

As the cases overlapping constraints with other cases, there are the cases which the trade volume on day $t$ and day $t-1$ are equal depending on the values of $Y_{i,t}^c$ and $Y_{i,t-1}^c$. For example, if we solve the case which $Y_{i,t}^c = 0, Y_{i,t-1}^c = 0, X_{i,t}^c = 1$, then we do not have to solve the cases which either $Y_{i,t}^c$ or $Y_{i,t-1}^c$ is zero and $X_{i,t}^c = 0$. When $Y_{i,t}^c = 0, Y_{i,t-1}^c = 0, X_{i,t}^c = 1$, the trade volume $S_{i,t}^c$ and $S_{i,t-1}^c$ are zero by a constraint which
the trade volume $S_{i,t}^c$ must be zero when $Y_{i,t}^c = 0$. If either $Y_{i,t}^c$ or $Y_{i,t-1}^c$ is zero and $X_{i,t}^c = 0$, the trade volume $S_{i,t}^c$ and $S_{i,t-1}^c$ must be zero by a constraint which the trade volume $S_{i,t}^c$ must be equal to $S_{i,t-1}^c$ when $X_{i,t}^c = 0$. Therefore, solving this case is same as solving the case which $Y_{i,t}^c = 0, Y_{i,t-1}^c = 0, X_{i,t}^c = 1$.

As the cases not being able to obtain a feasible solution, there are the cases which do not satisfy a constraint ensuring that prescribed trade volume must be traded depending on the values of $Y_{i,t}^c$. To satisfy the constraint that can trade only one type or fewer types in each day, we choose a type of products which can be traded in each day. We define the number of days which can trade product $i$ is $N_i$, then $N_i \times s_i^{max}$ is max trade volume of product $i$, $s_i^{max}$ is an upper limit of product $i$'s trade volume in each day. If $N_i \times s_i^{max}$ is less than $m_i$, a constraint ensuring that prescribed trade volume must be traded is not satisfied, $m_i$ is A product $i$'s prescribed trade volume. We omit the cases like this before the computations.

## 5 Computational experiments

To confirm the effectiveness of the proposed method, we obtain an optimal solution by using CPLEX. In optimization by CPLEX, not using a distributed optimization, we solve a supply chain planning for multiple companies as a total optimization problem. By numeral experiments, it is confirmed that we can obtain an optimal solution of a supply chain planning for multiple companies by the proposed method. Also, we compare the number of computations between exhaustive search algorithm and the proposed algorithm with the reduction of the computations. Table 1 shows the comparison of the number of computations between exhaustive search algorithm and the proposed algorithm. From the result, it is confirmed that the number of computations is significantly reduced, more than 99 percent in all cases. As the size of problem is larger, the reduction rate is higher. It is because that as the size of problem is larger, the proportion of the cases overlapping constraints with other cases is higher.

<table><caption>**Table 1.** The comparison of the number of computations between exhaustive search algorithm and algorithm reducing the computation.</caption><thead><tr><th></th><th>exhaustive search</th><th>reduction of the computation</th><th>reduction rate [%]</th></tr></thead><tbody><tr><td>case1</td><td>784</td><td>2</td><td>99.744898</td></tr><tr><td>case2</td><td>87,808</td><td>9</td><td>99.989750</td></tr><tr><td>case3</td><td>1,101,453,552</td><td>193</td><td>99.999982</td></tr><tr><td>case4</td><td>123,363,917,824</td><td>6,548</td><td>99.999994</td></tr><tr><td>case5</td><td>13,824,000</td><td>540</td><td>99.996093</td></tr><tr><td>case6</td><td>1,952,382,976</td><td>6,561</td><td>99.999664</td></tr><tr><td>case7</td><td>13,271,040,000</td><td>11,898</td><td>99.999910</td></tr><tr><td>case8</td><td>4,096,000</td><td>6</td><td>99.999854</td></tr><tr><td>case9</td><td>2,621,440,000</td><td>114</td><td>99.999996</td></tr><tr><td>case10</td><td>2,791,309,312</td><td>162</td><td>99.999994</td></tr></tbody></table>
It is confirmed that our proposed distributed optimization method can reduce the num-
ber of computations, however it is not enough to solve much larger problems. There-
fore, we need to continue to find the way to reduce the number of computations. The
values of constants influence on the number of computations, so we have to continue
to consider the influence of the value of constants on the optimality.

6 Conclusion

In this study, we examine the solution of optimization problems by the DPPDS algo-
rithm and propose the solution using an exhaustive search algorithm to solve a supply
chain planning for multiple companies including 0-1 variables. Also, we examine the
method reducing the computation while retaining optimality. As a result, we confirm
that we can obtain an optimal solution of the supply chain planning for multiple com-
panies by proposed method. Also, we confirm that the number of computations in the
proposed method can be reduced by the examined method. As a future work, we need
to examine the method to reduce the number of computations more while retaining
optimality. We also need to examine the influence on calculation time or optimality by
assessing the influence on the value of the objective function before computation and
omitting the case which cannot be expected an optimal solution.

References

1. T. Nishi, "Distributed optimization technique for supply chain management", The Japanese Society for Artificial Intelligence, Vol. 19, No. 5, pp. 571-578, (2004)

2. K. Sakurama, "Networked distributed optimization of massive systems", Journal of the Society of Instrument and Control Engineers, Vol. 56, No. 12, pp. 949-954, (2017)

3. T. Hatanaka, "Control of multi-agent systems – VI distributed optimization", Systems, Control and Information, Vol. 58, No. 3, pp. 124-131, (2014)

4. K. Sakurama, "Control of multi-agent systems – III consensus control (1)", Systems, Control and Information, Vol. 57, No. 9, pp. 386-396, (2013)

5. K. Sakurama, "Control of multi-agent systems – IV consensus control (2)", Systems, Control and Information, Vol. 57, No. 11, pp. 470-479, (2013)

6. N. Hayashi, M. Nagahara, "Control of multi-agent systems – II algebraic graph theory", Systems, Control and Information, Vol. 57, No. 7, pp. 283-292, (2013)

7. M. Zhu, S. Martínez, "On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods", IEEE Transactions on Automatic Control, Vol. 57, pp. 151-164, (2012)

8. T. Chang, A. Nedić, A. Scaglione, "Distributed constrained optimization by consensus-based primal-dual perturbation method", IEEE Transactions on Automatic Control, Vol. 59, pp. 1524-1538, (2014)

9. A. Nedić, A. Ozdaglar, P. A. Parrilo, "Constrained consensus and optimization in multi-agent networks", IEEE Transactions on Automatic Control, Vol. 55, pp. 922-938, (2010)

10. T. Nishi, R. Shinozaki, M. Konishi, "A distributed optimization system for supply chain planning among multi-companies using an augmented Lagrangian decomposition method", The Society of Instrument and Control Engineers, Vol. 40, No. 5, pp. 582-589, (2004)