This research deals with a study of the polyhedral structure of three important combinatorial
optimization problems, namely, the generalized upper bounding (GUS) constrained knapsack
problem, the set partitioning problem, and the quadratic zero-one programming problem, and
applies related techniques to solve a practical combinatorial naval defense problem.
In Part I of this research effort, we present new results on the polyhedral structure of the
foregoing combinatorial optimization problems. First, we characterize a new family of facets
for the GUS constrained knapsack polytope. This family of facets is obtained by sequential
and simultaneous lifting procedures of minimal GUS cover inequalities. Second, we develop
a new family of cutting planes for the set partitioning polytope for deleting any fractional basic
feasible solutions to its underlying linear programming relaxation. We also show that all the
known classes of valid inequalities belong to this family of cutting planes, and hence, this
provides a unifying framework for a broad class of such valid inequalities. Finally, we present
a new class of facets for the boolean quadric polytope, obtained by applying a simultaneous
lifting procedure.
The strong valid inequalities developed in Part I, such as facets and cutting planes, can be
implemented for obtaining exact and approximate solutions for various combinatorial optimization
problems in the context of a branch-and-cut procedure. In particular, facets and valid
cutting planes developed for the GUS constrained knapsack polytope and the set partitioning
polytope can be directly used in generating tight linear programming relaxations for a certain scheduling polytope that arises from a combinatorial naval defense problem. Furthermore,
these tight formulations are intended not only to develop exact solution algorithms, but also
to design powerful heuristics that provide good quality solutions within a reasonable amount
of computational effort.
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)
