A sequential simplex algorithm for the continuous convex piecewise linear network flow problem
| Autor: | Shuning Wang, Zhibin Nie |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Network simplex algorithm
050210 logistics & transportation Mathematical optimization 021103 operations research Linear programming Computer science 05 social sciences 0211 other engineering and technologies Linearity 02 engineering and technology Function (mathematics) Flow network Piecewise linear function Flow (mathematics) Simplex algorithm 0502 economics and business |
| Zdroj: | ICCA |
| DOI: | 10.1109/icca.2019.8899971 |
| Popis: | This paper presents a descent algorithm for the continuous convex piecewise linear network flow problem (CCPWLNFP). The CCPWLNFP can be reformulated as a linear programming problem and directly solved by mature algorithms. However, reformulation methods not only greatly increase the problem scale but also destroy the excellent structure of the constraint matrix. The sequential simplex algorithm (SSA) makes use of the linearity of the cost function on each segment and transforms the CCPWLNFP to a series of linear network flow problems with the original constraint matrix. The mature bounded network simplex algorithm can be applied to solve these linear network flow problems efficiently. In numerical experiments, the SSA is compared with two reformulation methods and shows its superior optimization efficiency. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|