Special versus standard algorithms for large-scale harvest scheduling problems

Simple item page
dc.contributor.authorLiu, Chiun-Mingen
dc.contributor.committeechairSherali, Hanif D.en
dc.contributor.committeememberSarin, Subhash C.en
dc.contributor.committeememberWang, Ching-Chengen
dc.contributor.departmentIndustrial Engineering and Operations Researchen
dc.date.accessioned2014-03-14T21:37:40Zen
dc.date.adate2012-06-10en
dc.date.available2014-03-14T21:37:40Zen
dc.date.issued1988-12-15en
dc.date.rdate2012-06-10en
dc.date.sdate2012-06-10en
dc.description.abstractThis 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.en
dc.description.degreeMaster of Scienceen
dc.format.extentviii, 63 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-06102012-040227en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-06102012-040227/en
dc.identifier.urihttp://hdl.handle.net/10919/43047en
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1988.L568.pdfen
dc.relation.isformatofOCLC# 19570312en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1988.L568en
dc.subject.lcshLoggingen
dc.subject.lcshWood -- Harvestingen
dc.titleSpecial versus standard algorithms for large-scale harvest scheduling problemsen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineIndustrial Engineering and Operations Researchen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V855_1988.L568.pdf
Size:
2.52 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Masters Theses