The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem
MetadataShow full item record
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.
- Doctoral Dissertations