The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem

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.

Accordingly, in Part ll of this dissertation, we present an application of such polyhedral results in order to construct effective approximate and exact algorithms for solving a naval defense problem. tn this problem, the objective is to schedule a set of illuminators in order to strike a given set of targets using surface-to-air missiles in naval battle-group engagement scenarios. The problem is conceptualized as a production floor shop scheduling problem of minimizing the total weighted flow time subject to time-window job availability and machine-downtime unavailability side constraints. A polynomial-time algorithm is developed for the case when ail the job processing times are equal (and unity without loss of generality) and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop three alternative formulations and analyze their relative strengths by comparing their respective linear programming relaxations. The special structures inherent in a particular strong zero-one integer programming model of the problem enable us to derive some classes of strong valid inequalities from the facets of the GUB constrained knapsack polytope and the set-packing polytope. Furthermore, these special structures enable us to construct several effective approximate and exact algorithms that provide solutions within specified tolerances of optimality, with an effort that admits real-time processing in the naval battle-group engagement scenario. Computational results are presented using suitable realistic test data.