Abstract
This dissertation poses fundamentally new results based on separation theory to resolve a number of issues in linear optimization. First, redundancies present in a collection of linear inequalities are characterized, and two separation procedures, based on strong separation of convex polyhedra, are devised specifically for resolving the redundancy problem. While the first procedure determines whether or not a given inequality is redundant relative to a polyhedron having a nonredundant representation, the second does the same for an arbitrary polyhedron. These separation procedures can be interpreted as determining whether a given vector belongs to a pointed, polyhedral cone and in a convex polytope, respectively. Then, by exploiting the duality relationships existing between separation and optimization, it is shown that the underlying theory can address a number of issues in polyhedral theory such as determining feasibility, dimensionality and boundedness of arbitrary polyhedra. The separation procedures are then specialized to resolve binary integer programming problems. As a fundamental result, it is shown that, for positive 0/1 programming problems, the separation procedures can generate facets of the underlying polytope in a number of steps that is polynomial in the problem size. A set of selected test problems is used to evaluate the computational characteristics of the solution procedure on binary problems arising in real-world applications. Computational evaluation focuses on solving assembly system design problems since this work is sponsored by an ongoing project directed toward that important area.
Parija, Gyana Ranjan (1994). A new approach for resolving certain linear optimization problems using separation theory. Texas A&M University. Texas A&M University. Libraries. Available electronically from
https : / /hdl .handle .net /1969 .1 /DISSERTATIONS -1516797.