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 and 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 and 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 and 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 and Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066

[4]

Deqiang Qu, Youlin Shang, Dan Wu, Guanglei Sun. Filled function method to optimize supply chain transportation costs. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3339-3349. doi: 10.3934/jimo.2021115

[5]

Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial and Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727

[6]

Jia Shu, Jie Sun. Designing the distribution network for an integrated supply chain. Journal of Industrial and Management Optimization, 2006, 2 (3) : 339-349. doi: 10.3934/jimo.2006.2.339

[7]

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 and Management Optimization, 2021, 17 (6) : 3269-3295. doi: 10.3934/jimo.2020118

[8]

Jun Tu, Zijiao Sun, Min Huang. Supply chain coordination considering e-tailer's promotion effort and logistics provider's service effort. Journal of Industrial and Management Optimization, 2022, 18 (3) : 2191-2220. doi: 10.3934/jimo.2021062

[9]

Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095

[10]

Ashkan Mohsenzadeh Ledari, Alireza Arshadi Khamseh, Mohammad Mohammadi. A three echelon revenue oriented green supply chain network design. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 157-168. doi: 10.3934/naco.2018009

[11]

Xiao-Xu Chen, Peng Xu, Jiao-Jiao Li, Thomas Walker, Guo-Qiang Yang. Decision-making in a retailer-led closed-loop supply chain involving a third-party logistics provider. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1161-1183. doi: 10.3934/jimo.2021014

[12]

Nurcan Deniz, Eren Ozceylan. A bibliometric and social network analysis of data-driven heuristic methods for logistics problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022190

[13]

Á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

[14]

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 and Management Optimization, 2019, 15 (1) : 199-219. doi: 10.3934/jimo.2018039

[15]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[16]

Abdolhossein Sadrnia, Amirreza Payandeh Sani, Najme Roghani Langarudi. Sustainable closed-loop supply chain network optimization for construction machinery recovering. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2389-2414. doi: 10.3934/jimo.2020074

[17]

Yongtao Peng, Dan Xu, Eleonora Veglianti, Elisabetta Magnaghi. A product service supply chain network equilibrium considering risk management in the context of COVID-19 pandemic. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022094

[18]

Yan Zhou, Chi Kin Chan, Kar Hung Wong. The impacts of retailers' regret aversion on a random multi-period supply chain network. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2651-2675. doi: 10.3934/jimo.2021086

[19]

Arman Hamedirostami, Alireza Goli, Yousef Gholipour-Kanani. Green cross-dock based supply chain network design under demand uncertainty using new metaheuristic algorithms. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3103-3131. doi: 10.3934/jimo.2021105

[20]

Gokhan Agac, Birdogan Baki, Ilker Murat Ar, Hamdi Tolga Kahraman. A supply chain network design for blood and its products using genetic algorithm: A case study of Turkey. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022179

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (110)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]