Fundamental properties of convex mixed-integer programs

Abstract

In this Ph.D. dissertation research, we lay the mathematical foundations of various fundamental concepts in convex mixed-integer programs (MIPs), that is, optimization problems where all the decision variables belong to a given convex set and, in addition, a subset of them are required to be integer. In particular, we study properties of their feasible region and properties of cutting planes. The main contribution of this work is the extension of several fundamental results from the theory of linear MIPs to the case of convex MIPs.

In the first part, we study properties of general closed convex sets that determine the closedness and polyhedrality of their integer hulls. We first present necessary and sufficient conditions for the integer hull of a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the integer hulls of general convex sets to be polyhedra. This result generalizes the well-known result due to Meyer in the case of linear MIPs. Under a simple technical assumption, we show that these sufficient conditions are also necessary for the integer hull of general convex sets to be polyhedra.

In the second part, we apply the previous results to mixed-integer second order conic programs (MISOCPs), a special case of nonlinear convex MIPs. We show that there exists a polynomial time algorithm to check the closedness of the mixed integer hulls of simple MISOCPs. Moreover, in the special case of pure integer problems, we present sufficient conditions for verifying the closedness of the integer hull of intersection of simple MISOCPs that can also be checked in polynomial time.

In the third part, we present an extension of the duality theory for linear MIPs to the case of conic MIPs. In particular, we construct a subadditive dual to conic MIPs. Under a simple condition on the primal problem, we are able to prove strong duality.

In the fourth part, we study properties of maximal S-free convex sets, where S is a subset of integers contained in an arbitrary convex set. An S-free convex set is a convex set not containing any points of S in its interior. In this part, we show that maximal S-free convex sets are polyhedra and discuss some properties of these sets.

In the fifth part, we study some generalizations of the split closure in the case of linear MIPs. Split cuts form a well-known class of valid inequalities for linear MIPs. Cook et al. (1990) showed that the split closure of a rational polyhedron - that is, the set of points in the polyhedron satisfying all split cuts - is again a polyhedron. In this thesis, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We also show how this result can be used to prove that some generalizations of split cuts, namely cross cuts, also yield closures that are rational polyhedra.