Dynamic Slope Scaling and Trust Interval Techniques for Solving Concave Piecewise Linear Network Flow Problems Dukwon Kim Center for Applied Optimization, Department of Industrial and Systems Engineering, 303 Weil Hall, University of Florida, Gainesville, Florida 32611 Panos M. Pardalos Center for Applied Optimization, Department of Industrial and Systems Engineering, 303 Weil Hall, University of Florida, Gainesville, Florida 32611 In this paper, we propose an efficient heuristic approach for solving concave Piecewise Linear Network Flow Problems (PLNFP) in which the cost is separable and each arc cost is concave piecewise linear function of the total flow along the arcs. The problem is well known to be NP -hard and exact global optimization algorithms are of limited use. In this paper, PLNFP is transformed into an equivalent Fixed-Charge Network Flow Problem (FCNFP) using an arc separation procedure, and we develop an algorithm combining the Dynamic Slope Scaling Procedure (DSSP) and Trust Interval techniques. Due to the fast growing size of the transformed FCNFP, exact branch-and-bound methods are not able to handle the problems of practical size. Based on the dynamic slope scaling algorithm developed for solving FCNFP in previous work, we add a trust interval technique based on solution tendencies to speed up the algorithm. The numerical experiments show that the proposed algorithm is quite efficient and its performance is very stable. © 2000 John Wiley & Sons, Inc. Keywords: minimum-cost network flow; piecewise linear cost; fixed charge; global optimization 1. INTRODUCTION In most network models considered in the literature, the involved costs are assumed to be linear and/or convex. In many of the applications encountered in practice, however, this assumption fails to hold. In fact, many of the problems arising in real-world situations exhibit concave piecewise linearities or economies of scale in their cost structures [3, 7]. Received November 1998; accepted December 1999 Correspondence to: P. M. Pardalos; e-mail: pardalos@ufl.edu c 2000 John Wiley & Sons, Inc. NETWORKS, Vol. 35(3), 216–222 2000 The concave Piecewise Linear Network Flow Problem (PLNFP) models arise in diverse applications along with price-discounting situations such as transportation, communication network design, production planning, location decision, and economic lot sizing. An extended survey can be found in [1]. Another usage of PLNFP models is to approximate global solutions for continuous smooth concave minimization problems in branch-andbound schemes [6]. These problems are well known to be NP-hard. However, in [2], a polynomial-time solvable concave cost network flow problem was observed (see also [8]). In this paper, three different approaches incorporating the Dynamic Slope Scaling Procedure (DSSP) [4] are discussed. The first approach is used to solve a concave PLNFP by implementing a revised DSSP algorithm on the original formulation of concave PLNFP, [CCPLNFP]. The second approach is to implement the original DSSP algorithm for the fixed-charge version of concave PLNFPs in the extended network. Note that usually we need to solve much larger fixed-charge network flow problems than the original concave PLNFP due to the separation of arcs [5]. For example, if each piecewise linear arc cost function in the original concave PLNFP has p linear segments (pieces), then the resulting fixed charge version of concave PLNFP, [CCPLNFP]FC , is p times larger than the original problem. This means that the DSSP algorithm can have less capability to solve large-scale concave PLNFPs. To improve the performance of the DSSP algorithm for the concave PLNFP in the second approach, a revised DSSP algorithm incorporating a local search scheme, so-called trust intervals, and a decision strategy, so-called a solution tendency, are discussed in the third approach. Computational results show that these schemes effectively remove unnecessary separated arcs from consideration in the extended network, so that the size of [CCPLNFP]FC can be reduced at each iteration of the DSSP algorithm. Computational results from the implementation of these three different approaches are reported. 2. THE PROBLEM AND FORMULATIONS We consider the following network problem with concave piecewise arc costs. Given a directed graph G = (N, A) consisting of a set N of m nodes and a set A of n arcs, then solve [CCPLNFP] min f(x) = X fij (xij ) (i,j)∈A subject to X (k,i)∈A xki − X xik = bi , ∀i ∈ N (1) (i,k)∈A 0 ≤ xij ≤ uij , ∀(i, j) ∈ A, (2) where f is separable and each fij is piecewise linear. For instance, the arc cost fij (xij ) can be defined in a standard form as follows: 1 c x + sij,1 if 0 ≤ xij < λij ij,1 ij 1 2 cij,2 xij + sij,2 if λij ≤ xij < λij fij (xij ) = .. .. . . r −1 r cij,rij xij + sij,rij if λijij ≤ xij ≤ λijij (= uij ), (3) r , r = 1, 2, . . . , rij − 1, are breakpoints in the where λij given interval [0, uij ] and rij is the number of linear segments in each arc cost function fij . Note that due to the concavity of arc costs slopes of each piecewise linear arc cost function cij,r , r = 1, 2, . . . , rij satisfy the following property: cij,1 > cij,2 > · · · > cij,rij . (4) Using the Arc-separation procedure (ASP) [5] (see Fig. 1), the original concave PLNFP can be transformed into a fixed-charge model in an extended network. This extended network is denoted by Ge (N, Ae ), where the number of arcs |Ae | is given by X rij . ne = |Ae | = (i,j)∈A Thus, the size of the extended network depends on the number of linear segments in each arc cost function. In general, additional constraints are required for each separated arc to specify the capacity of separated arcs. Due to the concavity of arc costs, however, it is not necessary to include these additional capacity constraints. This fact can be generalized in the following theorem: FIG. 1. Arc-separation procedure. Theorem 1. Given an extended network described ∗ is optimal for a minimum above, if a positive flow xij q−1 q ∗ ≤ λij for 1 ≤ q ≤ rij , concave PLNFP and if λij < xij then it takes only one arc, (i, j)q (i.e., q-th arc) among all separated arcs between node i and j, (i, j)k for k = 1, 2, . . . , rij . Proof. Let us consider an arc (i, j) ∈ A with rij segments of concave piecewise linear cost function fij . Dek the slope and fixed charge of the kth note by cij,k and sij piece of linear function for k = 1, 2, . . . , rij , respectively. Notice that these slopes reflect the decreasing property in (4). After the ASP, there are rij separated arcs the flow can take. Let us denote by flowk the optimal flow on the kth separated arc (i, j)k for k = 1, 2, . . . , rij . ∗ First, it is clear that if xij is less than or equal to 1 the first breakpoint λij then the optimal flow cannot be ∗ ) since we have the cost of arc split (i.e., flow1 = xij k 1 1 for k = 2, 3, . . . , rij . (i, j)1 , fij ≤ fij , ∀xij ≤ λij p Second, consider the following two cases when λij ≤ q−1 q ∗ ≤ λij , and suppose that the flowp and flowq λij < xij are optimal flows in the extended network problem: ∗ − ε > 0 for any Case I. flowp = ε and flowq = xij positive ε. Suppose that the optimal flow is split into two arcs (i, j)p and (i, j)q , 1 ≤ p < q ≤ rij . Now, let us evaluate the difference of the cost function values in the original ∗ and the extended network problem with PLNFP with xij p q flow and flow : p q ∗ ∗ − ε)] − fij (xij ) [fij (ε) + fij (xij ∗ ∗ − ε)] − (sij,q + cij,q xij ) = [sij,p + cij,p ε + sij,q + cij,q (xij = sij,q + ε(cij,p − cij,q ) > 0. q The inequality in the last term above holds since sij ≥ and cij,q < cij,p . But this contradicts the optimality of flowp and flowq . Case II. ∗ and flowq = 0. flowp = ε = xij NETWORKS–2000 217 As in Case I, we evaluate the difference of the cost function values between node i and j: p q ∗ ) [fij (ε) + fij (0)] − fij (xij ∗ ) = (sij,p + cij,p ε) − (sij,q + cij,q xij ∗ ∗ ) − (sij,q + cij,q xij ) = (sij,p + cij,p xij > 0. We can obtain a contradiction as in the argument for ∗ . Case I, showing that flowq = xij Based on the arc separation and Theorem 1, the problem can be formulated in a compact form. To formulate the fixed-charge version of the concave PLNFP, let us denote by (i, j)r xij,r fij,r the r-th separated arc between node i and j on an extended network; the flow in the r-th separated arc between node i and j; the fixed-charge cost function for r-th separated arc between node i and j, that is: ( fij,r (xij,r ) = cij,r xij,r + sij,r if xij,r > 0 0 otherwise. [CCPLNFP]FC rij X X (i,j)∈A r=1 rij X r=1 rij X X (i,k)∈A r=1 xij,r = xij , p k < x̄ij < λij , p = 1, 2, . . . , rij , then p k = λij , p = 1, 2, . . . , rij − 1, then Iij = Case III. If x̄ij {p, p + 1}. fij,r (xij,r ) R − [CCPLNFP]FC xik,r = bi , ∀i ∈ N (5) ∀(i, j) ∈ A min f(x) = subject to X X (k,i)∈A r∈Iij xij,r ≥ 0, 0 ≤ xij ≤ uij , ∀(i, j) ∈ A, r = 1, 2, . . . , rij ∀(i, j) ∈ A. It is clear that no additional constraints are needed to specify capacities for separated arcs (i, j)r ∈ Ae , ∀i, j ∈ N due to Theorem 1. As a result, the solution of concave PLNFP can be found by solving the fixedcharge network problem formulated as above. Note that [CCPLNFP]FC is much larger than is [CCPLNFP] although it is relatively easier to solve. However, the computational effort can be reduced by using a special search scheme incorporated in the DSSP approach. 218 p−1 Case II. If λij Iij = {p}. k = λij (= uij ), then Iij = {rij }. Case IV. If x̄ij Thus, we solve the following reduced [CCPLNFP]FC at each iteration of the DSSP instead of the original [CCPLNFP]FC . subject to (k,i)∈A r=1 k 1 < λij , then Iij = {1}. If 0 ≤ x̄ij rij min f(x) = xki,r − Based on Theorem 1, we know that the optimal flow ∗ xij takes only one among the separated arcs between node i and j in an extended network. This suggests that the solution can be obtained by only considering the most trustable separated arcs in which the solution flow occurs. In other words, solving a reduced [CCPLNFP]FC which has considerably fewer decision variables than has the original [CCPLNFP]FC is sufficient to find solutions. These trustable arcs can be chosen in the DSSP by identifying trust intervals with a solution tendency for each concave piecewise linear arc cost function. Three types of solution tendency can be observed, such as (1) staying in the current interval, (2) moving down to the next lower interval, and (3) moving up to the next higher interval. To explain such a mechanism, let us consider the k-th iteration in the DSSP. It is clear that there can be four k occurs. For situations in which the current solution, x̄ij each case, let us define Iij to be an index set of trust intervals for arc (i, j) ∈ A: Case I. Then, the problem is formulated as follows: rij X X 3. TRUST INTERVALS AND SOLUTION TENDENCY NETWORKS–2000 xki,r − X r∈Iij X X (i,j)∈A r∈Iij X X (i,k)∈A r∈Iij xij,r = xij , xij,r ≥ 0, 0 ≤ xij ≤ uij , fij,r (xij,r ) xik,r = bi , ∀i ∈ N (6) ∀(i, j) ∈ A ∀(i, j) ∈ A, ∀r ∈ Iij ∀(i, j) ∈ A. As mentioned earlier, this procedure can be considered to be a local search scheme which reduces the number of separated arcs investigated at each iteration. An example of trust intervals and the solution tendency discussed above is shown in Figure 2. FIG. 3. Graphical illustration of the initial solution. FIG. 2. dency. A graphical example of trust intervals and the solution ten- 4. ALGORITHMS We have developed distinct algorithms for each of the three approaches incorporating the DSSP to solve the FCNFP. Each was implemented and tested on a common set of 200 PLNFPs. It should be noted that the DSSP algorithm, discussed in Section 2, for solving the original concave PLNFP model, [CCPLNFP], can potentially handle not only fixed-charge network problems but also piecewise linear network problems. The performance of the DSSP algorithm on the original concave PLNFP without transforming it into a [CCPLNFP]FC is shown in the following section, including a comparison with the others. Three different approaches using the revised DSSP algorithms for each formulation model are described as follows. 1. Approach I. DSSP [CCPLNFP]: • algorithm for solving –If k ≥ 1, then update s if λijr−1 < x̄ijk ≤ λijr cij,r + x̄ij,r k ij for r = 1, 2, . . . , rij c̄ijk+1 = p c̄ij if x̄ijk = 0, (9) where p is the index of the most recent value p−1 of the slope scaling factor, c̄ijk , when x̄ij > 0. This updating scheme is shown in Figure 4. 2. Approach II. DSSP algorithm for solving [CCPLNFP]FC : In this approach, since the concave PLNFP has been transformed into a fixed-charge problem in an extended network, the original DSSP algorithm used for FCNFP can be implemented in the same scheme. However, we need to solve very large [CCPLNFP]FC instances since the size of extended networks considered is much larger than the original network. It is easy to see that the increasing rate of the size depends on rij . Consequently, the computational time can grow rapidly if there are many linear pieces in each arc cost. 3. Approach III. DSSP algorithm for solving R − [CCPLNFP]FC : Since this approach is basically the same as the second approach, the same initial solu- Obtain initial solution x̄ij0 by solving LP with c̄ij0 = cij,rij + sij,rij uij for (i, j) ∈ A. (7) It is clear that this initial solution is obtained by solving an LP problem with a simple linear underestimation of each concave piecewise linear arc cost. This initial solution scheme is illustrated in Figure 3. • Updating scheme: –If k = 0, then update s if λijr−1 < x̄ijk ≤ λijr cij,r + x̄ij,r k ij for r = 1, 2, . . . , rij (8) c̄ijk+1 = sij,rij cij,r + if x̄ijk = 0. ij uij FIG. 4. Graphical illustration of the updating scheme. NETWORKS–2000 219 TABLE 1. Computational results of DSSP in Approach I. Size DSSP Problem Branch and bound Group Set no. m n rij REa (%) (min, max) CPU (sec) (min, max) CPU (sec) (min, max) P1 1 12 35 3 2 12 35 5 0.082 (0.00, 0.28) 0.301 (0.01, 0.88) 0.012 (0.01, 0.02) 0.014 (0.01, 0.02) 5.384 (1.02, 8.30) 14.216 (1.29, 54.75) 3 18 80 3 4 18 80 5 0.688 (0.12, 1.23) 0.713 (0.13, 1.82) 0.016 (0.01, 0.03) 0.019 (0.01, 0.04) 229.718 (21.03, 781.40) 813.244 (45.11, 1610.38) 5 27 175 3 n/ab n/a 6 27 175 5 n/a 0.039 (0.02, 0.07) 0.072 (0.02, 0.08) 7 32 225 3 n/a 8 32 225 5 n/a 9 37 335 3 n/a 10 37 335 5 n/a P2 P3 P4 P5 a b n/a 0.048 (0.03, 0.11) 0.121 (0.04, 0.34) n/a 0.106 (0.06, 0.32) 0.153 (0.06, 0.45) n/a n/a n/a The average Relative Error Exact solutions are not available from B&B due to memory limitations. tions and updating scheme as in the original DSSP for FCNFP are used in the DSSP algorithm for solving the R − [CCPLNFP]FC model. Employing trust intervals based on the solution tendency, most unnecessary variables (arcs) in the [CCPLNFP]FC model can be removed from consideration at each iteration by identifying an index set of trust intervals, Iij , for each (i, j) ∈ A. Thus, the size of the resulting R − [CCPLNFP]FC will be much smaller than the [CCPLNFP]FC model, depending on the size of index sets Iij . At any iteration, let R be the size of R − [CCPLNFP]FC . Then, R= X where |Iij | denotes the number of elements in Iij . Note that 1 ≤ |Iij | ≤ 2. This means that the size of the problem to be solved at each iteration in this approach is at most twice that of the original concave PLNFP. TABLE 2. Computational results of DSSP in Approach II. Size DSSP Problem |Iij |, (i,j)∈A Branch and bound Group Set no. m n rij RE (%) (min, max) CPU (sec) (min, max) CPU (sec) (min, max) P1 1 12 35 3 2 12 35 5 0.080 (0.00, 0.18) 0.214 (0.01, 0.47) 0.019 (0.01, 0.03) 0.039 (0.01, 0.08) 8.914 (1.92, 19.13) 16.450 (1.98, 49.17) 3 18 80 3 4 18 80 5 0.387 (0.16, 0.62) 0.411 (0.14, 0.83) 0.087 (0.03, 0.15) 0.314 (0.07, 0.79) 204.805 (20.77, 737.61) 792.133 (43.23, 1065.05) 5 27 175 3 n/a n/a 6 27 175 5 n/a 0.399 (0.07, 0.81) 0.491 (0.09, 0.94) 7 32 225 3 n/a n/a 8 32 225 5 n/a 0.401 (0.11, 0.92) 1.443 (0.58, 3.69) 9 37 335 3 n/a n/a 10 37 335 5 n/a 1.219 (0.49, 4.01) 2.208 (0.92, 5.18) P2 P3 P4 P5 220 NETWORKS–2000 n/a n/a n/a TABLE 3. Computational results of DSSP in Approach III. Size DSSP Problem Branch and bound Group Set no. m n rij RE (%) (min, max) CPU (sec) (min, max) CPU (sec) (min, max) P1 1 12 35 3 2 12 35 5 0.081 (0.00, 0.19) 0.229 (0.01, 0.59) 0.017 (0.01, 0.04) 0.039 (0.01, 0.07) 8.914 (1.92, 19.13) 16.450 (1.98, 49.17) 3 18 80 3 4 18 80 5 0.382 (0.16, 0.62) 0.441 (0.14, 0.83) 0.080 (0.03, 0.15) 0.121 (0.05, 0.68) 204.805 (20.77, 737.61) 792.133 (43.23, 1065.05) 5 27 175 3 n/a n/a 6 27 175 5 n/a 0.333 (0.05, 0.79) 0.379 (0.06, 0.84) 7 32 225 3 n/a n/a 8 32 225 5 n/a 0.351 (0.09, 0.89) 1.126 (0.27, 3.96) 9 37 335 3 n/a n/a 10 37 335 5 n/a 1.085 (0.32, 3.43) 1.275 (0.68, 4.41) P2 P3 P4 P5 In the DSSP algorithms described above, the same stopping criterion as discussed in the previous study [4] was used with only minor changes for indexing. 5. NUMERICAL EXPERIMENTS To evaluate the efficiency and effectiveness of the algorithms, 200 problems of different sizes and structures were solved applying the above-described algorithms. These test problems are divided into five groups. Each group has two sets of problems, and each set contains 20 problems. The first and second sets in each group consist of problems with the fixed number of linear pieces rij = 3 and rij = 5, respectively. The algorithms were programmed in C incorporating CPLEX 4.0 and implemented on a SUN workstation running UNIX. Also, the branch-and-bound algorithm in CPLEX 4.0 was utilized to obtain exact solutions by solving the corresponding 0–1 mixed-integer programming problems. Due to the problem size and memory limitations, exact solutions were Pnot available when the total number of linear pieces, (i,j)∈A rij exceeded 400 in most instances. Since rij is a fixed number (3 or 5) in each group of problems, the total number of linear pieces is n times rij , where n denotes the number of arcs in the original network. Relative errors were computed as follows: # " fDSSP − fexact × 100, RE (%) = fexact and the solution time was measured by the total CPU time exclusive of I/O operations. Computational results for Approaches I, II, and III are summarized in Table 1, 2, and 3, respectively. These n/a n/a n/a results show that the DSSP in Approach I requires the smallest solution time (CPU time) to find solutions for all instances. However, the average relative errors in Approach I are larger than those in Approaches II and III. This implies that the DSSP in Approach I takes less time to obtain solutions, but the quality of solutions from the DSSP in Approach I is slightly worse than the others. For example, in problem set 4 of group P2 (which consists of 20 problems with 18 nodes, 80 arcs, and 5 linear pieces in each arc cost function), the average CPU time is 0.019 seconds in Approach I whereas it is 0.314 and 0.121 seconds in Approaches II and III, respectively. However, the average relative error is 0.713% in Approach I, whereas it is 0.411 and 0.441% in Approaches II and III, respectively. Comparing the results for Approaches II and III, the DSSP in Approach III which solves problems with the R − [CCPLNFP]FC model turn out to be more efficient (less solution time) than in Approach II, while the quality of solutions has no significant difference. This implies that FIG. 5 Comparison of the average relative errors. NETWORKS–2000 221 FIG. 6 Comparison of the average CPU times. the usage of “trust intervals” and “solution tendency” enhancements incorporated in the DSSP algorithm in Approach III is effective, especially when the rij values are large. This is evident in Tables 2 and 3, where the average CPU time for problem set 4 (with rij = 5) in group P2 is reduced from 0.314 to 0.121 seconds, whereas the average CPU time is reduced from 0.087 to 0.080 seconds in problem set 3 (with rij = 5). Comparisons of the average relative errors and the average CPU times using these three approaches are shown in Figures 5 and 6, respectively. In addition, the worst relative errors in Approaches I, II, and III are 1.82, 0.83, and 0.91%, respectively. As a result, the DSSP algorithms in both Approaches I and III have a typical trade-off between a quality of solutions and a solution time. Thus, choosing a proper approach depends upon which attribute is more critical in a given situation. 6. CONCLUDING REMARKS In this paper, the DSSP algorithms with three different approaches were developed and implemented for solving concave piecewise linear network flow problems. As shown by the computational results and comparisons, the DSSP in Approach I, which solves concave PLNFP without transforming to the fixed-charge network model, was the most efficient in CPU time, while the quality of solutions in Approach I was slightly lower than those in other approaches. This shows a strong possibility that the DSSP can be directly applied for solving more general concave and nonconvex optimization problems, such as continuous concave minimum-cost network problems and nonconvex discontinuous piecewise linear network flow problems. Another positive achievement in this paper is the successful implementation of the trust interval and solu- 222 NETWORKS–2000 tion tendency enhancements to reduce the size of the extended networks to be considered at each iteration. Although the DSSP algorithm in Approach III requires more solution time than does Approach I, it produces better near-optimal solutions, especially in large-scale problems. Considering the fact that the average CPU time in Approach III is still small (less than 2 seconds), this approach would be recommended in most cases except in the case where the solution time is relatively more critical than is the quality of the solutions. One of the referees of this paper suggested that Approaches II and III can be accomplished in the DSSP using the original network rather than in the extended network. It is possible only when the parallel arcs are uncapacitated. However, these two approaches are necessary for the DSSP to handle both capacitated and uncapacitated problems effectively. Acknowledgments The authors would like to thank the anonymous referees for several valuable comments. REFERENCES [1] G.M. Guisewite and P.M. Pardalos, Minimum concave-cost network flow problems: Applications, complexity, and algorithms, Ann Oper Res 25 (1990), 75–100. [2] G.M. Guisewite and P.M. Pardalos, A polynomial time solvable concave cost network flow problem, Networks 23 (1993), 143–147. [3] R. Horst, P.M. Pardalos, and N.V. Thoai, Introduction to global optimization, Kluwer, 1995. [4] D. Kim and P.M. Pardalos, A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure, Oper Res Lett 24 (1999), 195–203. [5] B.W. Lamar, “A method for solving network flow problems with general nonlinear arc costs,” D.-Z. Du and P.M. Pardalos (Editors), Network optimization problems, World Scientific, Singapore 1993, pp. 147–167. [6] B.W. Lamar, An improved branch and bound algorithm for minimum concave cost network flow problems, J Global Optim 3 (1993), 261–287. [7] P.M. Pardalos and J.B. Rosen, Constrained global optimization: Algorithms and applications, Lecture Notes in Computer Science 268, Springer-Verlag, Berlin, 1987. [8] P.M. Pardalos and S. Vavasis, Open questions in complexity theory for numerical optimization, Math Program 57 (1992), 337–339. [9] P.T. Thach, A decomposition method for the min concave cost flow problem with a staircase structure, Jpn J Appl Math 7 (1990), 103–120. [10] W.I. Zangwill, Minimum concave-cost flows in certain networks, Mgmt Sci 14 (1968), 429–450.

1/--страниц