One of the logistic problems that is encountered by management is the planning of routing structures. Therefore the availability of decision-making tools that determine minimum cost routes is essential. The purpose of this dissertation is to obtain a tight lower bound on the cost of a routing plan, and to possibly obtain an optimal route, by enhancing graphical-construct-based Lagrangean relaxation methodology. This enhancement synthesizes Lagrangean relaxation with the well-established polyhedral theory which uses facet-inducing inequalities to describe the facial structure of the associated routing problem. The algorithmic enhancement that is developed and tested in this dissertation is demonstrated in the context of the minimum cost Hamiltonian path problem. The entire algorithmic procedure is based on recognizing and successively incorporating facet-inducing inequalities into the Lagrangean function. In this sense the procedure solves a sequence of Lagrangean duals each providing a tighter lower bound on the routing problem. Each Lagrangean dual has the node-degree constraints and a set of facet-inducing inequalities dualized. Central to the development of the sequence of Lagrangean duals is the ability to identify facet-inducing inequalities. A graphical-construct-based dual-ascent algorithm, which is also developed in this dissertation, solves each Lagrangean dual to optimality and obtains a solution that enables the identification of additional facet-inducing inequalities. This solution is either the optimal primal solution or else, a solution that violates some facet-inducing inequalities that are not subsumed in the subgraph structure nor in the set of dualized constraints. Computational testing of this exact algorithm reveals the distinction between theoretical duality gaps and 'solution technique induced' duality gaps. The work in this dissertation extends the state-of-the-art of graphical-construct-based solution methodologies in as far as the resolution of the duality gap is concerned. The primary significance of resolving the gap using facet-inducing inequalities is not only that the revealed gap is explained by (or due to) facet-inducing inequalities but also that optimal primal solutions can be obtained without resorting to enumeration. The inherent advantage afforded by retaining graphical structures, while incorporating the power of facet-inducing inequalities, is evidenced by the relatively small number of facets that were required to obtain optimal primal solutions.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-8966 |
| Date | 01 January 1994 |
| Creators | Shmerling, Shirley |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.296 seconds