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. 
Tsai, K.H.
Keywords: Network simplex methods
Piecewise linear programming
Issue Date: 1997
Citation: 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
ISSN: 02175959
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Nov 24, 2020

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.