Fundamental properties of convex mixed-integer programs

Integer programming;Cutting planes;Convex hull;Integer hull;Optimization;Split cuts

Moran Ramirez, Diego Alejandro ; Dey, Santanu S. Industrial and Systems Engineering Ahmed, Shabbir Nemirovski, Arkadi Cook, William Gunluk, Oktay Vielma, Juan Pablo ; Dey, Santanu S.

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Integer programming;    Cutting planes;    Convex hull;    Integer hull;    Optimization;    Split cuts;   

Others  :  https://smartech.gatech.edu/bitstream/1853/52309/1/MORANRAMIREZ-DISSERTATION-2014.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

In this Ph.D. dissertation research, we lay the mathematical foundations ofvarious fundamental concepts in convex mixed-integer programs (MIPs), that is,optimization problems where all the decision variables belong to a given convexset and, in addition, a subset of them are required to be integer. In particular, westudy properties of their feasible region and properties of cutting planes. The maincontribution of this work is the extension of several fundamental results from thetheory of linear MIPs to the case of convex MIPs.In the first part, we study properties of general closed convex sets that determinethe closedness and polyhedrality of their integer hulls. We first presentnecessary and sufficient conditions for the integer hull of a general convex set tobe closed. This leads to useful results for special classes of convex sets such aspointed cones, strictly convex sets, and sets containing integer points in their interior.We then present a sufficient condition for the integer hulls of general convexsets to be polyhedra. This result generalizes the well-known result due to Meyer inthe case of linear MIPs. Under a simple technical assumption, we show that thesesufficient conditions are also necessary for the integer hull of general convex setsto be polyhedra.In the second part, we apply the previous results to mixed-integer second orderconic programs (MISOCPs), a special case of nonlinear convex MIPs. We show thatthere exists a polynomial time algorithm to check the closedness of the mixed integerhulls of simple MISOCPs. Moreover, in the special case of pure integerproblems, we present sufficient conditions for verifying the closedness of the integerhull 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 MIPsto the case of conic MIPs. In particular, we construct a subadditive dual to conicMIPs. Under a simple condition on the primal problem, we are able to prove strongduality.In the fourth part, we study properties of maximal S-free convex sets, whereS is a subset of integers contained in an arbitrary convex set. An S-free convexset is a convex set not containing any points of S in its interior. In this part, weshow that maximal S-free convex sets are polyhedra and discuss some propertiesof these sets.In the fifth part, we study some generalizations of the split closure in the caseof linear MIPs. Split cuts form a well-known class of valid inequalities for linearMIPs. 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 apolyhedron. In this thesis, we extend this result from a single rational polyhedronto the union of a finite number of rational polyhedra. We also show how this resultcan be used to prove that some generalizations of split cuts, namely cross cuts, alsoyield closures that are rational polyhedra.