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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/52309 |
| Date | 27 August 2014 |
| Creators | Moran Ramirez, Diego Alejandro |
| Contributors | Dey, Santanu S. |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf |
Page generated in 0.0018 seconds