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]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020066

[4]

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

[5]

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

[6]

Weihua Liu, Xinran Shen, Di Wang, Jingkun Wang. Order allocation model in logistics service supply chain with demand updating and inequity aversion: A perspective of two option contracts comparison. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020118

[7]

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

[8]

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

[9]

Á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

[10]

Abdolhossein Sadrnia, Amirreza Payandeh Sani, Najme Roghani Langarudi. Sustainable closed-loop supply chain network optimization for construction machinery recovering. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020074

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (30)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]