Polyhedral and Non-polyhedral Cutting Plane Methods: Theory, Algorithims and Applications

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

Cutting plane methods can be used to solve many classes of optimization problems, including integer programming problems. These methods form a sequence of relaxations of the problem and gradually tighten the relaxations in order to find a solution to the original problem. Polyhedral cutting plane methods work with linear programming relaxations of the problem of interest. Interior point cutting plane methods have the potential to solve problems that are not amenable to simplex methods, because of the size of the problem or because superior cutting planes may be generated at an interior point. Computational experience suggests that these methods can outperform simplex cutting plane methods, and that combining interior point and simplex methods can be especially useful. Nonpolyhedral cutting plane methods look at relaxations such as semidefinite programming problems. Methods of interest in this proposal include solving semidefinite programming problems by solving a sequence of smaller semidefinite programs, and solving integer programs through the addition of nonpolyhedral cutting planes. The non-polyhedral approaches offer the possibility of tackling problems that were previously unsolved, and of using a new, possibly better, approach to problems previously solved. The development of the methods discussed in this proposal will make it possible to solve problems that were previously considered intractable. The proposed research will result in efficient, practical algorithms for solving large instances of many classes of integer programming problems, as well as other optimization problems. These problems will be drawn from diverse fields, including engineering, economics, finance, and physics. A doctoral student will be supported by this proposal. Research developed as a result of the proposal will be incorporated into graduate courses in integer programming and linear programming at RPI. Test sets for various problems will be collected and generated, and these problems will be made available on the web. Computer code arising from this project will be made available electronically where possible.