Effectiveness of adaptive extragradient algorithms for network economics problems is demonstrated with the modified model of blood supply chain network. Informational system for comparing behavior of algorithms for solving variational inequalities is described. Described algorithms include adaptive modifications of extrapolation from the past, forwardbackward-forward and Tseng method. The blood supply chain model is a prominent example of more general perishable products delivery chain optimization problem. The provided software system enables users to edit model parameters, visualize networks, and solve pathbased cost minimization problems using a selected subset of these algorithms.
numerical experiments, optimization
Variational inequality (VI) is a powerful approach to modelling diverse set of problems, including, but not limited to, optimization and equilibrium problems [1-4]. Between other applications, last years they show promising results in some machine learning areas – especially for GANs and other adversarial techniques [5,6]. And, finally, a family of network economics problems could be naturally formulated as a VI. Such formulation was obtained for different kind of network economics problems in the series of papers by Anna Nagurney [7,8].
Problem of special interest is modelling a delivery chain of perishable products [9], where it’s unfeasible to store the product for a long time, and, as a result, product surplus in a demand point incurs serious discard charges. Moreover, every step of operation and transport of such kind of a product usually leads to some loss, also with corresponding discard charges. The similar model arises if we consider blood delivery supply chain, organized as sequential interaction of blood collection, processing and consuming facilities – from collection points to hospitals. Modelling of this problem for the structure of American Red Cross (ARC) was investigated in [10], with proposal of the VI formulation. Another VI model is used as part of blood supply chain optimization as bi-objective model in [11].
Intensive development of numerical algorithms for solving VI started from extragradient algorithm [12] and alternative algorithm [13] (now widely known as “extrapolation from the past”, or EFP, in machine learning area). As operator calculation and projection to feasible set can be really computationally expensive operations for medium to large sized problems, efforts have been made to build algorithms that require minimum necessary amount of such operations.
Also, VI solving algorithms often require a priory knowledge of the Lipschitz constant for the operator to determine algorithm step size – and that becomes a serious problem for applying them to real world problems, as calculating it could be complicated or almost impossible. To tackle this difficulty, adaptive versions of VI algorithms were proposed, that allow to modify step size dynamically during algorithm execution while preserving theoretical guarantee of the convergency.
2023 Copyright for this paper by its authors. CEUR
ceur-ws.org
Let’s us formulate the mathematical model of blood supply chain optimization, following [10].
Structure of the facilities and corresponding logistic can be schematically represented as the following graph:
In the graph above, edges represent different operations in the blood supply process – and corresponding model parameters, such as collection risks or operational and waste discard costs, are bound to the edges. Nodes represent facilities taking part in the supply chain. The first node is added for the model to be concise, and has no specific meaning – but can be considered as a top-level organization structure unit, e.g., Red Cross regional division, as in [10].
The process starts with blood collection. Specifics of the collection layer is that edges have risk parameter and corresponding costs associated with it, as the process itself is risky – donors can miss appointments because of many reasons – for example, heavy rain greatly decreases visits number. The next stages are testing for infection and contamination, separation of components (plasma and red cells), and storing components in special facilities. In the graph above, blood centers, component labs, and storage facilities are shown as a single layer to make drawing and model description clearer. Actually, it’s often the real case – and even if they are really separated, it does not incur significant model changes, as all edges have the same type of associated parameters.
Mathematical properties of the shipment stage edges also coincide with parameters from the testing, processing, and storage stage – but physical facilities are different, so we put them in a separate layer in the graph.
And the last, distribution, layer, corresponds to the last-mile delivery of the blood to demand points, which usually are hospitals. These nodes have a specific role in the model – a stochastic demand and corresponding surplus and shortage penalties are associated with them.
Let’s denote c, , , ℎ – number of each type of nodes: collection, testing/processing/storage, shipment and demand (hospitals). And let’s denote set of all edges as { }, = 1. . , where is the total number of edges (links) in our supply chain network. And let’s denote in-flow on the edge as (we will describe loss and out-flow later). Edge flows together form a vector = ( 1, … , ).
The operations with the blood itself have costs, which also can be associated with the edges. Let’s denote ( ) – unit operational cost on edge (it’s dependent on the flow). Then the total operational cost on the edge is ⋅ ( ).
Let’s denote = { }, = 1. .
– set of all simple paths from dummy source node to every demand point, where is a total number of such paths. Initial flow on path = { 1 , 2, … , } is denoted as ≥ 0, and it is the initial flow of the first edge of the path, which is always edge between the source node and a blood collection node. Our goal is to find optimal path flows vector = ( 1, … , ). The first obvious property of the feasible set is
xi ≥ 0, = 1. .
Each stage of blood processing could incur some losses – for example, small part of blood is taken to test facility and discarded afterward. Let’s associate loss multiplier ∈ (0,1] with every edge , = 1. . . We interpret it the next way: if an edge incoming flow (in-flow) is , then it’s outcome (outflow) is . In this paper we assume, that multipliers are independent of link flow (thou it will be interesting to consider depending case in the future).
Losses during blood processing incur waste disposal cost. It can be significant for such kind products, as blood – so it needs to be included into the model. Waste amount for the edge depends only on the edge flow and is equal to (1 − ) , so waste discard function is also flow dependent – let’s denote unit discard cost as ( ), and the total one will be ⋅ ( ).
In terms of path flows, total loss on the path can be calculated as = ∏ : ∈ , = 1. . . As a result, if initial flow on the path is , corresponding final path flow is , ∀ = 1. . . And for each destination node , = 1. . ℎ, let’s denote the supply amount as . Obviously, we have = ∑ ∈ , assume we
know ( ) = ( < ) = ∫ ( ) .
0 it’s
something like (∑ =ℎ1 where is a set of all paths from source node to demand node . At the same time, real demand is stochastic – we cannot know exact blood demand in a hospital for every moment in future. But we probability density function ( ) and probability distribution We are interested in minimizing expected difference between and – so, it’s tempting to use ( − )2) as the loss function. But consequences of blood shortage and surplus are essentially different, and it makes sense to consider them separately in the model.
Let’s denote blood shortage (undersupply) at the demand node as and blood surplus (oversupply) at the same node as 0, ≤ 0, ≥ = { − , > = max{0, − }, = {
− , < = max{0, − }.
Now corresponding part of the cost function for the model can be formulated the next way: ∑ ℎ =1 ( (
) + ( ))
shortage and surplus correspondingly.
where
, are the penalties (costs), and ( ), ( ) – mathematical expectations of blood
(
And, finally, it’s preferrable for the model to count for the blood collection risks. These risks are associated with the first layer edges only, and let’s assume they are also functions of the flow. Let’s denote risks as ( ), = 1. . . Risk minimization and cost minimization are different criteria, so in the cost function they can be weighted differently – let be the weight for risk part, and let cost part have weight of one.
It is worth making remarks about edge indices.
Remark 1: As the blood collection process has sequential stages, it’s always possible to enumerate edges in such a way, that any edge from a later stage has an index greater than the index of any other edge from an earlier stage. E.g., an index of a distribution edge is always greater than an index of a collection edge. We assume such kind of numeration in all following reasoning to simplify the model formulation. As a result, edge indices in any path ∈ make an increasing sequence.
Taking into account the remark above, each edge flow can be calculated by path flows: = ∑ : ∈
, where = ∏ : ∈ , < – product of all loss multipliers of edges, which are preceding edge in the path .
Remark 2: We have exactly collection edges on the first layer, so all edges , = 1. . are collection edges (it gives us a simple way to write risk component of the cost function below). 2.3.
Now we can formulate the supply chain network optimization problem as minimization of the Φ( ̅) = ∑ =1 ( ( ( ) + ( ))) + ∑ ℎ
=1 ( ( ) + ( )) +
with regards to (
∑
: ∈ , =1..
( )
where is expressed in terms of path flows with (
The problem can be formulated as a classic variational inequality. We need to find ∗ ∈ such, that where = + and ( − ∗, Φ
( ∗)) ≥ 0 ∀x ∈ Φ
: ∈ = ∑ [ ( ) + ( ) + ( ′ ( ) + ′ ( ))] + + ( ( ( ) − 1) + (
( )))
+ ( ( ) + ′ (
) ⋅ )
where and are indices of the first and the last edge in the path . Again, here is expressed in
terms of path flows, using equality (
Variational inequality (
At first, we need to introduce some notation. Let be real Hilbert space with dot product ( , ) and induced norm || ⋅ ||, be a non-empty convex closed subset of , and let’s ∶ → be a mapping.
Definition 1: Mapping ∶
→ is called monotone, if Definition 2: The following problem is called variational inequality (VI): (
− , − ) ≥ 0 ∀x, y ∈ H
find ∈ : ( , − ) ≥ 0 ∀y ∈
(
Further algorithm formulations will be done for problem (
Definition 3: The mapping :
→ is called metric projection to closed convex subset ⊂ , if ‖PCx − x‖ = min ‖ − ‖.
z∈C
The main idea behind the big family of projection methods for solving (
− ), where step size > 0.
kind of algorithms.
procedure:
But monotonicity of is not enough for the procedure above to converge to the solution of the VI. It
needs strong monotonicity or inversely strong monotonicity (co-coercivity). So, more advanced
algorithms were proposed, which do not require extra assumptions on – especially the extragradient
Historically the first extragradient algorithm, proposed in [12], has the next computational
{ = ( − )
+1 = ( − )
,
It was proved, that for monotone and continuous ∶
→ the sequence { }, generated by
procedure above, converges to the solution of (
Later a lot of improvements and modifications were done by different authors – to avoid extra calculations, prove convergence under weaker assumptions, drop the requirement to know the Lipschitz constant in advance, or use Bregman divergence instead of Euclidean distance to speed up projection – see [14-20]. Part of such results were obtained by the research group from Taras Shevchenko National University of Kyiv, to which the current paper's authors belong. One more important direction is development of parallelized versions of VI algorithms, as in [21]. 3.2.
Let us describe other selected algorithms, which are implemented as part of the system.
hyperplane projection was proposed.
the next form:
calculation on every step.
in [15]. The step calculation is:
in case of linear mapping , and
(
The first method was proposed in [13] in 1980, and gained popularity nowadays under the name extrapolation from the past. It has the next step calculation procedure: where convergence is proved with ∈ (0, 1
3 one mapping calculation on the step, but with two projections. The weak convergence in infinitedimensional space was proved in [20], where also modification with single projection and auxiliary ) for finite dimensional space. This procedure uses only
Another interesting method was proposed in [14] by P. Tseng in year 2000. The step formula has
where weak convergency is proved for ∈ (
(2 − −1 ))
+1 = ( − − ( − −1 ))
in generic case. The algorithm converges with ∈ (
All methods above in their original form require knowledge of Lipschitz constant of the mapping . Let’s describe the adaptive modifications, where step size will be modified during algorithm run to achieve convergency without using a priori known , which can be hard to calculate.
Here is the adaptive version of extrapolation from the past algorithm [17]. At first, we select
0, 0 ∈ , ∈ (
3 +1 = ( − ), +1 = ( +1 − ),
ℎ
= ( − ), +1 = − (
− ), with a stop condition +1 =
= . 1 > 0. And starting from = 1 we have:
Tseng algorithm can also be modified for adaptive step size calculation [18]. Let 1 ∈ , ∈ (
And here is an adaptive modification of Malitsky and Tam algorithm [17]. Let 0, 1 ∈ , 0, 1 > +1 = { { , ‖ +1 − ‖ ℎ } . ‖ +1 − ‖ , +1 ≠ ,
Remark 3: For all adaptive versions above, update procedure does not incur extra mapping calculation – all values will be cached and reused in algorithms implementation, so number of mapping calculations and projections is the same for both adaptive and stationary variants.
To allow solving blood supply chain optimization problem (
Basically, all VI based problems have common parts, which are used by algorithms – and the same is true for extragradient algorithms family. A problem should have constraints with projecting operation, and provide the mapping calculation routine. On the other side, big part of an algorithms’ parameters is common for all algorithms – e.g., starting point or initial step size. And some parameters are more specific – like the second starting point or the adaptive step size calculation multiplier. That is reflected inside the system with two class hierarchies – for algorithms and problems correspondingly.
The simplified schema is shown on the Figure 2. Test suite is responsible for running selected set of algorithms for the problem and saving run history (time and all problem and algorithm parameters on every iteration). It also interacts with graphing component (now shown on the figure), to draw convergency rate graphs according to different metrics.
The system2 contains Python 3 implementation of algorithms mentioned above, both adaptive and static modifications. Also, more than ten test problems implemented withing the architecture above, from simple test problems to more real problems, such as PageRank calculation or traffic network equilibrium search.
The functionality can be used from code and a command line (selecting problem, algorithms set and run parameters), which is convenient enough for researchers with python programming skills. For blood supply chain problem, we added visual interface for problem editing, running the algorithms and obtaining the results. The problems selector and editor UI (Figure 3 below) is implemented as a web application using Plotly Dash framework [22]. 2 Source code repository: https://github.com/compmath-sdeni/vi-alg-suite
Figure 4 shows, how calculation results are presented in web version of UI. For now, output includes convergence rate graph (iteration number vs. distance between approximate solutions) and textual information with final results, timing and run parameters. For problems with known solution graph can be switched to iteration vs. distance to real solution, and horizontal axis can be switched to calculation time instead of iteration number. Within textual information we also have specific characteristic of the problem, which are defined withing the problem class – for example, here we have supply amounts for each hospital. Under the hood, the system also saves detailed run history for every algorithm (in tabular format), so a researcher can monitor state and behavior on every iteration.
It can be seen, that in terms of precision after 1000 iterations adaptive algorithm of Tseng slightly
outperforms EFP and Malitsky-Tam (MT) on this test problem. At the same time, from numbers we
see, that time for 1000 iterations of Tseng is two times bigger (0.64 sec. vs 0.32 sec.) compared to both
EFP and MT – which is expected, as in this problem projection is very cheap ( = +), but the mapping
computation is very expensive (because of complicated derivative in (
It should be noted, that timing from the single run is not a stable measure of performance – but similar relative timings were obtained when running many experiments repeatedly and averaging the results. Calculations were done on Ubuntu Linux machine with Intel Core i7-1065G7 1.3 – 3.9GHz and 16GB RAM with python 3.10, numpy 1.24.3.
Considered adaptive versions of extragradient algorithms allow effectively solving blood supply chain optimization problem, without need of complicated handcrafting of step size and starting parameters. Implementation-friendly model formulation allows achieving reasonable performance and can be used for other problems of network economics family. And developed software system for applying VI algorithms to a different kind of problems considerably decreases time needed to both to get a solution for suitable problem and to conduct numerical experiments and compare behavior of algorithms from extragradient family. As further development directions, it is worth adding other types of algorithms, which are suitable for some subset of problems, and add a possibility for researchers to more easily plug in own algorithms and problems to the system.
This work was supported by the Ministry of Education and Science of Ukraine (project "Computational algorithms and optimization for artificial intelligence, medicine and defense", 0122U002026) and Vodafone Business machine learning and data science internship program.