An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems

Yang, Lu; Yang, Zhouwang Article An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems Operations Research Perspectives Provided in Cooperation with: Elsevier Suggested Citation: Yang, Lu; Yang, Zhouwang (2025) : An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems, Operations Research Perspectives, ISSN 2214-7160, Elsevier, Amsterdam, Vol. 14, pp. 1-13, https://doi.org/10.1016/j.orp.2025.100331 This Version is available at: https://hdl.handle.net/10419/325808 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by-nc-nd/4.0/ Contents lists available at ScienceDirect Operations Research Perspectives journal homepage: www.elsevier.com/locate/orp An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems✩ Lu Yang , Zhouwang Yang∗ University of Science and Technology of China, Hefei, PR China ARTICLE INFO Dataset link: https://github.com/lufizyang/Dat a-and-Code-for-CCNFP Keywords: Network flow Non-convex problem Approximation algorithm Regional first-order information Interval reduction ABSTRACT As production scales up, transportation networks increasingly involve nonlinear costs, leading to the concave cost network flow problem (CCNFP), which is notably challenging due to its nonlinearity. Existing nonlinear programming methods addressing the CCNFP often suffer from low efficiency and high computational cost, limiting their practical application. To overcome these limitations, this paper proposes the Successive Derivative Shortest Path (SDSP) algorithm, an efficient approach that combines a sequential linear approximation framework with regional first-order information of the objective function. By integrating regional first-order information and employing an interval reduction mechanism, the SDSP algorithm effectively avoids premature convergence to suboptimal solutions, thereby achieving higher-quality solutions. Numerical experiments, including parameter selection, validation, and comparative analysis, demonstrate that the SDSP algorithm outperforms existing methods in terms of both solution quality and convergence speed. This research offers a robust and efficient solution for the CCNFP, with potential applications in various fields, including logistics and supply chain networks, where concave cost network flow issues are common. 1. Introduction As societal demands evolve and production processes grow in complexity, the need for optimizing resource allocation to maximize economic efficiency has become increasingly critical. The minimumcost flow problem [1], a foundational model in optimization and resource allocation, has seen broad applications across diverse practical fields [2–4]. However, endogenous factors in real-world applications often introduce nonlinear cost structures, such as economies of scale [5] and risk-related costs [6], making these problems challenging for traditional minimum-cost flow algorithms [7–10] to address effectively. Consequently, concave cost network flow problems have emerged as a central focus within the optimization research community [11–13]. The Concave Cost Network Flow Problem (CCNFP) is a specialized variant of the minimum-cost flow problem1characterized by concave objective functions. Solving the CCNFP aims to identify feasible flows in a network that minimize the overall objective value. The inclusion of concave objectives enhances the CCNFP’s modeling flexibility, making it applicable to a wide range of scenarios in transportation [14–16] and warehousing [17,18]. For instance, the most reliable path ✩Funding: The work is supported by the NSF of China (Nos. 92270205, 12301659, 12171453), the National Key R&D Program of China (Nos. 2022YFA1005201, 2022YFA1005202, 2022YFA1005203), and the Major Project of Science and Technology Innovation Tackling Plan of Anhui Province (No. 202423e09050003). ∗Corresponding author. E-mail addresses: [email protected] (L. Yang), [email protected] (Z. Yang). 1In this article, the term ‘‘minimum-cost flow problem’’ refers specifically to its form with linear objective functions. problem [19] is essential for determining optimal travel routes and departure times, with reliability quantified by the standard deviation of travel time—a nonlinear component in the objective function. In warehousing, the joint location-inventory problem [6] addresses demand fluctuation risks by minimizing the standard deviation of product demand to reduce reliability costs. While concave costs provide richer modeling capabilities, they also introduce significant computational challenges, especially given the increasing complexity and scale of network topologies. The CCNFP is known to be NP-hard [18], with complexity stemming from the fact that minimizing a concave cost over a convex feasible region does not guarantee finding a global optimum [20]. This NP-hard nature presents challenges in developing efficient algorithms, particularly when attempting to find optimal or near-optimal solutions within a reasonable time frame. Consequently, research into high-quality, efficient algorithms for solving the CCNFP is essential for both theoretical advancements and practical applications. Existing research has yet to develop direct algorithms specifically for solving the CCNFP. Current approaches often simplify the network structure or treat it as a general nonlinear programming problem. The https://doi.org/10.1016/j.orp.2025.100331 Received 23 November 2024; Received in revised form 19 January 2025; Accepted 11 February 2025 Operations Research Perspectives 14 (2025) 100331 Available online 19 February 2025 2214-7160/© 2025 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/bync-nd/4.0/ ). L. Yang and Z. Yang Nomenclature 𝛼Lower bound of sampling interval 𝛽Upper bound of sampling interval 𝑤Average derivative value 𝜅Unbalanced state of node 𝜋Potential function 𝑥Flow on edge Acronyms CCNFP Concave cost network flow problem AugLag Augmented Lagrange function algorithm Penalty Penalty function algorithm SDSP Successive derivative shortest path SGSP Successive gradient shortest path SLSQP Sequential least square programming SSP Successive shortest path ARE Average relative error MRE Maximum relative error Parameters 𝐺Graph/network structure  𝐺Residual graph 𝑉 , 𝑆 , 𝐷Node set 𝐸 , 𝐸Edge set 𝑣, 𝑙 , 𝑘Node 𝑒Edge 𝑢Finite capacity on edge 𝑟Residual capacity on  𝐺 𝑏Supply on node 𝑐Cost function on edge 𝑃Path 𝑎Interval reduction coefficient 𝑀Maximum iteration count 𝑛𝑠Number of sampling points concave cost transportation problem, for instance, is a special case of the CCNFP formulated on a bipartite graph [11]. Additionally, some studies have focused on variants of the CCNFP with single-source, uncapacitated edges [20,21]. However, these simplified graph structures overlook the complexities inherent in real-world networks, limiting the practical applicability of such algorithms. For example, bipartite graphs assume a structure consisting solely of sources and sinks, an assumption that rarely holds in realistic settings. Even with these simplifications, solutions to such cases typically rely on metaheuristic methods [21–24], which often require substantial time to find suboptimal solutions without guarantees of convergence, even for moderately sized problems. Furthermore, since the CCNFP is inherently a nonlinear programming problem, established nonlinear programming algorithms, such as augmented Lagrangian methods and sequential least squares programming [12,25], can be applied. However, these methods face challenges due to the lack of theoretical guarantees for finding exact solutions and their typically prolonged solving times, making them less suitable for large-scale or time-sensitive applications. In this paper, we propose a novel sequential reduction algorithm, the Successive Derivative Shortest Path (SDSP) algorithm, which combines the Successive Shortest Path (SSP) algorithm [10] with first-order information of concave objective functions. While SSP is an exact algorithm for solving minimum-cost flow problems, it cannot be directly applied to the CCNFP. To address this, we approximate the concave cost function in the CCNFP by utilizing regional first-order information, thereby enabling an approximate solution to the problem. This approach allows us to establish a sequential process that generates a series of minimum-cost flow subproblems, each step incrementally optimizing the CCNFP solution. Additionally, by progressively reducing the interval size for calculating first-order information, the SDSP algorithm ensures convergence and mitigates the risk of premature convergence to suboptimal solutions. Theoretical analysis and validation experiments confirm that the sequential reduction process effectively directs the algorithm toward higher-quality solutions. Comparisons with other algorithms demonstrate the superior solution quality and convergence rate achieved by the SDSP algorithm. The remainder of this paper is organized as follows. Section 2 formally defines the concave cost network flow problem (CCNFP). Section 3presents the proposed algorithm in detail, followed by Section 4, which describes and discusses the simulation results. Finally, Section 5 concludes the paper with a summary of the findings and implications. 2. Formulation of problems The Concave Cost Network Flow Problem (CCNFP) is a nonlinear programming problem formulated on a graph structure with a concave objective function and subject to linear constraints. Let 𝐺(𝑉 , 𝐸)be a directed graph with a set of 𝑛nodes 𝑉= {𝑣𝑖}𝑛 𝑖=1 and a set of 𝑚directed edges 𝐸. Each node 𝑣𝑖has an associated supply 𝑏𝑖, which is used to partition the node set 𝑉into the three subsets: the source node set 𝑆= {𝑣𝑖∈𝑉∣𝑏𝑖>0}, the intermediate node set 𝑉𝑖𝑛 = {𝑣𝑖∈𝑉∣𝑏𝑖= 0}, and the sink node set 𝐷= {𝑣𝑖∈𝑉∣𝑏𝑖<0}. Each edge 𝑒𝑖𝑗 represents a directed connection from node 𝑣𝑖to node 𝑣𝑗.𝑥𝑖𝑗 is a non-negative real number that denotes the amount of flow through the edge 𝑒𝑖𝑗 , typically subject to a finite capacity 𝑢𝑖𝑗 . In the CCNFP, each edge 𝑒𝑖𝑗 has an associated concave cost function 𝑐𝑖𝑗 (𝑥𝑖𝑗 ), which depends on the flow 𝑥𝑖𝑗 . Similar to the minimum-cost flow problem, the Concave Cost Network Flow Problem (CCNFP) also enforces that the sum of the net flow and supply at each node equals zero, ensuring flow conservation across the network. This constraint can be written as ∑ 𝑗∈𝑉− 𝑖 𝑥𝑗 𝑖−∑ 𝑗∈𝑉+ 𝑖 𝑥𝑖𝑗 +𝑏𝑖= 0,∀𝑖∈𝑉(1) where 𝑉− 𝑖= {𝑗∈𝑉∶𝑒𝑗 𝑖∈𝐸}and 𝑉+ 𝑖= {𝑗∈𝑉∶𝑒𝑖𝑗 ∈𝐸}. Additionally, the flow value on each edge is constrained within the range from zero to its capacity, i.e., 0⩽𝑥𝑖𝑗 ⩽𝑢𝑖𝑗 . A solution that satisfies both of these constraints is a feasible solution to the CCNFP. Thus, the concave cost network flow problem can be formulated as min 𝑥𝐶(𝑥) =∑ 𝑒𝑖𝑗 ∈𝐸 𝑐𝑖𝑗 (𝑥𝑖𝑗 ) s.t. ∑ 𝑗∈𝑉− 𝑖 𝑥𝑗 𝑖−∑ 𝑗∈𝑉+ 𝑖 𝑥𝑖𝑗 =𝑏𝑖,∀𝑖∈𝑉 0⩽𝑥𝑖𝑗 ⩽𝑢𝑖𝑗 ,∀𝑒𝑖𝑗 ∈𝐸 (2) The formulation of CCNFP is a generalized definition of the network flow problems when Model (2) does not restrict its objective function type. The minimum-cost flow problem arises as a special case when the objective function simplifies to a linear function passing through the origin. In cases where the linear objective exhibits jump discontinuities at the origin, the problem transforms into a fixed-charge network flow problem [26]. The constraints are identical, establishing an equivalence in the feasible domains between the CCNFP and the minimum-cost flow problem on the same graph structure. This forms the basis for constructing a sequence of minimum-cost flow problems to approximate the CCNFP. The concepts outlined in the definition of CCNFP have direct correspondences with real-world scenarios. In logistics and transportation, the storage points of goods correspond to the source nodes in the graph, the demand points for goods correspond to the sink nodes, and the Operations Research Perspectives 14 (2025) 100331 2 L. Yang and Z. Yang transit points correspond to the intermediate nodes. The transportation routes naturally establish connections between these nodes. Goods transportation involves moving goods from storage points to demand points, often characterized by multi-sourcing and multi-tier transportation tasks. Additionally, large-scale or long-term transportation tasks, due to decreasing marginal costs [27], result in objective functions exhibiting concave characteristics. Therefore, CCNFP is particularly well-suited for application in such scenarios. 3. Sequential reduction algorithm In this section, we detail the SDSP algorithm, covering the foundational principles of the SSP algorithm and the sequential reduction mechanism that distinguishes SDSP. 3.1. Successive shortest path The SSP algorithm finds the optimal solution for the minimumcost flow problem by iteratively searching for the shortest path that balances supply and demand nodes between source and sink nodes in the residual graph. The residual graph  𝐺(𝑉 , 𝐸)is constructed based on 𝐺(𝑉 , 𝐸)by adding the reverse edges corresponding to each original edge in 𝐸. The set of reverse edges is denoted as 𝐸′= {𝑒′ 𝑗 𝑖∶𝑒𝑖𝑗 ∈𝐸}, where the edges 𝑒′ 𝑗 𝑖and 𝑒𝑗 𝑖are not the same. Therefore, the edge set  𝐸can be represented as  𝐸=𝐸∪𝐸′. During the solving process, flows on reverse edges {𝑥𝑒}𝑒∈𝐸′represent the algorithm’s ability to backtrack previously allocated flows. The unit cost of the reverse edge is the opposite number of the unit cost of the original edge, and the capacity of the reverse edge is the allocated flow on the original edge. Thus, the residual capacity in  𝐺(𝑉 , 𝐸)can be written as {𝑟𝑒=𝑢𝑒−𝑥𝑒, 𝑒∈𝐸 𝑟𝑒′=𝑥𝑒, 𝑒′∈𝐸′(3) where the residual capacity of reverse edges 𝑒′is the allocated flow 𝑥𝑒 on the original edge. SSP identifies the shortest path between a pair of source and sink nodes within the current residual graph, assigns the maximum feasible flow in each iteration, and repeats the above operation until all nodes satisfy the conservation condition. The unbalanced state 𝜅(𝑖), which characterizes the change of node supply in iterations, is defined as 𝜅(𝑖) =𝑏(𝑖) +∑ 𝑒∈𝐸− 𝑖 𝑥𝑒−∑ 𝑒∈𝐸+ 𝑖 𝑥𝑒,for all 𝑖∈𝑉(4) where 𝐸− 𝑖= {𝑒𝑗 𝑖∈𝐸∶𝑣𝑗∈𝑉} ∪ {𝑒′ 𝑗 𝑖∈𝐸′∶𝑣𝑗∈𝑉}, 𝐸+ 𝑖= {𝑒𝑖𝑗 ∈𝐸∶ 𝑣𝑗∈𝑉} ∪ {𝑒′𝑖𝑗 ∈𝐸′∶𝑣𝑗∈𝑉}. SSP introduces the potential function 𝜋(⋅) to eliminate the impact of negative costs in solving SSP and establishes a transformation from the edge cost 𝑐𝑒to the equivalent cost 𝑐𝜋 𝑒as 𝑐𝜋 𝑒𝑖𝑗 =𝑐𝑒𝑖𝑗 −𝜋(𝑖) +𝜋(𝑗)(5) where 𝑐𝑒𝑖𝑗 is the unit cost of edge 𝑒𝑖𝑗 ∈ 𝐸. In the SSP algorithm, the initial conditions are set as 𝑥𝑒= 0,∀𝑒∈ 𝐸 and 𝜋(𝑖) = 0,∀𝑣𝑖∈𝑉. Each node’s imbalance 𝜅(𝑖)is initialized to 𝑏(𝑖) for all 𝑣𝑖∈𝑉, forming the unbalanced node sets 𝑆=𝑣𝑖∶𝜅(𝑖)>0 and 𝐷=𝑣𝑖∶𝜅(𝑖)<0. SSP then selects a source 𝑘from set 𝑆and a sink 𝑙from set 𝐷, identifies all shortest paths from 𝑘to other nodes 𝑣𝑗∈𝑉, and calculates the path cost 𝑃𝑘𝑗 as 𝑑(𝑗) =∑𝑒∈𝑃𝑘𝑗 𝑐𝑒. Each node’s potential function 𝜋(𝑖)is updated based on the value 𝑑(𝑖)as 𝜋(𝑖) =𝜋(𝑖) −𝑑(𝑖),∀𝑣𝑖∈𝑉(6) Using the maximum feasible flow 𝛿on the shortest path 𝑃𝑘𝑙, the flow values for all edges on 𝑃𝑘𝑙 are updated by 𝑥𝑒={𝑥𝑒+𝛿 𝑒∈𝑃𝑘𝑙 𝑥𝑒𝑒∈ 𝐸∖𝑃𝑘𝑙 (7) where 𝛿= min[𝜅(𝑘),−𝜅(𝑙),min{𝑟𝑒∶𝑒∈𝑃𝑘𝑙}]. The residual capacity 𝑟𝑒, source set 𝑆, sink set 𝐷, and equivalent costs 𝑐𝜋 𝑒are then updated accordingly. Throughout the solving process, the positive value of 𝛿 ensures that SSP terminates after a finite number of steps, achieving a balanced state for all nodes. At the end, SSP yields the optimal solution to the minimum-cost flow problem. The full SSP process is outlined in Algorithm 1. Algorithm 1Successive Shortest Path Algorithm Input: Residual graph  𝐺(𝑉 , 𝐸), vector 𝐛 Output: Optimal solution 𝐱∗ 1: Initialization: 𝑥𝑒= 0,∀𝑒∈ 𝐸;𝜋(𝑖) = 0, 𝜅(𝑖) =𝑏(𝑖),∀𝑣𝑖∈𝑉. 2: 𝑆= {𝑣𝑖∶𝜅(𝑖)>0},𝐷= {𝑣𝑖∶𝜅(𝑖)<0} 3: while 𝑆≠∅do 4: Select nodes 𝑘∈𝑆and 𝑙∈𝐷 5: Calculate 𝑑(𝑗) = min 𝑃𝑘𝑗 {∑ 𝑒∈𝑃𝑘𝑗 𝑐𝑒∶𝑃𝑘𝑗 ⊂ 𝐸},∀𝑣𝑗∈𝑉 6: Update 𝜋(𝑖) =𝜋(𝑖) −𝑑(𝑖),∀𝑣𝑖∈𝑉 7: Compute 𝛿= min[𝜅(𝑘),−𝜅(𝑙),min{𝑟𝑒∶𝑒∈𝑃𝑘𝑙 }] 8: Update flows: 𝑥𝑒=𝑥𝑒+𝛿 ,∀𝑒∈𝑃𝑘𝑙 9: Update 𝑟𝑒:𝑟𝑒={𝑟𝑒−𝛿∀𝑒∈𝑃𝑘𝑙 𝑟𝑒+𝛿∀𝑒∈𝑃′ 𝑘𝑙 ⊳ 𝑃′ 𝑙 𝑘is the reverse path of 𝑃𝑘𝑙. 10: Update 𝜅(𝑘) =𝜅(𝑘) −𝛿,𝜅(𝑙) =𝜅(𝑙) −𝛿 11: if 𝜅(𝑘) = 0then 12: Remove node 𝑘from 𝑆 13: end if 14: if 𝜅(𝑙) = 0then 15: Remove node 𝑙from 𝐷 16: end if 17: Update 𝑐𝜋 𝑒:𝑐𝜋 𝑒𝑖𝑗 =𝑐𝑒𝑖𝑗 −𝜋(𝑖) +𝜋(𝑗),∀𝑒𝑖𝑗 ∈ 𝐸 18: end while 19: return 𝐱∗= {𝑥𝑒−𝑥𝑒′}𝑒∈𝐸 3.2. Successive derivative shortest path The SSP algorithm is unsuitable for solving CCNFP because the flow allocation in each iteration disrupts the order of edge costs, leading to inconsistencies in the shortest paths before and after allocation. Recognizing these limitations of SSP for CCNFP, this subsection describes the SDSP algorithm, which approximates the solution to CCNFP by iteratively solving a series of minimum-cost flow models. SDSP constructs an approximate minimum-cost flow model for CCNFP in each iteration, using the first-order information of the concave objective function to create a linear approximation cost. Proposition 1 provides theoretical support, showing that the optimal solution of the approximate model is consistently superior in objective value to the previous feasible solution when the first-order information is set to the gradients at the previous solution. However, the linear approximation based on the gradients leads the algorithm to converge to a suboptimal solution, with the objective value highly dependent on the initial feasible solution chosen. To address this, SDSP constructs regional first-order information by averaging derivative values of sample points within a given interval and gradually reduces the sampling interval to approach the gradient, allowing SDSP to converge to an approximate solution closer to the optimal solution of the original problem. Proposition 1. Given a feasible solution 𝑥0of the original problem (2), the approximate cost is generated by the gradients of the original objective function at 𝑥0. The gradients are denoted as ∇𝐶(𝑥0) = (… , 𝑐′ 𝑒(𝑥0 𝑒),… ). The objective of the approximate minimum-cost flow model is  𝐶(𝑥) = ∑𝑒∈𝐸𝑐′ 𝑒(𝑥0 𝑒)⋅𝑥𝑒. Then, the optimal solution of the approximate model 𝑥1 satisfies that 𝐶(𝑥1)⩽𝐶(𝑥0) In other words, solution 𝑥1improves upon 𝑥0in objective value when 𝑥1≠ 𝑥0. Operations Research Perspectives 14 (2025) 100331 3 L. Yang and Z. Yang Proof. Since the feasible domains of CCNFP and the minimum-cost flow problem are the same, 𝑥1is the feasible solution of CCNFP. By the first-order condition of the concave function, the original objective 𝐶(𝑥)satisfies that 𝐶(𝑦)⩽𝐶(𝑥) + ∇𝐶(𝑥)𝑇(𝑦−𝑥) Thus, the difference between objectives at solutions 𝑥1and 𝑥0satisfies 𝐶(𝑥1) −𝐶(𝑥0)⩽∇𝐶(𝑥0)𝑇(𝑥1−𝑥0) = 𝐶(𝑥1) − 𝐶(𝑥0) ⩽0 Equality holds if and only if 𝑥0is the optimal solution of the approximate model, that is, 𝑥1=𝑥0.□ In the graph 𝐺(𝑉 , 𝐸), let [𝛼𝑒, 𝛽𝑒]represent the sampling interval for edge 𝑒, and let 𝑛𝑠denote the number of sampling points. The following formula yields the average derivative value 𝑤𝑒under equidistant sampling: 𝑤𝑒=1 𝑛𝑠 𝑛𝑠 ∑ 𝑖=1 𝑐′ 𝑒(𝛼𝑒+ (𝑖− 1) ⋅𝛥𝑒),where 𝛥𝑒=𝛽𝑒−𝛼𝑒 𝑛𝑠− 1(8) Considering 𝑤𝑒as the unit cost on edge 𝑒, the constructed approximation model can be solved using SSP. In each iteration of SDSP, the algorithm solves the approximate model to obtain a feasible solution 𝑥(𝑘) 𝑒and then updates the lower and upper bounds of the sampling intervals for the next iteration. The updates for the interval’s bounds are as follows: 𝛼(𝑘+1) 𝑒= max {𝑥(𝑘) 𝑒−1 2⋅𝑎⋅(𝛽(𝑘) 𝑒−𝛼(𝑘) 𝑒),0}, 𝛽(𝑘+1) 𝑒= min {𝑥(𝑘) 𝑒+1 2⋅𝑎⋅(𝛽(𝑘) 𝑒−𝛼(𝑘) 𝑒), 𝑢𝑒}, (9) where 𝑎∈ (0,1) is the interval reduction coefficient, controlling the extent of reduction in each iteration. The algorithm iteratively performs this process until the optimal solution of the approximate model remains unchanged from the previous iteration. The details of SDSP are presented in Algorithm 2. Algorithm 2Successive Derivative Shortest Path Input: Graph 𝐺(𝑉 , 𝐸); Objective and derivative functions 𝑐𝑒(𝑥𝑒), 𝑐′ 𝑒(𝑥𝑒); Number of sampling points 𝑛𝑠 Output: Flows {𝑥𝑒}𝑒∈𝐸 1: Initialize {𝑤(1) 𝑒}𝑒∈𝐸and let [𝛼(1) 𝑒, 𝛽(1) 𝑒] = [0, 𝑢𝑒] 2: for 𝑘= 1to 𝑀do 3: 𝑥(𝑘) 𝑒= SSP(𝐺,{𝑤(𝑘) 𝑒}) 4: if |𝑐𝑒(𝑥(𝑘) 𝑒) −𝑐𝑒(𝑥(𝑘−1) 𝑒)|< 𝜖 ,∀𝑒∈𝐸then 5: break 6: end if 7: 𝛼(𝑘+1) 𝑒= max {𝑥(𝑘) 𝑒−𝑎⋅(𝛽(𝑘) 𝑒−𝛼(𝑘) 𝑒),0} 8: 𝛽(𝑘+1) 𝑒= min {𝑥(𝑘) 𝑒+𝑎⋅(𝛽(𝑘) 𝑒−𝛼(𝑘) 𝑒), 𝑢𝑒} 9: 𝛥(𝑘+1) 𝑒=𝛽(𝑘+1) 𝑒−𝛼(𝑘+1) 𝑒 𝑛𝑠−1 10: 𝑤(𝑘+1) 𝑒=1 𝑛𝑠∑𝑛𝑠 𝑖=1 𝑐′ 𝑒(𝛼(𝑘+1) 𝑒+ (𝑖− 1) ⋅𝛥(𝑘+1) 𝑒) 11: end for 12: return {𝑥∗ 𝑒}𝑒∈𝐸 In SDSP, the initial values of regional first-order information 𝑤𝑒and the parameters 𝑛𝑠, 𝑎cannot be directly determined through theoretical analysis, nor can they be automatically optimized by the algorithm. To address this, we design a series of numerical experiments to evaluate the impact of various initializations and parameter settings on the algorithm’s performance. These experiments serve as a reference for selecting initial values for regional first-order information and parameter settings, facilitating the practical application of SDSP. 3.3. Time and space complexity analysis This section analyzes the time and space complexity of the SSP and SDSP. The analysis of the SSP algorithm is based on the conclusions in the book Network Flows. The analysis of the SDSP is derived and analyzed based on the proposed algorithm in this paper. 3.3.1. Time complexity analysis In the SSP, each iteration solves a shortest path problem with nonnegative weights and strictly decreases the unbalanced state of some node. Consequently, if 𝑛is the number of nodes in Graph, 𝑚 is the number of edges in Graph, and 𝑈is an upper bound on the largest supply of any node, the SSP terminates in at most 𝑛𝑈 iterations. Let 𝑆(𝑛, 𝑚, 𝐶)denote the time taken to solve a shortest path problem with nonnegative weights, the time complexity of the SSP is 𝑂(𝑛𝑈 𝑆(𝑛, 𝑚, 𝑛𝐶)). In this paper, we apply Dijkstra’s algorithm to solve the shortest path problem, using a special data structure, the heap, to accelerate the Dijkstra’s algorithm. Lemma 1provides the time complexity of Dijkstra’s algorithm with binary heap implementation. Lemma 1. A binary heap data structure requires 𝑂(log 𝑛)time to perform insert, decrease-key, and delete-min, and it requires 𝑂(1) time for the other heap operations. Consequently, the binary heap version of Dijkstra’s algorithm runs in 𝑂(𝑚log 𝑛)time. Proof. The details of this lemma are provided in Section 4.7 of the book Network Flows.□ Lemma 1states that 𝑆(𝑛, 𝑚, 𝐶) =𝑂(𝑚log 𝑛), therefore establishing the time complexity of the SSP algorithm as presented in Theorem 1. Theorem 1. When the time complexity taken to solve a shortest path problem with nonnegative weights is 𝑂(𝑚log 𝑛), the time complexity of the SSP algorithm is 𝑂(𝑛𝑚𝑈 log 𝑛). In the SDSP algorithm, Proposition 1proves that the algorithm’s mechanism ensures the descent of the objective function, but the theoretical property of finite-step convergence remains unclear. To address this, a maximum iteration count 𝑀is introduced to guarantee the termination of the SDSP algorithm. Building on the time complexity of the SSP algorithm, Corollary 1provides the time complexity of the SDSP algorithm. Corollary 1. Let 𝑀be the maximum iteration count of the SDSP algorithm, the time complexity is 𝑂(𝑀 𝑛𝑚𝑈 log 𝑛). Although the finite-step convergence of the interval reduction mechanism in the SDSP algorithm lacks theoretical proof, numerical experiments show that the algorithm effectively achieves finite-step convergence in practice, requiring only a few iterations. 3.3.2. Space complexity analysis In the analysis of space complexity, it is necessary to consider the storage of the graph structure as well as the storage of variables involved in the solution process of the related algorithms. To determine the space complexity of the SDSP algorithm, we first calculate the space complexities of the Dijkstra and SSP algorithms as a foundation. In Dijkstra’s algorithm, the space complexity includes graph storage, priority queue, distance array, visited array, and auxiliary structures. The SSP algorithm computes the shortest path problem by invoking Dijkstra’s algorithm. Although the worst-case iteration count for the SSP algorithm is 𝑉×𝑈, since the space occupied by the variables in Dijkstra’s algorithm can be released after each invocation. Therefore, the SSP algorithm does not increase the space complexity order. Similarly, when the SDSP algorithm iterates over the SSP algorithm, it stores only the numerical results from the previous iteration. As a result, the overall space complexity remains unchanged in terms of order, with a slight increase in the constant factor coefficient. Table 1provides the detailed space complexity calculations for the three algorithms. Operations Research Perspectives 14 (2025) 100331 4 L. Yang and Z. Yang Table 1 Space complexity of variables in different algorithms. Variable Dijkstra SSP SDSP Graph storage 𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)𝑂(𝑉+𝐸) Priority queue (Binary heap) 𝑂(𝑉) Distance & Visited array 𝑂(𝑉) Residual graph 𝑂(𝑉+𝐸) 𝑆 , 𝐷 , 𝜋 , 𝑑 , 𝜅 𝑂(𝑉) Flows 𝑥 𝑂(𝐸)𝑂(𝐸) 𝛼 , 𝛽 , 𝛥, 𝜔 𝑂(𝐸) Auxiliary structures 𝑂(1) 𝑂(1) 𝑂(1) Total 𝑂(𝑉+𝐸)𝑂(𝑉+𝐸)𝑂(𝑉+𝐸) 4. Numerical experiments This section demonstrates the effectiveness and advantages of SDSP in solving CCNFP through a series of numerical experiments. Section 4.1 introduces the problem instances and their construction methods. Section 4.2 presents experiments that identify the most effective initialization method for regional first-order information and optimal parameter settings. Section 4.3 examines the impact of the sequential process and interval reduction mechanisms in SDSP. Finally, Section 4.4 compares the performance of SDSP with that of nonlinear programming algorithms and a sequential linear approximation algorithm, highlighting its superiority. The algorithms used in the numerical experiments are compiled and executed in a C++17 environment, except for the Sequential Least Squares Programming, which is implemented in Fortran and invoked through a Python interface. All program codes presented in this paper are executed on the same desktop computer, equipped with an Intel Core i7-11700 2.50 GHz processor and 32 GB of RAM. 4.1. Instruction of instances Since the related work does not provide available instances, we construct the graph structure of CCNFP based on the instance scales outlined in the literature. Additionally, we apply various categories of concave functions as the objective of CCNFP. The instance scale typically refers to the number of nodes and edges in the graph structure. In this paper, we construct seven groups of instances with different scales: (10, 40), (20, 100), (40, 300), (60, 400), (100, 1000), (150, 2500), and (250, 7500).2We randomly generate a specified number of nodes within a two-dimensional rectangular region using a uniform distribution. The connections between these nodes are determined by comparing their Euclidean distance to a threshold. A flexible threshold controls the number of connected node pairs, ensuring that the number of edges matches the specified scale for the graph. Next, we randomly select 10%, 20%, and 40% of the nodes to serve as the source and sink nodes in each instance, respectively. The node supply for each source follows the uniform distributions U(3,30), while the node supply for each sink follows U(−30,−3). Additionally, we constructed instances with various sampling distributions to assess their impacts the algorithm’s performance. Adjustments are applied to ensure the total supply equals zero. Excluding source and sink nodes, all other nodes are designated as intermediate nodes with a supply of zero. We assume that the cost function of each edge is a concave function passing the point (0,0). These cost functions are divided into three categories: Logarithmic, Power, and Sigmoid, and are defined as follows: 𝐶𝐿𝑜𝑔(𝑥) = log𝜃(𝑥+ 1), 𝐶𝑃 𝑜𝑤(𝑥) = (𝑥+ 1) 1 𝜃− 1, 𝐶𝑆 𝑖𝑔 (𝑥) =1 1 +𝜃−𝑥−1 2 (10) 2The first number represents the number of nodes, while the second represents the number of edges. Table 2 Information about instances. Instance characteristics Parameter values Node number 10, 20, 40, 60, 100, 150, 250 Edge number 40, 100, 300, 400, 1000, 2500, 7500 Source node radio 10%, 20%, 40% Sink node radio 10%, 20%, 40% Samp. Dist. for Source U(3,30),U(1,5) to U(26,30) Samp. Dist. for Sink U(−30,−3),U(−30,−26) to U(−5,−1) Objective function 𝐶𝐿𝑜𝑔 (𝑥), 𝐶𝑃 𝑜𝑤(𝑥), 𝐶𝑆 𝑖𝑔 (𝑥), 𝐶𝑀 𝑖𝑥(𝑥) Table 3 The formula for initializing 𝑤𝑒at specific points. Formula 𝑥𝑒= 0𝑥𝑒=𝑢𝑒∕2 𝑥𝑒=𝑢𝑒 Derivative value 𝑐′ 𝑒(0) 𝑐′ 𝑒(𝑢𝑒∕2) 𝑐′ 𝑒(𝑢𝑒) Interpolation slope – 2 𝑢𝑒 𝑐𝑒(𝑢𝑒∕2) 1 𝑢𝑒 𝑐𝑒(𝑢𝑒) where 𝜃∼U(2,12). Additionally, we define a mixed-cost function that combines the three concave functions. By partitioning the edge set 𝐸 into three disjoint subsets 𝐸1, 𝐸2, 𝐸3, we define the mixed objective function as follows: 𝐶𝑀 𝑖𝑥(𝑥) =⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ log𝜃(𝑥+ 1) for 𝑒∈𝐸1 (𝑥+ 1) 1 𝜃− 1for 𝑒∈𝐸2 1 1+𝜃−𝑥−1 2for 𝑒∈𝐸3 (11) The all information for generating instances are listed in Table 2, where Samp. Dist. stands for the sampling distribution. 4.2. Initialization and parameter selection In this subsection, we provide guidance on initialization methods, the number of sampling points, and the interval reduction coefficients based on numerical experiments. The initialization of regional first-order information significantly affects the solution. Numerical experiments help identify the most suitable initialization method by comparing the algorithm’s performance across different strategies. These strategies can be categorized into two groups. One group computes the regional first-order information using the update formula for 𝑤(𝑘) 𝑒over the initial sampling interval [0, 𝑢𝑒], denoted as  𝑐′ 𝑒. The other group uses the derivative values or linear interpolation slopes at specific points as the regional first-order information. In the experiments, we calculate the derivative value and the linear interpolation slope at the points 𝑥𝑒= 0, 𝑥𝑒=𝑢𝑒∕2,and 𝑥𝑒= 𝑢𝑒, as summarized in Table 3. Table 4presents the objective values obtained by SDSP under six different initialization methods for the constructed instances. In the experiment, 30 sampling points are used, and the interval reduction coefficient is set to 0.5. The Min column displays the minimum objective value for each instance. The relative error between the objective values for different initializations and the minimal value is then calculated for direct comparison. Two indicators are used to compare the results for different methods: ARE and MRE. ARE stands for Average Relative Error, which serves as an overall metric for evaluating algorithm performance. MRE stands to Maximum Relative Error, which is used to assess the algorithm’s performance in the worst-case scenario. Both ARE and MRE are provided in the table. The results indicate that SDSP performs best with the following initialization methods: 𝑤𝑒=2 𝑢𝑒 𝑐𝑒(𝑢𝑒 2),𝑐𝑒(𝑢𝑒) 𝑢𝑒 ,and  𝑐′ 𝑒. For these three initializations, the ARE remains consistently below 2.5%. In contrast, the ARE for the other methods exceeds 10%. However, the difference between these three initialization methods is insufficient to determine a clear winner. Next, we combine the results from Table 4with experiments on the number of samples and the interval reduction coefficient to identify the optimal initialization method, sampling number, and coefficient. Operations Research Perspectives 14 (2025) 100331 5 L. Yang and Z. Yang Table 4 The objective values of SDSP under six types of initialization. Objective Scale Objective values (𝑛𝑠= 30, 𝑎= 0.5) Min 𝑐′ 𝑒(0) 𝑐′ 𝑒(𝑢𝑒 2)2 𝑢𝑒 𝑐𝑒(𝑢𝑒 2)𝑐′ 𝑒(𝑢𝑒)𝑐𝑒(𝑢𝑒) 𝑢𝑒  𝑐′ 𝑒(𝑥𝑒) 𝐶𝐿𝑜𝑔 (𝑥) (20, 100) 16.110 15.966 15.928 15.966 15.966 15.928 15.928 (60, 400) 14.535 14.316 14.339 14.764 14.339 14.339 14.316 (150, 2500) 48.754 49.478 51.536 49.497 49.617 49.617 48.754 (250, 7500) 119.695 107.613 108.444 107.960 107.814 106.965 106.965 𝐶𝑃 𝑜𝑤 (𝑥) (20, 100) 4.582 4.617 4.617 4.617 4.617 4.617 4.582 (60, 400) 1.040 1.083 1.050 1.110 1.083 1.029 1.029 (150, 2500) 13.362 14.107 13.791 13.620 13.838 13.529 13.362 (250, 7500) 33.160 32.196 31.351 31.898 30.995 31.351 30.995 𝐶𝑆 𝑖𝑔 (𝑥) (20, 100) 6.495 6.753 5.749 6.753 5.749 6.249 5.749 (60, 400) 14.990 18.499 14.467 17.980 14.467 14.467 14.467 (150, 2500) 28.140 32.946 21.737 32.187 21.737 23.618 21.737 (250, 7500) 50.981 80.461 36.201 80.050 36.201 35.444 35.444 𝐶𝑀 𝑖𝑥(𝑥) (20, 100) 7.694 7.584 6.793 7.133 7.021 6.793 6.793 (60, 400) 7.946 12.666 8.037 12.666 7.917 8.725 7.917 (150, 2500) 28.148 37.207 18.596 38.605 18.799 19.149 18.596 (250, 7500) 55.973 96.011 39.558 96.758 39.787 38.972 38.972 ARE (%) 13.82 34.99 1.22 34.74 1.33 2.23 MRE (%) 51.37 146.36 5.71 148.28 5.25 10.21 Fig. 1. The trend of average relative error corresponds to the number of sampling points. The interval reduction coefficient is set to 0.5. Two experiments are designed to compare the performance of SDSP with varying sampling numbers and interval reduction coefficients under three selected initialization methods. Fig. 1illustrates the trend of the relative error in objective values as a function of the sampling number, while Fig. 2shows the trend of relative error with respect to the interval reduction coefficient. The results demonstrate that the linear interpolation slope initialization methods outperform the derivative mean method. However, no significant difference is observed between the two linear interpolation slope methods. Based on these findings, we adopt 𝑐𝑒(𝑢𝑒) 𝑢𝑒 as the initial regional first-order information, set the number of sampling points to one, and choose an interval reduction coefficient of 0.65. These two figures show more information about the effect of the regional first-order information and the interval reduction mechanism. In Fig. 1, fewer sampling points implies that the averaged derivative computed within the interval effectively approximates the gradient at a point closer to the upper part of the region. As the number of sampling points increases, the averaged derivative shifts to reflect the gradient of a point closer to the interval’s midpoint. When the initialization method uses the linear interpolation slope, fewer sampling points demonstrate a distinct advantage. From an optimization perspective, this phenomenon arises because the gradient of a concave function in the upper region of the interval is inherently steeper than at the midpoint. This steepness results in a lower effective cost for the reverse edge in the residual graph during the algorithm’s iterations, increasing the likelihood of its selection in subsequent iterations. This mechanism introduces natural reversibility to the flow assignments, allowing the algorithm to explore the solution space more effectively and avoid premature convergence. As a result, the algorithm can overcome the limitations of the successive shortest path algorithm, which struggles with concave cost structures, ultimately achieving higher-quality solutions and better objective values. This behavior highlights the practical utility of leveraging regional first-order information in the SDSP framework. In Fig. 2, the average relative error exhibits a distinct ‘‘U-shaped’’ relationship with the interval reduction coefficient. When the coefficient approaches zero, the algorithm relies only on the gradient value at the solution from the previous iteration to approximate the concave cost function. Conversely, when the coefficient approaches one, the algorithm uses a fixed-length interval for sampling to construct the linear objective. The experimental results show that both extreme approaches are suboptimal for solving the problem. An iterative framework based solely on single-point gradient values often converges to suboptimal solutions due to the challenge of revisiting previously assigned flow values. Conversely, using fixed-length interval sampling throughout the Operations Research Perspectives 14 (2025) 100331 6 L. Yang and Z. Yang Fig. 2. The trend of average relative error corresponds to the interval reduction coefficient. The number of sampling points is set to 30. Table 5 Validation on sequential process and regional first-order information. Objective Scale Objective values LPo LPu SGSP SDSP(𝑎= 1) SDSP 𝐶𝐿𝑜𝑔 (𝑥) (20, 100) 16.248 15.966 15.966 15.844 15.760 (60, 400) 14.689 15.233 15.233 14.556 14.222 (150, 2500) 53.033 55.037 55.037 45.689 44.772 (250, 7500) 89.473 80.368 78.816 75.795 71.763 𝐶𝑃 𝑜𝑤 (𝑥) (20, 100) 4.820 4.617 4.617 4.617 4.617 (60, 400) 1.069 1.116 1.116 1.015 1.006 (150, 2500) 13.734 14.053 13.891 13.198 12.830 (250, 7500) 23.483 21.327 20.553 20.444 19.793 𝐶𝑆 𝑖𝑔 (𝑥) (20, 100) 6.495 5.749 5.749 5.749 5.749 (60, 400) 15.999 14.500 14.000 14.500 12.956 (150, 2500) 34.614 22.834 22.834 22.834 19.244 (250, 7500) 57.630 38.026 38.206 38.026 37.525 𝐶𝑀 𝑖𝑥(𝑥) (20, 100) 8.914 7.442 7.442 7.076 7.021 (60, 400) 9.033 8.578 7.912 7.728 7.604 (150, 2500) 29.050 22.317 20.887 19.900 17.788 (250, 7500) 33.166 30.333 26.717 27.913 25.166 ARE (%) 24.79 10.52 7.90 4.67 – process risks assigning reverse flow to edges that should receive flow, hindering the algorithm’s ability to converge to high-quality solutions. The interval reduction mechanism effectively navigates the trade-offs between these opposing factors, enabling the algorithm to find a Paretooptimal balance. This mechanism is analogous to step-size adjustment in optimization algorithms: larger step sizes help escape local minima, while reductions ensure convergence to a local minimum in a more promising neighborhood. 4.3. Effectiveness This section aims to validate the effectiveness of SDSP by showcasing the improved performance achieved through both the sequential process and the incorporation of regional first-order information. In comparison, we construct two minimum-cost flow models to approximate the CCNFP in a single step. The linear unit cost on edges is defined as 𝑐𝑒(𝑥) =𝑐′ 𝑒(0)⋅𝑥or 𝑐𝑒(𝑥) =𝑐𝑒(𝑢𝑒) 𝑢𝑒 ⋅𝑥, with these two approximate models denoted as LPo and LPu respectively. Additionally, we simplify the SDSP by updating 𝑤(𝑘+1) 𝑒based solely on the gradients at point 𝑥(𝑘) 𝑒, that is, 𝑤(𝑘+1) 𝑒=𝑐′ 𝑒(𝑥(𝑘) 𝑒)which is denoted as SGSP. In the experiments, we ensure that the initialization and parameter settings of SGSP are consistent with those of SDSP. Table 5presents the objective values of these four approaches across 16 instances. The objective values obtained by SDSP are consistently minimal compared to the others for all instances. We calculate the average relative error between SDSP’s objective values and those of the other methods. The results show that the objective values achieved by SGSP are always less than or equal to those obtained by LPu, confirming the descent property outlined in Proposition 1. However, when updating 𝑤(𝑘+1) 𝑒using gradients, the sequential process only results in a modest 2.62% decrease in the objective value. Introducing regional first-order information into the sequential process leads to a substantial improvement, with the average relative error between SGSP and SDSP reaching 7.9%. The descending trend in ARE from LPu to SDSP highlights the crucial role that the sequential process and the integration of regional first-order information play in optimizing the objective values of CCNFP. Also, the results of SDSP with the parameter 𝑎= 1have been listed in the table for comparison. The SDSP algorithm without interval reduction explores a wider solution space than SGSP, resulting in a generally superior solution. However, the algorithm still shows a 4.67% potential for improvement when the interval reduction mechanism is incorporated. Fig. 3shows the decrease in the objective function across four cases with distinct target functions, comparing the performance of three iterative strategies. Both SDSP(𝑎= 0.65) and SGSP show a Operations Research Perspectives 14 (2025) 100331 7 L. Yang and Z. Yang Fig. 3. The decreasing process of SGSP and SDSP. steady decrease in the objective value over iterations, but SGSP often converges prematurely to suboptimal local minima. Conversely, SDSP without interval reduction (when 𝑎= 1) achieves better results than SGSP in several cases, but it lacks guaranteed monotonic decrease and quickly stagnates after a few iterations. The proposed interval reduction mechanism in SDSP effectively integrates the advantages of the other two strategies, enabling it to identify higher-quality solutions. Furthermore, even without a predefined maximum iteration limit, the interval reduction mechanism exhibits finite-step convergence in numerical experiments, reliably meeting the stopping criteria within a limited number of iterations. These findings highlight how SDSP balances exploration and exploitation, leading to robust and efficient optimization performance. 4.4. Comparison To evaluate the performance of SDSP, we conducted comparison experiments with existing algorithms for solving the concave cost network flow problem on different graph structure instances. We compare SDSP with two categories of algorithms. The first category includes three nonlinear programming algorithms: •Sequential Least Square Programming (SLSQP) [28] •Augmented Lagrange Function algorithm (AugLag) [29–33] •Penalty Function algorithm (Penalty) [29,30,34,35] SLSQP is a gradient-based optimization method that solves constrained nonlinear optimization problems by iteratively approximating the objective function and constraints with quadratic models, efficiently handling both equality and inequality constraints. The AugLag algorithm combines Lagrangian relaxation of constraints with an augmented penalty term, improving convergence and stability in solving constrained optimization problems. The Penalty method incorporates a penalty term into the objective function to penalize constraint violations, solving the problem as an unconstrained optimization while progressively tightening the penalty. The second category includes the sequential linear approximate algorithm, Dynamic Slope Scaling Procedure (DSSP) [36], which is also applicable to CCNFP. All baseline algorithm parameter settings are available in the shared GitHub repository, ensuring consistency by using the same set of parameters for all experimental cases. First, we conduct experiments on instances with graph structures that include seven different scales and three source node ratios, resulting in a total of 84 instances. The source node supply follows a sampling distribution of U(3,30). Next, we explore the performance of five algorithms on instances with different supply sampling distributions. Tables 6and 7present the average and maximum relative errors between the objective values obtained by the five algorithms and the minimum across 84 instances. The minimum for each instance is the smallest objective value among the five algorithms. The details of the results for all instances are listed in Appendix.Table 6shows the performance differences of the algorithms across instances with varying scales. Table 7shows the performance of the algorithms under different source node ratios. In Table 6, we observe that the average relative error of the proposed algorithm decreases as the instance scale increases: the larger the scale, the smaller the relative error. This suggests that as the problem scale increases, the SDSP algorithm can find the optimal solution in most cases. In contrast, both the SLSQP and DSSP algorithms show an increase in average relative error as the problem scale grows, while the average relative error of the AugLag algorithm remains around 10%. This further highlights the significant advantage of the SDSP algorithm in solving large-scale concave cost network flow problems. With an average relative error of 0.71% and a maximum relative error of 8.69%, the SDSP algorithm demonstrates both effectiveness and stability in solving this problem. Even in the worst-case scenario, the algorithm’s relative error remains within 10%, a level unattainable by the other compared algorithms. In Table 7, the performance of all five algorithms generally shows that the average relative error decreases as the ratio of source nodes Operations Research Perspectives 14 (2025) 100331 8