During the last decade, there have been major advances in solving a class of large-scale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems.
This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems.
For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are series-parallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case.
For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the ATSP case, we develop a Tree Composition method, which generates all non-spanning clique tree facetial inequalities. / Business, Sauder School of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/32385 |
| Date | January 1991 |
| Creators | Wang, Yaoguang |
| Publisher | University of British Columbia |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
Page generated in 0.0017 seconds