# American Institute of Mathematical Sciences

January  2007, 3(1): 71-85. doi: 10.3934/jimo.2007.3.71

## A bilinear relaxation based algorithm for concave piecewise linear network flow problems

 1 Center for Applied Optimization, Industrial and Systems Engineering Department, University of Florida, Gainesville, FL 32611, United States 2 Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611

Received  October 2005 Revised  February 2006 Published  January 2007

We present a continuous relaxation technique for the Concave Piecewise Linear Network Flow Problem (CPLNFP), which has a bilinear objective function and network constraints. We show that a global optimum of the resulting problem is a solution of CPLNFP. The theoretical results are generalized for a concave minimization problem with a separable objective function. An efficient and effective Dynamic Cost Updating Procedure (DCUP) is considered to find a local minimum of the relaxation problem, which converges in a finite number of iterations. We show that the CPLNFP is equivalent to a Network Flow Problem with Flow Dependent Cost Functions (NFPwFDCF), and we prove that the solution of the Dynamic Slope Scaling Procedure (DSSP) is an equilibrium solution of the NFPwFDCF. The numerical experiments show that the proposed algorithm can provide a better solution than DSSP using less amount of CPU time and iterations.
Citation: Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
 [1] Jun Pei, Panos M. Pardalos, Xinbao Liu, Wenjuan Fan, Shanlin Yang, Ling Wang. Coordination of production and transportation in supply chain scheduling. Journal of Industrial & Management Optimization, 2015, 11 (2) : 399-419. doi: 10.3934/jimo.2015.11.399 [2] Qiong Liu, Ahmad Reza Rezaei, Kuan Yew Wong, Mohammad Mahdi Azami. Integrated modeling and optimization of material flow and financial flow of supply chain network considering financial ratios. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009 [3] Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial & Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727 [4] Jia Shu, Jie Sun. Designing the distribution network for an integrated supply chain. Journal of Industrial & Management Optimization, 2006, 2 (3) : 339-349. doi: 10.3934/jimo.2006.2.339 [5] Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095 [6] Ashkan Mohsenzadeh Ledari, Alireza Arshadi Khamseh, Mohammad Mohammadi. A three echelon revenue oriented green supply chain network design. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 157-168. doi: 10.3934/naco.2018009 [7] Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670 [8] Wenbin Wang, Peng Zhang, Junfei Ding, Jian Li, Hao Sun, Lingyun He. Closed-loop supply chain network equilibrium model with retailer-collection under legislation. Journal of Industrial & Management Optimization, 2019, 15 (1) : 199-219. doi: 10.3934/jimo.2018039 [9] Jianbin Li, Niu Yu, Zhixue Liu, Lianjie Shu. Optimal rebate strategies in a two-echelon supply chain with nonlinear and linear multiplicative demands. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1587-1611. doi: 10.3934/jimo.2016.12.1587 [10] Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032 [11] Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074 [12] Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317 [13] Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial & Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51 [14] Alexander V. Kolesnikov. Hessian metrics, $CD(K,N)$-spaces, and optimal transportation of log-concave measures. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1511-1532. doi: 10.3934/dcds.2014.34.1511 [15] Claudio Buzzi, Claudio Pessoa, Joan Torregrosa. Piecewise linear perturbations of a linear center. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 3915-3936. doi: 10.3934/dcds.2013.33.3915 [16] Lorenzo Brasco, Filippo Santambrogio. An equivalent path functional formulation of branched transportation problems. Discrete & Continuous Dynamical Systems - A, 2011, 29 (3) : 845-871. doi: 10.3934/dcds.2011.29.845 [17] Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169 [18] Yeong-Cheng Liou, Siegfried Schaible, Jen-Chih Yao. Supply chain inventory management via a Stackelberg equilibrium. Journal of Industrial & Management Optimization, 2006, 2 (1) : 81-94. doi: 10.3934/jimo.2006.2.81 [19] Juliang Zhang. Coordination of supply chain with buyer's promotion. Journal of Industrial & Management Optimization, 2007, 3 (4) : 715-726. doi: 10.3934/jimo.2007.3.715 [20] Na Song, Ximin Huang, Yue Xie, Wai-Ki Ching, Tak-Kuen Siu. Impact of reorder option in supply chain coordination. Journal of Industrial & Management Optimization, 2017, 13 (1) : 449-475. doi: 10.3934/jimo.2016026

2018 Impact Factor: 1.025