---
abstract: |
    In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for packing sets as a function of the integrality gap. We also provide a similar lower bound on the split rank of covering polyhedra. These results indicate that whenever the integrality gap is high, these classes of cutting planes must necessarily be applied for many rounds in order to obtain the integer hull.\
    \
    **Keywords.** Integer programming, packing, covering, split rank, multi-branch split rank, lattice-free rank
author:
- 'Merve Bodur[^1]'
- 'Alberto Del Pia[^2]'
- 'Santanu S. Dey[^3]'
- 'Marco Molinaro[^4]'
bibliography:
- 'LatticeFreeRank.bib'
title: 'Lower bounds on the lattice-free rank for packing and covering integer programs'
---

Introduction {#sec:intro}
============

*Split cuts* are a very important class of cutting planes in integer programming both from a theoretical and computational perspective (see for example [@balas:1979; @BalasS08; @cook:ka:sc:1990]). Recently, many generalizations of split cuts have been studied, such as the *multi-branch split cuts* [@dash2014lattice; @dash2013t; @li:ri:2008] and the *lattice-free cuts* [@andersen2007inequalities; @basu2015geometric; @borozan:2007; @RichardDey]. In order to study the strength of the cutting plane procedures, a very useful concept is the notion of *rank* which represents the minimum rounds of cuts needed to obtain the integer hull. The notion of rank was first studied in the context of Chvátal-Gomory (CG) cuts [@Schrijver80]. Many lower bounds on the rank of the above mentioned closures have been proven; see [@BasuCM12; @bodur2017cutting; @cook:ka:sc:1990; @dey:lowerbnd:2009; @DeyL11; @li:ri:2008] for the split rank, see [@dash2013t] for the multi-branch rank, and see [@averkov2017approximation] for the lattice-free rank.

A standard notion describing the [difficulty]{} of an integer program is the *integrality gap* which in this paper refers to the ratio between the optimal objective function values of the integer program and its linear programming relaxation. While it is natural to expect that the rank of a cutting plane procedure should increase with the increase in the integrality gap, only a few results of this nature exist in the literature [@bodur2016aggregation; @PokuttaS11].

In this paper, we present lower bounds on the rank of the split closure, the multi-branch closure and the lattice-free closure for *packing sets* as a function of the integrality gap. We also provide a similar lower bound on the split rank of *covering polyhedra*. These results indicate that whenever the integrality gap is high, these classes of cutting planes must necessarily be applied for many rounds in order to obtain the integer hull.

The rest of the paper is organized as follows. We provide all necessary definitions in Section \[sec:Prelim\]. We state all our main results in Section \[sec:Statements\]. Finally, in Section \[sec:Packing\] and Section \[sec:Covering\] we present the proofs for results concerning the packing and covering cases, respectively.

Preliminaries {#sec:Prelim}
=============

For an integer $t \geq 1$, we use $[t]$ to describe the set $\{1, \dots, t\}$. Also, we represent the $j^{\text{th}}$ unit vector, the vector of ones and the vector of zeros in appropriate dimension by $e_j$, ${\boldsymbol{1}}$ and ${\boldsymbol{0}}$, respectively. Given a set of vectors $v^1, \hdots, v^t$, we denote the linear subspace spanned by these given vectors as $\spann ( \{ v^j \}_{j \in [t]} )$.

#### Sets.

In this paper, we work with *covering [polyhedra]{}* and *packing [polyhedra]{}*, which are of the form $$P_C = \{x \in {\mathbb{R}}^n_+ \mid Ax \ge b \} \quad \text{and} \quad P_P = \{x \in {\mathbb{R}}^n_+ \mid Ax \le b \},$$ respectively, where all the data $(A,b) \in {\mathbb{Q}}_+^{m \times n} \times {\mathbb{Q}}_+^m$. [Thus, an inequality of packing type (respectively covering type) is one of the form $a^\top x \le b$ (respectively $a^\top \ge b$) for non-negative $(a,b) \in {\mathbb{Q}}_+^n \times {\mathbb{Q}}_+$.]{} If it is obvious from the context that the polyhedron is of covering (resp. packing) type, we may drop the subscript $C$ (resp. $P$). For the packing case, we also work with more general sets. We call $Q \ {{\color{black}}\subseteq} \ {\mathbb{R}}_+^n$ a *packing set* if $x \in Q$ and ${\boldsymbol{0}}\leq y \leq x$ imply that $y \in Q$.

Throughout this paper, we make a technical assumption regarding the sets under consideration that we call as *well-behavedness*. The set $P_C$ is *well-behaved* if $A_{ij} \leq b_i$ for all $i \in [m], j \in [n]$. Notice that this is a natural assumption since if $A_{ij} > b_i$ for some $i \in [m], j \in [n]$, then we can replace the coefficient $A_{ij}$ by $b_i$ to obtain a tighter linear programming relaxation with the same set of feasible integer points. A packing set $Q$ is *well-behaved* if $e_j \in Q$ for all $j \in [n]$. This is not a restrictive assumption since if $e_j \notin Q$ for some $j \in [n]$, then we replace $Q$ with the packing set $\{ x \in Q \mid x_j = 0\}$, which provides a tighter linear relaxation with the same set of feasible integer points. Note that if $Q$ is the polytope $P_P$, then [the]{} well-behavedness definition is equivalent to $A_{ij} \leq b_i$ for all $i \in [m], j \in [n]$.

[A *relaxation* of a set $P$ is any superset $\tilde{P} \supseteq P$.]{} Let $\alpha > 0$ be a scalar. If a given covering polyhedron $\tilde{P}_C$ is a relaxation of $P_C$ and satisfies $$\min\{c^\top x \mid x \in \tilde{P}_C\} \ge \frac{1}{\alpha} \cdot \min\{c^\top x \mid x \in P_C\}, \ \ \forall c \in {\mathbb{R}}_+^n,$$ then $\tilde{P}_C$ is an *$\alpha$-approximation* of $P_C$. Similarly, given a packing set $P_P$ and one of its relaxation $\tilde{P}_P$ of packing type, $\tilde{P}_P$ is an *$\alpha$-approximation* of $P_P$ if $$\max\{c^\top x \mid x \in \tilde{P}_P\} \le \alpha \cdot \max\{c^\top x \mid x \in P_P \}, \ \ \forall c \in {\mathbb{R}}_+^n.$$ For a set $P \subseteq {\mathbb{R}}^n$, we define $\alpha P:= \{\alpha x \mid  x \in P\}$. The equivalent definitions of $\alpha$-approximation for covering and packing cases are provided in [@bodur2016aggregation] as $$\frac{1}{\alpha} \tilde{P}_C  {\subseteq}P_C \quad \text{and} \quad \tilde{P}_P {\subseteq}\alpha P_P,$$ respectively.

Given a polyhedron $P {\subseteq}{\mathbb{R}}^n$, we denote its integer hull by $P^I := \operatorname{conv}( \{x \mid x \in P \cap {\mathbb{Z}}^n\})$ where $\operatorname{conv}(\cdot)$ is the convex hull operator. We let ${z^{LP}(c)}$ and ${z^{I}(c)}$ to denote the optimal value of a given objective function $c^\top x$ over $P$ and $P^I$, respectively. For convenience, we will sometimes refer to ${z^{LP}(c)}$ and ${z^{I}(c)}$ as $z^{LP}$ and $z^{I}$, respectively.

#### Closures.

We call a set ${M}\in {\mathbb{R}}^n$ a *strict lattice-free set* if $M \cap {\mathbb{Z}}^n = \emptyset$. Note that the set ${M}$ need not to be convex. Given a set $Q$, one can obtain a relaxation of $Q^I$ as $$Q^{M}:= \operatorname{conv}(Q \setminus {M}).$$ Given a collection of strict lattice-free sets ${\mathcal{{M}}}$, we define the corresponding closure as $${\mathcal{{M}}}(Q) = \bigcap_{{M}\in {\mathcal{{M}}}} Q^{M}.$$ For convenience, we sometimes refer to ${\mathcal{{M}}}$ as the closure operator or just as closure.

Next, we define three special cases of the strict lattice-free closures, namely the split closure, the multi-branch closure and the lattice-free closure.

We denote the *split set* associated with $(\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}$ by $$S(\pi,\pi_0) := \{ x \in {\mathbb{R}}^n \mid \pi_0 < \pi^\top x < \pi_0+1\}.$$ [Denoting]{} the collection of all split sets by $${{\color{black}}{\mathcal{S}}= \{S(\pi,\pi_0) \mid (\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}\},}$$ the split closure of $Q$, denoted as ${\mathcal{S}}(Q)$, is defined to be $${\mathcal{S}}(Q) = \bigcap_{S \in {\mathcal{S}}} Q^S.$$ For convenience, we denote $Q^{S(\pi,\pi_0)}$ by $Q^{\pi,\pi_0} $ which is explicitly defined as $$Q^{\pi,\pi_0} = \operatorname{conv}(Q \setminus S(\pi,\pi_0)) = \operatorname{conv}\big( (Q \cap \{ \pi^\top x \leq \pi_0 \}) \cup (Q \cap \{ \pi^\top x \geq \pi_0+1 \}) \big).$$ A generalization of split closure, called the *$k$-branch split closure*, which is defined by [@li:ri:2008], is obtained by removing the union of *at most* $k$ split sets simultaneously. Letting $$\begin{aligned}
Q^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0} :&= \operatorname{conv}\Big( Q \setminus \bigcup_{i \in [k]} S(\pi^i,\pi^i_0) \Big) \\
&= \operatorname{conv}\left( \bigcap_i (Q \cap \{ (\pi^i)^\top x \leq \pi^i_0 \}) \cup (Q \cap \{ (\pi^i)^\top x \geq \pi^i_0+1 \}) \right),\end{aligned}$$ the $k$-branch split closure of $Q$, denoted by ${{\mathcal{S}}^{k}}(Q)$, can be written as $${{\mathcal{S}}^{k}}(Q) = \bigcap_{(\pi^i,\pi^i_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}},~i \in [k]} Q^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0}.$$ Note that the 1-branch split closure is equivalent to the split closure, i.e, ${\mathcal{S}}^{1}(Q)={\mathcal{S}}(Q)$.

A further generalization of the split closure is the so-called *lattice-free closure*, which is obtained by considering convex sets having no integer point in their interior; see [@dash2012two; @dash2014lattice] for relations to the $k$-branch split closure. A set $L {\subseteq}{\mathbb{R}}^n$ is called a *lattice-free set* if $\int(L) \cap {\mathbb{Z}}^n = \emptyset$ where $\int(\cdot)$ is the interior operator. For each integer $k \geq 2$, we define ${\mathcal{L}}^k$ as the family of full-dimensional lattice-free polyhedra $L \subset {\mathbb{R}}^n$ defined by *at most* $k$ inequalities. (Note that it is not possible to have lattice-free sets defined by only one inequality.) We denote the *$k$-lattice-free closure* of $P$ by ${\mathcal{L}}^k(Q)$, i.e., $${\mathcal{L}}^k(Q) = \bigcap_{L \in {{\color{black}}{\mathcal{L}}^k}} Q^L,$$ where $$Q^L := \operatorname{conv}(Q \setminus \int(L)).$$ Given a closure operator ${\mathcal{{M}}}$ and a nonnegative objective function $c \in {\mathbb{R}}^n_+$, we use $z^{{\mathcal{{M}}}}$ to denote the optimal value of the minimization (or maximization) of $c^\top x$ over the closure ${\mathcal{{M}}}(Q)$. Lastly, we define the *rank* of the closure ${\mathcal{{M}}}$, denoted by $\operatorname{rank}_{{\mathcal{{M}}}}(Q)$, as the minimum number of iterative applications of ${\mathcal{{M}}}$ to obtain the integer hull of $Q$. We note that the split rank, thus the multi-branch rank and the lattice-free rank, are finite whenever $Q$ is a rational polyhedron or is a bounded set [@Schrijver80].

Main results {#sec:Statements}
============

Packing
-------

The main proof strategy to prove lower bounds on ranks of various cutting plane closures is presented in the proposition below.

\[thm:thm1\] Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets which satisfies the following two conditions:

1.  Packing invariance: For any packing set $Q$, ${\mathcal{{M}}}(Q)$ is a packing set.

2.  Constant approximation: There exists $\alpha_{\mathcal{{M}}}\geq 1$ such that $Q {\subseteq}\alpha_{\mathcal{{M}}}{\mathcal{{M}}}(Q)$ for every well-behaved packing set $Q$.

Then, for any well-behaved packing set $Q$, $$\operatorname{rank}_{{\mathcal{{M}}}}(Q) \geq {{\color{black}}\sup_{c \in {\mathbb{R}}_+^n}} \left\lceil \frac {\log_2 \left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)}{\log_2 \alpha_{\mathcal{{M}}}}\right\rceil.$$

The proof of Proposition \[thm:thm1\] is based on a simple iterative argument, which is provided in Section \[subsec:4.1\].

### Tools to prove the assumptions of Proposition \[thm:thm1\]

In order to use Proposition \[thm:thm1\], we need to verify the packing invariance and constant approximation properties. The next tool is very helpful in proving packing invariance.

\[thm:thm2\] Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets. For ${T}{\subseteq}[n]$, define $H[{T}] := \{ x \in {\mathbb{R}}^n \mid x_j = 0, \ \forall j \in T\}$. Given ${M}\in {\mathcal{{M}}}$, let $$M[{T}] := ( M \cap H[{T}] ) + \spann ( \{ e_{j} \}_{j \in T} ).$$ Suppose that ${\mathcal{{M}}}$ satisfies the following property: For any ${M}\in {\mathcal{{M}}}$ and $T {\subseteq}[n]$, $M[{T}] \neq \emptyset$ implies that $M[{T}] \in {\mathcal{{M}}}$. Then ${\mathcal{{M}}}$ is packing invariant.

Note that it is straightforward to see that the set ${M}[T]$ in Theorem \[thm:thm2\] is guaranteed to be a strict lattice-free set by construction. The proof of Theorem \[thm:thm2\] is essentially based on the fact that a cut generated using a strict lattice-free set $M$ is dominated by a packing type inequality that is obtained using the strict lattice-free set $M[T]$ for a specifically chosen set $T$. The details of the proof of Theorem \[thm:thm2\] are given in Section \[subsec:4.2\].

We observe here that in order to use Proposition \[thm:thm1\], we must prove [the]{} constant approximation property for general well-behaved packing sets, rather than just for polyhedra. The reason is that the closures of some cutting plane families we consider are not known to be polyhedral. In order to prove [the]{} constant approximation property for general well-behaved packing sets, we will find it convenient to prove this property first for well-behaved packing polyhedra. It turns out that this is sufficient to prove constant approximation property for any well-behaved packing set as the next theorem states.

\[thm:thm3\] Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets with the following property: There exist $\alpha_{\mathcal{{M}}}\geq 1$ such that $P_P {\subseteq}\alpha_{\mathcal{{M}}}{\mathcal{{M}}}(P_P)$ for every well-behaved packing polyhedron $P_P$. Then, $Q {\subseteq}\alpha_{\mathcal{{M}}}{\mathcal{{M}}}(Q)$ for every well-behaved packing set $Q$.

Theorem \[thm:thm3\] is proven by first constructing a well-behaved packing polyhedron which is an inner approximation of $Q$ and is arbitrarily close to $Q$. We then show how to “transfer" the $\alpha_{\mathcal{{M}}}$ factor from this polyhedron to $Q$. The details of the proof of Theorem \[thm:thm3\] are provided in Section \[subsec:4.3\].

### Applications of Proposition \[thm:thm1\] to split, multi-branch split and lattice-free closures

We use Theorem \[thm:thm2\] to verify the following result.

\[thm:thm4\] ${\mathcal{{M}}}$ is packing invariant for ${\mathcal{{M}}}\in \{ {\mathcal{S}}, {\mathcal{S}}^k, {\mathcal{L}}^k \}$.

Theorem \[thm:thm4\] is proven in Section \[subsec:4.4\].

\[thm:thm5\] For ${\mathcal{{M}}}\in \{ {\mathcal{S}}, {\mathcal{S}}^k, {\mathcal{L}}^k \}$, ${\mathcal{{M}}}$ satisfies the constant approximation property, where [we can choose]{} $\alpha_{{\mathcal{S}}} = 2$, [$\alpha_{{\mathcal{S}}^k} = \min \{ 2^k,n \}+1$, and $\alpha_{{\mathcal{L}}^k} = \min \{ k,n \}+1$]{}.

Moreover, the factor $\alpha_{{\mathcal{S}}}$ is tight, i.e., for every $\epsilon >0$, there exists a well-behaved packing polyhedron $\tilde{P}_P$ such that $\tilde{P}_P \not\subseteq (2-\epsilon) {\mathcal{S}}(\tilde{P}_P)$.

Observe that the split cuts are a special case of multi-branch split cuts. However, we have stated their constant approximation result separately since the general factor for multi-branch split closure is not tight for the split closure. Indeed, proving the factor of 2 in the case of split cuts involves more careful analyses. Moreover, this factor of 2 for the split case is tight as stated in the theorem. The proof of Theorem \[thm:thm5\] for the split, multi-branch split and lattice-free cases are given in Sections \[subsubsec:4.5.1\], \[subsubsec:4.5.2\] and \[subsubsec:4.5.3\], respectively.

Note that a factor of $2$ is proven in [@bodur2016aggregation] as an approximation factor of the *aggregation closure*, which is very similar to the result [for the]{} split closure in Theorem \[thm:thm5\]. However, the split closure result of Theorem \[thm:thm5\] is not implied by the result of [@bodur2016aggregation] since for packing polyhedra, split cuts are not [always]{} dominated by *aggregation cuts*, see the example given in Observation \[obs:PackingSplitAgg\] in Appendix \[sec:appendix\].

Proposition \[thm:thm1\], Theorem \[thm:thm4\] and Theorem \[thm:thm5\] lead us to the following lower bounds on the rank of [the]{} split closure, $k$-branch split closure and $k$-lattice-free closure of packing sets. As Corollary \[cor:cor1\] is a direct application of Proposition \[thm:thm1\], we omit its proof.

\[cor:cor1\] Let $Q$ be a well-behaved packing set. Then

1.  $\operatorname{rank}_{{\mathcal{S}}}(Q) \geq {{\color{black}}\sup_{c \in {\mathbb{R}}_+^n}} \left\lceil \log_2 \left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)\right\rceil$.

2.  $\operatorname{rank}_{{\mathcal{S}}^k}(Q) \geq {{\color{black}}\sup_{c \in {\mathbb{R}}_+^n}} \left\lceil\frac{\log_2 \left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)}{\log_2 (\min \{ 2^k,n \}+1)}\right\rceil$ for any $k \in {\mathbb{Z}}_+, k \geq 1$.

3.  $\operatorname{rank}_{{\mathcal{L}}^k}(Q) \geq {{\color{black}}\sup_{c \in {\mathbb{R}}_+^n}} \left\lceil\frac{\log_2 \left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)}{\log_2 (\min \{ k,n \}+1)}\right\rceil$ for any $k \in {\mathbb{Z}}_+, k \geq 2$.

Corollary \[cor:cor1\] shows that if the integrality gap is high, then we cannot expect the split rank, the multi-branch split rank or the lattice-free rank of a well-behaved packing set to be low.

To the best of our knowledge, the only other paper analyzing the rank of general lattice-free closures is [@averkov2017approximation], and the only papers presenting lower bounds on the rank of multi-branch split closure for very special [kinds]{} of polytopes are [@dash2013t] and [@li:ri:2008]. We note that none of these bounds are related to the [integrality]{} gap.

There have been a number of papers giving lower bounds on split ranks such as [@BasuCM12; @bodur2017cutting; @cook:ka:sc:1990; @dey:lowerbnd:2009; @DeyL11] and bounds on a closely related concept, the [reverse]{} split rank [@ConfortiPSFSpli15]. To the best of our knowledge, this is the first work connecting the integrality gap to the split rank. We note that the first part of Corollary \[cor:cor1\] can be seen as a generalization of the result given in [@PokuttaS11] for the CG rank.

The lower bound on the split rank given in Corollary \[cor:cor1\] is tight within a constant factor as formally stated below.

\[prop:prop1\] There exists a well-behaved packing polyhedron $Q$ and a nonnegative objective function $c$ such that $\operatorname{rank}_{{\mathcal{S}}}(Q) \le O\left(\textup{log}_2\left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)\right)$.

The proof of Proposition \[prop:prop1\] is given in Section \[subsubsec:4.5.4\].

Covering
--------

We now state our results for covering [polyhedra]{}. All the proofs regarding the covering case are given in Section \[sec:Covering\].

\[thm:mainAppCovering\] Let $P_C$ be well-behaved. Then, the followings hold:

-   ${\mathcal{S}}(P_C)$ is a well-behaved covering polyhedron.

-   $\frac{1}{2} P_C   {\subseteq}{\mathcal{S}}(P_C) $.

Moreover, the bound given in (ii) is tight, i.e., for every $\epsilon >0$, there exists a well-behaved covering polyhedron $\tilde{P}_C$ such that $\frac{1}{2-\epsilon} \tilde{P}_C  \not {\subseteq}{\mathcal{S}}(\tilde{P}_C)$.

Regarding part (i) of Theorem \[thm:mainAppCovering\], ${\mathcal{S}}(P_C)$ is known to be a rational polyhedron since $P_C$ is assumed to be a rational polyhedron [[@cook:ka:sc:1990]]{}, and it is straightforward to show that the split closure is of covering type (Proposition \[prop:CoveringPoly\]); whereas its well-behavedness can be proven by showing that each split cut that violates the well-behavedness property is dominated by a well-behaved split cut (Proposition \[prop:CoveringSplitWell\]). Proof of part (ii) follows from a case analysis that gives the correct factor of [$\frac{1}{2}$]{} (Proposition \[prop:covering2approx\]). For the last statement in the theorem, we provide a tight example in Proposition \[prop:LBAC\].

Note that a [result similar]{} to Theorem \[thm:mainAppCovering\] is proven in [@bodur2016aggregation] with respect to the [aggregation closure]{}. However, Theorem \[thm:mainAppCovering\] is not implied by the result of [@bodur2016aggregation] since for covering polyhedra, split cuts are not dominated by [aggregation cuts]{}, see the example given in Observation \[obs:CoveringSplitAgg\] in Appendix \[sec:appendix\].

Similar to the proof of Proposition \[thm:thm1\] in the packing case, Theorem \[thm:mainAppCovering\] yields the following lower bound on the split rank of covering polyhedra.

\[cor:SplitRankPolyCovering\] Let $P_C$ be well-behaved. Then, $$\operatorname{rank}_{{\mathcal{S}}}(P_C) \geq {{\color{black}}\sup_{c \in {\mathbb{R}}_+^n}} \left\lceil \textup{log}_2\left( \frac{{z^{I}(c)}}{{z^{LP}(c)}}\right)\right\rceil.$$

Unlike the packing case, we are unable to generalize the result of Corollary \[cor:SplitRankPolyCovering\] for the case of $k$-lattice-free rank. The key technical argument that is a roadblock is to prove the well-behavedness of the $k$-lattice-free closure of covering polyhedron. [We do not know if the $k$-lattice-free closure of covering polyhedron is well-behaved. Note that in contrast]{} in the packing case, if we start from a well-behaved set and the closure is of packing type, then trivially the closure is also well-behaved.

Proofs for packing problems {#sec:Packing}
===========================

We use the following observation, from [@bodur2016aggregation], in some of the proofs.

\[obs:bijection\] Let $\phi:\mathbb{R}^n \rightarrow \mathbb{R}^n$ be a bijective map, let $\{S^i\}_{i \in I}$ be a collection of subsets of $\mathbb{R}^n$ and [for $S {\subseteq}\mathbb{R}^n$]{} let $\phi(S):= \{ \phi(x) \,|\, x \in S\}$. Then $\phi\left(\bigcap_{i \in I} S^i\right) = \bigcap_{i \in I} \phi(S^i)$.

Proof of Proposition \[thm:thm1\] {#subsec:4.1}
---------------------------------

Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets which satisfies the packing invariance and constant approximation properties. Let $Q {\subseteq}{\mathbb{R}}^n$ be a well-behaved packing set. Since $Q^I {\subseteq}{\mathcal{{M}}}(Q)$, we have that $e_j \in {\mathcal{{M}}}(Q)$ for all $j \in [n]$. Therefore, by the packing invariance property, ${\mathcal{{M}}}(Q)$ is also a well-behaved packing set.

[Assume that the rank of the closure ${\mathcal{{M}}}$ is finite, as there is nothing to prove otherwise.]{} Let $t = \operatorname{rank}_{{\mathcal{{M}}}}(Q)$ and let $c \in {\mathbb{R}}_+^n$ be a given objective vector. Define $z^{i}$ to be the optimal objective function value of maximizing $c^\top x$ over the $i^{\text{th}}$ closure with respect to ${\mathcal{{M}}}$ of $Q$. Since, ${\mathcal{{M}}}(Q)$ is a well-behaved packing set, by induction, the $i^{\text{th}}$ closure with respect to ${\mathcal{{M}}}$ of $Q$ is a well-behaved packing set. Therefore, the constant approximation property guarantees that $z^i \le {{\color{black}}\alpha_{\mathcal{{M}}}} z^{i+1}$. Thus, $$\begin{aligned}
\frac{{z^{LP}(c)}}{{z^{I}(c)}} = \frac{{z^{LP}(c)}}{z^1} \frac{z^1}{z^2}\dots\frac{z^{t-1}}{z^{t}} \leq {(\alpha_{\mathcal{{M}}})}^{t}.\end{aligned}$$ This implies the inequality $$\begin{aligned}
t = \operatorname{rank}_{{\mathcal{{M}}}}(Q) \geq \left\lceil \frac{\textup{log}_2\left( \frac{{z^{LP}(c)}}{{z^{I}(c)}}\right)}{\textup{log}_2 \alpha_{\mathcal{{M}}}} \right\rceil,\end{aligned}$$ which is the required result.

Proof of Theorem \[thm:thm2\] {#subsec:4.2}
-----------------------------

Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets with the following property. For ${T}{\subseteq}[n]$, define $H[{T}] := \{ x \in {\mathbb{R}}^n | x_j = 0, \ \forall j \in T\}$. Given ${M}\in {\mathcal{{M}}}$, let $$M[{T}] := ( M \cap H[{T}] ) + \spann ( \{ e_{j} \}_{j \in T} ).$$ Assume that for any ${M}\in {\mathcal{{M}}}$ and $T {\subseteq}[n]$, if $M[{T}] \neq \emptyset$, then $M[{T}] \in {\mathcal{{M}}}$. We will show that ${\mathcal{{M}}}$ is packing invariant.

Let $Q$ be a packing set. If $Q$ is empty, then there is nothing to prove. Therefore, assume that $Q$ is nonempty.

Let ${M}\in {\mathcal{{M}}}$. Let ${\beta}^\top x \le \delta$ be a valid inequality for $Q^{M}$. We will show that this inequality is dominated by a packing type inequality valid for ${\mathcal{{M}}}(Q)$. Let $T = \{ j \in [n] : {\beta}_j < 0\}$. If $T = \emptyset$, there is nothing to prove. So, assume that $T \neq \emptyset$.

For convenience, we define an operator $\breve{(\cdot)}$ as follows: For a given vector $u \in {\mathbb{R}}^n$, $\breve{u} \in {\mathbb{R}}^n$ is $$\begin{aligned}
\breve{u}_j = \left \{
\begin{array}{rl}
u_j, & \text{if} \ j \in [n] \setminus T \\
0, & \text{if} \ j \in T
\end{array}
\right. .  \label{eq:opBreve}
    \end{aligned}$$

We will show that $\breve {\beta}^\top x \le \delta$ is a valid inequality for ${\mathcal{{M}}}(Q)$. Since $\breve {\beta}\in {\mathbb{R}}^n_+$ and $\{x \in {\mathbb{R}}^n_+ : \breve {\beta}x \le \delta \} \subseteq \{x \in {\mathbb{R}}^n_+ : {\beta}^\top  x \le \delta \}$, we obtain the required result.

Let $\bar Q := Q \cap H[T]$. As $\bar Q \subseteq Q$, we have that ${\beta}^\top x \le \delta$ is a valid inequality for ${\bar Q}^{M}$. Since $\breve {\beta}^\top x = {\beta}^\top x$ for every $x \in H[T]$, we obtain that $$\label{betaineqValidForQbarM}
\breve {\beta}^\top x \le \delta \ \text{is a valid inequality for}  \ {\bar Q}^{M}.$$

Now, we [distinguish]{} two cases:

-   $H[{T}] \cap {M}= \emptyset$: In this case, we know that $\bar Q = {\bar Q}^{M}$, thus, using , we have that $\breve {\beta}x \leq \delta$ is valid for $\bar Q$. We show that $\breve {\beta}^\top x \le \delta$ is valid for $Q$, and therefore trivially for ${\mathcal{{M}}}(Q)$. Assume by contradiction that there is a point $x \in Q$ such that $\breve {\beta}^\top x > \delta$. We have $\breve {\beta}^\top \breve x = \breve {\beta}^\top x > \delta$. As $Q$ is a packing set, we have $\breve x \in Q$. Moreover, since $\breve x \in H[T]$, we have $\breve x \in \bar Q$. Thus $\breve x$ is a vector in $\bar Q$ with $\breve {\beta}^\top \breve x > \delta$, a contradiction since $\breve {\beta}x \leq \delta$ is valid for $\bar Q$. Therefore, in this case the statement is trivially satisfied.

-   $H[{T}] \cap {M}\neq \emptyset$: By the definition of $M[T]$, we have that ${M}[{T}] \neq \emptyset$ and $$H[{T}] \cap {M}= H[{T}] \cap {M}[T].$$ Therefore, $\bar Q \setminus {M}= \bar Q \setminus {M}[T]$, which together with imply that $$\label{factForContradictionMT}
    \breve {\beta}^\top x \le \delta \ \text{is a valid inequality for} \ {\bar Q}^{{\mathcal{{M}}}[T]}.$$ We now show that $\breve {\beta}^\top x \le \delta$ is a valid inequality for $Q^{{M}[T]}$. Assume by contradiction that there is a point $x \in Q \setminus {M}[T]$ such that $\breve {\beta}^\top x > \delta$. We have $\breve {\beta}^\top \breve x = \breve {\beta}^\top  x > \delta$. As $Q$ is a packing set, we have $\breve x \in Q$. Moreover, since $\breve x \in H[T]$, we have $\breve x \in \bar Q$. Finally, since $x \notin {M}[T]$, we obtain that also $\breve x \notin {M}[T]$ by definition of ${M}[T]$. Thus $\breve x$ is a vector in $\bar Q \setminus {M}[T]$ with $\breve {\beta}^\top \breve x > \delta$, a contradiction to .

Proof of Theorem \[thm:thm3\] {#subsec:4.3}
-----------------------------

Let ${\mathcal{{M}}}$ be a collection of strict lattice-free sets with the following property: There exist $\alpha_{\mathcal{{M}}}\geq 1$ such that $P_P {\subseteq}\alpha_{\mathcal{{M}}}{\mathcal{{M}}}(P_P)$ for every well-behaved packing polyhedron $P_P$. Let $Q$ be a well-behaved packing set. We will show that $Q {\subseteq}\alpha_{\mathcal{{M}}}{\mathcal{{M}}}(Q)$.

Our strategy to prove this statement is to first construct, in Lemma \[prop:SantanuLemma\], a well-behaved packing polyhedron which is an inner approximation of $Q$ and [can be chosen]{} arbitrarily close to $Q$.. Then, we apply the $\alpha_{\mathcal{{M}}}$ factor to this polyhedral approximation and “transfer" it to $Q$.

\[prop:SantanuLemma\] Let $\epsilon > 0$. Then, there exists a well-behaved packing polyhedron $P_\epsilon$ such that $\frac{1}{1+\epsilon} Q \subseteq P_\epsilon \subseteq Q$.

[First, consider the case that $Q$ is bounded.]{} Let $\sigma_Q$ be the support function of $Q$, i.e., $$\sigma_Q (u) = \sup \{ u^\top x | x \in Q \},$$ and $$C^n := \{ u \in {\mathbb{R}}^n_+ \, | \, \|u\|_2 = 1 \}.$$ Also, let $\tilde{Q} = \frac{1}{1+\epsilon} Q$. We first show that there exists $M > 0$ such that $$\label{eq:sigmaLB}
\sigma_{\tilde{Q}}(u) \geq M \ \text{for all} \ u \in C^n.$$ Let $S = \{ x \in {\mathbb{R}}^n_+ ~|~ {\boldsymbol{1}}^\top x \leq 1 \}$ and $\tilde{S} = \frac{1}{1+\epsilon} S$. Since $Q$ is well-behaved, we have that $S \subseteq Q$, thus $\tilde{S} \subseteq \tilde{Q}$. Therefore, $\sigma_{\tilde{S}}(u) \leq \sigma_{\tilde{Q}}(u)$ for all $u \in C^n$. Since [$\sigma_{\tilde{S}}(u) \geq \frac{1}{\sqrt{n}(1+\epsilon)}$]{} for all $u \in C^n$, holds.

Let $\bar{M} = \max \{ \|x\|_\infty ~|~ x \in \tilde{Q} \}$. It is well-known that $\sigma_{\tilde{Q}} (\cdot)$ is continuous since $\tilde{Q}$ is a compact convex set [@rockafellar:1970]. Moreover, as $\|\cdot\|_2$ is also continuous, [for any $u \in C^n$ and $\epsilon > 0$ there exists a neighborhood $N_u$ of $u$ (in the topology of the sphere)]{} such that for all $v \in N_u$ we have [$$\label{eq:contsigma}
|\sigma_{\tilde{Q}}(u) - \sigma_{\tilde{Q}}(v)| \le \frac{\epsilon M}{4}$$ ]{} and $$\label{eq:cont2norm}
\| u - v\|_2 \leq \frac{\epsilon M}{4 \bar{M}\sqrt{n}}.$$ Since $C^n$ is a compact set, there exists a finite list of vectors $v_1,\hdots,v_\ell $ such that $C^n = \cup_{i=1}^\ell N_{v_i}$. Define $$\label{eq:Psetdef}
P^1_\epsilon := \{ x \in {\mathbb{R}}^n_+ ~|~ (v_i)^\top x \leq \sigma_{\tilde{Q}}(v_i), \forall i=1,\hdots,\ell, \ \text{and} \ x_i \leq \bar{M}, \forall i=1,\hdots,n \}$$

We now show that $$\label{eq:innerapprox}
\tilde{Q} \subseteq P^1_\epsilon \subseteq (1+\frac{\epsilon}{2}) \tilde{Q} \subseteq Q.$$ Note that the first and the last containments are straightforward. In order to show the second containment, we [show]{} that $\sigma_{P^1_\epsilon}(u) / \sigma_{\tilde{Q}}(u) \leq 1+\frac{\epsilon}{2}$ for all $u \in C^n$. For a given $u \in C^n$, let $i \in \{ 1, \hdots,\ell\}$ such that $u \in N_{v_i}$. Observe that $$\begin{aligned}
\sigma_{P^1_\epsilon}(u) & \leq \sigma_{P^1_\epsilon}(v_i) + \sigma_{P^1_\epsilon}(u-v_i) \nonumber \\
& \leq \sigma_{P^1_\epsilon}(v_i) + \| u - v_i \|_2 \cdot \max_{x \in P^1_\epsilon} \{ \| x \|_2 \} \nonumber \\
& \leq \sigma_{P^1_\epsilon}(v_i) + \frac{\epsilon M}{{{\color{black}}4} \sqrt{n} \bar{M}} \sqrt{n} \bar{M} \nonumber \\
& = \sigma_{P^1_\epsilon}(v_i) + \frac{\epsilon M}{4} \nonumber \\
& \leq \sigma_{\tilde{Q}}(v_i) + \frac{\epsilon M}{4} \nonumber \\
& \leq \sigma_{\tilde{Q}}(u) + \frac{\epsilon M}{4} + \frac{\epsilon M}{4} \nonumber \\
& = \sigma_{\tilde{Q}}(u) + \frac{\epsilon M}{2},  \label{eq:fifthineq} \end{aligned}$$ where the first inequality is due to the subadditivity property of the support functions [@rockafellar:1970], the second is due to the Cauchy-Schwartz inequality, the third follows from and , the fourth inequality is implied by the constraints defining $P_\epsilon$ in , and the last inequality is satisfied by . Inequality can be written as $$\frac{\sigma_{P^1_\epsilon}(u)}{\sigma_{\tilde{Q}}(u)} \leq 1+ \frac{\epsilon M}{2 \sigma_{\tilde{Q}}(u)} \leq 1+ \frac{\epsilon}{2},$$ [the second inequality]{} follows from .

Due to , $P^1_\epsilon$ achieves almost all the required conditions except the fact that it may not be well-behaved. Therefore, let $$P_\epsilon = \operatorname{conv}{(P^1_\epsilon \cup S)}.$$ First, note that $\tilde{Q} \subseteq P^1_\epsilon \subseteq P_\epsilon \subseteq Q$ where the first two containments are straightforward, and the last containment follows from the fact that $S \subseteq Q$ and $P^1_\epsilon \subseteq Q$. It remains to verify that $P_\epsilon$ is a packing polyhedron which would imply that it is [a]{} well-behaved packing polyhedron since $S \subseteq P_\epsilon$. However, observe that $P_\epsilon$ is the convex hull of the union of two packing polyhedra, and therefore it is straightforward to verify that it is a packing polyhedron.

Now suppose $Q$ is not bounded. Then we can decompose it as $Q = B + R$, where $B$ is a bounded packing set and $R$ is the recession cone of $Q$; explicitly, let $I = \{i \mid \operatorname{cone}(e_i) \subseteq Q\}$, so $B = Q \cap \{x \mid x_i \le 0~\forall i \in I\}$ and $R = \operatorname{cone}(\{e_i\}_{i \in I})$. Furthermore, let $\bar{B} = \operatorname{conv}(B \cup \bigcup_{i \in I} e_i)$, so that $\bar{B}$ is a *well-behaved* bounded packing set; notice $Q = B + R = \bar{B} + R$.

Applying the proof above to the bounded set $\bar{B}$, we obtain a well-behaved packing *polyhedron* $P_\epsilon$ satisfying $\frac{1}{1+\epsilon} \bar{B} \subseteq P_\epsilon \subseteq \bar{B}$. Then $P_\epsilon + R$ is a well-behaved packing polyhedron (the polyhedrality follows from the fact $\bar{B}$ is a polytope and $R$ is finitely generated, see for example Theorem 3.13 of [@ConCorZam14b]). Finally, since $\alpha P_\epsilon + R = \alpha (P_\epsilon + R)$ for all $\alpha > 0$, $$\frac{1}{1+\epsilon} (\bar{B} + R) = \frac{1}{1 + \epsilon} \bar{B} + R \subseteq P_\epsilon + R \subseteq \bar{B} + R.$$ Since $\bar{B} + R = Q$, $P_\epsilon + R$ is the desired polyhedral approximation. This concludes the proof.

Noting that $${\mathcal{{M}}}(Q) = \bigcap_{{M}\in {\mathcal{{M}}}} Q^{M},$$ it is sufficient to prove that $$\label{eq:Pkplusone}
Q  \subseteq  (\alpha_{\mathcal{{M}}}) \,  Q^{M},$$ [for an arbitrary $M \in {\mathcal{{M}}}$]{} (see Observation \[obs:bijection\]).

Let $\epsilon > 0$ and $P_\epsilon$ be the well-behaved packing polyhedron satisfying the conditions of Lemma \[prop:SantanuLemma\]. Then, observe that $$\label{eq:generalContainment}
\frac{1}{1+\epsilon} Q \subseteq P_\epsilon \subseteq (\alpha_{\mathcal{{M}}}) (P_\epsilon)^{M}\subseteq (\alpha_{\mathcal{{M}}}) \,  Q^{M},$$ where the first and the last containments follow due to $\frac{1}{1+\epsilon} Q \subseteq P_\epsilon \subseteq Q$, whereas the second one holds by assumption and the fact that $P_\epsilon$ is well-behaved.

Note that can be written as $Q \subseteq (1+\epsilon) (\alpha_{\mathcal{{M}}}) \,  Q^{M}$. Since $\epsilon$ can be arbitrarily small, we obtain that $Q \subseteq (\alpha_{\mathcal{{M}}}) \,  Q^{M}$.

Proof of Theorem \[thm:thm4\] {#subsec:4.4}
-----------------------------

Note that it is sufficient to prove the statement for ${\mathcal{{M}}}\in \{ {\mathcal{S}}^k, {\mathcal{L}}^k \}$ since ${\mathcal{S}}$ is a special case of ${\mathcal{S}}^k$. We will use Theorem \[thm:thm2\] to prove this statement. That is, letting $T {\subseteq}[n]$, we will show that for every ${M}\in {\mathcal{{M}}}$, we have ${M}[{T}] \in {\mathcal{{M}}}$ as well. [Recall the operator $\breve{(\cdot)}$ from equation .]{}

-   Consider an arbitrary element of ${\mathcal{S}}^k$ as $$M = \bigcup_{i \in [k]} S(\pi^i,\pi^i_0).$$ Observe that $$M[{T}] = \bigcup_{i \in [k]} S(\breve \pi^i,\pi^i_0).$$ If $\breve \pi^i = {\boldsymbol{0}}$, then $S(\breve \pi^i,\pi^i_0) = \emptyset$. Therefore, $M[T]$ is also a $k$-branch split set since $k$-branch split is defined to be the union of at most $k$ split sets.

-   Consider an arbitrary element of ${\mathcal{L}}^k$ as $$M = \{ x \in {\mathbb{R}}^n | (\pi^i)^\top x < \pi^i_0, \ i = 1,\hdots,k \} .$$ Observe that $$M[{T}] = \{ x \in {\mathbb{R}}^n | (\breve \pi^i)^\top x < \pi^i_0, \ i = 1,\hdots,k \} .$$ If $\breve \pi^i = {\boldsymbol{0}}$, then either the inequality $(\breve \pi^i)^\top x < \pi^i_0$ is trivially satisfied, or $M[{T}] = \emptyset$. Therefore, $M[T]$ is also a $k$-lattice-free set since $k$-lattice-free set is defined to be the union of at most $k$ lattice-free sets.

Proof of Theorem \[thm:thm5\]
-----------------------------

In order to make the proofs more self-contained, we record here standard bounds on the integrality gap of well-behaved packing polyhedra, which are essentially Proposition 6 of [@bodur2016aggregation].

\[prop:intGapPack\] Consider a well-behaved packing polyhedron $P_P = \{x \in {\mathbb{R}}^n_+ \mid (a^i)^{\top} x \le b_i,~\forall i \in [m]\}$. Then $P_P$ is a $(\min\{m,n\} + 1)$-approximation of the integer hull $P_P^I$.

It is equivalent to show that $P_P$ is both an $(m+1)$- and an $(n+1)$-approximation of $P_P^I$. The former is precisely Proposition 6 of [@bodur2016aggregation], and the latter follows from similar arguments, reproduced here. Given a cost vector $c \in {\mathbb{R}}^n_+$, we need to show that $\max\{c^\top x \mid x \in P_P\} \le (n + 1) \max\{c^\top x \mid x \in P_P^I\} =: (n+1) z^I$. Let $x^{LP}$ be an optimal solution for the left-hand side, and let $\hat{x}$ be the integer solution obtained by rounding down each component of $x^{LP}$. Since each component of the difference $x^{LP} - \hat{x}$ is in $[0,1]$, we have $$\begin{aligned}
            z^I \ge c^\top \hat{x} \ge c^{\top} x^{LP} - \|c\|_{\infty}.
        \end{aligned}$$ Moreover, since $P_P$ is well-behaved, all canonical vectors $e_i$ belong to $P_P^I$ and hence $z^I \ge \|c\|_{\infty}$. Adding $n$ times this lower bound to the displayed equation, we obtain $(n+1)z^I \ge c^{\top} x^{LP}$, thus proving the desired result. This concludes the proof.

### Case of ${\mathcal{S}}$ {#subsubsec:4.5.1}

We show that $\alpha_{\mathcal{S}}= 2$ in Proposition \[prop:packing2approx\]. The proof of Proposition \[prop:packing2approx\] involves a reduction to analyzing split closure of a packing polyhedron in ${\mathbb{R}}^2$, and a case analysis in ${\mathbb{R}}^2$ gives the correct factor of 2 (Lemma \[lem:pack\_2approx\]). For the last statement in the theorem, we provide a tight example in Proposition \[prop:pack\_TightEx\].

[We start with the proof of the result for the two-dimensional case.]{}

\[lem:pack\_2approx\] Let $P_P \subseteq {\mathbb{R}}^2$ be well-behaved. Then $P_P {\subseteq}2 {\mathcal{S}}(P_P)$.

[By [@cook:ka:sc:1990] and by Theorem \[thm:thm4\], the set $S(P_P)$ is a well-behaved packing polyhedron. To show that $P_P {\subseteq}2 {\mathcal{S}}(P_P)$, we just need to show that for all facet-defining inequalities ${\beta}^\top x \le \delta$ of $S(P_P)$, the inequality ${\beta}^\top x \le 2  \delta$ is valid for $P_P$. This is trivially satisfied for the facet-defining inequalities of $S(P_P)$ of the type $x_i \ge 0$, thus it remains to be shown for the other facet-defining inequalities of $S(P_P)$. Since $S(P_P)$ is of packing type, such facet-defining inequalities are of the form ${\beta}^\top x \le \delta$ with ${\beta}\in {\mathbb{R}}^2_+$. Since the split closure is finitely generated [@Ave12], each facet-defining inequality ${\beta}^\top x \le \delta$ of $S(P_P)$ defines a facet of a set $P_P^T := \operatorname{conv}(P_P \setminus \int T)$, where $T$ is a split set. (Note that the polyhedra $P_P^T$ are not necessarily of packing type.) Therefore, to complete the proof of the lemma, it suffices to show that for every split set $T$, and for every inequality ${\beta}^\top x \le \delta$ with ${\beta}\in {\mathbb{R}}^2_+$ valid for $P_P^T$, the inequality ${\beta}^\top x \le 2  \delta$ is valid for $P_P$. We show that for every split set $T$, and for every ${\beta}\in {\mathbb{R}}^2_+$, there exists $\hat x \in P_P^T$ that satisfies $\max\{{\beta}^\top x \mid x \in P_P\} \le 2{\beta}^\top \hat x$. This completes the proof because ${\beta}^\top \hat x \le \delta$ implies that every point in $P_P$ satisfies ${\beta}^\top x \le \max\{{\beta}^\top x \mid x \in P_P\} \le 2{\beta}^\top \hat x \le 2 \delta$.]{}

[Now, fix a split set $T$ and a vector]{} ${\beta}\in {\mathbb{R}}^2_+$, and let $\bar x$ be a vector in $P_P$ that achieves $\max\{{\beta}^\top x \mid x \in P_P\}$. Since $P_P$ is a packing polyhedron, we have $\bar x \ge 0$. We divide the proof in three main cases based on the position of vector $\bar x$.

1\. In the first case we assume that $\bar x \ge (1,1)$, and we define $\hat x := \lfloor \bar x \rfloor$. Since $P_P$ is a packing polyhedron, we have that $\hat x \in P_P \cap {\mathbb{Z}}^2 \subseteq P_P^T$. As $\bar x \ge (1,1)$, we have $2 \hat x \ge \bar x$. Finally, ${\beta}\ge 0$ implies $2 {\beta}^\top \hat x \ge {\beta}^\top \bar x$ as desired.

2\. In the second case we assume that $\bar x \le (1,1)$. Since $P_P$ is well-behaved, we have that points $(1,0)$ and $(0,1)$ are in $P_P$ and therefore in $P_P^T$. If ${\beta}_1 \ge {\beta}_2$, we define $\hat x := (1,0)$. Then $2{\beta}^\top \hat x = 2 {\beta}_1 \ge {\beta}_1 + {\beta}_2$. Since ${\beta}\ge 0$ and $\bar x \le (1,1)$, we have ${\beta}_1 + {\beta}_2 \ge {\beta}^\top \bar x$, which implies $2{\beta}^\top \hat x \ge {\beta}^\top \bar x$ as desired. Symmetrically, if ${\beta}_2 \ge {\beta}_1$, we define $\hat x := (0,1)$, and obtain $2{\beta}^\top \hat x \ge {\beta}^\top \bar x$.

3\. In the third case we assume that $\bar x_1 < 1$ and $\bar x_2 > 1$. (The same argument works for the symmetric case $\bar x_2 < 1$ and $\bar x_1 > 1$.) Assume first that $T$ is *not* a vertical split set [$\{x \mid t \le x_1 \le t+1\}$]{} for some integer $t$. Define now $\hat x^1 := \lfloor \bar x \rfloor = (0,{\lfloor\bar x_2\rfloor})$. Since $P_P$ is [a packing polyhedron]{}, [the]{} vector $\hat x^1$ is in $P_P \cap {\mathbb{Z}}^2$, and therefore in $P_P^T$. If $2{\beta}^\top \hat x^1 = 2 {\beta}^\top (0,{\lfloor\bar x_2\rfloor}) \ge {\beta}^\top \bar x$, then we are done, thus we now assume $2 {\beta}^\top (0,{\lfloor\bar x_2\rfloor}) \le {\beta}^\top \bar x$.

Let $\hat x^2 := (\bar x_1, \bar x_2-1)$. It can be shown that, since $T$ is not a vertical split set, the vector $\hat x^2$ is in $P_P^T$. We show $2 {\beta}^\top \hat x^2 = 2{\beta}^\top (\bar x_1,\bar x_2 -1) \ge {\beta}^\top \bar x$. Since ${\lfloor\bar x_2\rfloor} \ge 1$ and ${\beta}_2 \ge 0$, we have ${\beta}^\top \bar x \ge 2 {\beta}_2 {\lfloor\bar x_2\rfloor} \ge 2 {\beta}_2$. By adding ${\beta}^\top \bar x$ to both sides we obtain $2 {\beta}^\top \bar x - 2 {\beta}_2 \ge {\beta}^\top \bar x$, thus $2{\beta}^\top (\bar x_1,\bar x_2 -1) \ge {\beta}^\top \bar x$.

Finally, assume that $T$ is a vertical split set [$\{x \mid t \le x_1 \le t+1\}$]{} for some integer $t$. Define now $\hat x^1 := (1,0)$. Since $P_P$ is well-behaved, [the]{} vector $\hat x^1$ is in $P_P \cap {\mathbb{Z}}^2$, and therefore in $P_P^T$. If $2{\beta}^\top \hat x^1 = 2 {\beta}^\top (1,0) \ge {\beta}^\top \bar x$, then we are done, thus we now assume $2 {\beta}^\top (1,0) \le {\beta}^\top \bar x$. Define $\hat x^2 := (0, \bar x_2)$ and note that $\hat x^2 \in P_P^T$ since $T$ is a vertical split set. We show $2{\beta}^\top\hat x^2 = 2{\beta}^\top (0, \bar x_2) \ge {\beta}^\top \bar x$. Since ${\beta}_1 \ge 0$ and $\bar x_1 < 1$, we have $2 {\beta}_1 \bar x_1 < 2 {\beta}_1$. By summing the latter with $2 {\beta}_1 \le {\beta}^\top \bar x$ we obtain $2 {\beta}_1 \bar x_1 \le {\beta}^\top \bar x$. By adding and subtracting $2{\beta}_2 \bar x_2$ to the left-hand, we get $2 {\beta}^\top \bar x - 2{\beta}_2 \bar x_2 \le {\beta}^\top \bar x$ which implies $2 {\beta}_2 \bar x_2 \ge {\beta}^\top \bar x$ as desired.

\[prop:packing2approx\] Let $Q {\subseteq}{\mathbb{R}}^n$ be a well-behaved packing set. Then, $Q {\subseteq}2 {\mathcal{S}}(Q).$

It is sufficient to prove this proposition for a packing polyhedron, $P_P$, due to Theorem \[thm:thm3\]. Let $(\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}$ and let ${\beta}^\top x \leq \delta$ be a valid inequality for $(P_P)^{\pi,\pi_0}$. Note that, due to Observation \[obs:bijection\], it is sufficient to show that ${\beta}^\top x \leq 2 \delta$ is valid for $P_P$. Due to Farkas’ Lemma [(e.g., Theorem 3.22 in [@ConCorZam14b])]{}, there exist ${{\color{black}}\lambda^1, \lambda^2} \in {\mathbb{R}}_+^m, \ {{\color{black}}\mu_1, \mu_2 \in {\mathbb{R}}_+}$ and ${{\color{black}}\sigma^1, \sigma^2} \in {\mathbb{R}}_+^n$ such that for any $j \in [n]$, we have $${\beta}_j  = \sum_{i=1}^m \lambda^1_i A_{ij} + \mu_1 \pi_j - \sigma^1_j = \sum_{i=1}^m \lambda^2_i A_{ij} - \mu_2 \pi_j - \sigma^2_j.$$ Let $$Q := \{ x \mid (\lambda^1)^\top Ax \leq (\lambda^1)^\top b, ~ (\lambda^2)^\top Ax \leq (\lambda^2)^\top b,  ~ x \geq 0\}.$$ Now, observe that $Q \supseteq P_P$. Therefore, it is sufficient to show that ${\beta}^\top x \leq 2 \delta$ is valid for $Q$. We will prove that the following holds: $$\label{eq:QclaimPacking}
Q \subseteq 2 Q^{\pi,\pi_0}.$$ Since ${\beta}^\top x \leq \delta$ is valid for $Q^{\pi,\pi_0}$ by the definition of $Q$, this will imply that ${\beta}^\top x \leq 2 \delta$ is valid for $Q$. In order to show that holds, we verify that $$\label{eq:minPacking}
\max \{ c^\top x \mid x \in Q\} \leq 2 \max \{ c^\top x \mid x \in Q^{\pi,\pi_0} \},$$ for any objective vector $c \in {\mathbb{R}}_+^n$. Let $x^*$ be a vertex of $Q$ that maximizes $c^\top x$ over $Q$. As $Q$ is defined by two linear inequalities, together with non-negativities, we know that at least $n-2$ components of $x^*$ are zero, say $x^*_j = 0$ for all $j=3,\hdots,n$. We will focus on the restriction of $Q$ to the first two variables, which we denote by $Q |_{{\mathbb{R}}^2}$.

Observe that $$\label{eq:qc1}
\max \{ c^\top x \mid x \in Q\} = \max \{ c_1 x_1 + c_2 x_2 | (x_1,x_2) \in Q |_{{\mathbb{R}}^2} \}.$$ Moreover, we have $$\label{eq:qc2}
\max \{ c^\top x \mid x \in Q^{\pi,\pi_0} \} \geq \max \{ c_1 x_1 + c_2 x_2 | (x_1,x_2) \in (Q |_{{\mathbb{R}}^2})^{\pi,\pi_0} \}$$ because [$(Q |_{{\mathbb{R}}^2})^{\pi,\pi_0} \subseteq Q^{\pi,\pi_0} |_{{\mathbb{R}}^2}$.]{} Due to and , in order to prove , it is sufficient to only prove in ${\mathbb{R}}^2$. Since $Q |_{{\mathbb{R}}^2}$ is well-behaved, this immediately follows from Lemma \[lem:pack\_2approx\].

\[prop:pack\_TightEx\] For every $\epsilon >0$, there exists a well-behaved packing polyhedron $\tilde{P}_P$ such that $\tilde{P}_P \not\subseteq (2-\epsilon) {\mathcal{S}}(\tilde{P}_P)$.

Let $\epsilon > 0$ and $M = \max\{1,\lceil \frac{2}{\epsilon}-1 \rceil \}$. Consider the instance $\textup{max} \{ x_1 + x_2 \,|\, x \in \tilde{P}_P\}$, where $$\begin{aligned}
\tilde{P}_P = \{x \in {\mathbb{R}}^2_+ \,|\, x_1 + Mx_2 \leq M, \ Mx_1 + x_2 \leq M \}.\end{aligned}$$ Note that $\tilde{P}_P$ is well-behaved. It is sufficient to show that $\frac{z^{LP}}{z^{{\mathcal{S}}}} \ge 2 - \epsilon$ for this instance.

1.  $z^{LP} \ge \frac{2M}{M + 1}$: It can be checked that the point $\bar x_1 = \bar x_2 = \frac{M}{M + 1}$ is in $\tilde{P}_P$. Thus, $z^{LP} \ge \frac{2M}{M + 1}$.

2.  $z^{{\mathcal{S}}} \le1$: Adding the two constraints defining $\tilde{P}_P$ we obtain the valid inequality $$\begin{aligned}
     x_1 + x_2 \le \frac{2M}{M + 1}\end{aligned}$$ The corresponding CG cut is $x_1 + x_2 \leq 1$. Since each CG cut is also a split cut we obtain $z^{{\mathcal{S}}} \le 1$.

Thus, $\frac{z^{LP}}{z^{{\mathcal{S}}}} \ge \frac{2M}{M + 1}$; and our choice of $M$ completes the proof.

We note that the example given in Proposition \[prop:pack\_TightEx\] is the same as the one used in [@bodur2016aggregation] to show that the $2$-approximation bound for the CG closure of a well-behaved packing polyhedron is tight.

### Case of ${\mathcal{S}}^k$ {#subsubsec:4.5.2}

We will show that [we can choose $\alpha_{{\mathcal{S}}^k} = \min \{ 2^k,n \}+1$]{}. It is sufficient to prove this proposition for a packing polyhedron, $P_P$, due to Theorem \[thm:thm3\].

Let $P_P = \{ x \in {\mathbb{R}}^n | Ax \leq b, x \geq 0\}$ and $\pi^i \in {\mathbb{Z}}^n, \pi^i_0 \in {\mathbb{Z}}\textup{ for all } i \in [k]$. It is sufficient to prove that $(\min\{2^k,n\}+1) \, (P_P)^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0} \supseteq  P_P$.

Let ${\beta}^\top x \leq \delta$ be a valid inequality for $(P_P)^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0}$. Since\
${\boldsymbol{0}}\in (P_P)^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0}$, we have $\delta \geq 0$. Therefore, it is sufficient to prove that $$(\min\{2^k,n\}+1) \left(  \{ x | {\beta}^\top x \leq \delta \} \right) \supseteq  P_P.$$ Let $\mathcal{G} = \{ G {\subseteq}{{\color{black}}[k]} : (P_P)_G^{{\pi}^1,\dots, {\pi}^k;\pi^1_0, \dots, \pi^k_0} \neq \emptyset \}$, where $(P_P)_G^{{\pi}^1,\dots, {\pi}^k;\pi^1_0, \dots, \pi^k_0}$ is defined as $$(P_P)_G^{\pi^1,\dots, \pi^k;\pi^1_0, \dots, \pi^k_0} = P_P {\mathbin{\scalebox{1.5}{\ensuremath{\cap}}}}\left(\bigcap_{i \in G} \{ (\pi^i)^\top x \geq \pi^i_0 + 1)\} \right){\mathbin{\scalebox{1.5}{\ensuremath{\cap}}}}\left(\bigcap_{i \in {{\color{black}}[k]} \setminus G} \{ (\pi^i)^\top x \leq \pi^i_0)\}\right).$$

By Farkas’ Lemma, we know that ${\beta}^\top x \leq \delta$ is valid for $$\label{eq:aggPPG}
\{ x \in {\mathbb{R}}_+^n | (\lambda^G)^\top A x \leq (\lambda^G)^\top b, (\pi^i)^\top x \geq \pi^i_0 + 1, \ \forall \ i \in G, \ (\pi^i)^\top x \leq \pi^i_0, \ \forall \ i \in {{\color{black}}[k]} \setminus G \},$$ for some $\lambda^G \in {\mathbb{R}}_+^m$.

Let $$Q = \{ x \in {\mathbb{R}}_+^n | (\lambda^G)^\top A x \leq (\lambda^G)^\top b, \ \forall G \in \mathcal{G} \}$$ which is well-behaved since $P_P$ is assumed to be well-behaved. Now, observe that $$\begin{aligned}
(\min\{2^k,n\}+1) \left(  \{ x | {\beta}^\top x \leq \delta \} \right) & \supseteq (\min\{|\mathcal{G}|,n\}+1) \left(  \{ x | {\beta}^\top x \leq \delta \} \right)  \\
& \supseteq (\min\{|\mathcal{G}|,n\}+1) Q^I \supseteq Q \supseteq P_P,\end{aligned}$$ where the second containment follows from , the third one follows from [Proposition \[prop:intGapPack\]]{} since $Q$ is well-behaved, and the last one is straightforward.

### Case of ${\mathcal{L}}^k$ {#subsubsec:4.5.3}

We show that [we can choose $\alpha_{{\mathcal{L}}^k} = \min \{ k,n \}+1$]{}. It is sufficient to prove this proposition for a packing polyhedron, $P_P$, due to Theorem \[thm:thm3\].

Let $P_P = \{ x \in {\mathbb{R}}^n | Ax \leq b, x \geq 0\}$ and [let]{} $$L = \{ x \in {\mathbb{R}}^n | (\pi^j)^\top x \leq \pi^j_0, \ j = 1,\hdots,k \}$$ [be lattice-free.]{} Then, observe that $$\label{eq:convPPL}
(P_P)^L = \operatorname{conv}(P_P \setminus \int(L)) = \operatorname{conv}\left(\bigcup_{j=1}^k \left\{ x \in P_P ~|~ (\pi^j)^\top x \geq \pi^j_0 \right\}  \right).$$ Without loss of generality, assume that the set $\{ x \in P_P ~|~ (\pi^j)^\top x \geq \pi^j_0 \}$ is non-empty if $j \leq r$, and empty otherwise, for some $r$ with $1 \leq r \leq k$.

Let ${\beta}^\top x \leq \delta$ be a valid inequality for $(P_P)^L$. Since the origin is contained in $(P_P)^L$, we have $\delta \geq 0$. Therefore, it is sufficient to prove that $$(\min\{k,n\}+1) \left(  \{ x | {\beta}^\top x \leq \delta \} \right) \supseteq  P_P.$$ By equation and Farkas’ Lemma, we know that ${\beta}^\top x \leq \delta$ is valid for $$\label{eq:aggPP}
\{ x \in {\mathbb{R}}_+^n | (\lambda^j)^\top A x \leq (\lambda^j)^\top b, (\pi^j)^\top x \geq \pi^j_0 \},$$ for $j = 1,\hdots,r$ where $\lambda^j \in {\mathbb{R}}_+^m$.

Let $$Q = \{ x \in {\mathbb{R}}_+^n | (\lambda^j)^\top A x \leq (\lambda^j)^\top b, \ j = 1,\hdots,r \}$$ which is well-behaved since $P_P$ is assumed to be well-behaved. Now, observe that $$(\min\{k,n\}+1) \left(  \{ x | {\beta}^\top x \leq \delta \} \right) \supseteq (\min\{k,n\}+1) Q^I \supseteq Q \supseteq P_P,$$ where the first containment follows from and $L$ being a lattice-free set, the second one follows from [Proposition \[prop:intGapPack\]]{} since $Q$ is well-behaved, and the last one is straightforward.

### Proof of Proposition \[prop:prop1\] {#subsubsec:4.5.4}

Let $P_P$ be the standard relaxation of the stable set polytope: $$\begin{aligned}
P_P = \{ x \in {\mathbb{R}}_+^{n} \,|\, x_i + x_j \le 1 \ \forall i,j \in [n], \ i < j\}.\end{aligned}$$ Corresponding to the clique inequality ${\boldsymbol{1}}^\top x \le 1$, we optimize the all ones vector over $P_P$ and $(P_P)^I$, and obtain $z^{LP}=n/2$ and $z^{I}=1$, respectively. The CG rank of the clique inequality is known to be $\lceil \log_2 (n-1) \rceil$ [@hartmann], therefore it also constitutes an upper bound on the split rank.

Proofs for covering problems {#sec:Covering}
============================

\[prop:CoveringPoly\] ${\mathcal{S}}(P_C)$ is a covering polyhedron.

If $P_C$ is empty, then there is nothing to prove. So, assume that $P_C$ is not empty. It is known that the split closure of a polyhedron is also a polyhedron [@cook:ka:sc:1990]. Let ${\beta}^\top x \geq \delta$ be a valid inequality for ${\mathcal{S}}(P_C)$. Then, there exists $(\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}$ such that ${\beta}^\top x \geq \delta$ is valid for $P_C^{\pi,\pi_0}$. If one side of the disjunction is empty, then we already know that ${\beta}^\top x \geq \delta$ is of covering type as it is a CG cut. Now, assume that both sides are nonempty. Then, due to Farkas’ Lemma, there exist multipliers $\lambda^1, \lambda^2 \in {\mathbb{R}}_+^m, \ \mu_1, \mu_2 \in {\mathbb{R}}_+$ and $\sigma^1, \sigma^2 \in {\mathbb{R}}_+^n$ for the aggregation $$\begin{aligned}
{4}
& (\lambda^1) \quad  && Ax \geq b \qquad \qquad \qquad && (\lambda^2) \quad && Ax \geq b \\
& (\mu_1) && - \pi^\top x \geq -\pi_0 && (\mu_2) && \pi^\top x \geq \pi_0 +1 \\
& (\sigma^1_j) && x_j \geq 0 && (\sigma^2_j) && x_j \geq 0 \qquad \qquad j=1,\hdots,n\end{aligned}$$ such that, for any $j=1,\hdots,n$, $$\label{eq:cSplit}
{\beta}_j  = \sum_{i=1}^m \lambda^1_i A_{ij} - \mu_1 \pi_j + \sigma^1_j = \sum_{i=1}^m \lambda^2_i A_{ij} + \mu_2 \pi_j + \sigma^2_j.$$ This implies that, for any $j=1,\hdots,n$, we have ${\beta}_j \geq 0$ (based on the sign of $\pi_j$, either the middle or the last expression [witnesses non-negativity]{}). Lastly, note that if $\delta < 0$, then ${\beta}^\top x \geq \delta$ is dominated by ${\beta}^\top x \geq 0$, which concludes the proof.

\[prop:covering2approx\] Let $P_C$ be well-behaved, i.e., $A_{ij} \leq b_i$ for all $i \in [m], j \in [n]$. Then, $$z^{LP} \geq \frac{1}{2} z^{{\mathcal{S}}}.$$

Let ${\beta}^\top x \geq \delta$ be a facet-defining inequality for ${\mathcal{S}}(P_C)$. Note that, due to Observation \[obs:bijection\], it is sufficient to show that ${\beta}^\top x \geq \frac{\delta}{2}$ is valid for $P_C$. [If ${\beta}^\top x \geq \delta$ is valid for $P_C$, then there is nothing to show. So, assume that it is a non-trivial inequality.]{}

If ${\beta}^\top x \geq \delta$ is a [non-trivial]{} CG cut, then [$\delta \geq 1$. We know that the strict inequality ${\beta}^\top x > \delta - 1$ is valid for $P_C$. If $\delta \geq 2$, then $\delta - 1 \geq \frac{\delta}{2}$, which implies that ${\beta}^\top x \geq \frac{\delta}{2}$ is valid for $P_C$. So, now assume that $\delta = 1$. Let $\lambda \in {\mathbb{R}}_+^m$ such that the CG cut is obtained by rounding up the coefficients and the right-hand-side of the base inequality $\lambda^\top A x \geq \lambda^\top b$, i.e., $\beta = {\lceil\lambda^\top A\rceil}$ and $\delta = {\lceil\lambda^\top b\rceil}$. As $\delta = 1$, we have $0 < \lambda^\top b \leq 1$. Thus, the scaled base inequality $(\lambda^\top A / \lambda^\top b) x \geq 1$ is valid for $P_C$. In addition, since $P_C$ is well-behaved, $\lambda^\top A_{\cdot j} \leq \lambda^\top b \ (\leq 1)$ for all $j \in [n]$ (where $A_{\cdot j}$ denotes the $j^\text{th}$ column of $A$. Then, for any $x \in P_C$, we have $$\beta^\top x = \sum_{j \in [n]} {\lceil\lambda^\top A_{\cdot j}\rceil} x_j \geq \sum_{j \in [n]} \frac{\lambda^\top A_{\cdot j}}{\lambda^\top b} x_j \geq 1 \geq \frac{{\lceil\lambda^\top b\rceil}}{2} = \frac{\delta}{2},$$ which implies that is $\beta^\top x \geq \frac{\delta}{2}$ valid for $P_C$. ]{}

Otherwise, let $(\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}$ be a corresponding vector such that ${\beta}^\top x \geq \delta$ is valid for $P_C^{\pi,\pi_0}$. Let $$Q := \{ x \mid (\lambda^1)^\top Ax \geq (\lambda^1)^\top b, ~ (\lambda^2)^\top Ax \geq (\lambda^2)^\top b,  ~ x \geq 0\},$$ where $\lambda^1$ and $\lambda^2$ are the multipliers that satisfy . Now, observe that $Q \supseteq P_C$. Therefore, it is sufficient to show that ${\beta}^\top x \geq \frac{\delta}{2}$ is valid for $Q$. We will prove that the following holds: $$\label{eq:Qclaim}
Q \subseteq \frac{1}{2} Q^{\pi,\pi_0}.$$ Since ${\beta}^\top x \geq \delta$ is valid for $Q^{\pi,\pi_0}$ by the definition of $Q$, this will imply that ${\beta}^\top x \geq \frac{\delta}{2}$ is valid for $Q$. In order to show that holds, we verify that $$\label{eq:min}
\min \{ c^\top x \mid x \in Q\} \geq \frac{1}{2} \min \{ c^\top x \mid x \in Q^{\pi,\pi_0} \},$$ for any objective vector $c \in {\mathbb{R}}_+^n$. Let $x^*$ be a vertex of $Q$ that minimizes $c^\top x$ over $Q$. If $x^*$ belongs to $Q^{\pi,\pi_0}$, we are done. Thus, assume that $x^* \notin Q^{\pi,\pi_0}$. We will prove by showing that there exists a point $\hat{x} \in Q^{\pi,\pi_0}$ such that $c^\top \hat{x} \leq 2 c^\top x^*$. As $Q$ is defined by two linear inequalities, together with non-negativities, we know that at least $n-2$ components of $x^*$ are zero, say $x^*_j = 0$ for all $j=3,\hdots,n$. We will focus on this restriction of $Q$ in ${\mathbb{R}}_+^2$ in order to identify $\hat{x}$. Without loss of generality, assume that $c_1 \geq c_2$. A key observation that follows from the definition of split cuts is $$\label{eq:vee}
(x^*_1+1,x^*_2,{\boldsymbol{0}}) \in Q^{\pi,\pi_0} \vee (x^*_1,x^*_2+1,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}.$$ [Moreover, if $\pi \neq e_1$, then $(x^*_1,x^*_2+1,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}.$\
]{} Now, we will consider two cases to prove .\
\
*Case 1*. $x^*_1 \geq 1$: [Using (\[eq:vee\]), there are two subcases based on whether $(x^*_1+1,x^*_2,{\boldsymbol{0}}) \in Q^{\pi,\pi_0} $ or $ (x^*_1,x^*_2+1,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}$. If $\hat{x} = (x^*_1+1,x^*_2,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}$, then it is sufficient to show that $$c^\top x^* \geq \frac{1}{2} (c^\top x^* + c_1),$$ which is equivalent to $c^\top x^* \geq  c_1$, which holds because $x^*_1 \geq 1$ and $c_1, c_2, x^*_2 \geq 0$. If $\hat{x} = (x^*_1,x^*_2 + 1,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}$, then it is sufficient to show that $$c^\top x^* \geq \frac{1}{2} (c^\top x^* + c_2),$$ which is equivalent to $c^\top x^* \geq  c_2$, which holds because $x^*_1 \geq 1$, $c_1 \geq c_2$ and $c_2, x^*_2 \geq 0$. ]{}\
\
*Case 2*. $0 \leq x^*_1 < 1$: Note that by construction, $Q$ is a well-behaved covering polyhedron. Now, consider the following two subcases:\
\
*Case 2a*. $(\pi,\pi_0) \neq (e_1,0)$: [In this case as discussed above]{}, [$\hat{x} = (x^*_1,x^*_2 + 1,{\boldsymbol{0}}) \in Q^{\pi,\pi_0}$]{}. It is sufficient to show that $$c^\top x^* \geq \frac{1}{2} (c^\top x^* + c_2),$$ which is equivalent to $c^\top x^* \geq c_2$. This holds as we have $x^*_1+x^*_2 \geq 1$ since $Q$ is well-behaved [and because $c_1 \geq c_2$]{}.\
\
*Case 2b*. $(\pi,\pi_0) = (e_1,0)$: Let $\hat{x} = (x^*_1,x^*_2 + x^*_1 x^*_2,{\boldsymbol{0}})$. We will first show that $\hat{x} \in Q^{\pi,\pi_0}$.

Figure \[fig:1pic\] illustrates the restriction of $Q$ to the first two variables, which we denote by $Q |_{{\mathbb{R}}^2}$. Observe that $Q |_{{\mathbb{R}}^2}$ is a well-behaved covering polyhedron because $Q$ is a well-behaved covering polyhedron. Note that $x_1^* > 0$ due to the assumption $x^* \notin Q^{e_1,0}$. [Since $0 < x^*_1 < 1$, and $Q |_{{\mathbb{R}}^2}$ is a well-behaved covering polyhedron, we have that $x_1 \geq  \gamma$ cannot be a valid inequality for $Q |_{{\mathbb{R}}^2}$ where $0< \gamma \leq x^*_1$. In other words, all non-trivial inequalities $\alpha_1 x_1 + \alpha_2 x_2 \geq \theta$ defining $Q |_{{\mathbb{R}}^2}$ must have $\alpha_2 > 0$. Therefore, there must exist a vertex of the form $(0,y)$ of $Q |_{{\mathbb{R}}^2}$.]{} Since $(x^*_1,x^*_2)$ is a vertex of $Q |_{{\mathbb{R}}^2}$ [with $x_1^* > 0$]{}, we know that $(0,y) \neq (x^*_1,x^*_2)$.

Let $(h,0)$ be the intercept of the line passing through the vertices $(0,y) $ and $(x^*_1,x^*_2)$. [We first claim that $h \geq 1$. Note that the supporting hyperplane corresponding to non-trivial facet-defining inequality at $(0, y)$ (i.e., different from $x_1 \geq 0$) intersects the $x_1$-axis at a point $(\tilde{h}, 0)$ with $\tilde{h} \geq 1$ due to well-behavedness of $Q |_{{\mathbb{R}}^2}$. Since the line passing through the vertices $(0,y) $ and $(x^*_1,x^*_2)$ has an intercept at least as large as $\tilde{h}$, we obtain that $h \geq 1$.]{}

Then, we have

(0,0) – (0,4.5); (0,0) – (4.5,0); (0,3.5) – (1.5,1.5); (1.5,1.5) – (4,0); (0,4.5) – (0,3.5) – (1.5,1.5) – (4,0) – (4.5,0) – (4.5,4.5) – cycle; (1.5,1.5) – (2.635,0); at (4,0) ; at (1.5,1.5) ; (xstar) at (2.1,1.7) [$(x^*_1,x^*_2)$]{}; at (0,3.5) ; (xstar) at (0.58,3.65) [$(0,y)$]{}; (h) at (2.635,-0.3) [$(h,0)$]{}; at (2.635,0) [x]{};

$$\label{eq:heq}
\frac{y}{h} = \frac{y - x^*_2}{x^*_1} \Rightarrow h = \frac{y x^*_1}{y-x^*_2} \ .$$

[Since $h \geq 1$, we have:]{} $$y x^*_1 \geq y - x^*_2 \iff \displaystyle y \leq \frac{x^*_2}{1-x^*_1} 
\Rightarrow \displaystyle (0, \frac{x^*_2}{1-x^*_1},{\boldsymbol{0}}) \in Q^{e_1,0}.$$ The last implication follows from the fact that $Q$ is a covering polyhedron, $(0,y,{\boldsymbol{0}}) \in Q$ and $(\pi,\pi_0) = (e_1,0)$. Similarly, we have $(1,x^*_2,{\boldsymbol{0}}) \in Q^{e_1,0}$. The following convex combination of these two points yields $\hat{x}$ as $$(1-x^*_1) (0, \frac{x^*_2}{1-x^*_1},{\boldsymbol{0}}) + x^*_1 (1,x^*_2,{\boldsymbol{0}}) = (x^*_1,x^*_2 + x^*_1 x^*_2,{\boldsymbol{0}}) = \hat{x}.$$ Finally, observe that [since $c_1 \geq 0$ and $0 \leq x^*_1 \leq 1$]{} $${{\color{black}}c^\top x^* \geq c_2 x^*_2 \geq  c_2 x^*_1 x^*_2 \Rightarrow c^\top x^* \geq \frac{1}{2} (c^\top x^* + c_2 x^*_1 x^*_2) = \frac{1}{2}c^\top\hat{x}},$$ which completes the proof.

We now show that Proposition \[prop:covering2approx\] is tight. In order to do so, we exhibit an instance of a well-behaved covering polyhedron and a nonnegative objective function such that LP is not better than a 2-approximation of ${\mathcal{S}}$. The construction given in the following example is the same that we used in [@bodur2016aggregation] to show that our $2$-approximation bounds for *1-row closure* and *1-row CG closure* are tight.

\[prop:LBAC\] For every $\epsilon >0$, there exists a well-behaved covering polyhedron $\tilde{P}_C$ such that $\frac{1}{2-\epsilon} \tilde{P}_C  \not {\subseteq}{\mathcal{S}}(\tilde{P}_C)$.

Let $\epsilon >0$ and $n = \textup{max}\{2,\lceil \frac{1}{\epsilon}\rceil\}$. Consider the instance $\textup{min} \{ \sum_{j = 1}^n x_j \,|\, x \in \tilde{P}_C\}$, where $$\begin{aligned}
\tilde{P}_C = \{x \in {\mathbb{R}}^n_+ \,|\, x_i + \displaystyle \sum_{j \in [n]\setminus \{i\}} 2x_j \geq 2, \ \forall i \in [n]\}.\end{aligned}$$ Note that $\tilde{P}_C$ is well-behaved. It is sufficient to show that $\frac{z^{{\mathcal{S}}}}{z^{LP}} \geq 2 - \epsilon$ for this instance.

1.  $z^{LP} \le \frac{2n}{2n - 1}$: It can be checked that the point $\bar x_j = \frac{2}{2n - 1}$ for each $j \in [n]$ is in $\tilde{P}_C$. Thus, $z^{LP} \le \frac{2n}{2n - 1}$.

2.  $z^{{\mathcal{S}}} \geq 2$: Adding all the constraints defining $\tilde{P}_C$ we obtain the valid inequality $$\begin{aligned}
     \sum_{j \in [n]} x_j \geq \frac{2n}{2n - 1}.\end{aligned}$$ The corresponding CG cut is $\sum_{j \in [n]} x_j \geq 2$. Since each CG cut is also a split cut we obtain $z^{{\mathcal{S}}} \geq 2$.

Thus, $\frac{z^{{\mathcal{S}}}}{z^{LP}} \geq 2 - \frac{1}{n}$; and our choice of $n$ completes the proof.

\[prop:CoveringSplitWell\] Let $P_C$ be well-behaved, i.e., $A_{ij} \leq b_i$ for all $i \in [m], j \in [n]$. Then, ${\mathcal{S}}(P_C)$ is well-behaved.

Let ${\beta}^\top x \geq \delta$ be a facet-defining (i.e., nondominated) inequality for ${\mathcal{S}}(P_C)$. If it is a CG cut, then we are done. Thus, we assume that it is a non-CG cut. For a contradiction, suppose that ${\beta}_1 > \delta$. [This is because any CG cut can be written as $\sum_j \lceil \sum_{i = 1}^m \lambda_i A_{ij} \rceil x_j \geq \lceil \sum_{i = 1}^m \lambda_i b_i \rceil$, where $\lambda_i \geq 0 $ for $i \in [m]$. Therefore $\sum_{i = 1}^m \lambda_i A_{ij} \leq \sum_{i = 1}^m \lambda_i $ for all $j \in [n]$, which implies that $\lceil \sum_{i = 1}^m \lambda_i A_{ij} \rceil \leq \lceil \sum_{i = 1}^m \lambda_i b_i \rceil$ for all $j \in [n]$.]{}

We know that ${\beta}^\top x \geq \delta$ is valid for $P_C^{\pi,\pi_0}$ for some $(\pi,\pi_0) \in {\mathbb{Z}}^n \times {\mathbb{Z}}$. Then, there exist multipliers $\lambda^1, \lambda^2 \in {\mathbb{R}}_+^m, \ \mu_1, \mu_2 \in {\mathbb{R}}_+$ and $\sigma^1, \sigma^2 \in {\mathbb{R}}_+^n$ such that $$\begin{aligned}
\label{eqn:CovWell_SideOne}
& ({\beta},\delta) = \lambda^1 (A,b) + \mu_1 (-\pi,-\pi_0) + \sigma^1 ({\boldsymbol{1}},0) \\
\label{eqn:CovWell_SideTwo}
& ({\beta},\delta) = \lambda^2 (A,b) + \mu_2 (-\bar{\pi},-\bar{\pi}_0) + \sigma^2 ({\boldsymbol{1}},0)\end{aligned}$$ where $(\bar{\pi},\bar{\pi}_0) = (-\pi,-\pi_0-1)$. Note that if $\sigma^1_1 > 0$ and $\sigma^2_1 > 0$, then we can obtain another split cut by decreasing both $\sigma^1_1$ and $\sigma^2_1$ by $\min \{ \sigma^1_1,\sigma^2_1\}$, which dominates the given split cut ${\beta}^\top x \geq \delta$. Therefore, we assume, WLOG, that $\sigma^2_1 = 0$. Then, we make the following two cases:\
*Case 1*. $- \bar{\pi}_0 \geq - \bar{\pi}_1$: This implies that $\lambda^2 A_{\cdot 1} + \mu_2 (-\bar{\pi}_1) \leq \lambda^2 b + \mu_2 (-\bar{\pi}_0)$ (where $A_{\cdot 1}$ denotes the first column of $A$), equivalently ${\beta}_1 \leq \delta$, which is a contradiction.\
*Case 2*. $- \bar{\pi}_0 \ {{\color{black}}<} - \bar{\pi}_1$: This condition is equivalent to $1-\pi_1 < -\pi_0$. We first claim that $\sigma^1_1 > \mu_1$. From and ${\beta}_1 > \delta$, we have $$\lambda^1 A_{\cdot 1} - \mu_1 \pi_1 + \sigma^1_1 > \lambda^1 b + \mu_1 (-\pi_0) >  \lambda^1 b + \mu_1 (1-\pi_1),$$ which implies that $$(\lambda^1 A_{\cdot 1}-\lambda^1 b) + \sigma^1_1 - \mu_1 > 0.$$ As $P_C$ is well-behaved, we have $\lambda^1 A_{\cdot 1}-\lambda^1 b \leq 0$, thus we get $\sigma^1_1 > \mu_1$. Next, we let $$\tilde{\pi} := \pi - e_1, \ \tilde{\sigma}^1 := \sigma^1 - \mu_1 e_1, \ \tilde{\sigma}^2 := \sigma^2 + \mu_2 e_1.$$ Note that $\tilde{\sigma}^1_1 > 0$. Also, due to and , we have $$\label{eq:CovWellBothSides}
({\beta},\delta) = \lambda^1 (A,b) + \mu_1 (-\tilde{\pi},-\pi_0) + \tilde{\sigma}^1 ({\boldsymbol{1}},0) = \lambda^2 (A,b) + \mu_2 (\tilde{\pi},-\bar{\pi}_0) + \tilde{\sigma}^2 ({\boldsymbol{1}},0).$$ Note that $\mu_2 > 0$ since otherwise, i.e., when $\mu_2 = 0$, the equation and $\sigma^2_1 = 0$ give the contradiction ${\beta}_1 = \lambda^2 A_{\cdot 1} \leq \lambda^2 b = \delta$. Therefore, we have $\tilde{\sigma}^2_1 > 0$ as well. If we reduce both $\tilde{\sigma}^1_1$ and $\tilde{\sigma}^2_1$ by a sufficiently small $\epsilon > 0$, so that they are still nonnegative, from we obtain another valid split cut $({\beta}- 2 \epsilon e_1)^\top x \geq \delta$ which dominates ${\beta}^\top x \geq \delta$, hence a contradiction.

**Acknowledgements.** Santanu S. Dey would like to acknowledge the support of the NSF grant CMMI\#1149400. Marco Molinaro would like to acknowledge the support of CNPq grants Universal \#431480/2016-8 and Bolsa de Produtividade em Pesquisa \#310516/2017-0; this work was partially while the author was a Microsoft Research Fellow at the Simons Institute for the Theory of Computing. [We would like to thank the reviewers for their careful and constructive comments that have significantly improved the paper.]{}

Additional proofs {#sec:appendix}
=================

\[obs:PackingSplitAgg\] For packing polyhedra, split cuts are not necessarily aggregation cuts.

An example, where there exists a split cut that cannot be obtained as an aggregation cut, is provided in Figure \[fig:PackingSplitAgg\].

(0,0) – (1.8,0) – (0.9,1.9) – (0,1.9) – cycle; (0,0) – (0,4.2); (0,0) – (4.2,0); (0,3.8) – (1.8,0); (0,1.9) – (4,1.9); at (0,2.7) ; at (1.8,1.4) ; (A) at (-0.2,3.8) [7]{}; (A) at (-0.2,2.7) [2]{}; (A) at (-0.35,1.9) [7/4]{}; (A) at (1.8,-0.2) [1]{}; (0,1.4) – (1.8,1.4); (A) at (-0.152,1.4) [1]{}; (1.8,3.8) – (1.8,0); (0,1.9) – (1.8,0);

In the figure, the shaded region represents the packing polyhedron $P = \{ x \in {\mathbb{R}}_+^2   \mid 7 x_1 + x_2 \leq 7, 4 x_2 \leq 7\}$. It is easy to see that $7 x_1+4 x_2 \leq 7$ (the dashed line in the figure) is a split cut obtained by using the split set $S(e_1,0)$. Note that this cut separates both of the points $(0,2)$ and $(1,1)$. We next show that this cut is not an aggregation cut by proving that $(0,2)$ and $(1,1)$ are not separated at the same time by any aggregation cut. An inequality is an aggregation cut for $P$ if it is valid for the set $P(\alpha) := \operatorname{conv}( \{ x\in {\mathbb{R}}_+^2 \mid (7-7\alpha) x_1 + (3 \alpha +1) x_2 \leq 7 \})$ for some $\alpha \in [0,1]$. It can be easily verified that if $\alpha \leq 5/6$, then $(0,2) \in P(\alpha)$, and if $\alpha \geq 1/4$, then $(1,1) \in P(\alpha)$.

\[obs:CoveringSplitAgg\] For covering polyhedra, split cuts are not necessarily aggregation cuts.

An example, where there exists a split cut that cannot be obtained as an aggregation cut, is provided in Figure \[fig:CoveringSplitAgg\].

(0,3.8) – (0.7108,1.1) – (4,1.1) – (4,3.8) – cycle; (0,0) – (0,4.2); (0,0) – (4.2,0); (0,3.8) – (1,0); (0,1.1) – (4,1.1); at (0,2.7) ; at (1,0.7) ; (A) at (-0.2,3.8) [7]{}; (A) at (-0.2,2.7) [6]{}; (A) at (-0.35,1.1) [7/4]{}; (A) at (1,-0.2) [1]{}; (0,0.7) – (1,0.7); (A) at (-0.152,0.7) [1]{}; (1,3.8) – (1,0); (0,3.8) – (1.222,0.5);

In the figure, the shaded region represents the covering polyhedron $P = \{ x \in {\mathbb{R}}_+^2   \mid 7 x_1 + x_2 \geq 7, 4 x_2 \geq 7\}$. It is easy to see that $21 x_1+4 x_2 \geq 28$ (the dashed line in the figure) is a split cut obtained by using the split set $S(e_1,0)$. Note that this cut separates both of the points $(0,6)$ and $(1,1)$. We next show that this cut is not an aggregation cut by proving that $(0,6)$ and $(1,1)$ are not separated at the same time by any aggregation cut. An inequality is an aggregation cut for $P$ if it is valid for the set $P(\alpha) := \operatorname{conv}( \{ x\in {\mathbb{R}}_+^2 \mid (7-7\alpha) x_1 + (3 \alpha +1) x_2 \geq 7 \})$ for some $\alpha \in [0,1]$. It can be easily verified that if $\alpha \geq 1/18$, then $(0,6) \in P(\alpha)$, and if $\alpha \leq 1/4$, then $(1,1) \in P(\alpha)$.

[^1]: bodur@mie.utoronto.ca

[^2]: delpia@wisc.edu

[^3]: santanu.dey@isye.gatech.edu

[^4]: mmolinaro@inf.puc-rio.br
