Objective Variation Network Simplex Algorithm for Concave Continuous Piecewise Linear Network Flow Problems
| Autor: | Shuning Wang, Yu Bai, ZhiBin Nie, ZhiMing Xu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Network simplex algorithm
0209 industrial biotechnology Mathematical optimization 021103 operations research Computer science Computation 0211 other engineering and technologies Linearity 02 engineering and technology Variation (game tree) Flow network Piecewise linear function 020901 industrial engineering & automation Simplex algorithm Piecewise |
| Zdroj: | ICCAE |
| DOI: | 10.1145/3192975.3192978 |
| Popis: | In this work, an efficient algorithm is developed for the local optimization of Concave Continuous Piecewise Linear Network Flow Problems (CCPLNFP) with network constraints. Inspired by the piecewise linearity and concavity of the cost functions in CCPLNFP, we propose an Objective Variation Network Simplex Algorithm (OVNSA) based on a network simplex method (NSM), which derives a locally optimal solution. For large-scale problems, OVNSA fails to obtain a local minimum within acceptable computation time. Hence, we propose a Modified Objective Variation Network Simplex Algorithm (MOVNSA), which provides a sub-optimal solution within reasonable computation time. Numerical experiments show high efficiency of the proposed algorithms compared with two relevant algorithms on random test problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|