The extreme point mathematical programming problem

Abstract

This dissertation deals with a class of nonconvex mathematical programs called Extreme Point Mathematical Programs (EPMP). These problems are generalizations of certain Integer Programming problems and also find their application in other nonconvex programs like the Concave Minimization problem. The research addresses the design and analysis of algorithms for EPMP. However, most of the ideas are quite general and apply to a wider class of mathematical programs including the Generalized Lattice Point Problem. We obtain a variety of cutting plane algorithms and analyze the convergence of such algorithms. Insightful examples of nonconvergence are also provided. Two finitely convergent algorithms are also presented. One of these is a cutting plane based procedure while the other is a branch and bound scheme. Computational experience with both algorithms is given.