space in a linear form, and in $\text{rank}_{1,w}$ it is essentially done in
the original space of the variables through nonlinear inequalities.

In the first experiment we set
$\lambda=10^{-2},\mu=10^{-4},p=50,d=1325,\pi=0.1$ and
$N\in\\{10,50,100,200\\}$. In Figure 1 we report the optimality gap and
solution time for different convex relaxations. In determining the optimality
gap, we compare the objective value of the given relaxation against the best
known feasible solution for the instance (among the ones found by the B&B
method applied to any of the formulations of (35) presented in (41), (47) and
(56). This solution corresponds to the optimal solution if the time limit has
not been reached in the B&B algorithm, or the best feasible solution reported
by MOSEK if the time limit has been reached.

The results in Figure 1 suggest that the qualities of the convex relaxations
based on the (56) formulation are the best. In particular,
$\text{rank}_{1}^{+}\\!$ relaxation attains an average gap smaller than $5\%$.
Moreover, adding valid inequalities to the sets $\Delta_{b}$ and $\Omega_{b}$
significantly improve the quality of the $\text{rank}_{1}\\!$ and
$\text{rank}_{1}^{+}\\!$ relaxations. For example, the
$\text{rank}_{1,v}^{+}\\!$ relaxation attains the average gap smaller than
$1\%$, which is $5$ times smaller than the gap attained by
$\text{rank}_{1}^{+}\\!$. However, adding these valid inequalities comes with
a computational downside. Specifically, the optimization problems now involve
more constraints, which result in longer solution times. It is also worth to
note that the optimality gap of the $\text{rank}_{1}\\!$ relaxations is
significantly superior to that of the separable and natural relaxations,
albeit at the expense of relatively longer solution times.

Finally, we highlight that the optimality gap of the continuous relaxations
from $\text{rank}_{1,v}\\!$ and $\text{rank}_{1,w}\\!$, with the latter being
inspired by (Wei et al., 2022b, Theorem 1), are identical. This is due to the
fact that when the variables ${\bm{w}}$ are relaxed to be continuous the
projection of $\text{rank}_{1,v}\\!$ in the original space leads to precisely
the same inequalities as in $\text{rank}_{1,w}\\!$. Nonetheless, it takes
roughly twice as long to solve the $\text{rank}_{1,w}\\!$ relaxation than the
$\text{rank}_{1,v}\\!$ relaxation. This is expected as the
$\text{rank}_{1,w}\\!$ relaxation introduces a considerably larger number of
constraints and variables compared to the $\text{rank}_{1,v}\\!$ relaxation.
It is also important to note that a complete implementation of (Wei et al.,
2022b, Theorem 1) requires using a characterization of
$\operatorname{conv}({\cal Z}\backslash\\{\bm{0}\\})$ which may possibly
involve an exponential number of constraints. In contrast,
$\text{rank}_{1,v}\\!$ relaxation handles this complexity through the use of
binary variables ${\bm{w}}$, making the $\text{rank}_{1,v}\\!$ relaxation much
more applicable in practice.

Figure 1: Comparison of different continuous relaxations for $p=50$ and
$\pi=0.1$ as $N$ varies.

We next examine the B&B performance of these alternative formulations of (35)
in which we always keep the variables ${\bm{z}}$ as binary but we create two
variants for each of the $\text{rank}_{1}\\!$ and $\text{rank}_{1}^{+}\\!$
formulations based on whether the variables ${\bm{w}}$ are kept as binary or
${\bm{w}}$ are relaxed to be continuous:

  * •

In _separable reformulation_ , we consider (41).

  * •

In _$\text{rank}_{1}\\!$ reformulation_, we consider (47).

  * •

In _$\text{rank}_{1,r}\\!$ reformulation_, we replace $\Delta_{b}$ in (47)
with $\operatorname{relax}_{{\bm{w}}}(\Delta_{b})$.

  * •

In _$\text{rank}_{1,v}\\!$ reformulation_, we replace $\Delta_{b}$ in (47)
with $\Delta_{b}\cap\Delta_{v}$.

  * •

In _$\text{rank}_{1,r,v}\\!$ reformulation_, we replace $\Delta_{b}$ in (47)
with $\operatorname{relax}_{{\bm{w}}}(\Delta_{b}\cap\Delta_{v})$.

  * •

In _$\text{rank}_{1,w}\\!$ reformulation_, we consider (4).

  * •

In _$\text{rank}_{1}^{+}\\!$ reformulation_, we consider (56).

  * •

In _$\text{rank}_{1,r}^{+}\\!$ reformulation_, we replace $\Omega_{b}$ in (56)
with $\operatorname{relax}_{{\bm{w}}}(\Omega_{b})$.

  * •

In _$\text{rank}_{1,v}^{+}\\!$ reformulation_, we replace $\Omega_{b}$ in (56)
with $\Omega_{b}\cap\Omega_{v}$.

  * •

In _$\text{rank}_{1,r,v}^{+}\\!$ reformulation_, we replace $\Omega_{b}$ in
(56) with $\operatorname{relax}_{{\bm{w}}}(\Omega_{b}\cap\Omega_{c})$.

Figure 2 reports the true optimality gap computed using the best known
heuristic solution (in our experiments this was usually obtained by a variant
of (47) formulation) as discussed earlier, the optimality gap reported by the
solver, the number of B&B nodes, and the solution time.

Figure 2: The B&B performance for $p=50$ and $\pi=0.1$ as $N$ varies.

We start by analyzing the true optimality gap and solver gap in Figure 2. As
also seen in Figure 1, in terms of true optimality gap, the formulations based
on (56) consistently outperform those based on (47) in terms of the true
optimality gap. This is primarily because the relaxations based on (56) can
produce high-quality lower bounds, even though these formulations take longer
to solve and thus result in significantly fewer number of nodes explored in
B&B. Among $\text{rank}_{1}\\!$ and $\text{rank}^{+}_{1}\\!$ variants, the
ones where the variables ${\bm{w}}$ are kept as binary perform better in terms
of the optimality gaps than the ones where ${\bm{w}}$ are relaxed to be
continuous even though having ${\bm{w}}$ binary results in fewer B&B nodes.
This is because when ${\bm{w}}$ are binary, the solver is able to leverage the
structure of the sets $\Delta_{b}$ and $\Omega_{b}$ to generate further cuts
and results in higher quality relaxations. Among $\text{rank}_{1}\\!$
variants, the performance of $\text{rank}_{1,v}\\!$ seems to be best and
$\text{rank}_{1,w}\\!$ seems to be the worst. As the continuous relaxation of
$\text{rank}_{1,w}$ takes longer to solve compared to those based on (47), its
B&B can explore only a smaller number of nodes, and therefore, results in a
worse optimality gap.

When we examine the gaps reported by the solver, we still observe that the
same phenomena, but this time the associated gaps reported by the solver are
considerably larger than the true optimality gaps. This is because for this
class of problems, the heuristic methods utilized by the solver are not very
advanced, and the good quality feasible solutions of a formulation are often
found at integral nodes in the B&B tree, so essentially by chance. Therefore,
the B&B procedure for the formulations that admit quick to solve node
relaxations often results in high quality feasible solutions. Consequently, in
the case of expensive lifted formulations such as (56) while the actual
optimality gaps are very close to zero, the solver is unable to report this
gap due to the inferior quality of the feasible solution found in the
associated B&B tree. To address this issue, BARON introduces the concept of
“relaxation-only constraints” (Sahinidis, 1996, accessed November 13, 2023).
These constraints are active during the relaxation step, but are disregarded
during the local search step. To the best of our knowledge, MOSEK 10 does not
support this feature, and thus in our figures we report both the true
optimality gap and the solver reported gap for the formulations tested.

In the second experiment we set $\lambda=10^{-2},\mu=10^{-4},N=100,\pi=0.1$
and $p\in\\{10,20,30,40,50\\}$, which translates to
$d\in\\{65,230,495,860,1325\\}$. Figure B.1 and Figure B.2 in Appendix B
compare the quality of different continuous relaxations and also report the
performance of the B&B algorithm, respectively. The observations from Figure
B.1 are very similar to the ones in Figure 1; thus we omit this discussion for
brevity. Despite the similarity between the observations in Figure B.2 and
Figure 2, it is worth noting that when $p=10$, the B&B performance is slightly
different. In particular, when $p=10$, all methods except
$\text{rank}_{1,r}^{+}\\!$ and $\text{rank}_{1,r,v}^{+}\\!$ can solve the
optimization problem in less than $20$ seconds. This implies that the integer
programs may be relatively simple to solve when the dimension is small. As a
result, stronger relaxations may not be needed when dealing with small scale
instances.

In the last experiment we set $\lambda=10^{-2},\mu=10^{-4},p=50,d=1325,N=100$
and $\pi\in\\{0.1,0.3,0.5,0.7,0.9\\}$; see Figure B.3 and Figure B.4 in
Appendix B for the quality of different continuous relaxations and the B&B
performance. In all of these instances time limit was reached in B&B, so the
solution time is not reported in Figure B.4. As the value of $\pi$ increases,
we notice that the optimality gap of the $\text{rank}_{1}\\!$ relaxation gets
closer to that of separable relaxation. This is expected as the binary
variable $w_{j}$ models whether ${\bm{a}}_{j}^{\top}{\bm{x}}=0$ or not. When
$\pi$ is large, the probability of such event is low. As a result, $w_{j}$ is
assigned a value of $1$ with high probability, which make the
$\text{rank}_{1}\\!$ relaxations much less effective. As a final observation,
we note that the value of $\pi$ seems to not affect the quality of the
$\text{rank}_{1}^{+}\\!$ relaxations; in particular these relaxations continue
to be of high quality even for high values of $\pi$.

##### Acknowledgements

This research is supported by Early Postdoc Mobility Fellowship SNSF grant
P2ELP2_195149 and AFOSR grant FA9550-22-1-0365.

## References

  * Aktürk et al. (2009) M. S. Aktürk, A. Atamtürk, and S. Gürel.  A strong conic quadratic reformulation for machine-job assignment with controllable processing times.  _Operations Research Letters_ , 37(3):187–191, 2009.
  * Atamtürk and Gómez (2018) A. Atamtürk and A. Gómez.  Strong formulations for quadratic optimization with M-matrices and indicator variables.  _Mathematical Programming_ , 170(1):141–176, 2018\.
  * Atamtürk and Gómez (2019) A. Atamtürk and A. Gómez.  Rank-one convexification for sparse regression.  _arXiv:1901.10334_ , 2019.
  * Atamtürk and Gómez (2020) A. Atamtürk and A. Gómez.  Safe screening rules for $\ell_{0}$-regression from perspective relaxations.  In _International Conference on Machine Learning_ , pages 421–430, 2020.
  * Atamtürk and Gómez (2022) A. Atamtürk and A. Gómez.  Supermodularity and valid inequalities for quadratic optimization with indicators.  _Mathematical Programming (Forthcoming)_ , pages 1–44, 2022.
  * Atamtürk et al. (2021) A. Atamtürk, A. Gómez, and S. Han.  Sparse and smooth signal estimation: Convexification of $\ell_{0}$-formulations.  _Journal of Machine Learning Research_ , 22:52–1, 2021\.
  * Bacci et al. (2019) T. Bacci, A. Frangioni, C. Gentile, and K. Tavlaridis-Gyparakis.  New MINLP formulations for the unit commitment problems with ramping constraints.  _Optimization Online_ , 2019.
  * Behdin and Mazumder (2021) K. Behdin and R. Mazumder.  Archetypal analysis for sparse nonnegative matrix factorization: Robustness under misspecification.  _arXiv:2104.03527_ , 2021.
  * Ben-Tal and Nemirovski (2001) A. Ben-Tal and A. Nemirovski.  _Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications_.  SIAM, 2001.
  * Bertsimas et al. (2021a) D. Bertsimas, R. Cory-Wright, and J. Pauphilet.  A new perspective on low-rank optimization.  _arXiv:2105.05947_ , 2021a.
  * Bertsimas and King (2016) D. Bertsimas and A. King.  OR forum—an algorithmic approach to linear regression.  _Operations Research_ , 64(1):2–16, 2016.
  * Bertsimas et al. (2016) D. Bertsimas, A. King, and R. Mazumder.  Best subset selection via a modern optimization lens.  _Annals of Statistics_ , 44(2):813–852, 2016\.
  * Bertsimas et al. (2021b) D. Bertsimas, J. Pauphilet, and B. Van Parys.  Sparse classification: a scalable discrete optimization perspective.  _Machine Learning_ , 110(11):3177–3209, 2021b.
  * Bertsimas and Van Parys (2020) D. Bertsimas and B. Van Parys.  Sparse high-dimensional regression: Exact scalable algorithms and phase transitions.  _Annals of Statistics_ , 48(1):300–323, 2020\.
  * Bien et al. (2013) J. Bien, J. Taylor, and R. Tibshirani.  A LASSO for hierarchical interactions.  _Annals of Statistics_ , 41(3):1111, 2013.
  * Bienstock (1996) D. Bienstock.  Computational study of a family of mixed-integer quadratic programming problems.  _Mathematical Programming_ , 74(2):121–140, 1996\.
  * Ceria and Soares (1999) S. Ceria and J. Soares.  Convex programming for disjunctive convex optimization.  _Mathematical Programming_ , 86(3):595–614, 1999\.
  * Combettes (2018) P. L. Combettes.  Perspective functions: Properties, constructions, and examples.  _Set-Valued and Variational Analysis_ , 26(2):247–264, 2018.
  * Cozad et al. (2014) A. Cozad, N. V. Sahinidis, and D. C. Miller.  Learning surrogate models for simulation-based optimization.  _AIChE Journal_ , 60(6):2211–2227, 2014.
  * Cozad et al. (2015) A. Cozad, N. V. Sahinidis, and D. C. Miller.  A combined first-principles and data-driven approach to model building.  _Computers & Chemical Engineering_, 73:116–127, 2015\.
  * Dantzig and Eaves (1973) G. B. Dantzig and B. C. Eaves.  Fourier-Motzkin elimination and its dual.  _Journal of Combinatorial Theory_ , 14(3):288–297, 1973.
  * Deza and Atamtürk (2022) A. Deza and A. Atamtürk.  Safe screening for logistic regression with $\ell_{0}$-$\ell_{2}$ regularization.  _arXiv:2202.00467_ , 2022.
  * Frangioni and Gentile (2006) A. Frangioni and C. Gentile.  Perspective cuts for a class of convex 0–1 mixed integer programs.  _Mathematical Programming_ , 106(2):225–236, 2006\.
  * Frangioni et al. (2020) A. Frangioni, C. Gentile, and J. Hungerford.  Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs.  _Mathematics of Operations Research_ , 45(1):15–33, 2020.
  * Gómez (2021) A. Gómez.  Outlier detection in time series via mixed-integer conic quadratic optimization.  _SIAM Journal on Optimization_ , 31(3):1897–1925, 2021.
  * Günlük and Linderoth (2010) O. Günlük and J. Linderoth.  Perspective reformulations of mixed integer nonlinear programs with indicator variables.  _Mathematical Programming_ , 124(1):183–205, 2010\.
  * Han and Gómez (2021) S. Han and A. Gómez.  Compact extended formulations for low-rank functions with indicator variables.  _arXiv:2110.14884_ , 2021.
  * Hastie et al. (2015) T. Hastie, R. Tibshirani, and M. Wainwright.  _Statistical learning with sparsity: the lasso and generalizations_.  CRC Press, 2015.
  * Hazimeh and Mazumder (2020a) H. Hazimeh and R. Mazumder.  Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms.  _Operations Research_ , 68(5):1517–1537, 2020a.
  * Hazimeh and Mazumder (2020b) H. Hazimeh and R. Mazumder.  Learning hierarchical interactions at scale: A convex optimization approach.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1833–1843, 2020b.
  * Hazimeh et al. (2023) H. Hazimeh, R. Mazumder, and P. Radchenko.  Grouped variable selection with discrete optimization: Computational and statistical perspectives.  _Annals of Statistics_ , 51(1):1–32, 2023.
  * Hazimeh et al. (2021) H. Hazimeh, R. Mazumder, and A. Saab.  Sparse regression at scale: Branch-and-bound rooted in first-order optimization.  _Mathematical Programming_ , pages 1–42, 2021.
  * Heller and Tompkins (1956) I. Heller and C. B. Tompkins.  An extension of a theorem of Dantzig’s.  In H. W. Kuhn and A. W. Tucker, editors, _Linear Inequalities and Related Systems_ , pages 247–254. Princeton University Press, 1956.
  * Hiriart-Urruty and Lemaréchal (2004) J.-B. Hiriart-Urruty and C. Lemaréchal.  _Fundamentals of Convex Analysis_.  Springer, 2004.
  * Huang et al. (2012) J. Huang, P. Breheny, and S. Ma.  A selective review of group selection in high-dimensional models.  _Statistical Science_ , 27(4), 2012.
  * Jeon et al. (2017) H. Jeon, J. Linderoth, and A. Miller.  Quadratic cone cutting surfaces for quadratic programs with on–off constraints.  _Discrete Optimization_ , 24:32–50, 2017.
  * Kucukyavuz et al. (2020) S. Kucukyavuz, A. Shojaie, H. Manzour, L. Wei, and H.-H. Wu.  Consistent second-order conic integer programming for learning Bayesian networks.  _arXiv:2005.14346_ , 2020.
  * Liu et al. (2022) P. Liu, S. Fattahi, A. Gómez, and S. Küçükyavuz.  A graph-based decomposition method for convex quadratic optimization with indicators.  _Mathematical Programming (Forthcoming)_ , 2022.
  * Lubin and Dunning (2015) M. Lubin and I. Dunning.  Computing in operations research using Julia.  _INFORMS Journal on Computing_ , 27(2):238–248, 2015.
  * Manzour et al. (2021) H. Manzour, S. Küçükyavuz, H.-H. Wu, and A. Shojaie.  Integer programming for learning directed acyclic graphs from continuous data.  _INFORMS Journal on Optimization_ , 3(1):46–73, 2021.
  * Natarajan (1995) B. K. Natarajan.  Sparse approximate solutions to linear systems.  _SIAM Journal on Computing_ , 24(2):227–234, 1995\.
  * Ramachandra et al. (2021) A. Ramachandra, N. Rujeerapaiboon, and M. Sim.  Robust conic satisficing.  _arXiv:2107.06714_ , 2021.
  * Rockafellar (1970) R. T. Rockafellar.  _Convex Analysis_.  Princeton University Press, 1970.
  * Rudin and Ustun (2018) C. Rudin and B. Ustun.  Optimized scoring systems: Toward trust in machine learning for healthcare and criminal justice.  _Interfaces_ , 48(5):449–466, 2018.
  * Sahinidis (1996) N. V. Sahinidis.  BARON: A general purpose global optimization software package.  _Journal of Global Optimization_ , 8:201–205, 1996.
  * Sahinidis (accessed November 13, 2023) N. V. Sahinidis.  BARON user manual v. 2023.11.10.  https://minlp.com/downloads/docs/baron%20manual.pdf, accessed November 13, 2023.
  * Tibshirani (1996) R. Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 58(1):267–288, 1996.
  * Wei et al. (2022a) L. Wei, A. Atamtürk, A. Gómez, and S. Küçükyavuz.  On the convex hull of convex quadratic optimization problems with indicators.  _arXiv:2201.00387_ , 2022a.
  * Wei et al. (2020) L. Wei, A. Gómez, and S. Küçükyavuz.  On the convexification of constrained quadratic optimization problems with indicator variables.  In _International Conference on Integer Programming and Combinatorial Optimization_ , pages 433–447, 2020.
  * Wei et al. (2022b) L. Wei, A. Gómez, and S. Küçükyavuz.  Ideal formulations for constrained convex optimization problems with indicator variables.  _Mathematical Programming_ , 192(1):57–88, 2022b.
  * Wolsey (1989) L. A. Wolsey.  Submodularity and valid inequalities in capacitated fixed charge networks.  _Operations Research Letters_ , 8(3):119–124, 1989.
  * Xie and Deng (2020) W. Xie and X. Deng.  Scalable algorithms for the sparse ridge regression.  _SIAM Journal on Optimization_ , 30(4):3359–3386, 2020.

##  A Additional Proofs

###### Proof

 _of Lemma 4 _ As for assertion (i), let $\overline{\cal
U}\\!:=\\!{\mathbb{R}}\times{\cal U}$ and $\overline{\cal
V}:=\\{(\tau,{\bm{\mu}},{\bm{t}}\hskip
1.00006pt):{\bm{1}}^{\top}{\bm{t}}=\tau\\}$. By construction, ${\cal V}$ is
the projection of $\overline{\cal U}\cap\overline{\cal V}$ onto
$(\tau,{\bm{\mu}})-$space. Hence, $\operatorname{conv}({\cal
V})=\operatorname{conv}(\operatorname{Proj}_{\tau,{\bm{\mu}}}(\overline{\cal
U}\cap\overline{\cal
V}))=\operatorname{Proj}_{\tau,{\bm{\mu}}}(\operatorname{conv}(\overline{\cal
U}\cap\overline{\cal V}))$. Therefore, in the remainder of the proof we
characterize convex hull of $\overline{\cal U}\cap\overline{\cal V}$. As
$\overline{\cal V}$ is convex, to prove $\operatorname{conv}(\overline{\cal
U}\cap\overline{\cal V})=\operatorname{conv}(\overline{\cal
U})\cap\overline{\cal V}$ it suffices to show that
$\operatorname{conv}(\overline{\cal U})\cap\overline{\cal
V}\subseteq\operatorname{conv}(\overline{\cal U}\cap\overline{\cal V})$.

Take a point $(\bar{\tau},\bar{\bm{\mu}},\bar{\bm{t}}\hskip 0.43057pt)$ from
$\operatorname{conv}(\overline{\cal U})\cap\overline{\cal V}$. Since
$(\bar{\tau},\bar{\bm{\mu}},\bar{\bm{t}}\hskip 0.43057pt)\in\overline{\cal
V}$, we have $\bar{\tau}={\bm{1}}^{\top}\bar{\bm{t}}$. On the other hand,
since $(\bar{\tau},\bar{\bm{\mu}},\bar{\bm{t}}\hskip
0.43057pt)\in\operatorname{conv}(\overline{\cal U})$, we can always express it
as a convex combination of a finite number of points in $\overline{\cal U}$,
that is, $(\bar{\tau},\bar{\bm{\mu}},\bar{\bm{t}}\hskip
0.43057pt)=\sum_{k\in[q]}\lambda_{k}(\tau^{k},{\bm{\mu}}^{k},{\bm{t}}^{k})$
for some finite $q$, $(\tau^{k},{\bm{\mu}}^{k},{\bm{t}}^{k})\in\overline{\cal
U}$, and $\lambda_{k}>0$ for all $k\in[q]$ satisfy
$\sum_{k\in[q]}\lambda_{k}=1$. Notice that there is no restriction on $\tau$
in the definition of $\overline{\cal U}$. Hence, we can take
$\tau^{k}:={\bm{1}}^{\top}{\bm{t}}^{k}$ for all $k\in[q]$. Therefore, we have
$(\tau^{k},{\bm{\mu}}^{k},{\bm{t}}^{k})\in\overline{\cal V}$ for all
$k\in[q]$. We thus deduce
$(\tau^{k},{\bm{\mu}}^{k},{\bm{t}}^{k})\in\overline{\cal U}\cap\overline{\cal
V}$ for all $k\in[q]$. Moreover, because
$\bar{\bm{t}}=\sum_{k\in[q]}\lambda_{k}{\bm{t}}^{k}$, we have
$\sum_{k\in[q]}\lambda_{k}\tau^{k}=\sum_{k\in[q]}\lambda_{k}({\bm{1}}^{\top}t^{k})={\bm{1}}^{\top}(\sum_{k\in[q]}\lambda_{k}t^{k})={\bm{1}}^{\top}\bar{\bm{t}}=\bar{\tau}$.
Hence, this proves that any point
$(\bar{\tau},\bar{\bm{\mu}},\bar{\bm{t}}\hskip 0.43057pt)$ can be written as a
convex combination of points from $\overline{\cal U}\cap\overline{\cal V}$ as
desired. Therefore, $\operatorname{conv}(\overline{\cal U}\cap\overline{\cal
V})=\operatorname{conv}(\overline{\cal U})\cap\overline{\cal V}$, and the
claim follows by projecting onto $(\tau,{\bm{\mu}})-$space.

As for assertion (ii), note that the set ${\cal V}$ is the affine
transformation of the convex set $\widetilde{\cal U}=\\{\bm{\eta}\in{\cal
U}:{\bm{B}}\bm{\eta}=\bm{b}\\}$, that is, ${\cal V}={\bm{A}}\,\widetilde{\cal
U}$. We then have

$\displaystyle\operatorname{cl}({\cal
V})=\operatorname{cl}(\operatorname{rint}({\cal
V}))=\operatorname{cl}({\bm{A}}(\operatorname{rint}(\widetilde{\cal U})))$
$\displaystyle=\operatorname{cl}({\bm{A}}(\operatorname{rint}(\operatorname{cl}(\widetilde{\cal
U}))))$
$\displaystyle=\operatorname{cl}(\operatorname{rint}({\bm{A}}(\operatorname{cl}(\widetilde{\cal
U}))))=\operatorname{cl}({\bm{A}}(\operatorname{cl}(\widetilde{\cal U}))).$

The first equality holds since a convex set and its relative interior have the
same closure. The second equality holds as the linear transformation and the
relative interior operators are interchangeable for convex sets (see
(Rockafellar, 1970, Theorem 6.6)); thus, we have $\operatorname{rint}({\cal
V})=\operatorname{rint}({\bm{A}}\,\widetilde{\cal
U})={\bm{A}}(\operatorname{rint}(\widetilde{\cal U}))$. The third equality
holds as the relative interior of a convex set and the relative interior of
its closure are the same. The fourth equality follows from the convexity of
$\operatorname{cl}(\widetilde{\cal U})$, which allows us to interchange the
linear transformation and the relative interior operators. Finally, the last
inequality holds as the closure of the relative interior of a convex set
equals the closure of the set. Since we assumed that there exists a point
$\bm{\eta}^{\star}\in\operatorname{rint}({\cal U})$ satisfying the condition
${\bm{B}}\bm{\eta}^{\star}=\bm{b}$, we have $\operatorname{cl}(\widetilde{\cal
U})=\\{\bm{\eta}\in\operatorname{cl}({\cal U}):{\bm{B}}\bm{\eta}=\bm{b}\\}$
thanks to (Rockafellar, 1970, Corrolay 6.5.1). Thus, we showed that

$\displaystyle\operatorname{cl}({\cal
V})=\operatorname{cl}({\bm{A}}(\operatorname{cl}(\widetilde{\cal
V})))=\operatorname{cl}(\\{{\bm{\mu}}:\exists\bm{\eta}\in\operatorname{cl}({\cal
U})\text{ s.t. }{\bm{A}}\bm{\eta}={\bm{\mu}},{\bm{B}}\bm{\eta}=\bm{b}\\}).$

As we assumed that $\bm{\eta}=\bm{0}$ is the only
$\bm{\eta}\in\operatorname{rec}(\operatorname{cl}(\widetilde{\cal V}))$ with
${\bm{A}}\bm{\eta}=\bm{0}$, by (Rockafellar, 1970, Theorem 9.1), we have
$\operatorname{cl}({\bm{A}}(\operatorname{cl}(\widetilde{\cal
V})))\\!=\\!{\bm{A}}(\operatorname{cl}(\widetilde{\cal V}))$. This completes
the proof. ∎

###### Proof

 _of Lemma 6 _ Note that the matrix

$\displaystyle{\bm{A}}=\begin{bmatrix}-1&~{}{\bm{1}}^{\top}\\\\[2.15277pt]
0&~{}{\bm{1}}^{\top}\end{bmatrix}$

is totally unimodular. Recall that if $A$ is totally unimodular, then the
matrix $[{\bm{A}}^{\top},~{}{\bm{I}},~{}-{\bm{I}}]^{\top}$ is also totally
unimodular. By definition,
$\Delta_{1}=\\{(w,{\bm{z}})\in\\{0,1\\}^{1+d}:~{}w\leq{\bm{1}}^{\top}{\bm{z}},~{}{\bm{1}}^{\top}{\bm{z}}\leq\kappa\\}$.
As the feasible set of $\Delta_{1}$ will be represented by the matrix
$[{\bm{A}}^{\top},~{}{\bm{I}},~{}-{\bm{I}}]^{\top}$ and an integer vector, the
set $\Delta_{1}$ is totally unimodular, and $\operatorname{conv}(\Delta_{1})$
is thus given by the continuous relaxation of $\Delta_{1}$. ∎

###### Proof

 _of Lemma 7 _ Note that the matrix

$\displaystyle{\bm{A}}=\begin{bmatrix}1&-{\bm{1}}_{d-1}^{\top}&0\\\\[2.15277pt]
0&-{\bm{1}}_{d-1}^{\top}&1\end{bmatrix}$

is totally unimodular as every square submatrix of $A$ has determinant $0$,
$+1$, or $-1$. Moreover, it is easy to see that

$\displaystyle\Delta_{1}$
$\displaystyle\textstyle=\\{(w,{\bm{z}})\in\\{0,1\\}^{1+d}:~{}w\leq{\bm{1}}^{\top}{\bm{z}},~{}z_{d}\leq\sum_{i\in[d-1]}z_{i}\\}$
$\displaystyle\textstyle=\\{(w,{\bm{z}})\in\\{0,1\\}^{1+d}:~{}w\leq\sum_{i\in[d-1]}z_{i},~{}z_{d}\leq\sum_{i\in[d-1]}z_{i}\\},$

which implies that the feasible set of $\Delta_{1}$ can be represented by the
matrix $[{\bm{A}}^{\top},~{}{\bm{I}},~{}-{\bm{I}}]^{\top}$ and an integer
vector. Thus, the new representation of $\Delta_{1}$ is totally unimodular,
and $\operatorname{conv}(\Delta_{1})$ is given by its continuous relaxation. ∎

###### Proof

 _of Lemma 8 _ The set $\Delta_{1}$ can be written as

$\displaystyle\Delta_{1}$
$\displaystyle=\left(\left\\{0\right\\}\times\left\\{\bm{0}\right\\}\right)\cup\left(\left\\{0,1\right\\}\times{\cal
Z}\backslash\left\\{\bm{0}\right\\}\right).$

Since $\operatorname{conv}(A\times
B)=\operatorname{conv}(A)\times\operatorname{conv}(B)$ and
$\operatorname{conv}(A\cup
B)=\operatorname{conv}(\operatorname{conv}(A)\cup\operatorname{conv}(B))$, we
arrive at

$\displaystyle\operatorname{conv}(\Delta_{1})$
$\displaystyle=\operatorname{conv}\left(\left(\left\\{0\right\\}\times\left\\{\bm{0}\right\\}\right)\cup\left([0,1]\times\operatorname{conv}({\cal
Z}\backslash\\{\bm{0}\\})\right)\right)$
$\displaystyle=\left\\{(w,{\bm{z}})\in{\mathbb{R}}^{1+d}:\exists\lambda\in[0,1]\text{~{}s.t.~{}}\begin{array}[]{l}{\bm{F}}^{0}{\bm{z}}\geq\bm{0},~{}0\leq
w\leq\lambda\\\\[4.30554pt]
{\bm{z}}^{\top}\bm{f}^{+}_{k}\geq\lambda,~{}\forall k\in{\cal
K},\\\\[4.30554pt] {\bm{z}}^{\top}\bm{f}_{l}^{-}\leq\lambda,~{}\forall
l\in{\cal L}\end{array}\right\\}$

The proof concludes by projecting out the variable $\lambda$ using the
Fourier-Motzkin elimination approach. ∎

###### Proof

 _of Lemma 9 _ By (Wei et al., 2022b, Lemma 3), we have

$\displaystyle\textstyle\operatorname{conv}({\cal
Z}\backslash\left\\{\bm{0}\right\\})=\left\\{{\bm{z}}\in[0,1]^{d}:~{}\begin{array}[]{l}1\leq\sum_{i\in[d-1]}z_{i}-(d-2)z_{d},\\\\[4.30554pt]
z_{d}\leq z_{i},~{}\forall i\in[d-1]\end{array}\right\\}.$ (A.3)

The proof concludes by applying Lemma 8. ∎

###### Proof

 _of Theorem 3.3 _ Recall the definition of $\widetilde{\cal T}$ and
$\Delta_{p}$. By letting

$\displaystyle{\bm{\beta}}_{i}:=(s_{i},{\bm{x}}_{i}),\,\bm{\gamma}:={\bm{t}},\,{\bm{\delta}}:=({\bm{w}},{\bm{z}}),\,\Delta:=\Delta_{p},\,{\bm{C}}_{i}=[-1,{\bm{a}}_{i}^{\top}],\,{\mathbb{C}}_{i}=\left\\{0\right\\},\,\forall
i\in[p],$

we can represent the set $\widetilde{\cal T}$ as an instance of the set ${\cal
W}$ defined as in (11). Then, Proposition 2 yields

$\displaystyle\operatorname{cl}\operatorname{conv}(\widetilde{\cal
T})\\!=\\!\left\\{({\bm{x}},{\bm{z}},{\bm{s}},{\bm{w}},{\bm{t}})\\!\in\\!{\mathbb{R}}^{d+d+p+p+p}:\begin{array}[]{l}h^{\pi}(s_{i},w_{i})\leq
t_{i},~{}\forall i\in[p]\\\\[4.30554pt]
{\bm{a}}_{i}^{\top}{\bm{x}}_{i}=s_{i},~{}\forall i\in[p]\\\\[4.30554pt]
({\bm{w}},{\bm{z}})\in\operatorname{conv}(\Delta_{p})\end{array}\right\\}.$

In the following we characterize $\operatorname{cl}\operatorname{conv}({\cal
T})$ in terms of $\operatorname{cl}\operatorname{conv}(\widetilde{\cal T})$.
Let ${\cal
T}^{\prime}:=\\{(\tau,{\bm{x}},{\bm{z}}):\exists{\bm{s}},{\bm{w}},{\bm{t}}\text{~{}s.t.~{}}({\bm{x}},{\bm{z}},{\bm{s}},{\bm{w}}.{\bm{t}})\in\widetilde{\cal
T},{\bm{1}}^{\top}{\bm{t}}=\tau\\}$. By Proposition 3, we have

$\displaystyle\operatorname{cl}\operatorname{conv}({\cal
T})=\operatorname{cl}\big{(}\operatorname{conv}(\operatorname{Proj}_{\tau,{\bm{x}},{\bm{z}}}({\cal
T}^{\prime}))\big{)}=\operatorname{cl}\big{(}\operatorname{Proj}_{\tau,{\bm{x}},{\bm{z}}}(\operatorname{conv}({\cal
T}^{\prime}))\big{)}.$

Moreover, applying Lemma 4 (i) yields

$\operatorname{conv}({\cal
T}^{\prime})\\!=\\!\\{(\tau,{\bm{x}},{\bm{z}}):\exists{\bm{s}},{\bm{w}},{\bm{t}}\text{
s.t.
}({\bm{x}},{\bm{z}},{\bm{s}},{\bm{w}},{\bm{t}})\in\operatorname{conv}(\widetilde{\cal
T}),\,{\bm{1}}^{\top}{\bm{t}}=\tau\\}.$

By letting

$\displaystyle\begin{array}[]{c}{\bm{\mu}}:=(\tau,{\bm{x}},{\bm{z}}),~{}\bm{\eta}:=(\tau,{\bm{x}},{\bm{z}},{\bm{s}},{\bm{w}},{\bm{t}}),~{}{\cal
U}:={\mathbb{R}}\times\operatorname{conv}(\widetilde{\cal T}),\\\\[4.30554pt]
{\bm{A}}:=[{\bm{I}}_{1+2d},~{}\bm{0}],~{}{\bm{B}}:=(-1,\bm{0},\bm{0},\bm{0},\bm{0},{\bm{1}}_{p})^{\top},~{}\bm{b}:=0,\end{array}$

we observe that
$\operatorname{Proj}_{\tau,{\bm{x}},{\bm{z}}}(\operatorname{conv}({\cal
T}^{\prime}))=\\{{\bm{\mu}}:\exists\bm{\eta}\in{\cal U}\text{ s.t.
}{\bm{A}}\bm{\eta}={\bm{\mu}},~{}{\bm{B}}\bm{\eta}=\bm{b}\\}$ as in Lemma 4
(ii). Moreover, the first requirement of Lemma 4 (ii) is trivially satisfied
as the variable $\tau$ is free in the set ${\cal U}$. In addition, we have the
set

$\displaystyle\left\\{\bm{\eta}\in\operatorname{cl}({\cal
U}):~{}{\bm{A}}\bm{\eta}=\bm{0},~{}{\bm{B}}\bm{\eta}=\bm{b}\right\\}$
$\displaystyle=$
$\displaystyle\left\\{(0,\bm{0},\bm{0},{\bm{s}},{\bm{w}},{\bm{t}}):~{}\begin{array}[]{l}({\bm{w}},\bm{0})\in\operatorname{conv}(\Delta_{p}),~{}{\bm{1}}^{\top}{\bm{t}}=0\\\\[4.30554pt]
s_{i}={\bm{a}}_{i}^{\top}{\bm{x}}_{i},\,h^{\pi}(s_{i},w_{i})\leq
t_{i},\,\forall i\in[p]\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\left\\{(0,\bm{0},\bm{0},{\bm{s}},{\bm{w}},{\bm{t}}):~{}{\bm{w}}=\bm{0},~{}{\bm{s}}=\bm{0},~{}h^{\pi}(0,0)\leq
t_{i},\,\forall
i\in[p],~{}{\bm{1}}^{\top}{\bm{t}}=0\right\\}=\left\\{\bm{0}\right\\},$

where the first equation holds by the definition of
$\operatorname{cl}\operatorname{conv}(\widetilde{\cal T})$ and the fact that
${\bm{A}}\bm{\eta}=\bm{0}$ implies
$(\tau,{\bm{x}},{\bm{z}})=(0,\bm{0},\bm{0})$, and the second equation holds
because, by definition of $\Delta_{p}$ we have $0\leq
w_{i}\leq{\bm{1}}^{\top}{\bm{z}}_{i}$ which enforces $w_{i}=0$ as
${\bm{z}}_{i}=\bm{0}$ for all $i\in[p]$, and the last equation holds as the
function $h$ satisfies $h(0)=0$, which along with ${\bm{1}}^{\top}{\bm{t}}=0$
implies ${\bm{t}}=\bm{0}$. Thus, we can apply Lemma 4 (ii) to conclude that

$\displaystyle\operatorname{cl}\operatorname{conv}({\cal
T})=\\{(\tau,{\bm{x}},{\bm{z}}):\exists{\bm{s}},{\bm{w}},{\bm{t}}\text{ s.t.
}({\bm{x}},{\bm{z}},{\bm{s}},{\bm{w}},{\bm{t}})\in\operatorname{cl}\operatorname{conv}(\widetilde{\cal
T}),~{}{\bm{1}}^{\top}{\bm{t}}=\tau\\}.$

The proof concludes by projecting out the variable ${\bm{t}}$ using the
Fourier-Motzkin elimination approach. ∎

The convex hull of $\Delta_{p}$ relies on the set

${\cal
Z}_{i}:=\\{{\bm{z}}_{i}\in{\mathbb{R}}^{d_{i}}:\exists\tilde{\bm{z}}\in{\cal
Z}~{}\text{s.t.}~{}\tilde{\bm{z}}_{i}={\bm{z}}_{i},~{}\tilde{\bm{z}}_{j}=\bm{0},\forall
j\neq i\\}$

for every $i\in[p]$. In particular, given any $i\in[p]$, we assume that

$\displaystyle\operatorname{conv}({\cal
Z}_{i}\backslash\left\\{\bm{0}\right\\})=\left\\{{\bm{z}}_{i}\in{\mathbb{R}}^{d_{i}}:{\bm{F}}_{i}^{0}{\bm{z}}_{i}\geq\bm{0},~{}\begin{array}[]{l}{\bm{z}}_{i}^{\top}\bm{f}^{+}_{ik}\geq
1,~{}\forall k\in{\cal K}_{i},\\\\[4.30554pt]
{\bm{z}}_{i}^{\top}\bm{f}_{il}^{-}\leq 1,~{}\forall l\in{\cal
L}_{i}\end{array}\right\\}.$ (A.6)

###### Lemma A.1

Given the representation of $\operatorname{conv}({\cal
Z}_{i}\backslash\left\\{\bm{0}\right\\})$ as in (A.6) for any $i\in[p]$, then

$\displaystyle\operatorname{conv}(\Delta_{p})=\left\\{({\bm{w}},{\bm{z}})\in{\mathbb{R}}^{p+d}:\begin{array}[]{l}\bm{0}\leq{\bm{w}}\leq\bm{1},~{}{\bm{1}}^{\top}{\bm{w}}\leq
1,~{}{\bm{F}}_{i}^{0}{\bm{z}}_{i}\geq\bm{0},~{}\forall i\in[p],\\\\[4.30554pt]
{\bm{z}}_{i}^{\top}\bm{f}^{+}_{ik}\geq w_{i},~{}\forall i\in[p],\forall
k\in{\cal K}_{i},\\\\[4.30554pt] {\bm{z}}_{i}^{\top}\bm{f}_{il}^{-}\leq
1,~{}\forall i\in[p],\forall l\in{\cal L}_{i},\\\\[4.30554pt]
{\bm{z}}_{i}^{\top}\bm{f}_{il}^{-}\leq{\bm{z}}_{i}^{\top}\bm{f}^{+}_{ik},~{}\forall
i\in[p],\forall k\in{\cal K},\forall l\in{\cal L}\end{array}\right\\}.$

###### Proof

 _of Lemma A.1 _ The set $\Delta_{p}$ can be written as the union of $p+1$
sets. Namely,

$\displaystyle\Delta_{p}$
$\displaystyle=\left(\left\\{\bm{0}\right\\}\times\left\\{\bm{0}\right\\}\right)\bigcup\limits_{i\in[p]}\left(\left\\{\bm{0},{\bm{e}}_{i}\right\\}\times\left(\times_{k\in[i-1]}\left\\{\bm{0}\right\\}\times{\cal
Z}_{i}\backslash\left\\{\bm{0}\right\\}\times_{k\in\\{i+1,\dots,p\\}}\left\\{\bm{0}\right\\}\right)\right).$

Since $\operatorname{conv}(A\times
B)=\operatorname{conv}(A)\times\operatorname{conv}(B)$ and
$\operatorname{conv}(A\cup
B)=\operatorname{conv}(\operatorname{conv}(A)\cup\operatorname{conv}(B))$, we
arrive at

$\displaystyle\operatorname{conv}(\Delta_{p})=\left\\{({\bm{w}},{\bm{z}})\in{\mathbb{R}}^{p+d}:\exists\bm{\lambda}\in{\mathbb{R}}^{p}\text{~{}s.t.~{}}\begin{array}[]{l}\bm{0}\leq\bm{\lambda}\leq{\bm{1}},~{}{\bm{1}}^{\top}\bm{\lambda}\leq
1,~{}{\bm{w}}\leq\bm{\lambda},\\\\[4.30554pt]
{\bm{F}}_{i}^{0}{\bm{z}}_{i}\geq\bm{0},~{}\forall i\in[p]\\\\[4.30554pt]
{\bm{z}}_{i}^{\top}\bm{f}^{+}_{ik}\geq\lambda_{i},~{}\forall i\in[p],\forall
k\in{\cal K}_{i},\\\\[4.30554pt]
{\bm{z}}_{i}^{\top}\bm{f}_{il}^{-}\leq\lambda_{i},~{}\forall i\in[p],\forall
l\in{\cal L}_{i}\end{array}\right\\}$

The proof concludes by projecting out the variable $\bm{\lambda}$ using the
Fourier-Motzkin elimination approach. ∎

###### Proof

 _of Lemma 13 _ Note that the matrix

$\displaystyle{\bm{A}}=\begin{bmatrix}{\bm{1}}^{\top}&~{}\phantom{-}\bm{0}^{\top}\\\
\\!\\!{\bm{I}}&~{}-{\bm{I}}\\\
\bm{0}^{\top}&\phantom{-}{\bm{1}}^{\top}\end{bmatrix}$

is totally unimodular. To see this, we partition the rows of ${\bm{A}}$ into
the two disjoint sets $\\{1\\}$ and $\\{2,\dots,d+2\\}$. As such, ${\bm{A}}$
is totally unimodular because every entry in ${\bm{A}}$ is $0$, $+1$, or $-1$,
every column of ${\bm{A}}$ contains at most two non-zero entries, and two
nonzero entries in a column of ${\bm{A}}$ with the same signs belong to either
$\\{1\\}$ or $\\{2,\dots,d+2\\}$, whereas two nonzero entries in a column of
${\bm{A}}$ with the opposite signs belong to $\\{2,\dots,d+2\\}$. Hence, by
(Heller and Tompkins, 1956, Theorem 2), the matrix ${\bm{A}}$ is totally
unimodular. As the feasible set of $\Omega$ is represented by the matrix
$[{\bm{A}}^{\top},~{}{\bm{I}},~{}-{\bm{I}}]^{\top}$ and an integer vector, the
set $\Omega$ is totally unimodular, and $\operatorname{conv}(\Omega)$ is given
by its continuous relaxation. ∎

We next provide ideal and lifted descriptions of $\operatorname{conv}(\Omega)$
for general ${\cal Z}$. Lemma A.2 (i) is particularly useful when the set
$\Omega\backslash\left\\{\bm{0}\right\\}$ is totally unimodular. In this case,
we can provide an ideal description for $\operatorname{conv}(\Omega)$. On the
other hand, Lemma A.2 (ii) is useful when the set ${\cal Z}$ is totally
unimodular.

###### Lemma A.2

The following holds.

  1. (i)

Suppose that $\operatorname{conv}(\Omega\backslash\left\\{\bm{0}\right\\})$
admits the following ideal representation

$\displaystyle\operatorname{conv}(\Omega\backslash\left\\{\bm{0}\right\\})=\left\\{\bm{\delta}\in{\mathbb{R}}^{2d}:{\bm{F}}^{0}\bm{\delta}\geq\bm{0},~{}\begin{array}[]{l}\bm{\delta}^{\top}\bm{f}^{+}_{k}\geq
1,~{}\forall k\in{\cal K},\\\\[4.30554pt] \bm{\delta}^{\top}\bm{f}_{l}^{-}\leq
1,~{}\forall l\in{\cal L}\end{array}\right\\}.$

Then, we have

$\displaystyle\operatorname{conv}(\Omega)\\!=\\!\left\\{\bm{\delta}\in{\mathbb{R}}^{d+d}:{\bm{F}}^{0}\bm{\delta}\geq\bm{0},~{}\begin{array}[]{l}\bm{\delta}^{\top}\bm{f}^{+}_{k}\geq
0,~{}\forall k\in{\cal K},\\\\[4.30554pt] \bm{\delta}^{\top}\bm{f}_{l}^{-}\leq
1,~{}\forall l\in{\cal L},\\\\[4.30554pt]
\bm{\delta}^{\top}\bm{f}_{l}^{-}\leq\bm{\delta}^{\top}\bm{f}^{+}_{k},~{}\forall
k\in{\cal K},\forall l\in{\cal L}\end{array}\right\\}.$

  2. (ii)

Let ${\cal O}_{i}=\\{{\bm{z}}\in{\mathbb{R}}^{d}:z_{i}=0\\}$. Then, we have

$\displaystyle\operatorname{conv}(\Omega)=\left\\{({\bm{w}},{\bm{z}})\\!:\\!\exists\tilde{\bm{z}}^{0},\dots,\tilde{\bm{z}}^{d}\text{
s.t.
}\begin{array}[]{l}{\bm{w}}\in{\mathbb{R}}_{+}^{d},~{}{\bm{1}}^{\top}{\bm{w}}\leq
1,\\\\[4.30554pt]
{\bm{z}}=\tilde{\bm{z}}^{0}+\sum_{i\in[d]}\tilde{\bm{z}}^{i}\\\\[4.30554pt]
\tilde{\bm{z}}^{0}\in(1-{\bm{1}}^{\top}{\bm{w}})\cdot\operatorname{conv}({\cal
Z})\\\\[4.30554pt] \tilde{\bm{z}}^{i}\in w_{i}\cdot\operatorname{conv}({\cal
Z}\backslash{\cal O}_{i}),~{}\forall i\in[d]\end{array}\right\\}.$

###### Proof

For case (i), notice that the set $\Omega$ can be written as the union of two
sets
$\Omega=\left(\left\\{\bm{0}\right\\}\times\left\\{\bm{0}\right\\}\right)\cup\left(\Omega\backslash\left\\{\bm{0}\right\\}\right)$.
We thus have

$\displaystyle\operatorname{conv}(\Omega)$
$\displaystyle=\operatorname{conv}\left(\left(\left\\{\bm{0}\right\\}\times\left\\{\bm{0}\right\\}\right)\cup\left(\operatorname{conv}(\Omega\backslash\\{\bm{0}\\})\right)\right)$
$\displaystyle=\left\\{\bm{\delta}\in{\mathbb{R}}^{d+d}:\exists\lambda\in[0,1]\text{~{}s.t.~{}}{\bm{F}}^{0}\bm{\delta}\geq\bm{0},~{}\begin{array}[]{l}\bm{\delta}^{\top}\bm{f}^{+}_{k}\geq\lambda,~{}\forall
k\in{\cal K},\\\\[4.30554pt]
\bm{\delta}^{\top}\bm{f}_{l}^{-}\leq\lambda,~{}\forall l\in{\cal
L}\end{array}\right\\}.$

The proof concludes by projecting out the variable $\lambda$ using the
Fourier-Motzkin elimination approach.

For case (ii), note that the set $\Omega$ can be written as the union of $d+1$
sets, that is, $\Omega=\left(\left\\{\bm{0}\right\\}\times{\cal
Z}\right)\bigcup\left(\cup_{i\in[d]}\left(\left\\{{\bm{e}}_{i}\right\\}\times({\cal
Z}\backslash{\cal O}_{i})\right)\right)$. We thus have

$\displaystyle\operatorname{conv}(\Omega)$ $\displaystyle=$
$\displaystyle\operatorname{conv}\left(\left(\left\\{\bm{0}\right\\}\times\operatorname{conv}({\cal
Z})\right)\bigcup\left(\cup_{i\in[d]}\left\\{{\bm{e}}_{i}\right\\}\times\operatorname{conv}({\cal
Z}\backslash{\cal O}_{i})\right)\right)$ $\displaystyle=$
$\displaystyle\left\\{({\bm{w}},{\bm{z}}):\begin{array}[]{l}\exists{\bm{w}}^{0},\dots,{\bm{w}}^{d}\\\
\exists{\bm{z}}^{0},\dots,{\bm{z}}^{d}\\\
\exists\bm{\lambda}\in{\mathbb{R}}_{+}^{d}\end{array}\text{ s.t.
}\begin{array}[]{l}{\bm{1}}^{\top}\bm{\lambda}\leq 1,\\\\[4.30554pt]
{\bm{w}}=(1-{\bm{1}}^{\top}\bm{\lambda}){\bm{w}}^{0}+\sum_{i\in[d]}\lambda_{i}{\bm{w}}^{i}\\\\[4.30554pt]
{\bm{z}}=(1-{\bm{1}}^{\top}\bm{\lambda}){\bm{z}}^{0}+\sum_{i\in[d]}\lambda_{i}{\bm{z}}^{i}\\\\[4.30554pt]
({\bm{w}}^{0},{\bm{z}}^{0})\in\left\\{\bm{0}\right\\}\times\operatorname{conv}({\cal
Z})\\\\[4.30554pt]
({\bm{w}}^{i},{\bm{z}}^{i})\in\left\\{{\bm{e}}_{i}\right\\}\times\operatorname{conv}({\cal
Z}\backslash{\cal O}_{i}),~{}\forall i\in[d]\end{array}\right\\}.$

The proof concludes by introducing the new variables
$\tilde{\bm{z}}^{0}=(1-{\bm{1}}^{\top}\bm{\lambda}){\bm{z}}^{0}$ and
$\tilde{\bm{z}}^{i}=\lambda_{i}{\bm{z}}^{i}$ for every $i\in[d]$, and then
projecting out the variable $\bm{\lambda}$ using the observation that
${\bm{w}}=\bm{\lambda}$. ∎

Armed with Lemma A.2, we are ready to provide characterizations for
$\operatorname{conv}(\Omega)$ in the cases of weak and strong hierarchy
constraints.

###### Proof

 _of Lemma 14 _ First, note that

$\displaystyle\Omega\backslash\\{\bm{0}\\}$
$\displaystyle\textstyle=\\{({\bm{w}},{\bm{z}})\in\\{0,1\\}^{d+d}:~{}{\bm{w}}\leq{\bm{z}},~{}{\bm{1}}^{\top}{\bm{w}}\leq
1,~{}\sum_{i\in[d-1]}z_{i}\geq 1\\}.$

Based on this let us consider the matrix

$\displaystyle{\bm{A}}=\begin{bmatrix}{\bm{I}}_{d}\quad&-{\bm{I}}_{d}\\\\[2.15277pt]
{\bm{1}}_{d}^{\top}\quad&\bm{0}_{d}^{\top}\\\\[2.15277pt]
\bm{0}_{d}^{\top}\quad&(-{\bm{1}}_{d-1},0)^{\top}\end{bmatrix}.$

This matrix is totally unimodular as we can partition rows of ${\bm{A}}$ into
the subsets $[d]$ and $\\{d+1,d+2\\}$ such that they satisfy the requirements
of (Heller and Tompkins, 1956, Theorem 2). Thus, the set
$\Omega\backslash\\{\bm{0}\\}$ is represented by constraints based on the
matrix $[{\bm{A}}^{\top},~{}{\bm{I}},~{}-{\bm{I}}]^{\top}$ and an integer
vector. Thus, $\Omega\backslash\\{\bm{0}\\}$ admits a totally unimodular
representation, and $\operatorname{conv}(\Omega\backslash\\{\bm{0}\\})$ is
given by its continuous relaxation. The proof concludes by applying Lemma A.2
(i). ∎

###### Proof

 _of Lemma 15 _ Note that ${\cal Z}$ is totally unimodular. Hence, the
continuous relaxation of ${\cal Z}$ gives $\operatorname{conv}({\cal Z})$. For
any $i\in[d-1]$, we also have ${\cal Z}\backslash{\cal
O}_{i}=\\{{\bm{z}}\in\\{0,1\\}^{d}:z_{i}=1,~{}z_{d}\leq z_{j},~{}\forall
j\in[d-1]\\}.$ It is easy to see that the continuous relaxation of ${\cal
Z}\backslash{\cal O}_{i}$ gives its convex hull. Besides, we have ${\cal
Z}\backslash{\cal O}_{d}=\\{\bm{1}\\}$. The proof follows by applying Lemma
A.2 (ii). ∎

##  B Additional Numerical Results

Figure B.1: Comparison of different continuous relaxations for $N=100$,
$\pi=0.1$ as $p$ (and thus $d$) varies.

Figure B.2: Performance of the B&B algorithm for $N=100$, $\pi=0.1$ as $p$
(and thus $d$) varies.

Figure B.3: Comparison of different continuous relaxations for
$(p,N)\\!=\\!(50,100)$ as $\pi$ varies.

Figure B.4: Performance of the B&B algorithm for $(p,N)\\!=\\!(50,100)$ as
$\pi$ varies.