# The Boolean polynomial polytope with multiple choice constraints

Sihong Shao111CAPT, LMAM and School of Mathematical Sciences, Peking
University, Beijing 100871, China. Email<EMAIL_ADDRESS>Yishan
Wu222CAPT, LMAM and School of Mathematical Sciences, Peking University,
Beijing 100871, China. Email<EMAIL_ADDRESS>
###### Abstract

We propose a polytope to study multiple choice polynomial programming (MCPP).
It is the convex hull of $0$-$1$ vectors satisfying multiple choice
constraints and production constraints both of which are associated with a
hypergraph. With the help of the decomposability property, we obtain an
explicit half-space representation of the MCPP polytope when the underlying
hypergraph is $\alpha$-acyclic by induction on the number of hyperedges. We
also present a necessary and sufficient condition for the inequalities lifted
from the facet-inducing ones for the multilinear polytope to be still facet-
inducing for the MCPP polytope.

Keywords: Pseudo-Boolean optimization, Multiple choice constraint, Multilinear
polytope, Hypergraph acyclicity, Lifted inequality

Mathematics Subject Classification: 90C09, 52B12, 90C57, 05C65, 90C26

##  1 Introduction

We consider a constrained $0$-$1$ polynomial programming problem of the
following form:

$\displaystyle\max_{x\in\\{0,1\\}^{n}}\quad$ $\displaystyle
f(x)=\sum_{J\in\mathcal{J}}a_{J}\prod_{i\in J}x_{i},$ (1.1a) s.t.
$\displaystyle\sum_{i\in I}x_{i}=1,\ \forall\,I\in\mathscr{P},$ (1.1b)

where $\mathcal{J}\subseteq 2^{[n]}$ is a family of nonempty subset of the
index set $[n]:=\\{1,2,\dots,n\\}$, $a\in\mathbb{R}^{\mathcal{J}}$ is the
vector of coefficients, and $\mathscr{P}$ is a partition of $[n]$, i.e., the
disjoint union of all $I\in\mathscr{P}$ is $[n]$. Without loss of generality,
we assume that $|I|>1$ for all $I\in\mathscr{P}$. The constraints in Eq.
(1.1b) imply that there is exactly one entry of $x$ per subset of the
partition equal to $1$. Thus the entries in each $I\in\mathscr{P}$ serve as a
decision with $|I|$ choices. Therefore, the constraints are often termed
“multiple choice constraints” [19], and Problem (1.1) is termed multiple
choice polynomial programming (MCPP) in this paper. The feasible region of
Problem (1.1) is denoted by $\mathcal{X}$. Since for all $x\in\mathcal{X}$,
any monomial of $f(x)$ with the divisor $x_{i}x_{i^{\prime}}$, $i\neq
i^{\prime}$, $i,i^{\prime}\in I$ and $I\in\mathscr{P}$, vanishes, we can
eliminate them from $f(x)$. Therefore, it can be further assumed that, for
each $J\in\mathcal{J}$, we have

$|J\cap I|\leqslant 1,\quad\forall\,I\in\mathscr{P}.$ (1.2)

In this situation, we call the objective function $f(x)$ to be _$\mathscr{P}$
-multilinear_ and let $\mathcal{J}_{\mathscr{P}}$ collect all the nonempty
subsets $J$s of $[n]$ that satisfy Eq. (1.2). Thus
$\mathcal{J}\subseteq\mathcal{J}_{\mathscr{P}}$.

Since $(x_{i})^{p}=x_{i}$ for $x_{i}\in\\{0,1\\}$, any $0$-$1$ polynomial
programming with multiple choice constraints can be reformulated into MCPP.
The polynomial $f(x)$ is often referred to as “multilinear function” [4]. Note
that if $|I|=2$ for all $I\in\mathscr{P}$, $\mathcal{X}$ is isomorphic to
$\\{0,1\\}^{|\mathscr{P}|}$, and Problem (1.1) degenerates to a pseudo-Boolean
optimization instance by substituting half of the components of $x$ according
to the multiple choice constraints (i.e., assumed
$I=\\{i,i^{\prime}\\}\in\mathscr{P}$, we can substitute $x_{i^{\prime}}$ by
$1-x_{i}$). Hence, MCPP subsumes pseudo-Boolean optimization (PBO) and can be
regarded as a generalization of the latter: From binary to “$|I|$-ary”. Since
PBO can model various combinatorial problems [4], MCPP is capable of modelling
problems generalized from them, for example, MAX-$k$-CUT [17] (generalized
from MAX-CUT) and hypergraph k-cut [7] (generalized from hypergraph cut), MAX-
CSP [9] (generalized from MAX-SAT). Meanwhile, there exist other problems
naturally associated with multiple choice decision which can be formulated as
MCPP, such as the calculation of star discrepancy [22]. It is worth mentioning
that all these problems are NP-hard.

This work is devoted into performing a polyhedral study of MCPP. To this end,
we need to first introduce a hypergraph $H(V,E)$ corresponding to Problem
(1.1) with

$V:=\mathscr{P},\quad E:=\\{E(J)|J\in\mathcal{J},|E(J)|>1\\},$ (1.3)

where $E(J):=\\{I\in\mathscr{P}||I\cap J|=1\\}$ is defined for each
$J\in\mathcal{J}_{\mathscr{P}}$. To facilitate the discussion, the family
$\mathcal{J}$ is enlarged into $\mathcal{J}^{H}$ by adding monomials for
ensuring the subset-uniform property with respect to (w.r.t) $V$. Actually, it
can be show that for any $\mathcal{J}$, there exists $\mathcal{J}^{H}$ such
that $\mathcal{J}\subseteq\mathcal{J}^{H}$ and thus after possibly introducing
zero entries of the coefficient vector $a$ for the added monomials in
$\mathcal{J}^{H}\setminus\mathcal{J}$, we can replace $\mathcal{J}$ with
$\mathcal{J}^{H}$ in Eq. (1.1a). More explanations on this point and the
family $\mathcal{J}^{H}$ are left for Section 2.1. After representing each
monomial $\prod_{i\in J}x_{i}$ with a new variable $w_{J}$ for
$J\in\mathcal{J}^{H}$, a common practice to obtain a linear objective function
from a polynomial one, and adding the production constraints
$w_{J}=\prod_{i\in J}w_{i}$, Problem (1.1) with $\mathcal{J}^{H}$ equivalently
becomes

$\displaystyle\max_{w\in\\{0,1\\}^{\mathcal{J}^{H}}}\quad$
$\displaystyle\sum_{J\in\mathcal{J}^{H}}a_{J}w_{J},$ (1.4a) s.t.
$\displaystyle w(I)=1,\ \forall\,I\in\mathscr{P},$ (1.4b) $\displaystyle
w_{J}=\prod_{i\in J}w_{i},\ \forall\,J\in\mathcal{J}^{H},\ |J|>1,$ (1.4c)

where we have applied the convention: $w_{i}:=w_{\\{i\\}}=x_{i}$ for all
$i\in[n]$, and $w(A)=\sum_{i\in A}w_{i}$ for any nonempty subset
$A\subseteq[n]$. In order to develop the polytope theory for Problem (1.4), it
is key to understand the structure of the convex hull of its feasible region.
We refer to the feasible region as _$\mathscr{P}$ -multilinear set_ w.r.t.
$H(V,E)$, denoted by $\mathscr{S}^{H}$, i.e.,

$\mathscr{S}^{H}=\left\\{w\in\\{0,1\\}^{\mathcal{J}^{H}}\middle|w(I)=1,\
\forall\,I\in V;w_{J}=\prod_{i\in J}w_{i},\
\forall\,J\in\mathcal{J}^{H},|J|>1\right\\}.$ (1.5)

The subsequent discussion focuses on $\mathrm{MC}^{H}$ — the convex hull of
$\mathscr{S}^{H}$: $\mathrm{MC}^{H}=\operatorname{conv}\mathscr{S}^{H}$, and
we call it the Boolean polynomial polytope with multiple choice constraints or
the MCPP polytope. In particular, the structural properties of
$\mathrm{MC}^{H}$, including its half-space representation and lifting facets
from related polytopes, are concerned.

###  1.1 Contributions of this work

The first contribution gives an explicit half-space representation of
$\mathrm{MC}^{H}$ under the condition that $H$ is $\alpha$-acyclic. The
$\alpha$-acyclic hypergraph belongs to the most general case among the well-
known four degrees of acyclicity: $\alpha$, $\beta$, $\gamma$ and Berge-
acyclic (see Theorem 6.1 of [16]). An important characterization is that
$\alpha$-acyclic hypergraphs have join trees [2].

######  Theorem 1.1 (Half-space Representation).

Suppose $H(V,E)$ is $\alpha$-acyclic and $T=(E,\mathcal{E})$ is a join tree of
$H$. Then

$\displaystyle\mathrm{MC}^{H}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}$ $\displaystyle w(I)=1,\ \forall\,I\in V;$ (1.6a)
$\displaystyle w_{i}-\sum_{J\in\mathcal{J}^{e}:J\ni i}w_{J}=0,\ \forall\,e\in
E,i\in I\in e;$ (1.6b) $\displaystyle\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}-\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J}=0,\
\forall\,ee^{\prime}\in\mathcal{E},|e\cap
e^{\prime}|>1,J_{0}\in\mathcal{J}^{e\cap e^{\prime}}\bigg{\\}}.$ (1.6c)

Theorem 1.1 allows us to solve Eq. (1.1) in polynomial time when the rank of
$H$ and $|I|$ for $I\in V$ are bounded.

We prove the above Theorem 1.1 by induction on $|E|$. The inductive step
mainly consists of deducting description of $\mathrm{MC}^{H}$ from known
descriptions of $\mathrm{MC}^{H_{1}}$ and $\mathrm{MC}^{H_{2}}$, where $H_{1}$
and $H_{2}$ are subhypergraphs of $H$. The crucial part of the deduction is a
sufficient condition for decomposability of $\mathrm{MC}^{H}$. We present it
in Theorem 4.1 of independent interest.

The second contribution is a verifiable necessary and sufficient condition for
a lifted inequality to be facet-inducing. The so-called “multilinear
polytope”, $\mathrm{MP}^{H}:=\operatorname{conv}\mathcal{S}^{H}$, was
introduced to study PBO [11]

$\max_{x\in\\{0,1\\}^{V}}\sum_{I\in V}p_{I}x_{I}+\sum_{e\in E}p_{e}\prod_{I\in
e}x_{I},$ (1.7)

where $\mathcal{S}^{H}$ is the multilinear set

$\mathcal{S}^{H}=\left\\{z\in\\{0,1\\}^{L(V)\cup E}\middle|z_{e}=\prod_{I\in
e}z_{I},\ \forall\,e\in E\right\\},$ (1.8)

$L(V):=\\{\\{I\\}|I\in V\\}$ denotes the collection of all singleton subsets
of $V$, and $z_{I}:=z_{\\{I\\}}$. It can be readily seen that compared to
$\mathscr{S}^{H}$ in Eq. (1.5) for MCPP, $\mathcal{S}^{H}$ for PBO lacks the
multiple choice constraints. Suppose $c\cdot z\leqslant\delta$ is a valid
inequality for $\mathrm{MP}^{H}$. For any $S_{I}\subseteq I,I\in V$, we have
$0\leqslant w(S_{I})\leqslant w(I)=1$ for any $w\in\mathscr{S}^{H}$. Thus, we
can replace $z_{I}$ with $w(S_{I})$ and $z_{e}$ with $\prod_{I\in e}w(S_{I})$,
then linearize the inequality to obtain a valid inequality for
$\mathrm{MC}^{H}$. More precisely, the following inequality is valid for
$\mathrm{MC}^{H}$:

$\sum_{e\in L(V)\cup E}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}}w_{i}\leqslant\delta,$ (1.9)

where the operator $\mathscr{L}$ replaces the monomials involving
$w_{i},i\in[n]$, i.e., $\prod_{i\in J}w_{i}$, with $w_{J}$. This can be seen
as follows: for any $w\in\mathscr{S}^{H}$, letting $z_{I}=w(S_{I})$ for $I\in
V$, and $z_{e}=\prod_{I\in e}\sum_{i\in S_{I}}w_{i}$ for $e\in E$, we have
$z\in\mathcal{S}^{H}$, and the LHS of the inequality Eq. (1.9) becomes $c\cdot
z$, so it holds for any $w\in\mathrm{MC}^{H}$. We call Eq. (1.9) the lifted
inequality of $c\cdot z\leqslant\delta$ w.r.t. $S_{I},I\in V$. Since facets
are important structure of polytopes, it is natural to ask:

> _Is the lifted inequality still facet-inducing for $\mathrm{MC}^{H}$ when
> $c\cdot z\leqslant\delta$ is facet-inducing for $\mathrm{MP}^{H}$? _

Answering the above question faces some difficulties because $\mathrm{MC}^{H}$
is not full-dimensional. We resort to the full-dimensional polytope
$\mathrm{MC}^{H}_{\leqslant}$ (see Eq. (3.2)). To utilize the properties of
$\mathrm{MC}^{H}_{\leqslant}$ more straightforwardly, it is required that
$\mathrm{MC}^{H}$ is isomorphic to $\mathrm{MC}^{H}_{\leqslant}$, the
sufficient condition of which is $H$ being downward-closed as stated in
Proposition 3.2. With these at our disposal, we give a positive answer in
Theorem 1.2 which provides an easily verifiable necessary and sufficient
condition.

######  Theorem 1.2 (Lifted Facet-inducing Inequalities).

Suppose the hypergraph $H(V,E)$ is downward-closed, i.e., for any
$e^{\prime}\subseteq e,e\in E$, $|e^{\prime}|>1$, we have $e^{\prime}\in E$.
Let $c\cdot z\leqslant\delta$ be a facet-inducing inequality for
$\mathrm{MP}^{H}$. Define

$\displaystyle V_{0}$ $\displaystyle=\\{I\in
V|\forall\,z\in\mathrm{MP}^{H},z_{I}=0\ \text{implies}\ c\cdot z=\delta\\},$
(1.10) $\displaystyle V_{1}$ $\displaystyle=\\{I\in
V|\forall\,z\in\mathrm{MP}^{H},z_{I}=1\ \text{implies}\ c\cdot z=\delta\\}.$
(1.11)

For any $S_{I}\subset I,S_{I}\neq\varnothing,I\in V$, the inequality (1.9) is
facet-inducing for $\mathrm{MC}^{H}$ if and only if the following condition
holds:

$|S_{I}|=1,\ \forall\,I\in V_{0}\ \text{and}\ |S_{I}|=|I|-1,\ \forall\,I\in
V_{1}.$ (1.12)

Theorem 1.2 specifies all the facets of $\mathrm{MC}^{H}$ that are lifted from
$\mathrm{MP}^{H}$. Note that when the condition $S_{I}\subset
I,S_{I}\neq\varnothing$ for $S_{I}$ is relaxed to $S_{I}\subseteq I$, Eq.
(1.9) remains a valid inequality. However, when $S_{I^{\prime}}=\varnothing$,
$w(S_{I^{\prime}})=0$, then Eq. (1.9) can be viewed as the lifted inequality
of $c^{\prime}\cdot z^{\prime}\leqslant\delta^{\prime}$, where
$c^{\prime}\cdot z^{\prime}\leqslant\delta^{\prime}$ is the inequality
obtained by removing the terms $z_{e}$ for $I^{\prime}\in e,e\in L(V)\cup E$
from $c\cdot z\leqslant\delta$, which is also valid (but not necessarily
facet-inducing). Similarly, when $S_{I^{\prime}}=I^{\prime}$,
$w(S_{I^{\prime}})=1$, Eq. (1.9) can be viewed as the inequality obtained by
replacing $z_{e}$ with $z_{e-I^{\prime}}$ in $c\cdot z\leqslant\delta$ and
lifting it. Therefore, Theorem 1.2 can effectively determine whether lifted
inequalities are facet-inducing facets even when there are $S_{I}$ such that
$S_{I}=\varnothing$ or $S_{I}=I$.

###  1.2 Related works

The study of polytope theory for $0$-$1$ polynomial programming may date back
to Padberg’s famous Boolean quadric polytope $\mathrm{QP}^{G}$ [20], which was
defined as the convex hull of the feasible region of linearized unconstrained
$0$-$1$ quadratic programming associated with a graph $G(V,E)$, i.e.,

$\mathrm{QP}^{G}=\operatorname{conv}\\{(x,y)\in\\{0,1\\}^{V}\times\\{0,1\\}^{E}|y_{ij}=x_{i}x_{j},\
\forall\,\\{i,j\\}\in E\\},$ (1.13)

where $y_{ij}$ is an alias of $y_{e}$. Various families of facets as well as
lifting properties of $\mathrm{QP}^{G}$ were studied there under the condition
that $G$ is a complete or sparse graph. On the other hand, $\mathrm{QP}^{G}$
is closely related to the cut polytope [1] via a bijective linear
transformation between them [8]. Since then, $\mathrm{QP}^{G}$ and the cut
polytope have been extensively studied due to their fundamental role in
Boolean quadratic programming [3, 23, 24]. Actually, the multilinear polytope
$\mathrm{MP}^{H}$ degenerates to $\mathrm{QP}^{G}$ when hypergraph $H$ reduces
to graph $G$, and a series of studies have been conducted on $\mathrm{MP}^{H}$
[12, 13, 14]. We will further show that $\mathrm{MP}^{H}$ is isomorphic to a
projection of $\mathrm{MC}^{H}$ (see Proposition 2.1).

However, both $\mathrm{MP}^{H}$ and $\mathrm{QP}^{G}$ are associated with
unconstrained programming problems. Polytopes associated with $0$-$1$
polynomial programming with multiple choice constraints date back to [15], and
several polytopes related to different kinds of $k$-cut problems of complete
graph were proposed at that time. Among them, the ${}^{\leqslant}k$-cut
polytope happens to be the image of $\mathrm{MC}^{K_{m}}$ under a linear
transformation since the weighted MAX-$k$-CUT of complete graph $K_{m}$ can be
formulated into MCPP (1.1). (Let $|V|=m$ and
$I=\\{i^{I}_{1},i^{I}_{2},\dots,i^{I}_{k}\\}$ for $I\in V$. Note that a
${}^{\leqslant}k$-cut can be expressed by a $x\in\mathcal{X}$, and components
of $\chi(S_{1},\dots,S_{h})$ of [15] can be formulated as
$1-\sum_{t=1}^{k}x_{i^{I_{1}}_{t}}x_{i^{I_{2}}_{t}}$.)

Very recently, the bipartite Boolean quadric polytope (BQP) with multiple
choice constraints [6]

$P(G,\mathcal{I})=\operatorname{conv}\left\\{(x,y,z)\in\\{0,1\\}^{X\cup Y\cup
E}\middle|x_{i}y_{j}=z_{ij},\forall\,ij\in E;x\in X^{\mathcal{I}}\right\\}$
(1.14)

was proposed for investigating a variant of bilinear programming

$\displaystyle\max_{(x,y)\in\\{0,1\\}^{X\cup Y}}$
$\displaystyle\quad\sum_{i\in X}a_{i}x_{i}+\sum_{j\in
Y}a_{j}y_{j}+\sum_{\\{i,j\\}\in E}a_{ij}x_{i}y_{i},$ (1.15a) s.t.
$\displaystyle\quad\sum_{i\in I}x_{i}\leqslant 1,\ \forall\,I\in\mathcal{I},$
(1.15b)

where $G=(X\cup Y,E)$ is a bipartite graph ($X$ and $Y$ are color classes of
$G$), $\mathcal{I}$ is a partition of $X$, and
$X^{\mathcal{I}}=\\{x\in\\{0,1\\}^{X}|\sum_{i\in I}x_{i}\leqslant 1,\ \forall
I\in\mathcal{I}\\}$ is the set of $0$-$1$ vectors that satisfy the multiple
choice constraints in Eq. (1.15b). We would like to point out that Eq. (1.15b)
is slightly different from Eq. (1.1b) for the former are inequalities.
Obviously, by introducing $x_{\bar{i}_{I}}=1-\sum_{i\in I}x_{i}\in\\{0,1\\}$
for $I\in\mathcal{I}$, Eq. (1.15b) becomes $\sum_{i\in
I}x_{i}+x_{\bar{i}_{I}}=1$, and Problem (1.15) can thus be reformulated as
MCPP (1.1). As a result, when $G$ is subset-uniform, $P(G,\mathcal{I})$ is
nothing but a projection of $\mathrm{MC}^{H}$ (see Example 3.2) and thus
Theorem 1.2 can be applied to $P(G,\mathcal{I})$ for achieving some results of
[6] in a straightforward manner (see Example 6.1)).

In a word, the proposed $\mathrm{MC}^{H}$ serves as a polytope associated with
general case of $0$-$1$ polynomial programming with (equality) multiple choice
constraints and is thus different from those existing polytopes mentioned
above. However, those polytopes can be regarded as images of $\mathrm{MC}^{H}$
under linear maps in certain conditions.

###  1.3 Organization and convention

The main task of this paper is to prove Theorems 1.1 and 1.2. In Section 2, we
give basic properties of $\mathrm{MC}^{H}$ that are useful for the subsequent
investigation. Since $\mathrm{MC}^{H}$ is not full-dimensional, Section 3
provides some techniques to address this deficiency such as considering full-
dimensional $\mathrm{MC}^{H}_{\leqslant}$. Then, Section 4 gives a sufficient
condition for the decomposability of $\mathrm{MC}^{H}$ which plays a key role
in proving Theorem 1.1. After that, Sections 5 and 6 detail the proofs of
Theorems 1.1 and 1.2, respectively. Finally, Section 7 rounds the paper off
with some discussions.

Throughout the rest of this paper, we adopt the following conventions.

  * •

Whenever we refer to $\mathrm{MC}^{H}$, it is assumed that the vertex set of
hypergraph $H$ is an partition of $[n]$ and $\mathrm{MC}^{H}$ is associated
with a concrete linearized MCPP instance (1.4).

  * •

For hypergraphs $H(V,E)$ and $H^{\prime}(V^{\prime},E^{\prime})$, we say that
$H$ is a _subhypergraph_ of $H^{\prime}$, denoted by $H\subseteq H^{\prime}$,
if $V\subseteq V^{\prime}$ and $E\subseteq E^{\prime}$.

  * •

A hypergraph is called _downward-closed_ , if for any $e^{\prime}\subseteq e$
and $e\in E$ with $|e^{\prime}|>1$, it holds that $e^{\prime}\in E$.

  * •

For any finite sets $S$ and $S^{\prime}\subseteq S$, and $x\in\mathbb{R}^{S}$,
we use $\operatorname{Proj}_{S^{\prime}}x\in\mathbb{R}^{S^{\prime}}$ to denote
the projection mapping that extracts components of $x$ whose indices are in
$S^{\prime}$. It extends to a set $X\subseteq\mathbb{R}^{S}$,

$\operatorname{Proj}_{S^{\prime}}X=\\{\operatorname{Proj}_{S^{\prime}}x|x\in
X\\}.$ (1.16)

  * •

For any set $S$ and $s\in S$, we use $S-s$ to denote $S\setminus\\{s\\}$.

  * •

We use the shorthand $st$ for an edge $\\{s,t\\}$ of a graph.

  * •

We use $\mathscr{L}$ to denote the linearization operator. It applies to a
multilinear polynomial (meaning that the polynomial is linear w.r.t. each
component) involving $w_{i},i\in[n]$ and replaces all the monomials
$\prod_{i\in J}w_{i}$ with $w_{J}$ (after possibly expanding the products).
Thus the resulting function is linear to $w_{J},J\subseteq[n]$. For example,

$\mathscr{L}(1-w_{1})(1-w_{2})=1-w_{1}-w_{2}+w_{\\{1,2\\}}.$

Note that the entries $J$ are limited in general, e.g., $J\in\mathcal{J}^{H}$.
Hence we have to certify all the monomials every time before applying the
operator $\mathscr{L}$. An important property of $\mathscr{L}$ is that the
operator does not change the value of the polynomial for any
$w\in\mathscr{S}^{H}$.

##  2 Basic properties

In this section, we first delineate the subset-uniformity of $\mathcal{J}^{H}$
and then present some basic properties associated with two kinds of projection
of $\mathrm{MC}^{H}$. Some of the properties are key in the proof of our main
theorems.

###  2.1 Subset-uniformity of $\mathcal{J}^{H}$

For each nonempty subset $e\subseteq[n]$, let

$\mathcal{J}^{e}:=\\{J\in\mathcal{J}_{\mathscr{P}}|E(J)=e\\}$ (2.1)

collect all the subsets in $\mathcal{J}_{\mathscr{P}}$ associated with $e$,
and then define

$\mathcal{J}^{H}:=\bigcup_{e\in L(V)\cup E}\mathcal{J}^{e},$ (2.2)

For any $J\in\mathcal{J}_{\mathscr{P}}$ and $i\in J$, $i,i^{\prime}\in I$,
$I\in V$, it is obvious that $E(J)=E(J\setminus\\{i\\}\cup\\{i^{\prime}\\})$.
Since $\mathcal{J}^{H}$ is consists of groups of $J$s that share the same
$E(J)$, we have

$J\in\mathcal{J}^{H}\ \text{if and only if}\
J\setminus\\{i\\}\cup\\{i^{\prime}\\}\in\mathcal{J}^{H}.$ (2.3)

We call the above property for $\mathcal{J}^{H}$ _subset-uniformity_ w.r.t.
$V$. This subset-uniformity is inspired by [6] and the definitions coincide in
the following sense: A bipartite graph $G(X\cup Y,E)$ is subset-uniform w.r.t.
the partition $\mathcal{I}$ (of $X$) in the context of [6] if and only if $E$
is subset-uniform w.r.t. the partition $\mathcal{I}\cup L(Y)$ of $X\cup Y$ in
our definition (2.3). The subset-uniformity allows us to access entries of $w$
by groups of $J\in\mathcal{J}^{e}$ when $e\in L(V)\cup E$. This is crucial for
many formulations of our propositions, see, e.g., the summation in Eqs. (2.7)
and (3.18). In fact, when some problems with certain symmetry, for instance,
MAX-$k$-CUT [22], are rewritten into the MCPP form (1.1), the resulting
$\mathcal{J}$ is naturally subset-uniform w.r.t. $V$. That is,
$\mathcal{J}^{H}\setminus\mathcal{J}$ only adds some singleton subsets
according to Eq. (2.2), which correspond to $w_{i},i\in[n]$ and are
indispensable in the linearized formulation Eq. (1.4).

###  2.2 Connections between $\mathrm{MC}^{H}$ and $\mathrm{MP}^{H}$

Arbitrarily choose an $\bar{i}_{I}\in I$ in order to stand for each $I\in V$
and let $R=\\{\bar{i}_{I}\\}_{I\in V}$. Then there exists a natural one-to-one
correspondence between $R$ and $V$, leading to the correspondence between
$\mathcal{J}^{H}|_{R}:=\\{J\in\mathcal{J}^{H}|J\subseteq R\\}$ and $L(V)\cup
E$:

$J\leftrightarrow E(J).$ (2.4)

Accordingly, it is easy to verify that

$\operatorname{Proj}_{\mathcal{J}^{H}|_{R}}\mathscr{S}^{H}=\left\\{w^{\prime}\in\\{0,1\\}^{\mathcal{J}^{H}|_{R}}\middle|w^{\prime}_{J}=\prod_{i\in
J}w^{\prime}_{i},\ \forall\,J\in\mathcal{J}^{H}|_{R},|J|>1\right\\}.$ (2.5)

Comparing Eqs. (1.8) and (2.5) together, we are able to conclude that there is
one-to-one correspondence between
$\operatorname{Proj}_{\mathcal{J}^{H}|_{R}}\mathscr{S}^{H}$ and
$\mathcal{S}^{H}$. Considering their convex hulls, the following connection as
stated in Proposition 2.1 is achieved.

######  Proposition 2.1.

Given a hypergraph $H(V,E)$, and $R=\\{\bar{i}_{I}\\}_{I\in V}$, where
$\bar{i}_{I}\in I$ for $I\in V$, then
$\operatorname{Proj}_{\mathcal{J}^{H}|_{R}}\mathrm{MC}^{H}$ is in one-to-one
correspondence with $\mathrm{MP}^{H}$, denoted as $w\leftrightarrow z$. The
mapping is defined as follows: For all $J\in\mathcal{J}^{H}|_{R}$, let
$z_{E(J)}=w_{J}$.

###  2.3 Connections between $\mathrm{MC}^{H}$ and $\mathrm{MC}^{H^{\prime}}$
when $H\subseteq H^{\prime}$

When $H$ is a subhypergraph of $H^{\prime}$, it is obvious that
$\mathcal{J}^{H}\subseteq\mathcal{J}^{H^{\prime}}$. From the definition (1.5),
it is also evident that
$\operatorname{Proj}_{\mathcal{J}^{H}}\mathscr{S}^{H^{\prime}}=\mathscr{S}^{H}$.
Considering their convex hulls, we arrive at the following proposition.

######  Proposition 2.2.

Suppose $H$ is a subhypergraph of $H^{\prime}$, then

$\operatorname{Proj}_{\mathcal{J}^{H}}\mathrm{MC}^{H^{\prime}}=\mathrm{MC}^{H}.$
(2.6)

When we add a hyperedge into $H$ and the resulting hypergraph is $H^{\prime}$,
there exists an isomorphism from $\mathrm{MC}^{H^{\prime}}$ to
$\mathrm{MC}^{H}$ as shown in Proposition 2.3. This result also serves as a
technical lemma for proving Theorem 1.1.

######  Proposition 2.3.

Given a hypergraph $H(V,E)$, let $e_{1}\in E$ and $e_{2}\subset e_{1}$ such
that $e_{2}\notin E$ and $|e_{2}|>1$. Define
$H^{\prime}=(V,E\cup\\{e_{2}\\})$. Then, the projection of
$\mathrm{MC}^{H^{\prime}}$ onto $\mathrm{MC}^{H}$ is a linear isomorphism, and

$\mathrm{MC}^{H^{\prime}}=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H^{\prime}}}\middle|\operatorname{Proj}_{\mathcal{J}^{H}}w\in\mathrm{MC}^{H};w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}w_{J^{\prime}},\ \forall\,J\in\mathcal{J}^{e_{2}}\right\\}.$ (2.7)

###### Proof.

Define $\mathcal{T}:\mathrm{MC}^{H}\rightarrow\mathrm{MC}^{H^{\prime}}$ that
linearly maps $v$ to $w$ as follows: For any $J\in\mathcal{J}^{e_{2}}$,

$w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}v_{J^{\prime}};$ (2.8)

and for $J\in\mathcal{J}^{H}$, $w_{J}=v_{J}$. Obviously,
$\operatorname{Proj}_{\mathcal{J}^{H}}w=v$.

When $v\in\mathscr{S}^{H}$, we claim that
$w=\mathcal{T}(v)\in\mathscr{S}^{H^{\prime}}$. It suffices to prove for
$J\in\mathcal{J}^{H^{\prime}}\setminus\mathcal{J}^{H}=\mathcal{J}^{e_{2}}$,

$w_{J}=\prod_{i\in J}w_{i}.$ (2.9)

It holds since

$\displaystyle w_{J}$
$\displaystyle=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}v_{J^{\prime}}$
$\displaystyle=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}\prod_{i\in J^{\prime}}v_{i}$ $\displaystyle=\prod_{i\in
J}v_{i}\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}\prod_{i\in J^{\prime}\setminus J}v_{i}$ $\displaystyle=\prod_{i\in
J}v_{i}\prod_{I\in e_{1}\setminus e_{2}}\sum_{i\in I}v_{i}$
$\displaystyle=\prod_{i\in J}v_{i},$

and $w_{i}=v_{i},i\in[n]$. Thus, $\mathcal{T}$ gives a one-to-one
correspondence between $\mathscr{S}^{H}$ and $\mathscr{S}^{H^{\prime}}$.
Moreover, since $\mathcal{T}$ is linear, it it naturally extended to form a
one-to-one correspondence between $\mathrm{MC}^{H}$ and
$\mathrm{MC}^{H^{\prime}}$. Hence, we have

$\displaystyle\mathrm{MC}^{H^{\prime}}$
$\displaystyle=\mathcal{T}(\mathrm{MC}^{H})$ (2.11a)
$\displaystyle=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H^{\prime}}}\middle|\operatorname{Proj}_{\mathcal{J}^{H}}w\in\mathrm{MC}^{H};w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}}:J^{\prime}\supseteq
J}w_{J^{\prime}},\ \forall\,J\in\mathcal{J}^{e_{2}}\right\\}.$ (2.11b)

∎

##  3 The affine hull of $\mathrm{MC}^{H}$

Given a hypergraph $H(V,E)$ and $D=\\{\bar{i}_{I}\\}_{I\in
V}\in\mathcal{J}^{V}$, let

$\displaystyle\mathcal{J}^{H}_{\leqslant}(D)$
$\displaystyle:=\mathcal{J}^{H}|_{[n]\setminus
D}=\left\\{J\in\mathcal{J}^{H}\middle|J\subseteq[n]\setminus D\right\\},$
(3.1) $\displaystyle\mathrm{MC}^{H}_{\leqslant}(D)$
$\displaystyle:=\operatorname{conv}\bigg{\\{}v\in\\{0,1\\}^{\mathcal{J}^{H}_{\leqslant}(D)}\bigg{|}v(I\setminus
D)\leqslant 1,\ \forall\,I\in V;$ $\displaystyle\hskip
113.50023ptv_{J}=\prod_{i\in J}v_{i},\
\forall\,J\in\mathcal{J}^{H}_{\leqslant}(D),|J|>1\bigg{\\}}.$ (3.2)

When $D$ is clear from the context, we often simply write
$\mathcal{J}^{H}_{\leqslant}$ and $\mathrm{MC}^{H}_{\leqslant}$ for
$\mathcal{J}^{H}_{\leqslant}(D)$ and $\mathrm{MC}^{H}_{\leqslant}(D)$,
respectively.

######  Example 3.1.

If $|I|=2$ for all $I\in V$, letting $R=[n]\setminus D$, we have
$R\in\mathcal{J}^{V}$. Then $\mathcal{J}^{H}_{\leqslant}=\mathcal{J}^{H}|_{R}$
and
$\mathrm{MC}^{H}_{\leqslant}=\operatorname{Proj}_{\mathcal{J}^{H}|_{R}}\mathrm{MC}^{H}$.
According to Proposition 2.1, we have $\mathrm{MC}^{H}_{\leqslant}$ is in one-
to-one correspondence with $\mathrm{MP}^{H}$.

######  Example 3.2.

Suppose $G(X\cup Y,E)$ is a subset-uniform bipartite graph in the context of
[6]. Then $P(G,\mathcal{I})$ is actually a special case of
$\mathrm{MC}^{H}_{\leqslant}$, which can be verified as follows. The subset-
uniformity requires $G$ to have the following properties: For any
$I\in\mathcal{I}$ and $i_{1},i_{2}\in I$, they share the same neighborhood in
$E$. Let $\bar{i}_{I},I\in\mathcal{I}\cup L(Y)$ be arbitrary indices other
than $X\cup Y$, and define

$\displaystyle V$
$\displaystyle=\\{I\cup\\{\bar{i}_{I}\\}\\}_{I\in\mathcal{I}\cup L(Y)},$ (3.3)
$\displaystyle\hat{E}$ $\displaystyle=\\{I_{1}I_{2}|\exists i_{1}\in
I_{1},i_{2}\in I_{2}\ \text{s.t.}\ i_{1}i_{2}\in E\\},$ (3.4) $\displaystyle
D$ $\displaystyle=\\{\bar{i}_{I}\\}_{I\in\mathcal{I}\cup L(Y)}.$ (3.5)

It is readily seen that $H=(V,\hat{E})$ is isomorphic to
$\mathcal{G}=(\mathcal{I}\cup Y,\mathcal{E})$ which is achieved by merging the
vertices in each subset of the partition $\mathcal{I}$ into a single vertex.
Additionally, $\mathcal{J}^{H}_{\leqslant}(D)=L(X)\cup L(Y)\cup E$. Comparing
Eqs. (3.2) and (1.14), we have that $\mathrm{MC}^{H}_{\leqslant}(D)$ is in
one-to-one correspondence with $P(G,\mathcal{I})$.

Let $v^{U}\in\\{0,1\\}^{\mathcal{J}^{H}_{\leqslant}}$ denote the vector with
entries $1$ corresponding to $J\subseteq U$ and $0$ for others. Take
$v^{U},U\in\\{\varnothing\\}\cup\mathcal{J}^{H}_{\leqslant}$. It is
straightforward to verify that they are $|\mathcal{J}^{H}_{\leqslant}|+1$
affinely independent vectors of $\mathrm{MC}^{H}_{\leqslant}$, implying:

######  Proposition 3.1.

$\mathrm{MC}^{H}_{\leqslant}(D)$ is full-dimensional.

Due to the equality constraints $w(I)=1$, $\mathrm{MC}^{H}$ is never full-
dimensional, and thus its affine hull is strictly contained in
$\mathbb{R}^{\mathcal{J}^{H}}$. With the help of
$\mathrm{MC}^{H}_{\leqslant}$, the half-space representation of
$\operatorname{aff}\mathrm{MC}^{H}$ can be reached when $H$ is downward-closed
(see Theorem 3.4). Comparing Eqs. (3.2) with (1.5), it is easily seen that
$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}\mathrm{MC}^{H}=\mathrm{MC}^{H}_{\leqslant}$.
Denote the restriction of this projection to $\mathrm{MC}^{H}$ by

$\operatorname{Proj}_{\leqslant}:\mathrm{MC}^{H}\rightarrow\mathrm{MC}^{H}_{\leqslant}.$
(3.6)

If $\operatorname{Proj}_{\leqslant}$ is invertible, then it defines a linear
isomorphism between $\mathrm{MC}^{H}$ and the full-dimensional
$\mathrm{MC}^{H}_{\leqslant}$. Although this is not always true, we are able
to give a sufficient condition (see Proposition 3.2). This isomorphism allows
us to verify whether a given inequality is facet-inducing for
$\mathrm{MC}^{H}$ in an easier way, see Section 6.

######  Proposition 3.2.

Suppose $H(V,E)$ is downward-closed. Given any $D\in\mathcal{J}^{V}$,
$\operatorname{Proj}_{\leqslant}$ in Eq. (3.6) defines a bijection between
$\mathrm{MC}^{H}$ and $\mathrm{MC}^{H}_{\leqslant}$.

###### Proof.

We define $\mathcal{T}:\mathrm{MC}^{H}_{\leqslant}\rightarrow\mathrm{MC}^{H}$
that maps $v$ to $w$ as follows:

$w_{J}=v_{J},\quad\forall\,J\in\mathcal{J}^{H}_{\leqslant},$ (3.7)

and for other components,

$w_{J}=\mathscr{L}\prod_{\bar{i}_{I}\in J\cap D}\left(1-\sum_{i\in
I-\bar{i}_{I}}v_{i}\right)\prod_{i\in J\setminus D}v_{i},\quad
J\in\mathcal{J}^{H}\setminus\mathcal{J}^{H}_{\leqslant}.$ (3.8)

Note that any monomial $\prod_{i\in J^{\prime}}v_{i}$ in the expansion of

$\prod_{\bar{i}_{I}\in J\cap D}\left(1-\sum_{i\in
I-\bar{i}_{I}}v_{i}\right)\prod_{i\in J\setminus D}v_{i}$

satisfies $E(J^{\prime})\subseteq E(J)\in L(V)\cup E$ and $J^{\prime}\cap
D=\varnothing$. Combining the downward-closedness of $H$, we have
$J^{\prime}\in\mathcal{J}^{H}_{\leqslant}$. Therefore, $\mathcal{T}$ is well-
defined.

Now, we verify that $\mathcal{T}$ is the inverse mapping of
$\operatorname{Proj}_{\leqslant}$. It is clear from (3.7) that
$\operatorname{Proj}_{\leqslant}\circ\mathcal{T}=id$. Next, we prove
$\mathcal{T}\circ\operatorname{Proj}_{\leqslant}=id$. For any
$w\in\mathscr{S}^{H}$, suppose $v=\operatorname{Proj}_{\leqslant}w$, then
$v\in\\{0,1\\}^{\mathcal{J}^{H}_{\leqslant}}$ satisfies the production
constraints. Hence, the values of any polynomial w.r.t. $v$ remain unchanged
under the linearization operator.

We prove that $\mathcal{T}_{J}(v)=w_{J}$ for any $J\in\mathcal{J}^{H}$.
Firstly, for any $J\in\mathcal{J}^{H}_{\leqslant}$, we have

$\mathcal{T}_{J}(v)=v_{J}=w_{J}.$

Especially, when $i\in[n]\setminus D$, $v_{i}=w_{i}$. Secondly, for any
$J\in\mathcal{J}^{H}\setminus\mathcal{J}^{H}_{\leqslant}$, we have

$\displaystyle\mathcal{T}_{J}(v)$
$\displaystyle=\mathscr{L}\prod_{\bar{i}_{I}\in J\cap D}\left(1-\sum_{i\in
I-\bar{i}_{I}}v_{i}\right)\prod_{i^{\prime}\in J\setminus D}v_{i^{\prime}}$
(3.9a) $\displaystyle=\prod_{\bar{i}_{I}\in J\cap D}\left(1-\sum_{i\in
I-\bar{i}_{I}}v_{i}\right)\prod_{i^{\prime}\in J\setminus D}v_{i^{\prime}}.$
(3.9b)

Using that fact that $i\in I-\bar{i}_{I}\subseteq[n]\setminus D$ and
$i^{\prime}\in J\setminus D\subseteq[n]\setminus D$, we can replace $v_{i}$
and $v_{i^{\prime}}$ with $w_{i}$ and $w_{i^{\prime}}$, respectively, and
obtain

RHS of Eq. (3.9) $\displaystyle=\prod_{\bar{i}_{I}\in J\cap
D}\left(1-\sum_{i\in I-\bar{i}_{I}}w_{i}\right)\prod_{i^{\prime}\in J\setminus
D}w_{i^{\prime}}$ (3.10a) $\displaystyle=\prod_{\bar{i}_{I}\in J\cap
D}w_{\bar{i}_{I}}\prod_{i^{\prime}\in J\setminus D}w_{i^{\prime}}$ (3.10b)
$\displaystyle=w_{J}.$ (3.10c)

Therefore, $\mathcal{T}(\operatorname{Proj}_{\leqslant}(w))=\mathcal{T}(v)=w$.
Combining the fact that $w$ is any vertex of $\mathrm{MC}^{H}$, and that both
$\mathcal{T}$ and $\operatorname{Proj}_{\leqslant}$ are linear, we conclude
that $\mathcal{T}\circ\operatorname{Proj}=id$ also holds on $\mathrm{MC}^{H}$.
That is, $\mathcal{T}=\operatorname{Proj}_{\leqslant}^{-1}$. ∎

The projection $\operatorname{Proj}_{\leqslant}$ in Eq. (3.6) also defines an
isomorphism between each facet of $\mathrm{MC}^{H}$ and its corresponding
facet of $\mathrm{MC}^{H}_{\leqslant}$. Consider a facet-inducing inequality
for $\mathrm{MC}^{H}$, $a\cdot w\leqslant\delta$, which induces facet $F$.
Suppose the nonzero components of $a$ corresponds only to
$J\in\mathcal{J}^{H}_{\leqslant}$, then it can be regarded as an inequality in
the space of $\mathrm{MC}^{H}_{\leqslant}$, i.e.,

$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}{a}\cdot v\leqslant\delta.$
(3.11)

For any $v\in\mathrm{MC}^{H}_{\leqslant}$, we have
$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}{a}\cdot
v=a\cdot\operatorname{Proj}_{\leqslant}^{-1}(v)$. Thus Eq. (3.11) is also
valid for $\mathrm{MC}^{H}_{\leqslant}$. Moreoever, it induces a facet,
$\operatorname{Proj}_{\leqslant}F$. It is easily seen that the inverse
proposition of facet of $\mathrm{MC}^{H}_{\leqslant}$ is also true, leading to
Corollary 3.3.

######  Corollary 3.3.

Suppose $H(V,E)$ is downward-closed. $\mathrm{MC}^{H}$ is defined w.r.t.
$D\in\mathcal{J}^{V}$. Let $a\cdot w\leqslant\delta$ be a valid inequality for
$\mathrm{MC}^{H}$ such that

$\\{J\in\mathcal{J}^{H}|a_{J}\neq 0\\}\subseteq\mathcal{J}^{H}_{\leqslant}.$
(3.12)

Then $a\cdot w\leqslant\delta$ is facet-inducing for $\mathrm{MC}^{H}$ if and
only if $\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}a\cdot
v\leqslant\delta$ is facet-inducing for $\mathrm{MC}_{\leqslant}^{H}$.

Proposition 3.1 implies
$\operatorname{aff}\mathrm{MC}_{\leqslant}^{H}=\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}}$.
The inverse linear mapping $\operatorname{Proj}_{\leqslant}^{-1}$ defined
above can be naturally extended to a linear map $\tilde{\mathcal{T}}$ on
$\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}}$ such that its definition is still
consistent with Eqs. (3.7) and (3.8). In consequence, we have

$\tilde{\mathcal{T}}(\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}})=\tilde{\mathcal{T}}(\operatorname{aff}\mathrm{MC}_{\leqslant}^{H})=\operatorname{aff}\tilde{\mathcal{T}}(\mathrm{MC}_{\leqslant}^{H})=\operatorname{aff}\mathrm{MC}^{H}.$
(3.13)

From this, the half-space representation of
$\operatorname{aff}\mathrm{MC}^{H}$ can be obtained.

######  Theorem 3.4.

Suppose $H(V,E)$ is downward-closed, and $D=\\{\bar{i}_{I}\\}_{I\in
V}\in\mathcal{J}^{V}$, then

$\operatorname{aff}\mathrm{MC}^{H}=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H}}\middle|w_{J}=\mathscr{L}\prod_{\bar{i}_{I}\in
J\cap D}\left(1-\sum_{i\in I-\bar{i}_{I}}w_{i}\right)\prod_{i\in J\setminus
D}w_{i},\
\forall\,J\in\mathcal{J}^{H}\setminus\mathcal{J}^{H}_{\leqslant}\right\\}.$
(3.14)

###### Proof.

We define
$\tilde{\mathcal{T}}:\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}}\rightarrow\mathbb{R}^{\mathcal{J}^{H}}$
that maps $v$ to $w$ as

$w_{J}=v_{J},\quad\forall\,J\in\mathcal{J}^{H}_{\leqslant},$ (3.15)

and for other components,

$w_{J}=\mathscr{L}\prod_{\bar{i}_{I}\in J\cap D}\left(1-\sum_{i\in
I-\bar{i}_{I}}v_{i}\right)\prod_{i\in J\setminus D}v_{i},\quad
J\in\mathcal{J}^{H}\setminus\mathcal{J}^{H}_{\leqslant}.$ (3.16)

Since the expressions are the same to Eqs. (3.7) and (3.8),
$\tilde{\mathcal{T}}$ is extension of $\mathcal{T}$ defined in the proof of
Proposition 3.2, and RHS of Eq. (3.16) is linear w.r.t. components of $w$
corresponding to indices in $\mathcal{J}^{H}_{\leqslant}$. Thus
$\tilde{\mathcal{T}}(\mathrm{MC}_{\leqslant}^{H})=\mathcal{T}(\mathrm{MC}^{H}_{\leqslant})=\mathrm{MC}^{H}$,
and Eq. (3.13) holds. Substituting $v_{J}$ by $w_{J}$ in Eq. (3.16), we obtain

$\tilde{\mathcal{T}}(\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}})=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H}}\middle|w_{J}=\mathscr{L}\prod_{\bar{i}_{I}\in
J\cap D}\left(1-\sum_{i\in I-\bar{i}_{I}}w_{i}\right)\prod_{i\in J\setminus
D}w_{i},\
\forall\,J\in\mathcal{J}^{H}\setminus\mathcal{J}^{H}_{\leqslant}\right\\}.$
(3.17)

The proof is thus completed using Eq. (3.13). ∎

Note that RHS of Eq. (3.14) depends on $D$ while
$\operatorname{aff}\mathrm{MC}^{H}$ is independent of $D$. In fact, there
exists an equivalent half-space representation of
$\operatorname{aff}\mathrm{MC}^{H}$ which remains unchanged for any
permutation within $I\in V$. The following corollary can be verified from
Theorem. 3.4.

######  Corollary 3.5.

Suppose $H(V,E)$ is downward-closed, then

$\displaystyle\operatorname{aff}\mathrm{MC}^{H}=$
$\displaystyle\bigg{\\{}w\in\mathbb{R}^{\mathcal{J}^{H}}\bigg{|}w(I)=1,\
\forall\,I\in V;$ (3.18) $\displaystyle
w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e^{\prime}}:J^{\prime}\supset
J}w_{J^{\prime}},\ \forall\,e,e^{\prime}\in L(V)\cup E,e\subset
e^{\prime},|e^{\prime}|=|e|+1,\forall\,J\in\mathcal{J}^{e}\bigg{\\}}.$

##  4 Decomposability of $\mathrm{MC}^{H}$

In this section, we provide a sufficient condition for the decomposability of
the MCPP polytope $\mathrm{MC}^{H}$. Let $H_{1}(V_{1},E_{1})$ and
$H_{2}(V_{2},E_{2})$ be subhypergraphs of $H$ such that $H_{1}\cup H_{2}=H$,
where $H_{1}\cup H_{2}$ is defined as $(V_{1}\cup V_{2},E_{1}\cup E_{2})$. We
say that $\mathrm{MC}^{H}$ is decomposable into $\mathrm{MC}^{H_{1}}$ and
$\mathrm{MC}^{H_{2}}$ if

$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}},$
(4.1)

where $\overline{\mathrm{MC}}^{H_{k}}$ collects all the points in
$\mathbb{R}^{J^{H}}$ whose projections on $\mathbb{R}^{J^{H^{k}}}$ belong to
$\mathrm{MC}^{H_{k}}$, $k=1,2$. Namely,

$\overline{\mathrm{MC}}^{H_{k}}=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H}}\middle|\operatorname{Proj}_{\mathcal{J}^{H_{k}}}w\in\mathrm{MC}^{H_{k}}\right\\},\quad
k=1,2.$ (4.2)

The decomposability in Eq. (4.1) implies that the half-space representation of
$\mathrm{MC}^{H}$ is the union of the half-space representations of
$\mathrm{MC}^{H_{1}}$ and $\mathrm{MC}^{H_{2}}$. Therefore, the study of
$\mathrm{MC}^{H}$ can be transferred to that of smaller $\mathrm{MC}^{H_{k}}$.
In the rest of this paper, for $w\in\mathbb{R}^{\mathcal{J}^{H}}$ and
$H^{\prime}$ being a subhypergraph of $H$, we shortly denote
$\operatorname{Proj}_{H^{\prime}}w=\operatorname{Proj}_{\mathcal{J}^{H^{\prime}}}w$.

######  Example 4.1.

A natural sufficient condition for the decomposability is $V_{1}\cap
V_{2}=\varnothing$, in which any $J_{1}\in\mathcal{J}^{H_{1}}$ and
$J_{2}\in\mathcal{J}^{H_{2}}$ are disjoint. In the definition of
$\mathscr{S}^{H}$ in Eq. (1.5), all production constraints $w_{J}=\prod_{i\in
J}w_{i}$ are partitioned into two unrelated groups. Hence

$\mathscr{S}^{H}=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H}}\middle|\operatorname{Proj}_{H_{k}}w\in\mathscr{S}^{H_{k}},\,k=1,2\right\\}.$
(4.3)

Then it is easy to see that
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$.

Due to the redundancy or non-full-dimensionality inside $\mathrm{MC}^{H}$
discussed in the previous section, the conditions for the decomposability may
be weaker than that for $\mathrm{MP}^{H}$ [13].

######  Theorem 4.1.

Suppose the hypergraphs $H(V,E)$, $H_{1}(V_{1},E_{1})$ and
$H_{2}(V_{2},E_{2})$ satisfy $H=H_{1}\cup H_{2}$. If $V_{1}\cap
V_{2}\in(L(V_{1})\cup E_{1})\cap(L(V_{2})\cup E_{2})$, then

$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}.$
(4.4)

###### Proof.

Take any $w\in\mathscr{S}^{H}$. It is easily seen that

$\operatorname{Proj}_{H_{k}}w\in\mathscr{S}^{H_{k}}\subset\mathrm{MC}^{H_{k}},\
k=1,2,$

implying
$w\in\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$. By the
arbitrariness of $w$, we have

$\mathscr{S}^{H}\subseteq\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}.$
(4.5)

As the RHS of the above equation is convex, we can take the convex hull on the
LHS, yielding

$\mathrm{MC}^{H}\subseteq\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}.$
(4.6)

Now it suffices to prove the inverse inclusion. Suppose $w$ is a vertex of the
polytope $\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$,
and let $u^{k}=\operatorname{Proj}_{H_{k}}w$, $k=1,2$. Since both
$\overline{\mathrm{MC}}^{H_{1}}$ and $\overline{\mathrm{MC}}^{H_{2}}$ are
rational polyhedra, $w$ is also rational. Then, by the definition of
$\overline{\mathrm{MC}}^{H_{k}}$, we know that $u^{k}\in\mathrm{MC}^{H_{k}}$,
so it can be expressed as convex combination of points in
$\mathscr{S}^{H_{k}}$. Since $u^{k}$ and all points in $\mathscr{S}^{H_{k}}$
are rational, the convex combination can be written as follows without loss of
generality:

$u^{k}=\frac{1}{s_{k}}\sum_{\ell=1}^{s_{k}}u^{k,\ell},$ (4.7)

where $u^{k,i}\in\mathscr{S}^{H_{k}},i=1,2,\dots,s_{k}$. Furthermore, by
repeating $u^{k,\ell}$, we can assume without loss of generality that
$s_{1}=s_{2}=:s$. Let $p=V_{1}\cap V_{2}$, and due to the condition,
$p\in(L(V_{1})\cup E_{1})\cap(L(V_{2})\cup E_{2})$. For any
$J\in\mathcal{J}^{p}$, we have $u^{1}_{J}=u^{2}_{J}=w_{J}$, and combining that
$u^{k,\ell}_{J}\in\\{0,1\\}$, we obtain

$sw_{J}=su^{k}_{J}=\sum_{\ell=1}^{s}u^{k,\ell}_{J}=|\\{\ell\in[s]|u^{k,\ell}_{J}=1\\}|,\quad
k=1,2.$ (4.8)

Since $\sum_{J\in\mathcal{J}^{p}}u^{k,\ell}_{J}=1$, the subsets of $[s]$,
$\\{\ell\in[s]|u^{k,\ell}_{J}=1\\}$, form a disjoint partion of $[s]$ over $J$
in $\mathcal{J}^{p}$. Note that both of $|\\{\ell\in[s]|u^{k,\ell}_{J}=1\\}|$
are equal to $sw_{J}$. Thus, we can rearrange $\\{u^{1,\ell}\\}_{\ell\in[s]}$
and assume that
$u^{1,\ell}_{J}=u^{2,\ell}_{J},\forall\,J\in\mathcal{J}^{p},\ell=1,2,\dots,s$.
Then, by the properties of $\mathscr{S}^{H_{k}}$, for any $i\in\bigcup_{I\in
p}I$, we have

$u^{k,\ell}_{i}=\sum_{J\in\mathcal{J}^{p}:J\ni i}u^{k,\ell}_{J},$ (4.9)

so $u^{1,\ell}_{i}=u^{2,\ell}_{i}$. Moreover, for any
$J\in\mathcal{J}^{H_{1}}\cap\mathcal{J}^{H_{2}}\subseteq\mathcal{J}^{p}$,
since $J\subseteq\bigcup_{I\in p}I$, we have

$u^{1,\ell}_{J}=\prod_{i\in J}u^{1,\ell}_{i}=\prod_{i\in
J}u^{2,\ell}_{i}=u^{2,\ell}_{J}.$ (4.10)

Therefore, we can naturally combine $u^{1,\ell}$ and $u^{2,\ell}$ to form
$w^{\ell}\in\mathscr{S}^{H}$ for $\ell\in[s]$, and

$w=\frac{1}{s}\sum_{\ell=1}^{s}w^{\ell}.$ (4.11)

This shows that $w$ is a convex combination of points in $\mathrm{MC}^{H}$,
and hence $w\in\mathrm{MC}^{H}$. By the arbitrariness,
$\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}\subseteq\mathrm{MC}^{H}$.
∎

######  Remark 1.

The above vertices matching technique, expressing a convex combination in
terms of $\frac{1}{s}\sum_{\ell=1}^{s}u^{k,\ell}$ and matching the vertices
$\\{u^{k,\ell}\\}_{\ell=1}^{s}$ between $k=1$ and $k=2$, is inspired by the
proof of Theorem 25.1 in [21]. In fact, using this technique to prove Theorem
5 of [12] and Theorem 4 of [14] is much simpler than the original approaches —
calculating all the coefficients of the convex combination.

##  5 Proof of Theorem 1.1

Recall that the join tree is an important characterization for
$\alpha$-acyclicity.

######  Theorem 5.1 (Part of Theorem 3.4 of [2]).

A hypergraph is $\alpha$-acyclic if and only if it has a join tree.

We repeat the definition of join tree to be more self-contained.

######  Definition 5.2 (Condition 3.9 of [2]).

Give a hypergraph $H(V,E)$, a join tree $T$ of $H$ is a tree (connected
acyclic undirected graph) with vertex set $E$ such that for any path, the
intersection of the two endpoints, is contained in every vertex along the
path. More precisely, let $e_{1}$ and $e_{2}$ be any distinct vertices of $T$,
then each vertex $e$ on the unique path connecting $e_{1}$ and $e_{2}$
satisfies $e_{1}\cap e_{2}\subseteq e$.

Note that each vertex of $T$ is a hyperedge of $H$. To distinguish it from
vertex of $H$, we sometimes refer to vertices of $T$ as nodes when we need to
stress their properties about $T$.

Before showing the proof, we quickly verify that RHS of Eq. (1.6) is a
relaxation of $\mathrm{MC}^{H}$.

Suppose $H$ is an arbitrary graph. It is easily seen that for any
$w\in\mathscr{S}^{H}$, $e\in E$, and $i_{0}\in I_{0}\in e$, we have

$\displaystyle\sum_{J\in\mathcal{J}^{e}:J\ni i_{0}}w_{J}$
$\displaystyle=\sum_{J\in\mathcal{J}^{e}:J\ni i_{0}}\prod_{i\in J}w_{i}$
(5.1a) $\displaystyle=w_{i_{0}}\prod_{I\in e-I_{0}}\sum_{i\in I}w_{i}$ (5.1b)
$\displaystyle=w_{i_{0}}.$ (5.1c)

Similarly, for any $e,e^{\prime}\in E$ with $|e\cap e^{\prime}|>1$ and
$J_{0}\in\mathcal{J}^{e\cap e^{\prime}}$, it holds that

$\sum_{J\in\mathcal{J}^{e}:J\supseteq J_{0}}w_{J}=\prod_{i\in
J_{0}}w_{i}=\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J}.$ (5.2)

Thus, we can define the following relaxation of $\mathrm{MC}^{H}$:

$\displaystyle\mathrm{MC}^{H}_{\cap}:=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}$ $\displaystyle w(I)=1,\ \forall\,I\in V;$ (5.3a)
$\displaystyle w_{i}-\sum_{J\in\mathcal{J}^{e}:J\ni i}w_{J}=0,\ \forall\,e\in
E,i\in I\in e;$ (5.3b) $\displaystyle\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}-\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J}=0,\
\forall\,e,e^{\prime}\in E,|e\cap e^{\prime}|>1,J_{0}\in\mathcal{J}^{e\cap
e^{\prime}}\bigg{\\}}.$ (5.3c)

Since $\mathscr{S}^{H}\subseteq\mathrm{MC}^{H}$, we have
$\mathrm{MC}^{H}\subseteq\mathrm{MC}^{H}_{\cap}$.

When $H$ is $\alpha$-acyclic, by Theorem 5.1, $H$ admits a join tree. Let
$T=(E,\mathcal{E})$ be its join tree. By limiting $e,e^{\prime}$ adjacent in
$T$ from the system of equalities Eq. (5.3c), $\mathrm{MC}^{H}_{\cap}$ can be
further relaxed into

$\displaystyle\mathrm{MC}^{H}_{T}:=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}$ $\displaystyle w(I)=1,\ \forall\,I\in V;$ (5.4a)
$\displaystyle w_{i}-\sum_{J\in\mathcal{J}^{e}:J\ni i}w_{J}=0,\ \forall\,e\in
E,i\in I\in e;$ (5.4b) $\displaystyle\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}-\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J}=0,\
\forall\,ee^{\prime}\in\mathcal{E},|e\cap
e^{\prime}|>1,J_{0}\in\mathcal{J}^{e\cap e^{\prime}}\bigg{\\}},$ (5.4c)

which is the same to the RHS of Eq. (1.6) of Theorem 1.1. It is obvious that
$\mathrm{MC}^{H}_{\cap}\subseteq\mathrm{MC}^{H}_{T}$. Note that the join tree
of $H$ is not unique, so $\mathrm{MC}^{H}_{T}$ may vary according to $T$.
However, the following lemma demonstrates that $\mathrm{MC}^{H}_{T}$ is in
fact independent of the choice of $T$.

######  Lemma 5.3.

Suppose $H=(V,E)$ is $\alpha$-acyclic, and $T=(E,\mathcal{E})$ is a join tree
of $H$, then $\mathrm{MC}^{H}_{\cap}=\mathrm{MC}^{H}_{T}$.

###### Proof.

Comparing Eq. (5.3) with Eq. (5.4), the only difference is that all equalities
in Eq. (5.4c) are contained in Eq. (5.3c), thus
$\mathrm{MC}^{H}_{T}\supseteq\mathrm{MC}^{H}_{\cap}$. To prove
$\mathrm{MC}^{H}_{T}=\mathrm{MC}^{H}_{\cap}$, it suffices to show that all
equalities in Eq. (5.3c) are implicit equalities of $\mathrm{MC}^{H}_{T}$.

Suppose $e,e^{\prime}\in E$, $|e\cap e^{\prime}|>1$, then there exists a
unique path from $e$ to $e^{\prime}$ in $T$. We prove by induction on the path
length $l$ that for any $J_{0}\in\mathcal{J}^{e\cap e^{\prime}}$, the
following equality holds for any $w\in\mathrm{MC}^{H}_{T}$:

$\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J}.$ (5.5)

When $l\leqslant 1$, the statement is trivial since $l=0$ implies
$e=e^{\prime}$ and $l=1$ implies $ee^{\prime}\in\mathcal{E}$, meaning that Eq.
(5.5) is just Eq. (5.4c).

Suppose $e_{1},e_{2}\in E$ with $|e_{1}\cap e_{2}|>1$ and the length of the
path from $e_{1}$ to $e_{2}$ in $T$ is $l$. Now assume the statement holds for
$e,e^{\prime}$ such that the path length is shorter that $l$. Note that Eq.
(5.5) holds even when $|e\cap e^{\prime}|\leqslant 1$ for the following
reasons: If $|e\cap e^{\prime}|=1=|J_{0}|$, according to equality Eq. (5.4b),
it is easy to see that both sides of Eq. (5.5) are equal to $w_{J_{0}}$; If
$|e\cap e^{\prime}|=0$, then $J_{0}=\varnothing$, and combining Eqs. (5.4a)
and (5.4b), both sides of Eq. (5.5) are equal to $1$. Therefore, we can assume
Eq. (5.5) holds without checking if $|e\cap e^{\prime}|>1$.

Take an internal node $e_{0}$ along the path from $e_{1}$ to $e_{2}$, then the
length of the path from $e_{1}$ to $e_{0}$ in $T$ is strictly less than $l$.
By the induction hypothesis, for any $J^{\prime}\in\mathcal{J}^{e_{1}\cap
e_{0}}$, the following equality holds for $w\in\mathrm{MC}^{H}_{T}$:

$\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J^{\prime}}w_{J}=\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq J^{\prime}}w_{J}.$
(5.6)

According to the properties of the join tree, $e_{1}\cap e_{2}\subseteq
e_{0}$, so $e_{1}\cap e_{2}\subseteq e_{1}\cap e_{0}$. Given
$J_{0}\in\mathcal{J}^{e_{1}\cap e_{2}}$, consider the index set of summation
for $J$ on the left side of Eq. (5.5) for $e\leftarrow e_{1}$, that is

$\mathcal{J}^{e_{1}}(J_{0}):=\left\\{J\in\mathcal{J}^{e_{1}}\middle|J\supseteq
J_{0}\right\\}.$ (5.7)

Suppose $J\in\mathcal{J}^{e_{1}}(J_{0})$. Let $J_{1}=J\cap\bigcup_{I\in
e_{1}\cap e_{0}}I$, then $J_{1}\in\mathcal{J}^{e_{1}\cap e_{0}}$. Since
$e_{1}\cap e_{2}\subseteq e_{1}\cap e_{0}$, we have $J_{1}\supseteq J_{0}$.
Moreover, as $J$ ranges over $\mathcal{J}^{e_{1}}(J_{0})$, the corresponding
$J_{1}$ ranges over $\\{J^{\prime}\in\mathcal{J}^{e_{1}\cap
e_{0}}|J^{\prime}\supseteq J_{0}\\}$. Thus elements $J$s of
$\mathcal{J}^{e_{1}}(J_{0})$ can be partitioned according to
$J\cap\bigcup_{I\in e_{1}\cap e_{0}}I$, namely,

$\mathcal{J}^{e_{1}}(J_{0})=\bigsqcup_{J^{\prime}\in\mathcal{J}^{e_{1}\cap
e_{0}}:J^{\prime}\supseteq
J_{0}}\left\\{J\in\mathcal{J}^{e_{1}}(J_{0})\middle|J\cap\bigcup_{I\in
e_{1}\cap e_{0}}I=J^{\prime}\right\\}.$ (5.8)

It is easily seen that the subset of the partition can be simplified as

$\left\\{J\in\mathcal{J}^{e_{1}}(J_{0})\middle|J\cap\bigcup_{I\in e_{1}\cap
e_{0}}I=J^{\prime}\right\\}=\\{J\in\mathcal{J}^{e_{1}}|J\supseteq
J^{\prime}\\}$ (5.9)

for $J^{\prime}\supseteq J_{0}$.

Thus we can partition the summation $\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J_{0}}w_{J}$ according to Eq. (5.8), i.e.,

$\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J_{0}}w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}\cap
e_{0}}:J^{\prime}\supseteq J_{0}}\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J^{\prime}}w_{J}.$ (5.10)

Similarly, partitioning the summation
$\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq J_{0}}w_{J}$ yields

$\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq
J_{0}}w_{J}=\sum_{J^{\prime}\in\mathcal{J}^{e_{1}\cap
e_{0}}:J^{\prime}\supseteq J_{0}}\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq
J^{\prime}}w_{J}.$ (5.11)

The RHS of Eqs. (5.10) and (5.11) are equal by applying Eq. (5.6) to the inner
summation. Therefore,

$\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq J_{0}}w_{J}$ (5.12)

Applying the induction hypothesis for $e_{2}$ and $e_{0}$ and deducing
similarly, we also obtain

$\sum_{J\in\mathcal{J}^{e_{2}}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e_{0}}:J\supseteq J_{0}}w_{J}.$ (5.13)

Combining Eqs. (5.12) and (5.13), it can be seen that Eq. (5.5) holds for
$w\in\mathrm{MC}^{H}_{T}$ with $e\leftarrow e_{1}$, $e^{\prime}\leftarrow
e_{2}$. ∎

Theorem 1.1 actually shows a stronger result: When $H$ is $\alpha$-acyclic,
$\mathrm{MC}^{H}_{T}$ is equal to $\mathrm{MC}^{H}$ and provides an explicit
half-space representation of the latter. We prove it by induction on $|E|$. To
apply the induction hypothesis, we partition $H$ into two subhypergraphs
$H_{1}$, $H_{2}$ according to a leaf node of $T$. Theorem 4.1 allows us to
achieve a half-space representation of $\mathrm{MC}^{H}$ from those of
$\mathrm{MC}^{H_{k}},k=1,2$. And Lemma 5.3 is important for verifying the
resulting representation is consistent with $\mathrm{MC}^{H}_{T}$.

###### Proof of Theorem 1.1.

Without loss of generality, assume that $H$ does not have any isolated
vertices. Otherwise, let $V_{0}$ be the set of all isolated vertices of $H$,
and $H^{\prime}=(V\setminus V_{0},E)$ be the hypergraph obtained by removing
$V_{0}$ from $H$. Then $H^{\prime}$ has the same set of hyperedges as $H$ and
is also $\alpha$-acyclic. Additionally, the join tree of $H$ is also the join
tree of $H^{\prime}$. Since any $I\in V_{0}$ is an isolated vertex, for
$i_{0}\in I$, the $w_{i_{0}}$ component of $w\in\mathscr{S}^{H}$ does not
appear in the production constraints $w_{J}=\prod_{i\in J}w_{i}$ defined in
Eq. (1.5). Furthermore, because the indices of the remaining components are in
$\mathcal{J}^{H^{\prime}}$, we have

$\mathscr{S}^{H}=\left\\{w\in\\{0,1\\}^{\mathcal{J}^{H}}\middle|\operatorname{Proj}_{H^{\prime}}w\in\mathscr{S}^{H^{\prime}};w(I)=1,\
\forall\,I\in V_{0}\right\\}.$ (5.14)

Let $\mathcal{J}_{0}=\bigcup_{I\in V_{0}}I$. Taking the convex hull of both
sides of the above equation yields

$\displaystyle\mathrm{MC}^{H}=\bigg{\\{}w\in\mathbb{R}^{\mathcal{J}^{H}}\bigg{|}$
$\displaystyle\operatorname{Proj}_{H^{\prime}}w\in\mathrm{MC}^{H^{\prime}};$
(5.15a)
$\displaystyle\operatorname{Proj}_{\mathcal{J}_{0}}w\in\operatorname{conv}\left\\{u\in\\{0,1\\}^{\mathcal{J}_{0}}\middle|u(I)=1,\
\forall\,I\in V_{0}\right\\}\bigg{\\}}.$ (5.15b)

It is evident that Eq. (5.15b) is equivalent to

$\operatorname{Proj}_{\mathcal{J}_{0}}w\geqslant 0\ \text{and}\ w(I)=1,\
\forall\,I\in V_{0}.$ (5.16)

These inequalities are already contained in Eq. (5.4a). Thus, if
$\mathrm{MC}^{H^{\prime}}=\mathrm{MC}^{H^{\prime}}_{T}$, then
$\mathrm{MC}^{H}=\mathrm{MC}^{H}_{T}$.

In the rest of the proof, it is assumed that $H$ has no isolated vertices. We
prove the theorem by induction on $|E|$. First, when $H$ contains no
hyperedges, $T$ is an empty graph, and the theorem holds. When $|E|=1$, since
$H$ has no isolated vertices, we have $H=(e,\\{e\\})$. Let
$\Delta^{\mathcal{J}^{e}}$ be the standard simplex defined as

$\Delta^{\mathcal{J}^{e}}:=\left\\{u\in\mathbb{R}^{\mathcal{J}^{e}}_{\geqslant
0}\middle|\sum_{J\in\mathcal{J}^{e}}u_{J}=1\right\\},$ (5.17)

all vertices of which are $0$-$1$ vectors. Now we define the linear map
$\mathcal{T}:u\mapsto w$ as follows:

$\displaystyle w_{J}$ $\displaystyle=u_{J},\quad$ $\displaystyle\forall\,J$
$\displaystyle\in\mathcal{J}^{e},$ (5.18a) $\displaystyle w_{i}$
$\displaystyle=u_{i},\ $ $\displaystyle\forall\,i$ $\displaystyle\in I,I\in
e.$ (5.18b)

Consider the polytope $P^{H}=\mathcal{T}(\Delta^{\mathcal{J}^{e}})$ obtained
by mapping $\Delta^{\mathcal{J}^{e}}$ via $\mathcal{T}$. It is easy to see
that its half-space representation is given by

$P^{H}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}w_{i}=\sum_{J\in\mathcal{J}^{e}:J\ni i}w_{J},\
\forall\,I\in e,i\in I;\sum_{J\in\mathcal{J}^{e}}w_{J}=1\bigg{\\}}.$ (5.19)

Moreover, the vertex set of $P^{H}$ is obtained by mapping the vertex set of
$\Delta^{\mathcal{J}^{e}}$ via $\mathcal{T}$. It is easy to verify that the
vertex set of $P^{H}$ is exactly $\mathscr{S}^{H}$, hence
$P^{H}=\mathrm{MC}^{H}$. Note that in this case, the join tree of $H$ consists
of a single node and no edges, so Eq. (5.4c) does not exist. It is easy to
verify that Eqs. (5.19) and (5.4) are equivalent half-space representations:
$\mathrm{MC}^{H}=P^{H}=\mathrm{MC}^{H}_{T}$, and the theorem holds for
$|E|=1$.

Now suppose $|E|>1$. Let $H$ be a $\alpha$-acyclic hypergraph, and
$T=(E,\mathcal{E})$ be a join tree of $H$. Let $e_{1}$ be a leaf node of $T$,
and $e_{2}$ be the unique neighbor of $e_{1}$ in $T$. Then the path from
$e_{1}$ to any node $e$ other than $e_{1}$ in $T$ contains $e_{2}$. By the
definition of a join tree, $e\cap e_{1}\subseteq e_{2}$, implying $e\cap
e_{1}\subseteq e_{1}\cap e_{2}$. Let $V_{2}=\bigcup_{e\in E-e_{1}}e$, then

$e_{1}\cap V_{2}=\bigcup_{e\in E-e_{1}}e_{1}\cap e\subseteq e_{1}\cap e_{2}.$
(5.20)

On the other hand, since $e_{2}\subseteq V_{2}$, we have $e_{1}\cap
e_{2}\subseteq e_{1}\cap V_{2}$, hence

$e_{1}\cap V_{2}=e_{1}\cap e_{2}.$ (5.21)

Let $V_{1}=e_{1}$, $p=e_{1}\cap e_{2}$. From Eq. (5.21), we have $p=V_{1}\cap
V_{2}$. Since $H$ has no isolated vertices, we have

$V_{1}\cup V_{2}=\bigcup_{e\in E}e=V.$

Let $H_{1}=(V_{1},\\{e_{1}\\})$ and $H_{2}=(V_{2},E-e_{1})$, both of which are
subhypergraphs of $H$, satisfying that $V_{1}\cup V_{2}=V$, hence $H=H_{1}\cup
H_{2}$. Since $H_{1}$ has only one hyperedge, it is $\alpha$-acyclic, and its
join tree is $T_{1}=(\\{e_{1}\\},\varnothing)$. Removing the node $e_{1}$ from
$T$ yields the tree $T_{2}:=(E-e_{1},\mathcal{E}-e_{1}e_{2})$, which is the
join tree of $H_{2}=(V_{2},E-e_{1})$, so $H_{2}$ is also $\alpha$-acyclic. By
the induction hypothesis applied to $H_{1}$ and $H_{2}$, we have
$\mathrm{MC}^{H_{k}}=\mathrm{MC}^{H_{k}}_{T_{k}}$ for $k=1,2$, namely,

$\displaystyle\mathrm{MC}^{H_{1}}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H_{1}}}\bigg{|}$ $\displaystyle w(I)=1,\ \forall\,I\in
V_{1};$ (5.22a) $\displaystyle w_{i}=\sum_{J\in\mathcal{J}^{e_{1}}:J\ni
i}w_{J},\ \forall\,I\in V_{1},i\in I\bigg{\\}},$ (5.22b)

and

$\displaystyle\mathrm{MC}^{H_{2}}=\bigg{\\{}$ $\displaystyle
w\in\mathbb{R}_{\geqslant 0}^{\mathcal{J}^{H_{2}}}\bigg{|}$ $\displaystyle
w(I)=1,\ \forall\,I\in V_{2};$ (5.23a) $\displaystyle
w_{i}=\sum_{J\in\mathcal{J}^{e}:J\ni i}w_{J},\ \forall\,e\in E-e_{1},i\in I\in
e;$ (5.23b) $\displaystyle\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J},\
\forall\,ee^{\prime}\in\mathcal{E}-e_{1}e_{2},|e\cap
e^{\prime}|>1,J_{0}\in\mathcal{J}^{e\cap e^{\prime}}\bigg{\\}}.$ (5.23c)

If we can apply Theorem 4.1 to $H=H_{1}\cup H_{2}$, then we have
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$.
However, the condition of the theorem, $p\in(L(V_{1})\cup
E(H_{1}))\cap(L(V_{2})\cup E(H_{2}))$, may not hold generally. Therefore, we
consider several cases.

1\. $|p|\leqslant 1$.

Now either $|p|=1$ or $|p|=0$ holds. In the first case, $p=L(V_{1})\cap
L(V_{2})$, so the condition $p\in(L(V_{1})\cup E(H_{1}))\cap(L(V_{2})\cup
E(H_{2}))$ holds, and we have
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$.
In the latter case, $p=\varnothing$, and by Example 4.1, we also have
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}}$.
Combining the equalities from Eqs. (5.22) and (5.23) gives the half-space
representation of $\mathrm{MC}^{H}$, which can be easily verified to be
identical to Eq. (5.4). Thus, $\mathrm{MC}^{H}=\mathrm{MC}^{H}_{T}$, and the
theorem holds.

2\. $|p|>1$.

We consider when $p\notin E$ or $p\in E$ seperately. The latter case is
further divided into $p\in E-e_{1}$ and $p=e_{1}$. Thus there are three cases
under investigation.

(1) $p\notin E$.  In this case, let $H_{1}^{\prime}=(V_{1},\\{e_{1},p\\})$,
$H_{2}^{\prime}=(V_{2},(E-e_{1})\cup\\{p\\})$, and
$H^{\prime}=(V,E\cup\\{p\\})$. Then $H^{\prime}=H_{1}^{\prime}\cup
H_{2}^{\prime}$ satisfies the conditions of Theorem 4.1. Therefore,
$\mathrm{MC}^{H^{\prime}}=\overline{\mathrm{MC}}^{H_{1}^{\prime}}\cap\overline{\mathrm{MC}}^{H_{2}^{\prime}}$.

Note that $p\subset e_{1}$. By Proposition 2.3, the half-space representation
of $\mathrm{MC}^{H_{1}^{\prime}}$ can be obtained by adding equalities to
$\mathrm{MC}^{H_{1}}$, namely

$\displaystyle\mathrm{MC}^{H_{1}^{\prime}}=\bigg{\\{}w\in\mathbb{R}^{\mathcal{J}^{H_{1}^{\prime}}}_{\geqslant
0}\bigg{|}$ $\displaystyle w(I)=1,\ \forall\,I\in V_{1};$ (5.24a)
$\displaystyle w_{i}=\sum_{J\in\mathcal{J}^{e_{1}}:J\ni i}w_{J},\
\forall\,I\in V_{1},i\in I;$ (5.24b) $\displaystyle
w_{J_{0}}=\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq J_{0}}w_{J},\
\forall\,J_{0}\in\mathcal{J}^{p}\bigg{\\}}.$ (5.24c)

Similarly, since $p\subset e_{2}\in E-e_{1}$, the half-space representation of
$\mathrm{MC}^{H_{2}^{\prime}}$ can also be obtained by adding equalities to
$\mathrm{MC}^{H_{2}}$, resulting in

$\mathrm{MC}^{H_{2}^{\prime}}=\left\\{w\in\mathbb{R}^{\mathcal{J}^{H_{2}^{\prime}}}\middle|\operatorname{Proj}_{H_{2}}w\in\mathrm{MC}^{H_{2}};w_{J_{0}}=\sum_{J\in\mathcal{J}^{e_{2}}:J\supseteq
J_{0}}w_{J},\ \forall\,J_{0}\in\mathcal{J}^{p}\right\\}.$ (5.25)

Since $\mathrm{MC}^{H^{\prime}}$ is decomposable into
$\mathrm{MC}^{H_{1}^{\prime}}$ and $\mathrm{MC}^{H_{2}^{\prime}}$, the half-
space representation of $\mathrm{MC}^{H^{\prime}}$ can be defined by the union
of inequalities in Eqs. (5.24) and (5.25). Combining Eq. (5.23), we obtain

$\displaystyle\mathrm{MC}^{H^{\prime}}=\bigg{\\{}$ $\displaystyle
w\in\mathbb{R}_{\geqslant 0}^{\mathcal{J}^{H^{\prime}}}\bigg{|}$
$\displaystyle w(I)=1,\ \forall\,I\in V;$ (5.26a) $\displaystyle
w_{i}=\sum_{J\in\mathcal{J}^{e}:J\ni e}w_{J},\ \forall\,e\in E,i\in I\in e;$
(5.26b) $\displaystyle\sum_{J\in\mathcal{J}^{e}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e^{\prime}}:J\supseteq J_{0}}w_{J},\
\forall\,ee^{\prime}\in\mathcal{E}-e_{1}e_{2},|e\cap
e^{\prime}|>1,J_{0}\in\mathcal{J}^{e\cap e^{\prime}};$ (5.26c) $\displaystyle
w_{J_{0}}=\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e_{2}}:J\supseteq J_{0}}w_{J},\
\forall\,J_{0}\in\mathcal{J}^{p}\bigg{\\}}.$ (5.26d)

By Proposition 2.2,
$\mathrm{MC}^{H}=\operatorname{Proj}_{H}\mathrm{MC}^{H^{\prime}}$. Hence the
half-space representation of $\mathrm{MC}^{H}$ can be obtained by applying
Fourier-Motzkin elimination to Eq. (5.26) and eliminating the components in
$\mathcal{J}^{H^{\prime}}\setminus\mathcal{J}^{H}=\mathcal{J}^{p}$. As these
components do not appear in Eqs. (5.26a)–(5.26c), it is easily seen that

$\displaystyle\mathrm{MC}^{H}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}$ $\displaystyle w\ \text{satisfies
Eqs.~{}\eqref{eq:cons_multiple_choice}--\eqref{eq:cons_T_neibr}};$ (5.27a)
$\displaystyle\sum_{J\in\mathcal{J}^{e_{1}}:J\supseteq
J_{0}}w_{J}=\sum_{J\in\mathcal{J}^{e_{2}}:J\supseteq J_{0}}w_{J},\
\forall\,J_{0}\in\mathcal{J}^{p}\bigg{\\}}.$ (5.27b)

Clearly, Eq. (5.27b) is the same as the specific equality in Eq. (5.4c) where
$e\leftarrow e_{1}$ and $e^{\prime}\leftarrow e_{2}$, so
$\mathrm{MC}^{H}=\mathrm{MC}^{H}_{T}$.

(2) $p\in E-e_{1}$. In this case, $p$ is a hyperedge of $H$. Let
$H_{1}^{\prime}=(V_{1},\\{e_{1},p\\})$, then $H=H_{1}^{\prime}\cup H_{2}$
satisfies the conditions of Theorem 4.1, so
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}^{\prime}}\cap\overline{\mathrm{MC}}^{H_{2}}$.
Combining Eqs. (5.24) and (5.23), we obtain

$\mathrm{MC}^{H}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}w\ \text{satisfies
Eqs.~{}\eqref{eq:cons_multiple_choice}--\eqref{eq:cons_T_neibr} and
\eqref{eq:cons_H_1_prime_e_1}}\bigg{\\}};\\\ $ (5.28)

Note that equalities of Eqs. (5.26a)–(5.26c) are all contained in Eq. (5.3),
while Eq. (5.24c) is the special case of Eq. (5.3c) where $e\leftarrow p$,
$e^{\prime}\leftarrow e_{1}$. Thus equalities of $\mathrm{MC}^{H}$ are
contained in those of $\mathrm{MC}^{H}_{\cap}$, implying
$\mathrm{MC}^{H}\supseteq\mathrm{MC}^{H}_{\cap}$. However,
$\mathrm{MC}^{H}_{\cap}$ is actually a relaxation of $\mathrm{MC}^{H}$.
Combining Lemma 5.3, we have
$\mathrm{MC}^{H}=\mathrm{MC}^{H}_{\cap}=\mathrm{MC}^{H}_{T}$.

(3) $p=e_{1}$. In this case, $p$ is also a hyperedge of $H$. Let
$H_{2}^{\prime}=(V_{2},(E-e_{1})\cup\\{p\\})$, then $H=H_{1}\cup
H_{2}^{\prime}$ satisfies the conditions of Theorem 4.1, so
$\mathrm{MC}^{H}=\overline{\mathrm{MC}}^{H_{1}}\cap\overline{\mathrm{MC}}^{H_{2}^{\prime}}$.
Combining Eqs. (5.22) and (5.25), we obtain

$\displaystyle\mathrm{MC}^{H}=\bigg{\\{}w\in\mathbb{R}_{\geqslant
0}^{\mathcal{J}^{H}}\bigg{|}$ $\displaystyle w\ \text{satisfies
Eqs.~{}\eqref{eq:cons_multiple_choice}--\eqref{eq:cons_T_neibr}};$ (5.29a)
$\displaystyle w_{J_{0}}=\sum_{J\in\mathcal{J}^{e_{2}}:J\supseteq
J_{0}}w_{J},\ \forall\,J_{0}\in\mathcal{J}^{p}\bigg{\\}}.$ (5.29b)

Similar to case (2), it also holds that $\mathrm{MC}^{H}=\mathrm{MC}^{H}_{T}$.

∎

Since Problem (1.4) is equivalent to $\max_{w\in\mathrm{MC}^{H}}a\cdot w$ and
linear programming admits polynomial-time algorithms [18], Theorem 1.1 allows
us to estimate the complexity of MCPP when $H$ is $\alpha$-acyclic. We only
need to estimate the dimension of $w$ and the number of inequalities and
equalities in the half-space representation of $\mathrm{MC}^{H}$.

We define the _rank_ of hypergraph $H$, denoted by $r$, as the maximum
cardinality of its hyperedges, and let

$M=\max_{e\in E}|\mathcal{J}^{e}|,\ \ \text{and}\ \
M_{\cap}=\max_{e,e^{\prime}\in E:e\cap
e^{\prime}\neq\varnothing}|\mathcal{J}^{e\cap e^{\prime}}|.$

With $\hat{d}=\max_{I\in V}|I|$, we can bound $M$ and $M_{\cap}$ as
$M_{\cap}\leqslant M\leqslant\hat{d}^{r}$. It is easy to see that the
dimension of $w$, $|\mathcal{J}^{H}|$, does not exceed $M(|V|+|E|)$. Noting
that $|\mathcal{E}|=|E|-1$, it is readily seen that the number of equalities
in the half-space representation of $\mathrm{MC}^{H}$ (1.6) does not exceed
$|V|+|E|r\hat{d}+|E|M_{\cap}$, and the number of inequalities is
$|\mathcal{J}^{H}|$. Thus, the number of inequalities and equalities is
$\mathcal{O}(|V|+|E|)$ providing a constant upper bound on $r$ and $\hat{d}$.
Combining the fact that the number of nonzero coefficients of original form
(1.1) is at least $(|V|+|E|)$, MCPP is solvable in polynomial time.

######  Remark 2.

Note that MCPP (1.1) is generalization of PBO (1.7) by letting $|I|=2,I\in V$.
Therefore, PBO (1.7) is also polynomial solvable when $H$ is $\alpha$-acyclic
and its rank is bounded ($\hat{d}=2$ in this case). We should mention that
this observation does not contradict the NP-hardness of PBO (1.7) (also when
$H$ is $\alpha$-acyclic) as shown in [10]. Since in that work, the PBO
instance reduced from MAX-CUT is associated with a hypergraph $H$ with rank
equal to $|V|$, thus unbounded.

##  6 Proof of Theorem 1.2

In order to prove Theorem 1.2, we need a lemma on $\mathrm{MP}^{H}$. Let
$F\subseteq\mathrm{MP}^{H}$ be a facet of $\mathrm{MP}^{H}$ and $U\subseteq
V$, and define

$\displaystyle V_{1}^{F}$ $\displaystyle=\\{I\in
V|\forall\,z\in\mathrm{MP}^{H},z_{I}=1\ \text{implies}\ z\in F\\},$ (6.1)
$\displaystyle E_{U}$ $\displaystyle=\\{e\in L(V)\cup
E\cup\\{\varnothing\\}|e\subseteq V\setminus U,e\cup U\in L(V)\cup E\\}.$
(6.2)

######  Lemma 6.1.

If hypergraph $H$ is downward-closed and $U\subseteq V\setminus V_{1}^{F}$ is
nonempty, then either $E_{U}$ is empty, or the projection of the face
$F_{U}:=\\{z\in F|z_{I}=0,\forall\,I\in U\\}$ onto
$\mathbb{R}^{E_{U}\setminus\\{\varnothing\\}}$, i.e.,
$\operatorname{Proj}_{E_{U}\setminus\\{\varnothing\\}}F_{U}$ is full-
dimensional.

###### Proof.

Suppose $E_{U}$ is nonempty and the
$\operatorname{Proj}_{E_{U}\setminus\\{\varnothing\\}}F_{U}$ is not full-
dimensional. It can be easily seen from the downward-closedness of $E$ that
$\varnothing\in E_{U}$.

Since $\operatorname{Proj}_{E_{U}-\varnothing}F_{U}$ is not full-dimensional,
there exists a nonzero vector $\hat{c}\in\mathbb{R}^{E_{U}-\varnothing}$ and
$\delta^{\prime}\in\mathbb{R}$ such that

$\hat{c}\cdot\operatorname{Proj}_{E_{U}-\varnothing}z=\delta^{\prime}$

for all $z\in F_{U}$. Padding $\hat{c}$ with zeros, we obtain
$c^{\prime}\in\mathbb{R}^{L(V)\cup E}$. Then we have for any $z\in F_{U}$,

$c^{\prime}\cdot
z=\hat{c}\cdot\operatorname{Proj}_{E_{U}-\varnothing}z=\delta^{\prime}.$ (6.3)

We claim that the equality on $\mathbb{R}^{L(V)\cup E}$

$c\cdot z-\delta:=\mathscr{L}(c^{\prime}\cdot z-\delta^{\prime})\prod_{I\in
U}(1-z_{I})=0$ (6.4)

holds for all $z\in F$. First, to verify this is indeed a equality on
$\mathbb{R}^{L(V)\cup E}$, it suffices to consider the linearization operator
only needs $z_{e}$ components for $e\in L(V)\cup E$. For convenience, let
$c^{\prime}_{\varnothing}=-\delta^{\prime}$. For any $e$ such that
$c^{\prime}_{e}\neq 0$, since $c^{\prime}$ is achieved by padding $\hat{c}$
with zeros, we have $e\in E_{U}$ (note that $e$ may be $\varnothing$, but
$\varnothing$ also belongs to $E_{U}$). Expanding $\prod_{I\in U}(1-z_{I})$
yields monomials of the form $\prod_{I\in e^{\prime}}z_{I}$, where
$e^{\prime}\subseteq U$. Therefore, the linearization operator $\mathscr{L}$
requires components $z_{e\cup e^{\prime}}$, where $e\in E_{U}$ and
$e^{\prime}\subseteq U$, with $z_{\varnothing}=1$. It follows from the
definition of $E_{U}$ that

$e\cup e^{\prime}\subseteq e\cup U\in L(V)\cup E.$

Combining the downward-closedness of $H$, we arrive at

$e\cup e^{\prime}\in L(V)\cup E\cup\\{\varnothing\\}.$

Therefore, Eq. (6.4) is indeed a equality on $\mathbb{R}^{L(V)\cup E}$.

Now it suffices to verify that

$(c^{\prime}\cdot z-\delta^{\prime})\prod_{I\in U}(1-z_{I})=0$ (6.5)

holds for all vertices $z$ of $F$. Let us suppose $z\in\mathcal{S}^{H}\cap F$.
(i) If there exists $I_{1}\in U$ such that $z_{I_{1}}=1$, then
$1-z_{I_{1}}=0$, and the conclusion holds. (ii) If $z_{I}=0$ for all $I\in U$,
then $z\in F_{U}$. By the assumption of $F_{U}$, we have $c^{\prime}\cdot
z-\delta^{\prime}=0$, which means that Eq. (6.5) also holds.

The above dedution shows that $F\subseteq\\{z\in\mathrm{MP}^{H}|c\cdot
z=\delta\\}$. Since $\mathrm{MP}^{H}$ is full-dimensional with $F$ being its
facet, we have $F=\\{z\in\mathrm{MP}^{H}|c\cdot z=\delta\\}$. However, from
the definition of (6.4), for any $I\in U$ and $z\in\mathrm{MP}^{H}$, as long
as $z_{I}=1$, we have $c\cdot z=\delta$, implying $z\in F$, and thus
$U\subseteq V_{1}^{F}$, a contradiction. ∎

Theorem 1.2 shows that Condition (1.12) is necessary and sufficient for Eq.
(1.9) to be facet-inducing. When the condition does not hold for $\bm{S}$, we
construct $\bm{S}^{\prime}$ and $\bm{S}^{\prime\prime}$ such that

$a(\bm{S})\cdot w-\delta=(a(\bm{S}^{\prime})\cdot
w-\delta)+(a(\bm{S}^{\prime\prime})\cdot w-\delta).$

Then $a(\bm{S})\cdot w\leqslant\delta$ is sum of two valid inequalities and
thus not facet-inducing. This is the basic idea for proving the necessity. As
for the sufficiency, we prove it in the context of
$\mathrm{MC}^{H}_{\leqslant}$ which is guaranteed by Corollary 3.3. Suppose
Condition (1.12) holds and the face induced by

$\operatorname{Proj}_{\leqslant}a(\bm{S})\cdot v\leqslant\delta$ (6.6)

is contained in the facet induced by

$a^{\prime}\cdot v\leqslant\delta^{\prime}.$ (6.7)

We construct several classes of vertices of $\mathrm{MC}^{H}_{\leqslant}$ such
that equality of Eq. (6.6) holds for them. By the inclusion relationship, we
can obtain properties of $a^{\prime}$ and $\delta^{\prime}$. With the help of
Lemma 6.1, we are able to verify that Eq. (6.7) is a scalar multiplication of
Eq. (1.9), and hence they induce the same facet.

###### Proof of Theorem 1.2.

For convenience, let $c_{\varnothing}=-\delta$. Define the support of $c$ as

$\operatorname{supp}c:=\\{e\in L(V)\cup E\cup\\{\varnothing\\}|c_{e}\neq
0\\}.$ (6.8)

It is clear that when $I\in\bigcap_{e\in\operatorname{supp}c}e$, if
$z\in\mathrm{MP}^{H}$ satisfies $z_{I}=0$, then $z_{e}=0$ for all
$e\in\operatorname{supp}c$ (note that $z_{e}\leqslant z_{I}$ is valid for
$\mathrm{MP}^{H}$), thus

$\sum_{e\in L(V)\cup
E\cup\\{\varnothing\\}}c_{e}z_{e}=\sum_{e\in\operatorname{supp}c}c_{e}z_{e}=0.$
(6.9)

Hence $\bigcap_{e\in\operatorname{supp}c}e\subseteq V_{0}$.

Similarly, if $I^{\prime}\notin\bigcap_{e\in\operatorname{supp}c}e$, then
there exists $e_{0}\in\operatorname{supp}c$ such that $I^{\prime}\notin
e_{0}$. We take $e_{0}$ to be the inclusionwise minimal set one. Now we define
$\hat{z}\in\mathcal{S}^{H}$ as follows. For all $I\in e_{0}$, let
$\hat{z}_{I}=1$, and for the rest $I$s we let $\hat{z}_{I}=0$. For each $e\in
E$, let $\hat{z}_{e}=\prod_{I\in e}\hat{z}_{I}$ to assure
$\hat{z}\in\mathcal{S}^{H}$. Now that $\hat{z}$ satisfies
$\hat{z}_{I^{\prime}}=0$, and

$\sum_{e\in L(V)\cup
E\cup\\{\varnothing\\}}c_{e}\hat{z}_{e}=\sum_{e\in\operatorname{supp}c:e\subseteq
e_{0}}c_{e}\hat{z}_{e}=c_{e_{0}}\neq 0,$ (6.10)

which implies $\bigcap_{e\in\operatorname{supp}c}e\supseteq V_{0}$. Combining
$\bigcap_{e\in\operatorname{supp}c}e\subseteq V_{0}$, we have
$\bigcap_{e\in\operatorname{supp}c}e=V_{0}$.

Let $\mathcal{P}^{0}$ denote the family of all non-empty proper subsets. We
define

$a:\bigtimes_{I\in
V}\mathcal{P}^{0}(I)\rightarrow\mathbb{R}^{\mathcal{J}^{H}}$ (6.11)

to represent the coefficients of $w$ on the LHS of Eq. (1.9) with argument
being $(S_{I})_{I\in V}$, i.e.,

$a(\bm{S})\cdot w=\sum_{e\in L(V)\cup E}c_{e}\mathscr{L}\prod_{I\in
e}\sum_{i\in S_{I}}w_{i},$ (6.12)

with $\bm{S}=(S_{I})_{I\in V}\in\bigtimes_{I\in V}\mathcal{P}^{0}(I)$. To be
convenient, let $a_{\varnothing}(\bm{S})=-\delta$ (although we do not regard
it as a component of $a(\bm{S})$). It is clear that for $J\in\mathcal{J}^{H}$
such that $J\subseteq\bigcup_{I\in V}S_{I}$, $a_{J}(\bm{S})=c_{E(J)}$, and for
other $J\in\mathcal{J}^{H}$, $a_{J}(\bm{S})=0$. Note that when $c_{E(J)}$, for
all $J\in\mathcal{J}^{H}$, we have $a_{J}(\bm{S})=0$. We write $\bigcup
S_{I}:=\bigcup_{I\in V}S_{I}$ in short.

Necessity. We show necessity by proving that if there exists $I^{\prime}\in
V_{0}$ such that $|S_{I^{\prime}}|>1$, or $I^{\prime\prime}\in V_{1}$ such
that $|S_{I^{\prime\prime}}|<|I^{\prime\prime}|-1$, then $a(\bm{S})\cdot
w\leqslant\delta$ is not facet-inducing for $\mathrm{MC}^{H}$. We distinguish
two cases.

Case 1: there exists $I^{\prime}\in V_{0}$ such that $|S_{I^{\prime}}|>1$. Let
$S_{I^{\prime}}=S^{\prime}_{I^{\prime}}\sqcup S^{\prime\prime}_{I^{\prime}}$
be a disjoint union, where $S^{\prime}_{I^{\prime}}$ and
$S^{\prime\prime}_{I^{\prime}}$ are nonempty. Then define

$S^{\prime}_{I}=\begin{cases}S_{I},&I\neq I^{\prime}\\\
S^{\prime}_{I^{\prime}},&I=I^{\prime}\end{cases},\ \text{and}\
S^{\prime\prime}_{I}=\begin{cases}S_{I},&I\neq I^{\prime}\\\
S^{\prime\prime}_{I^{\prime}},&I=I^{\prime}\end{cases}.$ (6.13)

We claim that

$a(\bm{S})=a(\bm{S}^{\prime})+a(\bm{S}^{\prime\prime}).$ (6.14)

To prove the assertion, we verify the equality for its all components
$J\in\mathcal{J}^{H}$. (i) If $a_{J}(\bm{S})\neq 0$, then $J\subseteq\bigcup
S_{I}$ and $E(J)\in\operatorname{supp}c$. Since $I^{\prime}\in V_{0}\subseteq
e$, $J\cap I^{\prime}$ is a singleton. Let $J\cap I^{\prime}=\\{i_{0}\\}$,
then we have $i_{0}\in S_{I^{\prime}}$. Noting that
$S_{I^{\prime}}=S^{\prime}_{I^{\prime}}\sqcup S^{\prime\prime}_{I^{\prime}}$
is a disjoint union, either $i_{0}\in S^{\prime}_{I^{\prime}}$ or $i_{0}\in
S^{\prime\prime}_{I^{\prime}}$ holds. When $i_{0}\in S^{\prime}_{I^{\prime}}$,
we have $J\subseteq\bigcup S^{\prime}_{I}$ and $J\nsubseteq\bigcup
S^{\prime\prime}_{I}$, thus $a_{J}(\bm{S}^{\prime})=c_{e}$ and
$a_{J}(\bm{S}^{\prime\prime})=0$; similarly when $i_{0}\in
S^{\prime\prime}_{I^{\prime}}$, we have $a_{J}(\bm{S}^{\prime})=0$ and
$a_{J}(\bm{S}^{\prime\prime})=c_{e}$. In both cases,
$a_{J}(\bm{S})=a_{J}(\bm{S}^{\prime})+a_{J}(\bm{S}^{\prime\prime})$. (ii) If
$a_{J}(\bm{S})=0$, then at least one of $J\nsubseteq\bigcup S_{I}$ and
$c_{E(J)}=0$ holds, it is easy to verify that
$a_{J}(\bm{S}^{\prime})=a_{J}(\bm{S}^{\prime\prime})=0$, thus
$a_{J}(\bm{S})=a_{J}(\bm{S}^{\prime})+a_{J}(\bm{S}^{\prime\prime})$.
Therefore, the assertion holds.

Since $V_{0}=\bigcap_{e\in\operatorname{supp}c}e$ is nonempty, we have
$\varnothing\notin\operatorname{supp}c$, implying $\delta=-a_{\varnothing}=0$.
Thus

$a(\bm{S})\cdot w-\delta=(a(\bm{S}^{\prime})\cdot
w-\delta)+(a(\bm{S}^{\prime\prime})\cdot w-\delta).$ (6.15)

By the definition of $a(\cdot)$, $a(\bm{S}^{\prime})\cdot w\leqslant\delta$ is
the lifted inequality of $c\cdot z\leqslant\delta$ w.r.t. $\bm{S}^{\prime}$,
thus also valid and not an implicit equality. The same property also holds for
$a(\bm{S}^{\prime\prime})\cdot w\leqslant\delta$. Moreover, considering the
nonzero components of $a(\bm{S})$ and $a(\bm{S}^{\prime})$, it can be easily
verified that $a(\bm{S})\cdot w\leqslant\delta$ is not a scalar multiplication
of $a(\bm{S}^{\prime})\cdot w\leqslant\delta$. Therefore, as the sum of two
valid inequalities, $a(\bm{S})\cdot w\leqslant\delta$ is not facet-inducing.

Case 2: there exists $I^{\prime\prime}\in V_{1}$ such that
$|S_{I^{\prime\prime}}|<|I^{\prime\prime}|-1$. Define $\bm{S}^{\prime}$ by
$S_{I^{\prime\prime}}^{\prime}=I^{\prime\prime}\setminus S_{I^{\prime\prime}}$
and $S_{I}^{\prime}=S_{I},I\neq I^{\prime\prime}$. Thus,
$|S_{I^{\prime\prime}}^{\prime}|>1$. Since for all $w\in\mathrm{MC}^{H}$, $w$
satisfies the multiple choice constraints

$\sum_{i\in S_{I^{\prime\prime}}}w_{i}+\sum_{i\in
S_{I^{\prime\prime}}^{\prime}}w_{i}=1,$

we can replace $\sum_{i\in S_{I^{\prime\prime}}}w_{i}$ with $1-\sum_{i\in
S_{I^{\prime\prime}}^{\prime}}w_{i}$, then

$\displaystyle\sum_{e\in L(V)\cup E}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}}w_{i}-\delta$ (6.16a) $\displaystyle=$ $\displaystyle-\delta+\sum_{e\in
L(V)\cup E:I^{\prime\prime}\notin e}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}^{\prime}}w_{i}+$ (6.16b) $\displaystyle\sum_{e\in L(V)\cup
E:I^{\prime\prime}\in e}c_{e}\mathscr{L}\left(1-\sum_{i\in
S_{I^{\prime\prime}}^{\prime}}w_{i}\right)\prod_{I\in
e-I^{\prime\prime}}\sum_{i\in S_{I}^{\prime}}w_{i}.$ (6.16c)

The possibility of linearization operator of the part Eq. (6.16c) being
performed within the indices in $\mathcal{J}^{H}$ is guaranteed by the
downward-closedness of $H$.

Similar to the $\psi_{U}$ defined in Eqs. (3) and (4) of [11] in the case of
$|U|=1$, we define the affine mapping $\psi^{I}:\mathbb{R}^{L(V)\cup
E}\rightarrow\mathbb{R}^{L(V)\cup E}$ for each $I\in V$ flipping the $I$th
entry as follows:

$\displaystyle\psi^{I}_{e}(z)$
$\displaystyle=\mathscr{L}(1-z_{I})\prod_{\bar{I}\in e-I}z_{\bar{I}},\ I\in
e;$ (6.17a) $\displaystyle\psi^{I}_{e}(z)$ $\displaystyle=z_{e},\ I\notin e,$
(6.17b)

where $e\in L(V)\cup E$. It is clear that $\psi^{I}$ is a bijection on
$\mathcal{S}^{H}$. Now let

$c^{\prime}\cdot z-\delta^{\prime}=c\cdot\psi^{I^{\prime\prime}}(z)-\delta.$
(6.18)

Then $c^{\prime}\cdot z\leqslant\delta^{\prime}$ is also facet-inducing.
Expressing Eq. (6.18) more explicitly, we have

$\displaystyle c^{\prime}\cdot z-\delta^{\prime}=\sum_{e\in L(V)\cup
E:I^{\prime\prime}\notin e}c_{e}z_{e}+\sum_{e\in L(V)\cup
E:I^{\prime\prime}\in e}c_{e}\mathscr{L}(1-z_{I^{\prime\prime}})\prod_{I\in
e-I^{\prime\prime}}z_{I}-\delta.$ (6.19a)

Lifting the RHS of the above equation w.r.t. $\bm{S}^{\prime}$ yields exactly
the RHS of Eq. (6.16), so does the LHS, i.e.,

$\sum_{e\in L(V)\cup E}c^{\prime}_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}^{\prime}}w_{i}-\delta^{\prime}=\sum_{e\in L(V)\cup
E}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in S_{I}}w_{i}-\delta.$ (6.20)

From the definition of $V_{1}$ in Eq. (1.11), it follows that for any
$z\in\mathrm{MP}^{H}$, if $z_{I^{\prime\prime}}=0$, then
$\psi^{I^{\prime\prime}}_{I^{\prime\prime}}(z)=1$, hence $c^{\prime}\cdot
z-\delta^{\prime}=c\cdot\psi^{I^{\prime\prime}}(z)-\delta=0$. Therefore,
$I^{\prime\prime}$ belongs to

$V_{0}^{\prime}:=\\{I\in V|\forall\,z\in\mathrm{MP}^{H},z_{I}=0,\
\text{implies}\ c^{\prime}\cdot z=\delta^{\prime}\\}.$ (6.21)

It is clear that $V_{0}^{\prime}$ w.r.t. $c^{\prime}\cdot
z\leqslant\delta^{\prime}$ corresponds to $V_{0}$ in Eq. (1.10) w.r.t. $c\cdot
z\leqslant\delta$. Combining $|S_{I^{\prime\prime}}^{\prime}|>1$ and the
argument in Case 1, we conclude that

$\sum_{e\in L(V)\cup E}c^{\prime}_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}^{\prime}}w_{i}\leqslant\delta^{\prime}$

is not facet-inducing, so $a(\bm{S})\cdot w\leqslant\delta$ is not facet-
inducing either.

Sufficiency.  Suppose that the given $\bm{S}$ satisfies Condition (1.12). In
this part of the proof, we do not consider other $a(\bm{S})$, so we simply
write $a$ for $a(\bm{S})$.

Considering the flipping technique described earlier, we can sequentially flip
the components in $V_{0}$ of $z$. For each step, suppose we flip the entry
$I^{\prime}$, then we replace $c\cdot z\leqslant\delta$ with
$c\cdot\psi^{I^{\prime}}(z)\leqslant\delta$, and replace $S_{I^{\prime}}$ with
$I^{\prime}\setminus S_{I^{\prime}}$ correspondingly. By the observations
regarding $V_{0}$ and $V_{0}^{\prime}$ we made before, $V_{0}$ and $V_{1}$
will change to $V_{0}-I^{\prime}$ and $V_{1}\cup\\{I^{\prime}\\}$
respectively. Therefore, after all the flipping, we will arrive at
$V_{0}=\varnothing$. Consequently, we may assume that $V_{0}=\varnothing$
without loss of generality.

For each $I\in V$, let $\bar{i}_{I}\in I\setminus S_{I}$ be arbitrarily chosen
index, and define $D=\\{\bar{i}_{I}\\}_{I\in V}$. Then for all
$J\in\mathcal{J}^{H}$, $a_{J}\neq 0$ implies
$J\in\mathcal{J}^{H}_{\leqslant}$. We will show that

$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}{a}\cdot v\leqslant\delta$
(6.22)

is facet-inducing for $\mathrm{MC}_{\leqslant}^{H}$ in Eq. (3.2). By Corollary
3.3, $a\cdot w\leqslant\delta$ is also facet-inducing for $\mathrm{MC}^{H}$.

Let $F$ be the face induced by (6.22), which contained in the facet
$F^{\prime}$ induced by $a^{\prime}\cdot v\leqslant\delta^{\prime}$, where
$a^{\prime},v\in\mathbb{R}^{\mathcal{J}^{H}_{\leqslant}}$. We set
$a^{\prime}_{\varnothing}=-\delta^{\prime}$. To establish the sufficiency, we
only need to demonstrate that $F$ is identical to $F^{\prime}$, and the main
task is to prove that there exists $\lambda>0$ such that

$a^{\prime}_{J}=\lambda a_{J},\
\forall\,J\in\mathcal{J}^{H}_{\leqslant}\cup\\{\varnothing\\}.$ (6.23)

We simply denote $\bigcup_{I\in V}S_{I}$ by $\bigcup S_{I}$ . We first prove
the case where $J\subseteq\bigcup S_{I}$.

Arbitrarily choose $\tilde{i}_{I}\in S_{I}$, and define
$R=\\{\tilde{i}_{I}\\}_{I\in V}$. It is clear that
$R\in\mathcal{J}^{V}|_{\bigcup S_{I}}$. Define a mapping
$\mathcal{T}^{R}:\mathcal{S}^{H}\rightarrow\mathrm{MC}^{H}_{\leqslant}$ given
by $z\mapsto v$ as follows:

$\displaystyle v_{\tilde{i}_{I}}$ $\displaystyle=z_{I},$ $\displaystyle\quad
I$ $\displaystyle\in V;$ (6.24a) $\displaystyle v_{i}$ $\displaystyle=0,$
$\displaystyle\quad i$ $\displaystyle\in[n]\setminus R,$ (6.24b)

and $v_{J}=\prod_{i\in J}v_{i}$ for all $J\in\mathcal{J}^{H}_{\leqslant}$
where $|J|>1$ to ensure $v\in\mathrm{MC}^{H}_{\leqslant}$.

It is easily seen that for $J\in\mathcal{J}^{H}_{\leqslant}$, $v^{k}_{J}\neq
0$ only when $J\subseteq R$, i.e., $J\in\mathcal{J}^{H}|_{R}$. In this case,

$v_{J}=\prod_{\tilde{i}_{I}\in J}v_{\tilde{i}_{I}}=\prod_{I\in
E(J)}z_{I}=z_{E(J)}.$ (6.25)

The relationship between $J$ and $E(J)$ is indeed a one-to-one correspondence
between $\mathcal{J}^{H}|_{R}$ and $L(V)\cup E$. We denote the inverse mapping
that maps $e=E(J)$ to $J=J(e,R)=R\cap\bigcup_{I\in e}S_{I}$. Then,

$\sum_{e\in L(V)\cup
E}a_{J(e,R)}^{\prime}z_{e}=\sum_{J\in\mathcal{J}^{H}|_{R}}a_{J}^{\prime}v_{J}=a^{\prime}\cdot
v\leqslant\delta^{\prime}.$ (6.26)

By the arbitrariness of $z\in\mathcal{S}^{H}$, it follows that

$\sum_{e\in L(V)\cup E}a_{J(e,R)}^{\prime}z_{e}\leqslant\delta^{\prime}$
(6.27)

is valid for $\mathrm{MP}^{H}$. Similarly,

$\displaystyle\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}a\cdot v$
$\displaystyle=\sum_{e\in L(V)\cup E}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}}v_{i}$ $\displaystyle=\sum_{e\in L(V)\cup E}c_{e}\prod_{I\in e}z_{I}$
$\displaystyle=c\cdot z.$

We denote the vertices on $\mathrm{MP}^{H}$ that satisfy $c\cdot z=\delta$ as
$z^{1},z^{2},\dots,z^{s}\in\mathcal{S}^{H}$. Define
$v^{k}=\mathcal{T}^{R}(z^{k})$ for $k=1,2,\dots,s$. Then
$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}a\cdot v^{k}=c\cdot
z^{k}=\delta$, thus $v^{k}\in F$, and consequently, Eq. (6.26) becomes
equality for $v\leftarrow v^{k}$. Hence, $z^{k}$ also makes Eq. (6.27) become
equality, which implies that the facet induced by $c\cdot z\leqslant\delta$ is
contained in the face defined by Eq. (6.27). By the definition of facet, Eq.
(6.27) is also facet-inducing. Since $\mathrm{MP}^{H}$ is full-dimensional,
these two facet-inducing inequalities, Eq. (6.27) and $c\cdot
z\leqslant\delta$, are positive scalar multiple of each other. Namely, there
exists a scalar $\lambda_{R}>0$ such that

$a^{\prime}_{J(e,R)}=\lambda_{R}c_{e},\ \forall\,e\in L(V)\cup
E\cup\\{\varnothing\\},$ (6.28)

where we define $J(\varnothing,R)=\varnothing$. By the definition of
$\operatorname{supp}c$, the above equation implies

$\lambda_{R}=a^{\prime}_{J(e,R)}/c_{e},\ \forall\,e\in\operatorname{supp}c.$
(6.29)

This equality holds for any $R\in\mathcal{J}^{V}|_{\bigcup S_{I}}$. Note that
given one $J\in\mathcal{J}^{H}|_{\bigcup S_{I}}\cup\\{\varnothing\\}$ such
that $E(J)\in\operatorname{supp}c$, for all $R\in\mathcal{J}^{V}|_{\bigcup
S_{I}}$ such that $R\supseteq J$, we have $J(E(J),R)=J$, implying that the
corresponding $\lambda_{R}$ are identical. Since
$\bigcap_{e\in\operatorname{supp}c}e=V_{0}=\varnothing$, we can prove the
equality of all $\lambda_{R}$s by selecting different $J$s.

We strictly prove as follows: Suppose to the contrary that there exist
$R,R^{\prime}\in\mathcal{J}^{V}|_{\bigcup S_{I}}$ such that
$\lambda_{R}\neq\lambda_{R^{\prime}}$, then let $R,R^{\prime}$ be the pair
that maximizes $|R\cap R^{\prime}|$ among them. Let $i_{I^{\prime}}\in
R\setminus R^{\prime}$ and $i_{I^{\prime}}^{\prime}\in R^{\prime}$, where
$i_{I^{\prime}},i^{\prime}_{I^{\prime}}\in S_{I^{\prime}}\subset I^{\prime}$.
Obviously, $i_{I^{\prime}}\neq i_{I^{\prime}}^{\prime}$. Since
$\bigcap_{e\in\operatorname{supp}c}e=\varnothing$, there exists
$e_{0}\in\operatorname{supp}c$ such that $I^{\prime}\notin e_{0}$. Let
$\hat{R}=(R-i_{I^{\prime}})\cup\\{i^{\prime}_{I^{\prime}}\\}$, then
$|\hat{R}\cap R^{\prime}|=|R\cap R^{\prime}|+1$. It can be readily observed
that

$\displaystyle J(e_{0},R)$ $\displaystyle=R\cap\bigcup_{I\in e_{0}}S_{I}$
$\displaystyle=(R-i_{I^{\prime}})\cap\bigcup_{I\in e_{0}}S_{I}$
$\displaystyle=(\hat{R}-i^{\prime}_{I^{\prime}})\cap\bigcup_{I\in e_{0}}S_{I}$
$\displaystyle=J(e_{0},\hat{R}),$

so
$\lambda_{R}=a^{\prime}_{J(e,R)}/c_{e}=a^{\prime}_{J(e,\hat{R})}/c_{e}=\lambda_{\hat{R}}$,
thus $\lambda_{\hat{R}}\neq\lambda_{R^{\prime}}$, contradicting the maximality
of $|R\cap R^{\prime}|$.

Hence, we can let $\lambda>0$ such that
$\lambda_{R}=\lambda,\forall\,R\in\mathcal{J}^{V}|_{\bigcup S_{I}}$. Now Eq.
(6.28) becomes

$a^{\prime}_{J(e,R)}=\lambda c_{e},\ \forall\,e\in L(V)\cup
E\cup\\{\varnothing\\}.$ (6.30)

As $e$ ranges over $L(V)\cup E\cup\\{\varnothing\\}$ and $R$ ranges over
$\mathcal{J}^{V}|_{\bigcup S_{I}}$, $J(e,R)$ ranges over
$\mathcal{J}^{H}|_{\bigcup S_{I}\cup\\{\varnothing\\}}$. Thus, for any
$J\in\mathcal{J}^{H}|_{\bigcup S_{I}}\cup\\{\varnothing\\}$, we have

$a^{\prime}_{J}=\lambda c_{E(J)}=\lambda a_{J}.$ (6.31)

Next, we only need to prove the case where $J\in\mathcal{J}^{H}_{\leqslant}$
but $J\nsubseteq\bigcup S_{I}$, and we will show that $a^{\prime}_{J}=0$.
Combining with $a_{J}=0$, we also have $a^{\prime}_{J}=\lambda a_{J}$.

Previously, we defined $v^{k}\in F$, and here we are going to construct more
vertices on $F$ to obtain more properties using
$\operatorname{Proj}_{\mathcal{J}^{H}_{\leqslant}}a\cdot v=\delta$ when $v$ is
on $F$.

Recall that $z^{1},z^{2},\dots,z^{s}\in\mathcal{S}^{H}$ are vertices of the
facet defined by $c\cdot z\leqslant\delta$. Given any $U\subseteq V\setminus
V_{1}$, let $K_{U}=\\{k\in[s]|z^{k}_{I}=0,\forall\,I\in U\\}$ be the index of
these vertices where the components corresponding to $I\in U$ are all zero. We
have

$F_{U}=\\{z\in\mathrm{MP}^{H}|c\cdot z=\delta;z_{I}=0,\forall\,I\in
U\\}=\operatorname{conv}\\{z^{k}|k\in K_{U}\\}.$

For any $\tilde{i}_{I}\in S_{I},I\in V\setminus U$ and
$\tilde{i}_{I}\in(I-\bar{i}_{I})\setminus S_{I},I\in U$, we can define two
sets of $v^{k},\bar{v}^{k}\in\mathrm{MC}^{H},k\in K_{U}$ as follows,

$\displaystyle\bar{v}^{k}_{\tilde{i}_{I}}$ $\displaystyle=1,$
$\displaystyle\quad I$ $\displaystyle\in U,$ (6.32a)
$\displaystyle\bar{v}^{k}_{\tilde{i}_{I}}$ $\displaystyle=z^{k}_{I},$
$\displaystyle I$ $\displaystyle\in V\setminus U,$ (6.32b)

and for remaining $i\in[n]$, $\bar{v}^{k}_{i}=0$. The definition of
$v^{k},k\in K_{U}$ is similar to before, $v^{k}=\mathcal{T}^{R}(z^{k})$, i.e.,

$v^{k}_{\tilde{i}_{I}}=z^{k}_{I},\quad I\in V\setminus U,$ (6.33)

and for remaining $i\in[n]$, $v^{k}_{i}=0$. $\bar{v}^{k}_{J}$ and $v^{k}_{J}$
for $|J|>1$ is defined by production constraints. The only difference between
$\bar{v}^{k}$ and $v^{k}$ is that $\bar{v}^{k}_{\tilde{i}_{I}}=1$ while
$v^{k}_{\tilde{i}_{I}}=z^{k}_{I}=0$, where $I\in U$, and that the components
$\bar{v}^{k}_{J}$ and $v^{k}_{J}$ with $J$ containing $\tilde{i}_{I}$. Note
that $z^{k}_{I}=0,\forall\,k\in K_{U},I\in U$, so we still have

$\sum_{i\in I}v^{k}_{i}=\sum_{i\in I}\bar{v}^{k}_{i}=z^{k}_{I},$ (6.34)

and hence

$a\cdot\bar{v}^{k}=a\cdot v^{k}=c\cdot z^{k}=\delta,\ \forall\,k\in K_{U}.$
(6.35)

By the assumption of $F$ and $F^{\prime}$, $v^{k},\bar{v}^{k}$ are on the face
$F\subseteq F^{\prime}$, implying

$a^{\prime}\cdot(\bar{v}^{k}-v^{k})=a^{\prime}\cdot\bar{v}^{k}-a^{\prime}\cdot
v^{k}=0.$ (6.36)

Next, we will express $a^{\prime}\cdot(\bar{v}^{k}-v^{k})$ in detail. Similar
to the previous definition, let $R=\\{\tilde{i}_{I}\\}_{I\in V}$,
$J(e,R)=R\cap\bigcup_{I\in e}S_{I}$.

It is easily seen that for all $J\in\mathcal{J}^{H}_{\leqslant}$,
$v^{k}_{J}\leqslant\bar{v}^{k}_{J}$. Thus $\bar{v}^{k}_{J}-v^{k}_{J}\neq 0$ if
and only if $\bar{v}^{k}_{J}=1$ and $v^{k}_{J}=0$. By definitions Eqs. (6.32)
and (6.33), this holds only if

$J\cap\bigcup_{I\in U}S_{I}\neq\varnothing\ \text{and}\ J\subseteq R.$ (6.37)

Suppose $J_{0}$ satisfies the above condition and $e_{0}=E(J_{0})$, then
$J_{0}=J(e_{0},R)$. Partition $e_{0}$ into subsets of $V\setminus U$ and $U$
respectively, denoted by $e^{\prime}$ and $U^{\prime}$, and defined by
$e^{\prime}=e_{0}\setminus U$, $U^{\prime}=e_{0}\cap U$. Since
$J\cap\bigcup_{I\in U}S_{I}\neq\varnothing$, we have
$U^{\prime}\neq\varnothing$.

For any nonempty $\bar{U}\subseteq V\setminus V_{1}$, let

$E_{\bar{U}}=\\{e\in L(V)\cup E\cup\\{\varnothing\\}|e\subseteq
V\setminus\bar{U},e\cup\bar{U}\in L(V)\cup E\\}.$ (6.38)

Since $e^{\prime}\cup U^{\prime}=e_{0}\in L(V)\cup E$, we have $e^{\prime}\in
E_{U^{\prime}}$. Note that for any $I\in U$, $\bar{v}^{k}_{\tilde{i}_{I}}=1$,
thus

$\displaystyle\bar{v}^{k}_{J_{0}}$ $\displaystyle=\prod_{i\in
J(e^{\prime},R)}\bar{v}^{k}_{i}\prod_{i\in J(U^{\prime},R)}\bar{v}^{k}_{i}$
$\displaystyle=\prod_{i\in J(e^{\prime},R)}\bar{v}^{k}_{i}$
$\displaystyle=\bar{v}^{k}_{J(e^{\prime},R)}$
$\displaystyle=z^{k}_{e^{\prime}},$

where we define $\bar{v}^{k}_{\varnothing}=1$ and $z^{k}_{\varnothing}=1$.

Now $a^{\prime}\cdot(\bar{v}^{k}-v^{k})$ can be expressed by summing all
$a^{\prime}_{J}\cdot(\bar{v}^{k}_{J}-v^{k}_{J})$ such that $J$ satisfies Eq.
(6.37). Noting that in this case $v^{k}_{J}=0$ (but $\bar{v}^{k}_{J}=1$ may
not hold, as Eq. (6.37) is a necessary condition for
$v^{k}_{J}\neq\bar{v}^{k}_{J}$), we have

$\displaystyle 0$ $\displaystyle=a^{\prime}\cdot(\bar{v}^{k}-v^{k})$ (6.39a)
$\displaystyle=\sum_{U^{\prime}\subseteq
U:U^{\prime}\neq\varnothing}\sum_{e^{\prime}\in
E_{U^{\prime}}:e^{\prime}\subseteq V\setminus U}a^{\prime}_{J(e^{\prime}\cup
U^{\prime},R)}\bar{v}^{k}_{J(e^{\prime}\cup U^{\prime},R)}$ (6.39b)
$\displaystyle=\sum_{U^{\prime}\subseteq
U:U^{\prime}\neq\varnothing}\sum_{e^{\prime}\in
E_{U^{\prime}}:e^{\prime}\subseteq V\setminus U}a^{\prime}_{J(e^{\prime}\cup
U^{\prime},R)}z^{k}_{e^{\prime}}.$ (6.39c)

The above equation holds for $k\in K_{U}$.

Now, we can prove $a^{\prime}_{J}=0$ by induction on $|J\setminus\bigcup
S_{I}|$. Note that we assume $J\in\mathcal{J}^{H}_{\leqslant}$ and
$J\nsubseteq\bigcup S_{I}$, so $|J\setminus\bigcup S_{I}|>0$.

When $|J\setminus\bigcup S_{I}|=1$, let $e_{0}=E(J)$ and define
$\tilde{i}_{I},I\in e_{0}$ as $\\{\tilde{i}_{I}\\}_{I\in e_{0}}=J$. For
$I\notin e_{0}$, we arbitrarily choose $\tilde{i}_{I}\in S_{I}$. Let
$R=\\{\tilde{i}_{I}\\}_{I\in V}$, then $R\supseteq J$. Suppose
$J\setminus\bigcup S_{I}=\\{\tilde{i}_{I_{0}}\\}$ and let $U=\\{I_{0}\\}$.
Note that $\tilde{i}_{I_{0}}\in(I_{0}-\bar{i}_{I_{0}})\setminus S_{I_{0}}$ and
$S_{I}=I-\bar{i}_{I},\forall\,I\in V_{1}$, so $U\subseteq V\setminus V_{1}$.
We define $K_{U}$ and $\bar{v}^{k}$, $v^{k}$, $k\in K_{U}$, by Eqs. (6.32) and
(6.33). Since $|U|=1$, Eq. (6.39) becomes

$\sum_{e^{\prime}\in E_{U}:e^{\prime}\subseteq V\setminus
U}a^{\prime}_{J(e^{\prime}\cup U,R)}z^{k}_{e^{\prime}}=0.$ (6.40)

Note that the condition $e^{\prime}\subseteq V\setminus U$ for summation can
be omitted since it is already defined in $E_{U}$. Since $e_{0}\supseteq U$
and $e_{0}\in L(V)\cup E$, we know $E_{U}$ is nonempty. By Lemma 6.1,
$F_{U}=\operatorname{conv}\\{z^{k}|k\in K_{U}\\}$ projected onto
$\mathbb{R}^{E_{U}-\varnothing}$ is full-dimensional. However, Eq. (6.40)
implies that for all points $z^{\prime}$ on
$\operatorname{Proj}_{E_{U}-\varnothing}F_{U}$, it holds that

$\sum_{e^{\prime}\in E_{U}-\varnothing}a^{\prime}_{J(e^{\prime}\cup
U,R)}z^{\prime}_{e^{\prime}}=a^{\prime}_{J(U,R)},$ (6.41)

hence $a^{\prime}_{J(e^{\prime}\cup U,R)}=0,\forall\,e^{\prime}\in E_{U}$. In
particular, when $e^{\prime}=e_{0}\setminus U$, we have $J=J(e^{\prime}\cup
U,R)$, yielding $a^{\prime}_{J}=0$.

Suppose $|J\setminus\bigcup S_{I}|>1$. Similar to the previous case, let
$e_{0}=E(J)$, define $\tilde{i}_{I}$ by $\\{\tilde{i}_{I}\\}_{I\in e_{0}}=J$,
and arbitrarily choose $\tilde{i}_{I}\in S_{I}$ for $I\notin e_{0}$. Likewise,
we let $R=\\{\tilde{i}_{I}\\}_{I\in V}$ and $U=\\{I\in V|\tilde{i}_{I}\in
J\setminus\bigcup S_{I}\\}$. We also define $K_{U}$ and $\bar{v}^{k}$, $v^{k}$
for $k\in K_{U}$. Again, we have $U\subseteq V\setminus V_{1}$ and Eq. (6.39)
holds.

Considering the index $U^{\prime}$ of the outer sum in Eq. (6.39c) where
$U^{\prime}\subset U$, it is easy to see that $|J(e^{\prime}\cup
U^{\prime},R)\setminus\bigcup S_{I}|=|J(U^{\prime},R)|=|U^{\prime}|<|U|$, so
the induction hypothesis implies $a^{\prime}_{J(e^{\prime}\cup
U^{\prime},R)}=0$. These parts of the outer sum vanish and the remainder is
summing over $U^{\prime}=U$, hence

$\sum_{e^{\prime}\in E_{U}}a^{\prime}_{J(e^{\prime}\cup
U,R)}z^{k}_{e^{\prime}}=0,\ \forall\,k\in K_{U}.$ (6.42)

Applying Lemma 6.1, we conclude that $a_{J(e^{\prime}\cup U,R)}=0$ holds for
any $e^{\prime}\in E_{U}$. Since $J=J(e_{0},R)$ and $e_{0}\supseteq U$, we
have $a^{\prime}_{J}=0$.

In conclusion, there exists $\lambda>0$ such that for any
$J\in\mathcal{J}^{H}_{\leqslant}\cup\\{\varnothing\\}$, we have
$a^{\prime}_{J}=\lambda a_{J}$. Namely,

$a^{\prime}\cdot v-\delta^{\prime}=\lambda(a\cdot v-\delta),$

which indicates that the face defined by $a\cdot v\leqslant\delta$ is the same
as the facet induced by $a^{\prime}\cdot v\leqslant\delta^{\prime}$. The
sufficiency holds. ∎

In fact, the above proof also shows that when Eq. (1.12) holds, Eq. (1.9) is
also facet-inducing for $\mathrm{MC}^{H}_{\leqslant}(D)$ where
$D\in\mathcal{J}^{V}$ and $D\subseteq[n]\setminus\bigcup S_{I}$. Thus we have
the following corollary.

######  Corollary 6.2.

Suppose the hypergraph $H(V,E)$ is downward-closed and $D\in\mathcal{J}^{V}$.
Let $c\cdot z\leqslant\delta$ be a facet-inducing inequality for
$\mathrm{MP}^{H}$. $V_{0}$ and $V_{1}$ are defined by Eqs. (1.10) and (1.11),
respectively. For any $S_{I}\subset I\setminus D,S_{I}\neq\varnothing,I\in V$,
the inequality

$\sum_{e\in L(V)\cup E}c_{e}\mathscr{L}\prod_{I\in e}\sum_{i\in
S_{I}}v_{i}\leqslant\delta$

is facet-inducing for $\mathrm{MC}^{H}_{\leqslant}$ if and only if Condition
(1.12) holds.

There exists a similar operation named “copying” proposed in [6] that
introduces classes of valid inequalities for $P(G,\mathcal{I})$ inherited from
BQP. The work specified two classes among them in its Theorems 3.6 and 3.7.
Since BQP with multiple choice constraints is a special case of
$\mathrm{MC}^{H}_{\leqslant}$ (which is isomorphic to $\mathrm{MC}^{H}$ when
$H$ is a graph), it can be quickly verified that these theorems are
corollaries to Corollary 6.2.

######  Example 6.1.

Let $G(X\cup Y,E)$ be a bipartite graph with $X$ and $Y$ being color classes
of $G$. Sections 3.2.1 and 3.2.2 of [6] discussed the so called cycle
inequalities and $I_{mm22}$ Bell inequalities of BQP, respectively, and
provided two classes of facet-inducing inequalities for $P(G,\mathcal{I})$
which is achiedved by applying 0-lifting and copy operation to them. (See
Theorems 3.6 and 3.7 of the paper.) The condition for $G$ is subset-uniform.
Let $\mathcal{G}=(\mathcal{I}\cup Y,\mathcal{E})$ achieved by merging the
vertices in each subset of the partition $\mathcal{I}$ into a single vertex.
Since BQP is a special case of multilinear polytope, we can express the BQP
w.r.t. $\mathcal{G}$ by $\mathrm{MP}^{\mathcal{G}}$. The cycle inequality
w.r.t. cycle
$\\{I_{1}I_{2},I_{2}I_{3},\dots,I_{m}I_{1}\\}\subseteq\mathcal{E}$ reads

$-z_{I_{1}I_{m}}+\sum_{p=1}^{m-1}z_{I_{p}I_{p+1}}-\sum_{p=2}^{m-1}z_{I_{p}}\leqslant
0.$ (6.43)

Since $\mathcal{G}$ is bipartite, $m$ is even and $m\geqslant 4$. We assume
that $I_{1},I_{3},\dots,I_{m-1}\in\mathcal{I}$. It can be easily verified that
$V_{0}=V_{1}=\varnothing$ for Eq. (6.43). Define $H(V,\hat{E})$ and $D$ by
Eqs. (3.3)–(3.5) in Example 3.2. Then $P(G,\mathcal{I})$ is in one-to-one
correspondence with $\mathrm{MC}^{H}_{\leqslant}$. By Corollary 6.2, for any
nonempty $S_{I_{p}}\subset I_{p},p=1,3,\dots,m-1$ along with
$S_{I_{p}}=I_{p},p=2,4,\dots,m$, the lifted inequality of Eq. (6.43) w.r.t.
$S_{I_{p}}$ is facet-inducing, and it is the same to the cycle+copying
inequalities, Eq. (9) of [6]. Thus Theorem 3.6 of that paper holds. For the
case of $I_{mm22}$ Bell inequalities, it is also clear that
$V_{0}=V_{1}=\varnothing$, and Theorem 3.7 of [6] holds.

##  7 Conclusion and discussion

We proposed the Boolean polynomial polytope with multiple choice constraints,
$\mathrm{MC}^{H}$, to study the feasible region of linearized MCPP (1.4). Two
main theorems were proved. The first gives the explicit half-space
representation of $\mathrm{MC}^{H}$ when the hypergraph $H$ is
$\alpha$-acyclic. The second provides a necessary and sufficient condition for
the inequalities lifted from the facet-inducing ones for the multilinear
polytope $\mathrm{MP}^{H}$ to be still facet-inducing for $\mathrm{MC}^{H}$.
However, compared with the rich polyhedral study for the unconstrained case,
there is still very little research on $\mathrm{MC}^{H}$ at current stage and
many possible directions are left for the future. We list some of them below.

  * •

It will be interesting to develop separation algorithms for the lifted facet-
inducing inequalities.

  * •

It is mentioned that the description of $\operatorname{aff}\mathrm{MC}^{H}$
for general hypergraph $H$ is still unclear in Section 3. A possible way to
determine the implicit equalities for $\operatorname{aff}\mathrm{MC}^{H}$ is
adding hyperedges into $H$ to achieve a downward-closed $H^{\prime}$ such that
$\mathrm{MC}^{H}$ is isomorphic to $\mathrm{MC}^{H^{\prime}}$. Then the known
properties of $\operatorname{aff}\mathrm{MC}^{H^{\prime}}$ may be useful for
$\operatorname{aff}\mathrm{MC}^{H}$.

  * •

Since $\mathrm{MC}^{H}_{\leqslant}$ is actually the same to $\mathrm{MP}^{H}$
when $|I|=2$ for all $I\in V$ (see Example 3.1), it is plausible to think that
the results of $\mathrm{MC}^{H}$, e.g., Theorems 1.1 and 4.1, may be
specialized for $\mathrm{MP}^{H}$ through the isomorphism between
$\mathrm{MC}^{H}$ and $\mathrm{MC}^{H}_{\leqslant}$ (under a certain
condition).

  * •

There is a less well-known acyclicity degree called “cycle-free” defined in
[5]. The condition for this cycle-freedom is even weaker than that for the
$\alpha$-acyclicity. It may be worth studying the properties of
$\mathrm{MC}^{H}$ when $H$ is cycle-free.

  * •

For small hypergraph $H$, there are special facet-inducing inequalities for
$\mathrm{MC}^{H}$ other than those lifted from $\mathrm{MP}^{H}$ found by
symbolic computation. Similar inequalities for general $\mathrm{MC}^{H}$ still
need to be identified and classified.

Acknowledgements. This work was funded by the National Key R & D Program of
China (No. 2022YFA1005102) and the National Natural Science Foundation of
China (Nos. 12325112, 12288101).

## References

  * [1] F. Barahona and A. R. Mahjoub, On the cut polytope, Math. Program., 36 (1986), pp. 157–173.
  * [2] C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM, 30 (1983), pp. 479–513.
  * [3] E. Boros and P. L. Hammer, Cut-polytopes, boolean quadric polytopes and nonnegative quadratic pseudo-boolean functions, Math. Oper. Res., 18 (1993), pp. 245–253.  Publisher: INFORMS.
  * [4] , Pseudo-Boolean optimization, Discrete Appl. Math., 123 (2002), pp. 155–225.
  * [5] J. Brault-Baron, Hypergraph acyclicity revisited, ACM Comput. Surv., 49 (2016), pp. 54:1–54:26.
  * [6] A. Bärmann, A. Martin, and O. Schneider, The bipartite boolean quadric polytope with multiple-choice constraints, SIAM J. Optim., 33 (2023), pp. 2909–2934.  Publisher: Society for Industrial and Applied Mathematics.
  * [7] K. Chandrasekaran, C. Xu, and X. Yu, Hypergraph k-cut in randomized polynomial time, Math. Program., 186 (2021), pp. 85–113.
  * [8] C. De Simone, The cut polytope and the Boolean quadric polytope, Discrete Math., 79 (1990), pp. 71–75.
  * [9] V. Deineko, P. Jonsson, M. Klasson, and A. Krokhin, The approximability of MAX CSP with fixed-value constraints, J. ACM, 55 (2008), pp. 1–37.
  * [10] A. Del Pia and S. Di Gregorio, On the complexity of binary polynomial optimization over acyclic hypergraphs, Algorithmica, 85 (2023), pp. 2189–2213.
  * [11] A. Del Pia and A. Khajavirad, A polyhedral study of binary polynomial programs, Math. Oper. Res., 42 (2017), pp. 389–410.
  * [12] , The multilinear polytope for acyclic hypergraphs, SIAM J. Optim., 28 (2018), pp. 1049–1076.  _eprint: https://doi.org/10.1137/16M1095998.
  * [13] , On decomposability of multilinear sets, Math. Program., 170 (2018), pp. 387–415.
  * [14] , A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs, Math. Program., (2023).
  * [15] M. Deza, M. Grötschel, and M. Laurent, Clique-web facets for multicut polytopes, Math. Oper. Res., 17 (1992), pp. 981–1000.  Publisher: INFORMS.
  * [16] R. Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30 (1983), pp. 514–550.
  * [17] A. Frieze and M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Algorithmica, 18 (1997), pp. 67–81.
  * [18] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.
  * [19] R. M. Nauss, The 0-1 knapsack problem with multiple choice constraints, European J. Oper. Res., 2 (1978), pp. 125–131.
  * [20] M. Padberg, The boolean quadric polytope: Some characteristics, facets and relatives, Math. Program., 45 (1989), pp. 139–172.
  * [21] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Springer Berlin, Heidelberg, 2002\.
  * [22] S. Shao and Y. Wu, An ODE approach to multiple choice polynomial programming, Oct. 2023.  arXiv:2212.06371 [math].
  * [23] H. D. Sherali, Y. Lee, and W. P. Adams, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, Oper. Res. Lett., 17 (1995), pp. 19–26.
  * [24] Y. Yajima and T. Fujie, A polyhedral approach for nonconvex quadratic programming problems with box constraints, J. Global Optim., 13 (1998), pp. 151–170.