This paper studies the local optimality condition for the widely applied concave piecewise linear network flow problem (CPLNFP). Traditionally, for CPLNFP the complexity of checking the local optimality condition is exponentially related to the number of active arcs (i.e., arcs in which the flow is at the breakpoints). When the scale of CPLNFP is large, even local optimality is unverifiable and the corresponding local algorithms are inefficient. To overcome this shortcoming, a new local optimality condition is given. This new condition is based on the concavity and piecewise linearity of the cost function and makes full use of the network structure. It is proven that the complexity of the new condition is polynomial. Therefore, using the new condition to verify the local optimality is far superior to using the traditional condition, especially when there are many active arcs.
Citation: Zhibin Nie, Shuning Wang, Xiaolin Huang. A polynomial local optimality condition for the concave piecewise linear network flow problem[J]. AIMS Mathematics, 2021, 6(3): 2094-2113. doi: 10.3934/math.2021128
This paper studies the local optimality condition for the widely applied concave piecewise linear network flow problem (CPLNFP). Traditionally, for CPLNFP the complexity of checking the local optimality condition is exponentially related to the number of active arcs (i.e., arcs in which the flow is at the breakpoints). When the scale of CPLNFP is large, even local optimality is unverifiable and the corresponding local algorithms are inefficient. To overcome this shortcoming, a new local optimality condition is given. This new condition is based on the concavity and piecewise linearity of the cost function and makes full use of the network structure. It is proven that the complexity of the new condition is polynomial. Therefore, using the new condition to verify the local optimality is far superior to using the traditional condition, especially when there are many active arcs.
| [1] | J. Xu, Y. Tu, Z. Zeng, A nonlinear multiobjective bilevel model for minimum cost network flow problem in a large-scale construction project, Math. Probl. Eng., 2012 (2012), 115–123. |
| [2] |
V. Prahalad, K. Mathur, R. H. Ballou, An efficient generalized network-simplex-based algorithm for manufacturing network flows, J. Comb. Optim., 15 (2008), 315–341. doi: 10.1007/s10878-007-9080-6
|
| [3] | F. S. Salman, R. Ravi, J. N. Hooker, Solving the Capacitated Local Access Network Design Problem, Informs J. Comput., 20 (2008), 243–254. |
| [4] | C. D'Ambrosioa, A. Lodi, S. Wiese, et al., Mathematical programming techniques in water network optimization, Eur. J. Oper. Res., 243 (2015), 774–788. |
| [5] | T. L. Magnanti, D. Stratila, Separable concave optimization approximately equals piecewise linear optimization, In: Integer Programming and Combinatorial Optimization, Springer, Berlin, 2004. |
| [6] | B. W. Lamar, A method for solving network flow problems with general non-linear arc costs, In: Network Optimization Problems: Algorithms Applications and Complexity, World Scientific, Singapore, 1993. |
| [7] |
A. Saif, S. Elhedhli, A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem, Optim. Lett., 10 (2016), 1087–1100. doi: 10.1007/s11590-016-0998-4
|
| [8] |
Y. Perlman, I. Levner, Perishable Inventory Management in Healthcare, Journal of Service Science and Management, 7 (2014), 11–17. doi: 10.4236/jssm.2014.71002
|
| [9] |
S. Yan, Y. L. Shih, W. T. Lee, A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems, J. Global Optim., 49 (2011), 539–559. doi: 10.1007/s10898-010-9548-2
|
| [10] | Z. Xu, K. Liu, X. Xi, S. Wang, Method of hill tunneling via weighted simplex centroid for continuous piecewise linear programming, 2015 Conference on Decision and Control, 24 (2015), 301–316. |
| [11] |
D. Kim, P. M. Pardalos, Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems, Networks, 35 (2000), 216–222. doi: 10.1002/(SICI)1097-0037(200005)35:3<216::AID-NET5>3.0.CO;2-E
|
| [12] | A. Nahapetyan, P. M. Pardalos, A bilinear relaxation based algorithm for Concave Piecewise Linear Networks Flow Problems, J. Ind. Manag. Optim., 3 (2007), 71–85. |
| [13] | A. R. Conn, M. Mongeau, Discontinuous piecewise linear optimization, Math. Program., 80 (1998), 315–380. |
| [14] |
L. T. H. An, P. D. Tao, The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems, Ann. Oper. Res., 133 (2005), 23–46. doi: 10.1007/s10479-004-5022-1
|
| [15] |
X. Huang, J. Xu, X. Mu, S. Wang, The hill detouring method for minimizing hinging hyperplanes functions, Comput. Oper. Res., 39 (2012), 1763–1770. doi: 10.1016/j.cor.2011.10.017
|
| [16] | G. B. Dantzig, Linear Programming and Extensions, Journal of Industrial and Management Optimization, Princeton University Press, NJ, 1963. |
| [17] |
P. Kovacs, Minimum-cost flow algorithms: an experimental evaluation, Optim. Methods Softw., 30 (2015), 94–127. doi: 10.1080/10556788.2014.895828
|
| [18] |
M. Holzhauser, S. O. Krumke, C. Thielen, A Network Simplex Method for the Budget-Constrained Minimum Cost Flow Problem, Eur. J. Oper. Res., 259 (2017), 864–872. doi: 10.1016/j.ejor.2016.11.024
|
| [19] | D. Klingman, A. Napier, J. Stutz, NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems, Manage. Sci., 20 (1973), 814–821. |
Figures(5) / Tables(1)
Zhibin Nie, Shuning Wang, Xiaolin Huang. A polynomial local optimality condition for the concave piecewise linear network flow problem[J]. AIMS Mathematics, 2021, 6(3): 2094-2113. doi: 10.3934/math.2021128
DownLoad: