Please use this identifier to cite or link to this item:
|Title:||A simplex method and its implementation for network piecewise linear programming|
|Authors:||Sun, J. |
|Keywords:||Network simplex methods|
Piecewise linear programming
|Source:||Sun, J.,Tsai, K.H. (1997). A simplex method and its implementation for network piecewise linear programming. Asia-Pacific Journal of Operational Research 14 (1) : 55-68. ScholarBank@NUS Repository.|
|Abstract:||Network piecewise linear programming is a useful model in operations research. It could be solved as network linear programming through a reformulation approach which greatly increases the number of variables. This paper describes a direct simplex algorithm and its implementation for network piecewise linear programming. By allowing nonbasic variables to take breakpoint values and using nominal costs at breakpoints of the objective function, this method keeps the number of variables in the original level and simplifies the computation of the reduced cost. This is important for applications in which the number of breakpoints is large; for instance, the stochastic network flow problem and the piecewise linearized convex network program. The method takes good advantage of tree data structures and combines ratio test with the computation of reduced costs. Computational experiment is conduced on the 40 benchmark network programs of Klingman et al. by replacing the linear costs with piecewise linear costs. The result of the test shows that solving a network problem with piecewise linear cost is not much harder than solving a linear problem on the same network.|
|Source Title:||Asia-Pacific Journal of Operational Research|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 15, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.