Algorithms for optimizing piecewise linear functions and for degree-constrained minimum spanning tree problems

Two issues are discussed in depth in this dissertation--the optimization of nondifferentiable functions and the degree constrained minimum spanning tree problem. First we study the optimization of nondifferentiable functions. We limit to the class of functions which are continuous, piecewise linear and concave (or convex). Lagrangian relaxation duals belong to this category. We have designed a new algorithm--the intersection algorithm to compute the optimal solution. This algorithm will be shown to converge geometrically. Three combinatorial optimization problems have been tested. These are the bi-knapsack problem, the assignment problem and the uncapacitated facility location problem. By comparing the results with subgradient optimization algorithm and multiplier adjustment algorithm, we found that our algorithm runs faster than subgradient algorithm and is easier to implement than the multiplier adjustment algorithm. Second, we study the degree constrained minimum spanning tree problem. The degree constrained minimum spanning tree is a minimum spanning tree with a given root node restricted to have a prespecified degree. It finds applications in telecommunication, electronic circuit board design, computer networking, in the relaxation method for solving the multiple traveling salesman problem and vehicle routing problems. We have found efficient polynomial algorithms for obtaining optimal degree constrained spanning tree in $O(n\sp2)$ time which is the same computational complexity as a regular minimum spanning tree problem. Some important properties on the degree constrained spanning tree are also found and discussed in this dissertation