This research will investigate a variety of topics in discrete optimization. The models derive from integer programming problems of broad applicability in operations research, computer science, and many areas of the natural, engineering, mathematical, and social sciences. The apparent computational intractibility of the most general such models is well known; thus, highly structured combinatorial optimization models are the focus of the proposed research. The models to be studied are frequently directly applicable to real-world problems and in other instances serve as components in solution methodology for more general models. Algorithmic insight gained from study of such highly structured models is often a useful guide in the design of heuristic solution procedures of general applicability. Two major research projects are proposed. First, a classification scheme for combinatorial packing and covering models is proposed as a means to guide further research on problems related to supply-demand networks, production scheduling, stock cutting, two-terminal cut packing, branchings, and vertex packing. Second, a linear duality model is proposed as a unifying framework for investigating duality properties of linear subspaces, polyhedral cones, rational geometric lattices, and certain classes of integer programming problems.
