Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/45027
Title: A simplex method and its implementation for network piecewise linear programming
Authors: Sun, J. 
Tsai, K.H.
Keywords: Network simplex methods
Optimization
Piecewise linear programming
Issue Date: 1997
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
URI: http://scholarbank.nus.edu.sg/handle/10635/45027
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)

93
checked on Dec 15, 2017

Google ScholarTM

Check


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