This thesis is concerned with structure exploitation and the design of algorithms for solving
large-scale harvest scheduling problems. We discover that the harvest scheduling problem involving area constraints possesses a network structure. In Model I-Form 1, the network constraints form a separable block diagonal structure, which permits one to solve for the decision variables belonging
to each individual area constraints as independent knapsack problems. In Model II-Form 1, the network constraints constitute a longest path problem, and a Longest Path Algorithm is developed to solve this problem in closed form. The computational time for this scheme is greatly reduced
over that for the revised simplex method. The Dantzig-Wolfe algorithm is coded and tuned to solve
general Model II problems, taking advantage of the Longest Path Algorithm in the subproblem
step, and using the revised simplex method to solve the master problems. Computational results
show that the algorithm solves problems to within one percent accuracy far more efficiently than
the revised simplex method using MPS III. Both the CPU time and number of iterations for the
Dantzig-Wolfe algorithm are less than those for the MPS III, depending on the problem size.
Results also suggest that the Dantzig-Wolfe algorithm makes rapid advances in the initial iterations,
but has a slow convergence rate in the final iterations. A Primal-Dual Conjugate Subgradient Algorithm
is also coded and tuned to solve general Model II problems. Results show that the computational effort is greatly affected by the number of side constraints. If the number of side
constraints is restricted, the Primal-Dual Conjugate Subgradient Algorithm can give a more efficient
algorithm for solving harvest scheduling problems. Overall, from a storage requirement viewpoint,
the Primal-Dual Conjugate Subgradient Algorithm is best, followed by the Dantzig-Wolfe algorithm
and then the revised simplex method. From a computational efficiency viewpoint, if the optimality criterion is suitably selected, the Dantzig-Wolfe algorithm is best, provided that the
number of side constraints are not too many, followed by the revised simplex method and then the
Primal-Dual Conjugate Subgradient Algorithm.
next to an author's name indicates that all files or directories associated with their ETD are accessible from the Virginia Tech campus network only.
![[VT]](http://scholar.lib.vt.edu/images/ETD-db/restricted.gif)
