On Subadditive Duality for Conic Mixed-Integer Programs

In this paper, we show that the subadditive dual of a feasible conic mixed-integer program (MIP) is a strong dual whenever it is feasible. Moreover, we show that this dual feasibility condition is equivalent to feasibility of the conic dual of the continuous relaxation of the conic MIP. In addition, we prove that all known … Read more

Lattice closures of polyhedra

Given $P\subset\R^n$, a mixed-integer set $P^I=P\cap (\Z^{t}\times\R^{n-t}$), and a $k$-tuple of $n$-dimensional integral vectors $(\pi_1, \ldots, \pi_k)$ where the last $n-t$ entries of each vector is zero, we consider the relaxation of $P^I$ obtained by taking the convex hull of points $x$ in $P$ for which $ \pi_1^Tx,\ldots,\pi^T_kx$ are integral. We then define the $k$-dimensional … Read more

On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

For a fixed integer $t > 0$, we say that a $t$-branch split set (the union of $t$ split sets) is dominated by another one on a polyhedron $P$ if all cuts for $P$ obtained from the first $t$-branch split set are implied by cuts obtained from the second one. We prove that given a … Read more

On the polyhedrality of cross and quadrilateral closures

Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook, Kannan and Schrijver (1990) showed that the split closure of a rational polyhedron $P$ is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We … Read more

Closedness of Integer Hulls of Simple Conic Sets

Let $C$ be a full-dimensional pointed closed convex cone in $R^m$ obtained by taking the conic hull of a strictly convex set. Given $A \in Q^{m \times n_1}$, $B \in Q^{m \times n_2}$ and $b \in Q^m$, a simple conic mixed-integer set (SCMIS) is a set of the form $\{(x,y)\in Z^{n_1} \times R^{n_2}\,|\,\ Ax +By … Read more

Strong Dual for Conic Mixed-Integer Programs

Mixed-integer conic programming is a generalization of mixed-integer linear programming. In this paper, we present an extension of the duality theory for mixed-integer linear programming to the case of mixed-integer conic programming. In particular, we construct a subadditive dual for mixed-integer conic programming problems. Under a simple condition on the primal problem, we are able … Read more

Some Properties of Convex Hulls of Integer Points Contained in General Convex Sets

In this paper, we study properties of general closed convex sets that determine the closed-ness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results … Read more

On Maximal S-free Convex Sets

Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. … Read more