The proposed research focuses on several topics in Integer Programming with the objective of advancing our understanding of the underlying mathematics of some combinatorial optimization problems. The importance of the research lies on the fact that significant advances on the understanding of the mathematics associated with these problems yield improvements in the capacity of solving large scale problems, that typically arise in real world applications. The techniques to be used are the ones typical of Integer Programming and Polyhedral Combinatorics. More specifically, the PI's will investigate structural propertiese of 0.1 matrices whose associated set packing polytope has integer extreme points. They also intend to continue investigations on the facial structure of some polytopes associated with some packing or covering problems. Algorithmic issues related to optimization problems on circuits of binary matroids will also be studied. Professors Rao and Conforti are well known researchers in combinatorial optimization and are well qualified to achieve success in this research. New York University is a suitable environment for the study. An award is recommended at the revised budget level for two years.
