A generator and a simplex solver for network piecewise linear programs
This is a brief report on our recent work in network piecewise linear programming (NPLP), and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical network linear program generator NETGEN. The generator creates networks of the same...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Published: |
Springer-Verlag
1994
|
| Online Access: | http://hdl.handle.net/20.500.11937/91448 |
| _version_ | 1848765523427328000 |
|---|---|
| author | Sun, Jie Tsai, K. |
| author_facet | Sun, Jie Tsai, K. |
| author_sort | Sun, Jie |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This is a brief report on our recent work in network piecewise linear programming (NPLP), and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical network linear program generator NETGEN. The generator creates networks of the same topological structures as NETGEN, but each arc is associated with a convex piecewise linear cost. The purpose of this program is to provide a set of standard test problems which can be used to compare the performance of various algorithms for NPLP. In the second part, we introduce a network simplex method that directly solves a network piecewise linear program without reformulating it as a network linear program of higher dimension. Forty benchmark NPLP problems are solved by this method and a reformulation method. The computational results are in favor of the direct method and show that solving an NPLP problem is not much harder than solving a network linear program of the same dimension. © 1994 Science Press, Beijing, China and Allerton Press, Inc., New York, U.S.A. |
| first_indexed | 2025-11-14T11:36:36Z |
| format | Journal Article |
| id | curtin-20.500.11937-91448 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T11:36:36Z |
| publishDate | 1994 |
| publisher | Springer-Verlag |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-914482023-04-20T04:51:02Z A generator and a simplex solver for network piecewise linear programs Sun, Jie Tsai, K. This is a brief report on our recent work in network piecewise linear programming (NPLP), and it consists of two parts. In the first park, we describe a generator for NPLP problems which is derived from the classical network linear program generator NETGEN. The generator creates networks of the same topological structures as NETGEN, but each arc is associated with a convex piecewise linear cost. The purpose of this program is to provide a set of standard test problems which can be used to compare the performance of various algorithms for NPLP. In the second part, we introduce a network simplex method that directly solves a network piecewise linear program without reformulating it as a network linear program of higher dimension. Forty benchmark NPLP problems are solved by this method and a reformulation method. The computational results are in favor of the direct method and show that solving an NPLP problem is not much harder than solving a network linear program of the same dimension. © 1994 Science Press, Beijing, China and Allerton Press, Inc., New York, U.S.A. 1994 Journal Article http://hdl.handle.net/20.500.11937/91448 10.1007/BF02006117 Springer-Verlag restricted |
| spellingShingle | Sun, Jie Tsai, K. A generator and a simplex solver for network piecewise linear programs |
| title | A generator and a simplex solver for network piecewise linear programs |
| title_full | A generator and a simplex solver for network piecewise linear programs |
| title_fullStr | A generator and a simplex solver for network piecewise linear programs |
| title_full_unstemmed | A generator and a simplex solver for network piecewise linear programs |
| title_short | A generator and a simplex solver for network piecewise linear programs |
| title_sort | generator and a simplex solver for network piecewise linear programs |
| url | http://hdl.handle.net/20.500.11937/91448 |