This is a program of research on several topics in combinatorial optimization with the objective of enhancing understanding of the underlying mathematics of some combinatorial problems. The importance of the research lies in the fact that a better understanding of the mathematics associated with these problems (most of them belonging to the class of nonpolynomial- complete or hard problems) can be used in the design of algorithms that solve and prove optimality of medium to large instances that typically arise in real world applications. The research includes investigation of the properties of 0, 1 matrices, whose associated set packing polytope has integer extreme points, and the facial structure of some combinatorial polytopes associated with connectivity and partitioning problems on graphs. The algorithmic issues associated with the detection of violated constraints for such problems will be investigated. The problem area of combinatorial optimization is very important, a breakthrough in this area would be highly leveraged.
