A simplex method and its implementation for network piecewise linear programming

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.