9802773 Balas The research funded by this grant addresses some basic theoretical and methodological aspects of integer and combinatorial optimization. Over the last few years the principal investigators have developed a technique called lift-and-project for solving mixed integer programs. When embedded in an enumerative framework, called branch-and-cut, this approach has shown itself to be highly robust and competitive with the best available alternatives. A major goal of the research is to consolidate these results and develop the approach in new directions, by solving several open problems concerning the properties of the cutting planes used; the way of generating and handling them; and, the interplay between cutting and branching. Part of this research will combine polyhedral methods with some tools borrowed from artificial intelligence. A closely related research topic is focussed on a heuristic procedure called OCTANE, which uses a neighborhood search defined by a construction based on polarity. Another topic involves ideal 0-1 matrices, which make certain integer programs defined by them solvable as linear programs. Finally, a substantial part of the research will focus on the traveling salesman problem, and some of its generalizations, focusing on a dynamic programming approach that can efficiently solve large classes of problems in this area. The research envisaged here is expected to substantially enhance the state of the art in solving integer and combinatorial optimization problems in general, traveling salesman-type problems in particular. Some of the investigations are aimed at gaining new theoretical insights and a deeper understanding of the structures involved, but most of the research is methodological in nature and is therefore expected to result in more efficient algorithms and computer codes. The problems to which such algorithms may be applicable range from investment decisions, capacity expansion models, location and distribution problems, to industrial scheduling and sequencing.
