Cardinality constraints and systems of restricted representatives

Abstract

Cardinality constraints have received considerable attention from the Constraint Programming community as (so-called) global constraints that appear in the formulation of several real-life problems, while also having an interesting combinatorial structure. After discussing the relation of cardinality constraints with well-known combinatorial problems (e.g., systems of restricted representatives), we study the polytope defined by the convex hull of vectors satisfying two such constraints, in the case where all variables share a common domain. We provide families of facet-defining inequalities that are polytime separable, together with a condition for when these families of inequalities define a convex hull relaxation. Our results also hold for the case of a single such constraint.

1 Motivation

The cardinality constraint, initially introduced as the global cardinality constraint (Regin 1996), restricts the number of occurrences of values assigned to a set of variables. Each value is given a lower bound and an upper bound, and the constraint requires that the number of occurrences of each of the values falls within these bounds in this set of variables. This constraint can be written as (Hooker 2012, Sect. 7.10.1)

$$\begin{aligned}&cardinality(x,J;l,u), \\&x_{j}\in D_{j},j\in J. \end{aligned}$$

Let $\mathop {\bigcup }\nolimits _{j\in J}D_{j}=D=\{d_{0},\ldots ,d_{|D|-1}\}$ be the set of all values and $K=\{0,\ldots ,|D|-1\}$ the set indexing it. The constraint states that each value $d_{k}$ ($k\in K$) must occur at least $l_{k}$ and at most $u_{k}$ times among the variables $\{x_{j}:j\in J\},$ where $l\le u$ (i.e., $l_k \le u_k$ for all $k \in K$). Without loss of generality, let $d_{0}<\cdots <d_{|K|-1}.$

This constraint has several applications (Bulatov and Marx 2010), including instruction scheduling (van Beek and Wilken 2001) and car sequencing (Quimper et al. 2005). This has motivated an extensive literature within the Constraint Programming (CP) community in the form of procedures that reduce the set of solutions through tightening the domain of each variable. In CP terms, this research effort aims at accomplishing various forms of consistency (see Hooker 2012 for related definitions) including arc-consistency (Regin 1996), cost-based arc consistency (Regin 2002) and bounds consistency (Katriel and Thiel 2005; Quimper et al. 2005). A generalization of the cardinality constraint, discussed in Samer and Szeider (2011), is the extended global cardinality constraint, in which the number of occurrences of each value $d_{k}\in D$ must belong to a set of (not necessarily subsequent) integers, called the cardinality set of $d_{k}.$ Another interesting extension of the cardinality constraint to set, multiset and tuple variables appears in Quimper and Walsh (2006).

In contrast, the literature from an Integer Programming (IP) perspective remains limited. Two families of valid inequalities for the single cardinality constraint appear in (Hooker (2012), Sect. 7.10.1), together with a claim that these inequalities describe the convex hull of vectors satisfying a cardinality constraint. Preliminary results are presented in Mourtos (2013) regarding two cardinality constraints in the special case where all variables share a common domain $D=\{0,\ldots ,|D|-1\}=K.$ These results include a condition for the associated polytope to be full-dimensional, and, given that the polytope is full-dimensional, conditions for the inequalities of Hooker (2012) to be facet-defining. The polyhedral study of multiple cardinality constraints, e.g., the dimension and the facets of the associated polytope, is also limited. Notably, results of this kind exist for the multiple alldifferent constraints (Bergman and Hooker 2014; Magos and Mourtos 2011; Magos et al. 2012) (the alldifferent constraint is a special case of the cardinality constraint, in which $l_{k}=0$ and $u_{k}=1$ for all $k\in K$).

Multiple cardinality constraints give rise to a cardinality system, i.e., a set $C$ of cardinality constraints in which all variables share the same domain (i.e., $x_{j}\in D,\forall j\in J$) and all constraints admit the same lower and upper bounds on the occurrence of each value. The formulation

$$\begin{aligned} cardinality(x,J_{c};l,u),c\in C, \end{aligned}$$

(1)

dictates that each value $d_{k}\in D$ must occur at least $l_{k}$ and at most $u_{k}$ times ($l\le u$) in each constraint $c\in C,$ where $J=\mathop {\bigcup }\nolimits _{c\in C}J_{c}$ is the set of all variables.

The polyhedral study of global constraints has been the common theme of several recent papers. A typical such paper considers a constraint

$$\begin{aligned} constraint(x,J;...)\subseteq \mathop {\bigotimes }\nolimits _{j\in J}D_{j},\text { where }x_{j}\in D_{j},j\in J, \end{aligned}$$

where $J$ is the set of variables and $\mathop {\bigotimes }\nolimits _{j\in J}D_{j}$ is the external product of the domains of all the variables. Then, such a paper considers the polytope defined by the convex hull of vectors satisfying such a constraint, assuming that $D_{j}=D$ ($j\in J$); i.e., the polytope $P=conv\{x\in D^{|J|}:x$ satisfies $constraint(x,J;...)\}.$ Obtaining valid inequalities for $P$ allows the formulation of LP-relaxations for the constraint in hand, while using (in the formulation) only the facet-defining among these inequalities results in a ‘tight’ relaxation. A formulation containing all facet-defining inequalities provides a convex hull relaxation. There are several arguments in support of such relaxations regarding the effective integration of CP and IP methods (Hooker 2012; Milano et al. 2002).

Furthermore, it remains important to obtain these relaxations using just the variables appearing originally, without including any additional $0-1$ variables (as in Hooker 2012, Sect 7.10.2). At the very least, this approach results in a significant reduction in the number of variables, since the standard approach replaces each variable $x_{j}\in D$ with $\left| D\right|$ binary variables $z_{ij}$ through setting $x_{j}=\mathop {\sum }\nolimits _{i\in D}i\cdot z_{ij}$ (see, for example, Williams and Yan 2001). Constraints for which this has been accomplished via finding some (or all) of the facets of $P$ include alldifferent (Williams and Yan 2001), cumulative scheduling (Hooker and Yan 2002), cardinality rules (Balas et al. 2004; Yan and Hooker 1999) and circuit (Kaya and Hooker 2011). Such polytopes are also of interest from a technical perspective, since the polyhedral combinatorics literature focuses on examining polytopes defined on binary, rather than $n$-ary, variables. The facet-defining inequalities of the polytopes arising from $n$-ary formulations are typically quite different from the facet-defining inequalities of the associated binary polytopes (e.g., Kaya and Hooker 2011). Another benefit is that valid inequalities defined in the original $n$-ary space can be ‘translated’ into a binary model in order to further strengthen it (Bergman and Hooker 2014).

The cardinality constraint is of particular interest also because of its relation to fundamental combinatorial problems. To better illustrate this relation, consider the ‘variable-value’ graph $G(V_{G},E_{G}),$ defined by $V_{G}=\{x_{j}:j\in J\}\cup D$ and $E_{G}=\{(x_{j},d):j\in J,$ $d\in D_{j}\}.$ An example is shown at Fig. 1. For each $v\in V_{G},$ define $\delta (v)=\{e\in E_{G}:e$ is incident to $v\}.$ Given a vector $b\in Z_{+}^{|V_{G}|},$ a subset $S$ of edges (i.e., $S\subseteq E_{G}$) is a simple $b$ -edge cover if $|S\cap \delta (v)|\ge b_{v}$ (Schrijver (2004), Sect. 21.9) and a simple $b$ -matching if $|S\cap \delta (v)|\le b_{v}$ (Schrijver (2004), Sect. 21.3). In other words, a subset of edges is a simple $b$-edge cover if the subset includes at least $b_{v}$ edges incident to node $v$ (for each $v\in V$) and a simple $b$-matching if the subset includes at most $b_{v}$ such edges.

Fig. 1

Graph $G$ for ${cardinality}(x,\{1,2,3,4\};[0,1],[4,2]),x_{j}\in D_{j}=\{0,1\}.$

For each $e\in E_{G}$ let $y_{e}\in \{0,1\}$ and, for each $v\in V_{G},$ define $y(v)=\sum \{y_{e}:e\in \delta (v)\}.$ It is clear that there is a $1-1$ correspondence between vectors $x$ satisfying $cardinality(x,J;l,u)$ and subsets of $E_{G}$ satisfying

$$\begin{aligned}&y(x_j)=1,j\in J, \\&l_{d}\le y(d)\le u_{d},d\in D. \end{aligned}$$

Therefore, $cardinality(x,J;l,u)$ is an $n$-ary representation of the subsets of edges that are simple $(\dot{e},l)$-edge covers and $(\dot{e},u)$-matchings of graph $G,$ where $\dot{e}=[1\cdots 1]\in R^{|J|}.$ Considering the example of Fig. 1, notice that the ordered pair appearing besides each node denotes the smallest and the largest number of edges to be incident to it, e.g., node ‘$x_{1}$’ must have exactly one edge incident to it (since variable $x_{1}$ must receive a value) whereas node ‘$1$’ must have at least $1$ and at most $2$ edges incident to it (since value $0$ must be received by at least $l_{1}=1$ and at most $u_{1}=2$ variables). The ‘broken’ edges at Fig. 1 correspond to the solution $x_{1}=x_{2}=0,x_{3}=x_{4}=1.$

As another example, consider the collection of sets $\{D_{j},j\in J\}$ where $\mathop {\bigcup }\nolimits _{j\in J}D_{j}=D$ and $l,u\in Z_{+}^{|D|}\,$ with $l\le u.$ According to Ford and Fulkerson (1958), a system of restricted representatives (SRR) with respect to $l$ and $u$ is a sequence $(x_{1},\ldots x_{|J|})$ such that

$$\begin{aligned} x_{j}\in D_{j},l_{d}\le |\{j\in J:x_{j}=d\}|\le u_{d}\text { for all }d\in D=\mathop {\bigcup }\nolimits _{j\in J}D_{j}. \end{aligned}$$

(2)

In this way, each vector $x$ satisfying $cardinality(x,J;l,u)$ is an SRR and vice-versa. Equivalently, a cardinality constraint models transversals (Mirsky 1971) with lower and upper bounds (Schrijver (2004), Theorems 22.17 and 22.18]. We recall that a transversal with respect to the collection of sets $\{D_{j},j\in J\}$ is a sequence of pairwise different elements $(d_{1},\ldots ,d_{|J|})$ such that $d_{j}\in D_{j},$ while a transversal with lower and upper bounds $l,u\in Z_{+}^{|D|}\,$ ($l\le u$) is a sequence $(x_{1},\ldots x_{|J|})$ satisfying (2).

The ‘variable-value’ graph can be generalized for a cardinality system (1), the only difference being that $V_{G}$ now includes one node for each variable occurring in any $J_{c},c\in C.$ For that graph, the problem of simultaneous matchings (Kutz et al. 2008) asks for “a subset of edges that is simultaneously a perfect matching for each constraint set in $C$” (i.e., for each $\{x_{j},j\in J_{c}\},c\in C$)$.$ As observed in Kutz et al. (2008), a solution to this problem corresponds to a solution for multiple alldifferent constraints and vice-versa. Accordingly, a solution of a cardinality system corresponds to a solution to the problem of simultaneous $(\dot{e},l)$-edge covers and $(\dot{e},u)$-matchings (and simultaneous SRRs/transversals) and vice-versa. Since the cardinality system generalizes simultaneous matchings (Kutz et al. 2008, Theorem 1) implies that it remains $NP-complete$ to find a feasible solution to a cardinality system having $|C|\ge 2$ if the domains of the variables are not the same.

In this paper, we pursue a polyhedral study of the cardinality system (and SRRs) by examining the polytope defined by the convex hull of vectors satisfying two cardinality constraints, in the case where all variables share a common domain $D$ of arbitrary, yet pairwise different, real numbers. We establish the dimension of this polytope (Sect. 2) and examine which inequalities of two known families are facet-defining (Sect. 3). Then, we provide a condition for these families to define a convex hull relaxation (Sect. 4).

2 The polytope and its dimension

Let $|C|=2$ and let $J=J_{1}\cup J_{2}$ be the set indexing the variables belonging to at least one of the cardinality constraints. The cardinality system is written as

$$\begin{aligned}&cardinality(x,J_{1};l,u), \end{aligned}$$

(3)

$$\begin{aligned}&cardinality(x,J_{2};l,u), \end{aligned}$$

(4)

$$\begin{aligned}&x_{j}\in D,\forall j\in J. \end{aligned}$$

(5)

Note that the above system assumes that the bounds on the number of occurrences of each domain value are the same for both constraints. However, these bounds can differ from one constraint to the other. Therefore, let us emphasize that this paper concentrates on the case where the bounds are the same for both constraints, since several of the results presented here do not generalize when these bounds differ from one constraint to the other.

Let $J_{1}\cap J_{2}=T$ and $I_{1}=J_{1}\backslash T,I_2=J_{2}\backslash T$, i.e., the set $T$ indexes the variables that are common to both constraints, while $I_{1}$ and $I_{2}$ are the sets of variables appearing exclusively in the first and the second constraint, respectively. Notice that $T=\emptyset$ implies that the constraints are variable-wise disjoint while $I_{1}=\emptyset$ or $I_{2}=\emptyset$ yields $|C|=1,\,$ since one constraint would be ‘dominated’ by the other. Thus, we only consider cardinality systems for which none of $I_{1},I_{2}$ or $T$ is empty. The polytope of two cardinality constraints, namely $P_{I},$ is defined by

$$\begin{aligned} P_{I}=conv\{x\in D^{|J|}:\text { (3), (4) are satisfied}\}. \end{aligned}$$

A point of $P_{I} \cap D^{|J|}$ satisfying (3) and (4) is hereafter called a vertex; i.e., $P_I$ is the convex hull of its vertices. We use the term ‘vertex’ with a slight abuse of terminology, meaning that a vertex here is not necessarily a face of $P_{I}$ with dimension $0$. That is, a vertex is defined here as a point of $P_I$, whose coordinates are all from the set $D$, that is feasible with respect to (3) and (4).

To facilitate our presentation, we denote as $o(x;c,k)$ the number of occurrences of value $d_{k}$ in constraint $c$ at vertex $x,$ i.e., $o(x;c,k)=\left| \{j\in J_{c}:x_{j}=d_{k}\}\right| .$ In addition, we define the following notation to enable us to compactly represent changes to vertices.

Notation

For two vertices $x^{\prime },\tilde{x}\in P_{I}:$

• (i) $\tilde{x}=x^{\prime }(j_{1};d_{k}\rightarrow d_{k^{\prime }})$ denotes that $\tilde{x}$ is derived from $x^{\prime }$ by only changing the value of variable $x_{j_{1}}$ ($j_{1}\in J$) from $d_{k}$ to $d_{k^{\prime }}$ ($\{k,k^{\prime }\}\subseteq K$); i.e., $x_{j_{1}}^{\prime }=d_{k}\ne d_{k^{\prime }}$ while $\tilde{x}_{j_{1}}=d_{k^{\prime }}$ and $\tilde{x}_{j}=x_{j}^{\prime }$ for all $j\in J\backslash \{j_{1}\}.$

• (ii) $\tilde{x}=x^{\prime }(j_{1}\leftrightarrow j_{2})$ denotes that $\tilde{x}$ is derived from $x^{\prime }$ by only swapping the values of variables $x_{j_{1}}$ and $x_{j_{2}}$ ($\{j_{1},j_{2}\}\subseteq J$); i.e., $x_{j_{1}}^{\prime }\ne x_{j_{2}}^{\prime }$ while $\tilde{x}_{j_{1}}=x_{j_{2}}^{\prime },\tilde{x}_{j_{2}}=x_{j_{1}}^{\prime }$ and $\tilde{x}_{j}=x_{j}^{\prime }$ for all $j\in J\backslash \{j_{1},j_{2}\}.$

• (iii) $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},i_{2}\})$ denotes that $\tilde{x}$ is derived from $x^{\prime }$ by only swapping the value of variable $x_{t}$ ($t\in T$) with the common value of variables $x_{i_{1}}$ ($i_{1}\in I_{1}$) and $x_{i_{2}}$ ($i_{2}\in I_{2}$); formally, $x_{i_{1}}^{\prime }=x_{i_{2}}^{\prime }\ne x_{t}^{\prime }$ while $\tilde{x}_{t}=x_{i_{1}}^{\prime },\tilde{x}_{i_{1}}=\tilde{x}_{i_{2}}=x_{t}^{\prime }$ and $\tilde{x}_{j}=x_{j}^{\prime }$ for all $j\in J\backslash \{i_{1},i_{2},t\}.$ Note that this operation will always preserve feasibility.

Examples appear in Table 1, which assumes $D=\{0,1,2,3\}.$

Table 1 A cardinality system of two constraints

Occasionally, it becomes convenient, and unambiguous, to say that a value $d_{k}$ ($k\in K$) appears in $S$ ($S\subseteq J$) at a vertex $x\in P_{I}$ to denote that $x_{j}=d_{k}$ for some $j\in S.$ Accordingly, we may say that a value $d_{k}$ ($k\in K$) appears at least (or at most) $o$ times in $S$ ($S\subseteq J$) in predicate $c$ ($c\in C$) at a vertex $x\in P_{I}$ to denote that $o(x;c,k)\ge o$ ($\le o$).

We assume without loss of generality that $|J_{1}|\le |J_{2}|.$ Then, one may establish that

$$\begin{aligned} P_{I}\ne \emptyset \text { if and only if}\ \mathop {\sum }\nolimits _{k\in K}l_{k}\le |J_{1}|\le |J_{2}|\le \mathop {\sum }\nolimits _{k\in K}u_{k}. \end{aligned}$$

(6)

Let us also stipulate that $0\le l_{k}\le u_{k}$ and $u_{k}\ge 1$ for all $k\in K.$

A degenerate case arises if $l_{k} =|J_{1}|$ for some value $d_{k}.$ In this case, all the variables in the first constraint must receive the same value at all vertices. Thus, the study of $P_{I}$ reduces to the study of a single cardinality constraint. Hence, assume hereafter that $l_{k}<|J_{1}|$ for all $k\in K$. Since $|J_{1}|\le |J_{2}|$, this assumption implies also that $l_{k}<|J_{2}|$ for all $k\in K$.

Let us provide a vertex of $P_I$, which will be used in the following proofs. Let the variables in any $x\in P_{I}$ be indexed, starting with the variables in $I_{1},$ then $T,$ then $I_{2};$ i.e.,

$$\begin{aligned} x=\left( x_{1},\ldots ,x_{|I_{1}|},x_{|I_{1}|+1},\ldots ,x_{|I_{1}|+|T|},x_{|I_{1}|+|T|+1},\ldots ,x_{|I_{1}|+|T|+|I_{2}|}\right) . \end{aligned}$$

(7)

Also, assuming $|D| \ge 2$, let $l_{k_{0}}=\max \{l_{k}:k\in K\}$ and $l_{k_{1}}=\max \{l_{k}:k\in K\backslash \{k_{0}\}\};$ i.e., $d_{k_{0}}$ and $d_{k_{1}}$ are the values with the largest and the second largest lower bounds. For simplicity let $k_{0}=0$ and $k_{1}=1;$ i.e., $l_{0}\ge l_{1}\ge l_{k}$ for all $k\in K\backslash \{0,1\}.$ The same argument works if the domain values $d_{k_{0}}$ and $d_{k_{1}}$ are not the domain values with the lower index.

Now, consider the vertex $x^{\prime }$ with $x_{1}^{\prime }=d_{0},$ $x_{|I_{1}|+|T|}^{\prime }=d_{1},$ variables $x_{2}^{\prime },\ldots ,x_{l_{0}}^{\prime }$ assigned value $d_{0}$ only if $l_{0}>1,$ variables $x_{l_{0}+1}^{\prime },\ldots ,x_{l_{0}+l_{1}-1}^{\prime }$ assigned value $d_{1}$ only if $l_{1}>1,$ and, for each $k=2,\ldots ,|K|-1,$ the next $l_{k}$ variables assigned value $d_{k}.$ Up to this point, the number of variables assigned in $J_{1}$ is

• $2$ (i.e., $x_{1}^{\prime }$ and $x_{|I_{1}|+|T|}^{\prime }$), if $l_{0}=0$ thus $l_{k}=0$ for all $k\in K\backslash \{0\},$ or

• $l_{0}+1,$ if $l_{0}\ge 1$ but $l_{1}=0$ thus $l_{k}=0$ for all $k\in K\backslash \{0,1\},$ or

• $\sum _{k\in K}l_{k},$ if $l_{0}\ge l_{1}\ge 1.$

These variables exist in $J_{1},$ since $|J_{1}| \ge 2$ because $I_{1}$ and $T$ are both non-empty, $|J_{1}|>l_{0}$ by assumption and $|J_{1}|\ge \sum _{k\in K}l_{k}$ by (6). Hence, the number of $m=\max \{\sum _{k\in K}l_{k},l_{0}+1,2\}$ variables assigned so far in $J_{1}$ (i.e., $x_{1}^{\prime },\ldots ,x_{m-1}^{\prime }$ and $x_{|I_{1}|+|T|}^{\prime }$) suffices to satisfy all lower bounds.

Since $|J_{1}|\le \sum _{k\in K}u_{k},$ there are sufficient occurrences of values to be assigned to the remaining variables in $J_{1}.$ Hence the first among the variables $x_{m}^{\prime },\ldots ,x_{|I_{1}|+|T|-1}^{\prime }$ are assigned value $d_{0}$ until $d_{0}$ occurs $u_{0}$ times, the next variables are assigned value $d_{1}$ until $d_{1}$ occurs $u_{1}$ times, and so on, until variable $x_{|I_{1}|+|T|-1}^{\prime }$ is assigned. This assigns values to all variables in $J_{1}=I_{1}\cup T.$

In addition, let $x_{|I_{1}|+|T|+j}^{\prime }=x_{j}^{\prime },j=1,\ldots ,|I_{1}|$ (this is possible since $|I_{1}|\le |I_{2}|$) and all variables $x_{|I_{1}|+|T|+j}^{\prime },j=|I_{1}|+1,\ldots ,|I_{2}|,$ assigned any value $d_{k}$ whose upper bound $u_{k}$ has not been reached. This assignment of values to variables in $J_{2}$ is feasible since setting $x_{|I_{1}|+|T|+j}^{\prime }=x_{j}^{\prime },j=2,\ldots ,|I_{1}|$ satisfies the lower bounds, while $|J_{2}|\le \sum _{k\in K}u_{k}$ implies that there are sufficient occurrences of values in $I_2$ to satisfy the constraint. Therefore, $x^{\prime }$ satisfies (3) and (4), thus it is a vertex of $P_{I}.$

Regarding the example of Table 1 for $l=[0,0,1,0]$ and $u=[1,1,2,1],$ vertex $x^{\prime }$ is obtained by assigning $x_{1}^{\prime }=2$ (since $l_{2}$ is the maximum lower bound), $x_{5}^{\prime }=0$ (i.e., value $0$ plays the role of $d_{1}$), then assigning $x_{2}^{\prime }=2$ to reach the upper bound for value $2$ and $x_{3}^{\prime }=1,x_{4}^{\prime }=3$ to reach the upper bounds for the remaining values; lastly, $x_{5+j}^{\prime }=x_{j}^{\prime },j=1,2,3.$ For $l=[0,0,2,0],u=[2,2,3,1],$ $x^{\prime }$ has $x_{1}^{\prime }=x_{2}^{\prime }=2,$ $x_{5}^{\prime }=0,$ then $x_{3}^{\prime }=2$ and $x_{4}^{\prime }=0$ to reach the upper bounds for values $2$ and $0$ and, lastly, $x_{5+j}^{\prime }=x_{j}^{\prime },j=1,2,3.$

Studying $P_{I}$ becomes meaningful if it contains more than one vertex.

Proposition 1

$P_{I}$ has more than one vertex if and only if $|D|\ge 2$.

Proof

If $D=\{d_{0}\},$ $P_{I}$ has a single vertex $x^{\prime }$ with $x_{j}^{\prime }=d_{0}$ for all $j\in J.$

To show the ‘if’ part, consider the vertex $x^{\prime }$ described above. Observe that $x_{1}^{\prime }=x_{|I_{1}|+|T|+1}^{\prime }=d_{0}$ and $x_{|I_{1}|+|T|}^{\prime }=d_{1}\ne d_{0}.$ The point $\tilde{x}=x^{\prime }(|I_{1}|+|T|\leftrightarrow \{1,|I_{1}|+|T|+1\})$ satisfies (3) and (4) (i.e., $\tilde{x}$ is a vertex of $P_{I}$), since the number of times each value appears in each constraint at $\tilde{x}$ remains as in $x^{\prime }.$ Vertex $x^{\prime }$ is different from $\tilde{x}$, since $x^{\prime }_1=d_0$ whereas $\tilde{x}_1=d_1$. $\square$

It is known (e.g., Schrijver 2004) that $P_{I}$ is full-dimensional if and only if no equality $\alpha x=\alpha _{0}$ is satisfied by all $x\in P_{I}.$ If, for some $c \in C$, $|J_{c}|=\sum _{k\in K}l_{k}$, then each value $d_k$ appears exactly $l_k$ times in $J_c$ at all vertices of $P_I$, thus the equality

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in J_{c}}x_{j}=\mathop {\sum }\nolimits _{k\in K}l_{k}\cdot d_{k} \end{aligned}$$

(8)

is satisfied by all vertices of $P_I$ (and hence by all $x \in P_I$). In a similar manner, $|J_{c}|=\sum _{k\in K}u_{k}$ for some $c \in C$, implies that all $x \in P_I$ satisfy

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in J_{c}}x_{j}=\mathop {\sum }\nolimits _{k\in K}u_{k}\cdot d_{k}. \end{aligned}$$

(9)

On the other hand, if, for all $c \in C$,

$$\begin{aligned} \mathop {\sum }\nolimits _{k\in K}l_{k}<|J_{c}|<\mathop {\sum }\nolimits _{k\in K}u_{k}, \end{aligned}$$

(10)

one would expect that no equality having $\mathop {\sum }\nolimits _{j\in J_{c}}x_{j}$ as its left-hand side is satisfied by all $x \in P_I$. This may not be true, i.e., it may be that, although (10) holds, an equality having $\mathop {\sum }\nolimits _{j\in J_{c}}x_{j}$ as its left-hand side, but with a right-hand side different from (8) and (9), is satisfied by all $x \in P_I$. Let us provide an example.

Example 1

Let $I_{1}=\{1,2\},T=\{3,4\}$ and $I_{2}=\{5,6\},D= \{d_{0},d_{1}\},l=[2,1]$ and $u=[2,6].$ Since $|J_{1}|=4>l_{0}+l_{1}=3,$ the equality $x_{1}+x_{2}+x_{3}+x_{4}=l_{0}d_{0}+l_{1}d_{1}=2d_{0}+d_{1}$ is satisfied by no $x\in P_{I}.$ However, value $d_{0}$ occurring at most twice in $J_{1}$ forces value $d_{1}$ to occur at least twice (despite $l_{1}=1$). Thus, the equality $x_{1}+x_{2}+x_{3}+x_{4}=2(d_{0}+d_{1})$ is satisfied by all $x\in P_{I}.$

Let us add the conditions that, for all $k \in K$,

$$\begin{aligned} l_{k}&\ge |J_{2}|-\mathop {\sum }\nolimits _{k^{\prime }\in K\backslash \{k\}}u_{k^{\prime }}, \end{aligned}$$

(11)

$$\begin{aligned} u_{k}&\le |J_{1}|-\mathop {\sum }\nolimits _{k^{\prime }\in K\backslash \{k\}}l_{k^{\prime }}. \end{aligned}$$

(12)

These conditions can be adopted without loss of generality. If, for example, $l_{k}<|J_{2}|-\mathop {\sum }\nolimits _{k^{\prime }\in K\backslash \{k\}}u_{k^{\prime }},$ value $k$ must appear at least $l_{k}^{^{\prime }}=|J_{2}|-\mathop {\sum }\nolimits _{k^{\prime }\in K\backslash \{k\}}u_{k^{\prime }}$ times, hence replacing $l_{k}$ with $l_{k}^{^{\prime }}$ yields a cardinality system with an identical set of solutions. For Example 1, $l_{1}=1$ is replaced by $l_{1}^{\prime }=2.$ Given (11) and (12), (10) becomes a necessary and sufficient condition for $P_I$ to be full-dimensional.

Theorem 2

$$\begin{aligned} \dim P_{I}=\left\{ \begin{array}{ll} |J| &{} \text {if }\sum _{k\in K}l_{k}<|J_{1}|\le |J_{2}|<\sum _{k\in K}u_{k},\\ |J|-1 &{} \text {if } \sum _{k\in K}l_{k}=|J_{1}|<|J_{2}|<\sum _{k\in K}u_{k},\text { }\\ |J|-1 &{} \text {if } \sum _{k\in K}l_{k}<|J_{1}|<|J_{2}|=\sum _{k\in K}u_{k},\text { }\\ |J|-2\ &{} \text {if }|J_{1}|=|J_{2}|=\sum _{k\in K}l_{k}\\ |J|-2\ &{} \text {if }|J_{1}|=|J_{2}|=\sum _{k\in K}u_{k}\\ |J|-2\ &{} \text {if }|J_{1}|=\sum _{k\in K}l_{k} \text { and }|J_{2}|=\sum _{k\in K}u_{k.} \end{array}\right. \end{aligned}$$

We first provide some preliminary results, with proof, that will be used in the proof of the theorem.

Proposition 3

If equality $\alpha x=\alpha _{0}$ is satisfied by all $x\in P_{I}$ then (i) $\alpha _{i}=\lambda _{c}$ for all $i\in I_{c},c\in C$ and (ii) $\alpha _{t}=\lambda _{1}+\lambda _{2}$ for all $t\in T.$

Proof

To show (i), let $c=1.$ For $|I_{1}|=1,$ the proposition trivially holds. Therefore, assume $|I_{1}|\ge 2.$ Let the variables be indexed as in (7).

Consider the vertices $x^{\prime }$ and $\tilde{x}$ from the proof of Proposition 1 and recall that $x^{\prime }_1=d_0$ and $\tilde{x}_1=d_1$ while $x^{\prime }_2=\tilde{x}_2$. Since variable $x_1$ receives a different value at vertices $x^{\prime }$ and $\tilde{x}$, while variable $x_2$ receives the same value at both $x^{\prime }$ and $\tilde{x}$, $x^{\prime }_1 \ne x^{\prime }_2$ or $\tilde{x}_1 \ne \tilde{x}_2$. Therefore there exists some vertex $\hat{x}$ with $\hat{x}_1 = d_k \ne \hat{x}_2 = d_{k^{\prime }}$. It is clear that the vertex $\bar{x}=\hat{x}(1\leftrightarrow 2)\in P_{I}.$ Since $\alpha x=\alpha _{0}$ for all $x\in P_{I},$ equation $\alpha \hat{x}=\alpha \bar{x}$ yields, after deleting identical terms,

$$\begin{aligned} \alpha _{1}(d_{k}-d_{k^{\prime }})=\alpha _{2}(d_{k}-d_{k^{\prime }}). \end{aligned}$$

Therefore, $\alpha _{1}=\alpha _{2}$ since $d_{k^{\prime }}\ne d_{k}.$ Since index $2$ could have been assigned to any variable in $I_{1}\backslash \{1\},$ all of the coefficients of the variables in $I_{1}$ must be equal to $\alpha _{1}.$ The same reasoning holds for the coefficients associated with the variables in $I_{2}.$ Therefore, let $\lambda _{1}$ and $\lambda _{2}$ be the coefficients of the variables in $I_{1}$ and $I_{2},$ respectively.

To show (ii), take the vertices $x^{\prime }$ and $\tilde{x}$ from the proof of Proposition 1. Then, equation $\alpha x^{\prime }=\alpha \tilde{x}$ yields, after deleting identical terms,

$$\begin{aligned} (\lambda _{1}+\lambda _{2})(d_{0}-d_{1})=\alpha _{|I_{1}|+|T|}(d_{0}-d_{1}), \end{aligned}$$

so that $\alpha _{|I_{1}|+|T|}=\lambda _{1}+\lambda _{2}.$ As any variable with index in $T$ could have been chosen as $x_{|I_{1}|+|T|},$ each such variable’s coefficient must be $\lambda _{1}+\lambda _{2},\,\$finishing the proof. $\square$

For the system of Table 1 and $l=[0,0,1,0],$ $u=[1,1,2,1],$ $\alpha \bar{x}=\alpha \tilde{x}$ yields $\alpha _{1}=\alpha _{2}=\lambda _{1},$ while $\alpha x^{\prime }=\alpha \tilde{x}$ yields $\alpha _{5}=\alpha _{1}+\alpha _{6}=\lambda _{1}+\lambda _{2}.$

Lemma 4

For any vertex $x\in P_{I}$ and $c\in C,$ if $o(x;c,k^{\prime })>l_{k^{\prime }}$ for some $k^{\prime }\in K,$ there is $\tilde{k}\in K\backslash \{k^{\prime }\}$ such that $o(x;c,\tilde{k})<u_{\tilde{k}}.$

Proof

Assuming that $o(x;c,k)=u_{k}$ for all $k\in K\backslash \{k^{\prime }\}$ yields

$$\begin{aligned} |J_{c}|&= \mathop {\sum }\limits _{k\in K\backslash \{k^{\prime }\}}o(x;c,k)+o(x;c,k^{\prime })\\&= \mathop {\sum }\limits _{k\in K\backslash \{k^{\prime }\}}u_{k}+o(x;c,k^{\prime })>\mathop {\sum }\limits _{k\in K\backslash \{k^{\prime }\}}u_{k}+l_{k^{\prime }}\ge |J_{c}|, \end{aligned}$$

a contradiction (notice that the last ‘$\ge$’ follows from (11)). $\square$

Proposition 5

For $c\in C,$ if $\sum _{k\in K}l_{k}<|J_{c}|<\sum _{k\in K}u_{k}$ and $\alpha x=\alpha _{0}$ is satisfied by all $x\in P_{I}$ then $\alpha _{i}=0$ for all $i\in I_{c}.$

Proof

Let $c=1$ and take $x^{\prime }$ from the proof of Proposition 1. Since $\sum _{k\in K}l_{k}<|J_{1}|,$ some value $d_{k^{\prime }}$ appears more that $l_{k^{\prime }}$ times in $J_{1};$ i.e., $o(x;c,k^{\prime })>l_{k^{\prime }}.$ Then, by Lemma 4, $o(x^{\prime };c,\tilde{k})<u_{\tilde{k}}$ for some value $d_{\tilde{k}}\ne d_{k^{\prime }}.$

If value $d_{k^{\prime }}$ appears in $I_{1},$ let $i_1 \in I_1$ be an index where this occurs; i.e., $x_{i_{1}}^{\prime }=d_{k^{\prime }},i_{1}\in I_{1}.$ Observe that $\bar{x}=x^{\prime }(i_{1};d_{k^{\prime }}\rightarrow d_{\tilde{k}})$ is a vertex of $P_{I}$ since $o(\bar{x};1,\tilde{k})=o(x^{\prime };1,\tilde{k})+1\le u_{\tilde{k}}$ and $o(\bar{x};1,k^{\prime })=o(x^{\prime };1,k^{\prime })-1\ge l_{k^{\prime }}.$ Since $\alpha x=\alpha _{0}$ is satisfied by all $x\in P_{I},\alpha x^{\prime }=\alpha \bar{x}$ yields

$$\begin{aligned} \alpha _{i_{1}}d_{k^{\prime }}=\alpha _{i_{1}}d_{\tilde{k}}. \end{aligned}$$

(13)

Otherwise, value $d_{k^{\prime }}$ appears only in $T$ (i.e., $x_{i_{1}}^{\prime }\ne d_{k^{\prime }}$) hence let $t \in T$ be an index where this occurs; i.e., $x_{t}^{\prime }=d_{k^{\prime }},t\in T$. By construction of $x^{\prime },x_{|I_{1}|+|T|+i_{1}}^{\prime }=x_{i_{1}}^{\prime }\ne d_{k^{\prime }}$, hence the vertex $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},|I_{1}|+|T|+i_{1}\})\in P_{I}$ has $\tilde{x}_{i_{1}}=d_{k^{\prime }}.$ As in the argument above, the vertex $\bar{x}=\tilde{x}(i_{1};d_{k^{\prime }}\rightarrow d_{\tilde{k}})\in P_{I},$ thus $\alpha \tilde{x}=\alpha \bar{x}$ yields (13).

Equation (13) yields $\alpha _{i_{1}}=0.$ By Proposition 3i, $\lambda _{1}=0$ hence $\alpha _{i}=0$ for all $i\in I_{1}.$ $\square$

For the system of Table 1 and $l=[0,0,2,0]$ and $u=[2,2,3,1],$ $\alpha x^{\prime }=\alpha \bar{x}$ yields $\alpha _{1}=0.$

Let us now show the proof of Theorem 2.

Proof (Theorem 2)

Consider some equality $\alpha x=\alpha _{0}$ that is satisfied by all $x\in P_{I}$. Then, $\alpha _{j}, j \in J,$ can be expressed in terms of scalars $\lambda _{1}$ and $\lambda _{2}$ as in Proposition 3i–ii.

If $\sum _{k\in K}l_{k}<|J_{1}|\le |J_{2}|<\sum _{k\in K}u_{k},$ Proposition 5 yields that $\alpha _{i}=0$ for all $i\in I_{1}\cup I_{2}$. Hence, Proposition 3i implies $\lambda _1=\lambda _2=0$ and, then, Proposition 3ii yields $\alpha _{t}=0$ for all $t\in T;$ i.e., $\alpha _{j}=0$ for all $j\in J.$ Thus, no equality is satisfied by all $x\in P_{I},$ therefore $P_{I}$ is full-dimensional.

For all other cases, an equality (8) or (9) holds for $J_1$ or $J_2$ (or both).

Regarding the second and the third case of Theorem 2, for which $\dim P_{I}=|J|-1$, let us show the proof only for the third case. Thus, let $\sum _{k\in K}l_{k}<|J_{1}|<|J_{2}|=\sum _{k\in K}u_{k}$. Since $\sum _{k\in K}l_{k}<|J_{1}|<\sum _{k\in K}u_{k}$, Proposition 5 yields $a_i=0$ for all $i \in I_1$, thus Proposition 3i implies $\lambda _{1}=0$. Given that, Proposition 3i-ii yield $\alpha _{j}=\lambda _{2},j\in I_{2}\cup T=J_{2}.$ Notice also that, at any vertex $x$ of $P_{I}$, $|J_{2}|=\sum _{k\in K}u_{k}$ implies that each value $d_{k}$ appears $u_{k}$ times at $J_{2}$. Therefore,

$$\begin{aligned} \alpha _{0}=\alpha x=\mathop {\sum }\nolimits _{j\in I_{1}}\alpha _{j}x_{j}+\mathop {\sum }\nolimits _{j\in J_{2}}\alpha _{j}x_{j}=\mathop {\sum }\nolimits _{j\in J_{2}}\lambda _{2}x_{j}=\lambda _{2}\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k}. \end{aligned}$$

Thus, any $\alpha x=\alpha _{0}$ satisfied by all $x \in P_I$ is a multiple of $\mathop {\sum }\nolimits _{j\in J_{2}}x_{j}=\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k}$. Hence, the latter is the only equality (up to scalar multiplication) satisfied by all $x\in P_{I}$, thus $\dim P_{I}=|J|-1.$ Regarding the second case of Theorem 2, an analogous argument shows that $\alpha _{0}= \lambda _{1}\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}$.

Regarding the last three cases of Theorem 2, for which $\dim P_{I}=|J|-2$, we prove that

$$\begin{aligned} \alpha _{0}=(\lambda _{1}+\lambda _{2})\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k} \end{aligned}$$

for the fourth case,

$$\begin{aligned} \alpha _{0}=(\lambda _{1}+\lambda _{2})\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k} \end{aligned}$$

for the fifth case, and,

$$\begin{aligned} \alpha _{0}=\lambda _{1}\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}+\lambda _{2}\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k} \end{aligned}$$

(14)

for the last case. Let us illustrate the proof only for the last case of Theorem 2, since the remaining cases can be shown in a similar manner. For that case, $|J_{1}|=\sum _{k\in K}l_{k}$ and $|J_{2}|=\sum _{k\in K}u_{k}$ imply that, at any vertex $x \in P_I$, each value $d_{k}$ appears exactly $l_{k}$ times in $J_{1}$ and $u_{k}$ times in $J_{2}.$ Then, using Proposition 3, (14) is written as

$$\begin{aligned} \alpha _{0}&=\alpha x =\mathop {\sum }\nolimits _{j\in I_{1}}\alpha _{j}x_{j}+\mathop {\sum }\nolimits _{j\in T}\alpha _{j}x+\mathop {\sum }\nolimits _{j\in I_{2}}\alpha _{j}x_{j}\\&=\lambda _{1}\mathop {\sum }\nolimits _{j\in I_{1}}x_{j}+(\lambda _{1}+\lambda _{2})\mathop {\sum }\nolimits _{j\in T}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in I_{2}}x_{j}\\&=\lambda _{1}\mathop {\sum }\nolimits _{j\in I_{1}\cup T}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in I_{2}\cup T}x_{j}=\lambda _{1}\mathop {\sum }\nolimits _{j\in J_{1}}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in J_{2}}x_{j}\\&=\lambda _{1}\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}+\lambda _{2}\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k}. \end{aligned}$$

Therefore, any $\alpha x=\alpha _{0}$ satisfied by all $x \in P_{I}$ is a linear combination of the equalities $\mathop {\sum }\nolimits _{j\in J_{1}}x_{j}=\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}$ and $\mathop {\sum }\nolimits _{j\in J_{2}}x_{j}=\mathop {\sum }\nolimits _{k\in K}u_{k}d_{k}$. Thus, these two are the only equalities (up to scalar multiplication) satisfied by all $x\in P_{I}.$ In addition, they are linearly independent, since the sets of variables in their left-hand side are different. That is, since the variables indexed by $I_1$ appear only in the first equality, whereas the variables indexed by $I_2$ appear only in the second one, no equality is linearly dependent on the other. Hence, these equalities form a minimum equation system of rank $2$ for $P_{I}$, thus $\dim P_{I}=|J|-2.$ $\square$

3 Facet-defining inequalities

To identify the facets of $P_{I},$ let us recall some definitions from (Hooker (2012), Sect. 7.10.1). For $c\in C,$

$$\begin{aligned} p_{c}(k)=\min \left\{ u_{k},|J_{c}|-\mathop {\sum }\nolimits _{i=0}^{k-1}p_{c}(i) -\mathop {\sum }\nolimits _{i=k+1}^{|K|-1}l_{i}\right\} ,&k=0,\ldots ,|K|-1, \end{aligned}$$

(15)

$$\begin{aligned} q_{c}(k)=\min \left\{ u_{k},|J_{c}|-\mathop {\sum }\nolimits _{i=k+1}^{|K|-1}q_{c}(i)- \mathop {\sum }\nolimits _{i=0}^{k-1}l_{i}\right\} ,&k=|K|-1,\ldots ,0. \nonumber \\ \end{aligned}$$

(16)

As also discussed in (Hooker (2012), Sect. 7.10.1), $p_{c}(k)$ and $q_{c}(k)$ are the number of occurrences of value $d_{k}$ if $\mathop {\sum }\nolimits _{j\in J_{c}}x_{j}$ is minimized and maximized, respectively.

In more detail, the sum of all $|J_{c}|$ variables of constraint $c\in C$ is minimized once the smallest value $d_{0}$ has the largest number of occurrences, denoted as $p_{c}(0).$ That number cannot be larger than $u_{0}$ and, in addition, it cannot exceed $|J_{c}|-\mathop {\sum }\nolimits _{i=1}^{|K|-1}l_{i},$ since each value $d_{k},k\in K\backslash \{0\}$ must also occur at least $l_{k}$ times. Then, the number of occurrences of value $d_{1}$ is bounded not only by $u_{1}$ but also by $|J_{c}|-p_{c}(0)-\mathop {\sum }\nolimits _{i=2}^{|K|-1}l_{i},$ since value $0$ occurs $p_{c}(0)$ times and each value $d_{k},k\in K\backslash \{0,1\}$ must occur at least $l_{k}$ times. Repeating this procedure for $k=0,\ldots ,|K|-1$ (in that order) yields $p_{c}(k)$ as the number of occurrences of value $d_{k},k\in K$ when $\mathop {\sum }\nolimits _{j\in J_{c}}x_{j}$ is minimized. The, in a sense, inverse procedure computes $q_{c}(k),k=|K|-1,\ldots ,0;$ i.e., the number of occurrences of value $d_{|K|-1}$ in a maximum sum of all variables is computed first, followed by the number of occurrences of value $d_{|K|-2}$ and so on.

For $S\subseteq J_{c}$, let $p_{c}(|S|,k)$ or $q_{c}(|S|,k)$ denote the number of occurrences of value $d_{k}$ once the sum of $|S|$ variables is minimized or maximized, respectively. Hence, for $c\in C$ and $S\subseteq J_{c},$ we define

$$\begin{aligned}&p_{c}(|S|,k)=\min \left\{ p_{c}(k),|S|-\mathop {\sum }\nolimits _{i=0}^{k-1}p_{c}(|S|,i)\right\} ,k=0,\ldots ,|K|-1, \end{aligned}$$

(17)

$$\begin{aligned}&q_{c}(|S|,k)=\min \left\{ q_{c}(k),|S|-\mathop {\sum }\nolimits _{i=k+1}^{|K|-1}q_{c}(|S|,i)\right\} ,k=|K|-1,\ldots ,0. \nonumber \\ \end{aligned}$$

(18)

That is, the sum of variables indexed by $S$ is minimized by selecting value $d_{0}$ $\min \{p_{c}(0),|S|\}$ times, value $d_{1}$ $\min \{p_{c}(1),|S|-p_{c}(|S|,0)\}$ times (since value $d_{0}$ already occurs $p_{c}(|S|,0)$ times in $S$) and so on. Accordingly, this sum is maximized by selecting value $d_{|K|-1}$ $\min \{q_{c}(|K|-1),|S|\},$ value $d_{|K|-2}$ $\min \{q_{c}(|K|-2),|S|-q_{c}(|S|,|K|-1)\}$ times (since value $d_{|K|-1}$ already occurs $q_{c}(|S|,|K|-1)$ times in $S$) and so on.

Notice that $p_{c}(|S|,k)$ and $q_{c}(|S|,k)$ vary not only with respect to $|S|$ but also with respect to $c,$ i.e., to $|J_{c}|.$ Hence, to provide a concise presentation hereafter, let us assume that $|J_{1}|=|J_{2}|=n$ and omit ‘$c$’ from the definitions (15), (16), (17) and (18). The results hold even if $|J_{1}| \ne |J_{2}|.$

Example 2

With respect to the system of Table 1, for $l=[0,0,2,0]$ and $u=[2,2,3,1],$ notice that $p(0)=2,p(1)=1,p(2)=2,p(3)=0.$ Also, $p(3,0)=p(0),p(3,1)=p(1),p(3,2)=p(3,3)=0,$ while $p(4,0)=p(0),p(4,1)=p(1),p(4,2)=1<p(2),p(4,3)=0.$ Moreover, $q(0)=0,q(1)=1,q(2)=3$ and $q(3)=1;$ also, $q(4,3)=1,q(4,2)=3,q(4,1)=q(4,0)=0,$ while $q(3,3)=1,q(3,2)=2,q(3,1)=q(3,0)=0.$

It now becomes apparent that the inequalities

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in S}x_{j}&\ge \mathop {\sum }\nolimits _{k\in K}p(|S|,k)\cdot d_{k},S\subseteq J_{c},c\in C, \end{aligned}$$

(19)

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in S}x_{j}&\le \mathop {\sum }\nolimits _{k\in K}q(|S|,k)\cdot d_{k},S\subseteq J_{c},c\in C, \end{aligned}$$

(20)

are valid for $P_{I}.$ Although the number of inequalities (19) or (20) per constraint is $2^{n}-1$ (i.e., the number of all subsets of an $n$-set except for the empty subset), both families of inequalities are separable in $O(n\log n)$ steps (Hooker (2012), Sect. 7.10.1). For $|S|=1,$ (19) and (20) reduce to the trivial inequalities $d_{0}\le x_{j}\le d_{|K|-1},j\in J.$ Also, $p(n,k)=p(k),q(n,k)=q(k),$ hence for $|S|=n$ (19) and (20) can be written as

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in J_{c}}x_{j}&\ge \mathop {\sum }\nolimits _{k\in K}p(k)\cdot d_{k},c\in C, \end{aligned}$$

(21)

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in J_{c}}x_{j}&\le \mathop {\sum }\nolimits _{k\in K}q(k)\cdot d_{k},c\in C. \end{aligned}$$

(22)

Let us summarize some direct consequences of (15)-(18), to be utilized in the following proofs.

Corollary 6

(i)   $l_{k}\le p(|S|,k)\le p(k)\le u_{k},k\in K,S\subseteq J_{c},c\in C$

• (ii) $l_{k}\le q(|S|,k)\le q(k)\le u_{k},k\in K,S\subseteq J_{c},c\in C$

• (iii) $\mathop {\sum }\nolimits _{k\in K}p(k)=\mathop {\sum }\nolimits _{k\in K}q(k)=n$

• (iv) $\mathop {\sum }\nolimits _{k\in K}p(|S|,k)=\mathop {\sum }\nolimits _{k\in K}q(|S|,k)=|S|,S\subseteq J_{c},c\in C$

The following two lemmas, showing which of inequalities (19) and (20) cannot be facet-defining for $P_{I},$ appear in Mourtos (2013) for the special case where $D=\{0,\ldots ,|D|-1\}=K.$ The proofs for arbitrary $D,$ following analogous arguments, are presented here for completeness.

Lemma 7

(i)   Inequalities (19) are redundant for $2\le |S|\le p(0)$ and for $n-p(|K|-1)\le |S|\le n-1.$

• (ii) Inequalities (20) are redundant for $2\le |S|\le q(|K|-1)$ and for $n-q(0)\le |S|\le n-1.$

Proof

We only show (i), since (ii) can be shown in a similar manner. For $2\le |S|\le p(0),$ (17) implies $p(|S|,0)=|S|$ but $p(|S|,k)=0$ for $k\in K\backslash \{0\}.$ Thus, (19), reduces to

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in S}x_{j}\ge |S|\cdot d_{0}, \end{aligned}$$

hence equals the sum of inequalities $x_{j}\ge d_{0},$ $j\in S.$

For $n-p(|K|-1)\le |S|\le n-1,$ (17) yields $p(|S|,k)=p(k),$ for all $k\in K\backslash \{|K|-1\},$ since $n-p(|K|-1)\le |S|.$ Hence,

$$\begin{aligned} p(|S|,|K|-1)&= \min \{p(|K|-1),|S|-\mathop {\sum }\nolimits _{k\in K\backslash \{|K|-1\}}p(|S|,k)\} \nonumber \\&= \min \{p(|K|-1),|S|-\mathop {\sum }\nolimits _{k\in K\backslash \{|K|-1\}}p(k)\}. \end{aligned}$$

(23)

By Corollary 6iii, $\mathop {\sum }\nolimits _{k\in K\backslash \{|K|-1\}}p(k)=n-p(|K|-1)$ thus (23) becomes

$$\begin{aligned} p(|S|,|K|-1)=\min \{p(|K|-1),|S|-n+p(|K|-1)\}, \end{aligned}$$

implying $p(|S|,|K|-1)=|S|-n+p(|K|-1),$ since $|S|\le n-1.$ But then, (19), written as

$$\begin{aligned} \mathop {\sum }\nolimits _{j\in S}x_{j}\ge (|S|-n+p(|K|-1))\cdot d_{|K|-1}+\mathop {\sum }\nolimits _{k\in K\backslash \{|K|-1\}}p(k)\cdot d_{k}, \end{aligned}$$

can be obtained by adding (21) and inequalities $-x_{j}\ge -d_{|K|-1},j\in J_{c}\backslash S.$ $\square$

Let $P^{l}(S)=\{x\in P_{I}:x$ satisfies (19) at equality$\}$ and $P^{u}(S)=\{x\in P_{I}:x$ satisfies (20) at equality$\}$ be the face defined by (19) and (20), respectively ($S\subseteq J_{c},c\in C$). The faces $P^{l}(J_{c})$ and $P^{u}(J_{c})$ are defined accordingly. Define also $K^{l}(S)=\{k\in K:p(|S|,k)=p(k)\}$ as the subset of values that appear in $S$ at any vertex of $P^{l}(S)$ as many times as they appear in $J_{c}$ at any vertex of $P^{l}(J_{c}).$ The set $K^{u}(S)=\{k\in K:q(|S|,k)=q(k)\}$ has an analogous interpretation.

Lemma 8

(i)   $\mathop {\sum }\nolimits _{k\in K^{l}(S)}p(k)+\mathop {\sum }\nolimits _{k\in K\backslash K^{l}(S)}l_{k}\ge n$ implies $P^{l}(S)\subseteq P^{l}(J_{c})$

• (ii) $\mathop {\sum }\nolimits _{k\in K^{u}(S)}q(k)+\mathop {\sum }\nolimits _{k\in K\backslash K^{u}(S)}l_{k}\ge n$ implies $P^{u}(S)\subseteq P^{u}(J_{c})$

Proof

We only show (i), since the proof of (ii) is almost identical. At an arbitrary vertex $x\in P^{l}(S),$ $o(x;c,k)=p(k)$ for any $k\in$ $K^{l}(S),$ by the definition of $K^{l}(S).$ Also, $o(x;c,k)=l_{k}$ for any $k\in$ $K\backslash K^{l}(S),$ since the opposite, i.e., $o(x;c,k^{\prime })>l_{k^{\prime }}$ for some $k^{\prime }\in$ $K\backslash K^{l}(S),$ yields

$$\begin{aligned} n&= \mathop {\sum }\nolimits _{k\in K}o(x;c,k)=\mathop {\sum }\nolimits _{k\in K^{l}(S)}o(x;c,k)+\mathop {\sum }\nolimits _{k\in K\backslash K^{l}(S)}o(x;c,k)\\&>\mathop {\sum }\nolimits _{k\in K^{l}(S)}p(k)+\mathop {\sum }\nolimits _{k\in K\backslash K^{l}(S)}l_{k}\ge n, \end{aligned}$$

a contradiction. In addition, $p(k)=l_{k}$ for all $k\in$ $K\backslash K^{l}(S),$ since the opposite, i.e., $p(k^{\prime })>l_{k^{\prime }}$ for some $k^{\prime }\in$ $K\backslash K^{l}(S),$ yields (through Corollary 6iii)

$$\begin{aligned} n&= \mathop {\sum }\nolimits _{k\in K}p(k)=\mathop {\sum }\nolimits _{k\in K^{l}(S)}p(k)+\mathop {\sum }\nolimits _{k\in K\backslash K^{l}(S)}p(k)>\mathop {\sum }\nolimits _{k\in K^{l}(S)}p(k)\\&+\mathop {\sum }\nolimits _{k\in K\backslash K^{l}(S)}l_{k}\ge n, \end{aligned}$$

a contradiction. But then, at any vertex $x\in P^{l}(S),$ each value $d_{k}$ appears $p(k)$ times thus $x\in P^{l}(J_{c}).$ Since a face of $P_{I}$ is the convex hull of vertices in it, $P^{l}(S)\subseteq P^{l}(J_{c}).$ $\square$

Example 2

(cont.) Since $p(0)=2,$ Lemma 7i yields that (19) is redundant for $|S|=2.$ By Lemma 8i, since $|S|=3$ implies $K^{l}(S)=\{0,1\}$ and $l_{2}=2,$ $p(3,0)+p(3,1)+l_{2}=5=n$ hence $P^{l}(S)\subseteq P^{l}(J_{c}),c\in C.$ In the same manner, Lemma 8i yields that $P^{l}(S)\subseteq P^{l}(J_{c})$ for $|S|=4.$

Since Lemma 7ii does not apply (because $q(3)=1$ and $q(0)=0$), (19) is not redundant for $|S|\in \{4,3,2\}.$ Also, $K^{u}(S)=\{2,3\}$ for $|S|=4$ and $K^{u}(S)=\{3\}$ for $|S|=3,2,$ thus no $P^{l}(S)$ for $|S|\in \{4,3,2\}$ is contained in $P^{l}(J_{c}),c\in C$ by Lemma 8ii (observe that $q(3)+l_{2}=3<n$).

Note that Lemmas 7 and 8 hold irrespectively of whether $|C|=2$ or $|J_{1}|=|J_{2}|=n$, since neither condition is assumed within the corresponding proofs.

Let us discuss the consequences of $|J_{1}|=|J_{2}|=n$. Given $|J_{1}|=|J_{2}|=n$, if $|J_{1}|=\sum _{k\in K}l_{k}$ then $|J_{2}|=\sum _{k\in K}l_{k}$, hence each value $d_k$ appears exactly $l_k$ times in both $J_1$ and $J_2$ at any vertex of $P_I$. Then, it can only be that $l_k=u_k$ for all $k \in K$ (this follows also from (11) and (12)). Hence, $|J_{1}|=\sum _{k\in K}l_{k}$, given $|J_{1}|=|J_{2}|=n$, implies $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$, in which case (8) coincides with (9) for both $J_1$ and $J_2$.

In addition, $|J_{1}|=|J_{2}|$ yields that (8) holds for $J_{1}$ if and only if it holds also for $J_{2}$. Thus, $\dim P_{I}\in \{|J|,$ $|J|-2\}$. Notice that, if $\dim P_{I}=|J|-2$ (i.e., if $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$), equalities (8) for $J_1$ and $J_2$ are part of the minimum equation system of $P_{I}$, thus not defining proper faces of $P_I$ (i.e., $P^{l}(J_{1})=P^{l}(J_{2})=P_I$).

Now, $P^{l}(S)$ cannot be a facet of $P_{I}$ if (19) is redundant or $P^{l}(S)$ is contained in another proper face of $P_{I}$. Thus, Lemmas 7 and 8 provide conditions under which $P^{l}(S)$ is not a facet of $P_{I}$. Specifically, Lemma 8 provides a condition under which $P^l(S)$ is contained in the face $P^{l}(J_1)$ or $P^{l}(J_2)$. Therefore, if $P^{l}(J_1)$ and $P^{l}(J_2)$ are proper faces of $P_I$, Lemma 8 (if its condition holds) yields that $P^l(S)$ is not a facet. However, if $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$, both $P^{l}(J_1)$ and $P^{l}(J_2)$ are not proper faces of $P_{I}$ (because $P^{l}(J_{1})=P^{l}(J_{2})=P_I$), hence Lemma 8, even if its condition holds, does not yield that $P^l(S)$ is not a facet. That is, Lemma 8 may yield that $P^l(S)$ is not a facet only if $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$. Following the same reasoning, we add the condition that, if $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$, then $S$ is not equal to $J_1$ or $J_2$. Let us introduce a definition encompassing all these conditions, listed here only for $P^l(S)$.

Definition 9

For $c\in C$, an $S\subseteq J_{c}$ is non-dominated with respect to (19) if $S$ satisfies the following:

• (i) $p(0)<|S|<n-p(|K|-1)$ or $|S|=1$ or $|S|=n$;

• (ii) if $\sum \nolimits _{k\in K}l_{k}<n<\sum \nolimits _{k\in K}u_{k}$, then $P^{l}(S) \not \subset P^{l}(J_c)$;

• (iii) if $\sum \nolimits _{k\in K}l_{k}=n=\sum \nolimits _{k\in K}u_{k}$, then $S \subset J_c$.

Theorem 10

For $c\in C$ if $S\subseteq J_{c}$ is non-dominated then $P^{l}(S)$ is a facet of $P_{I}$; i.e.,

$$\begin{aligned} \dim P^{l}(S)=\left\{ \begin{array}{ll} |J|-1 &{} \text {if }\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k},\\ |J|-3\text { } &{} \text {otherwise.}\end{array}\right. \end{aligned}$$

We prove Theorem 10 only for $P^{l}(S),$ after proving some intermediate results.

Lemma 11

For $c \in C$, let $S\subseteq J_{c}$ be non-dominated. If $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$, there is a vertex $x \in P^{l}(S)$ such that $o(x;c,k)>l_k$ for some value $d_k$ $(k \in K)$ appearing in $J_c \backslash S$.

Proof

Let $c=1$ and $S\subseteq J_{1}.$ Assume to the contrary that, at any vertex $x \in P^{l}(S)$, $o(x;1,k)=l_{k}$ for any value $d_{k}$ appearing in $J_{1}\backslash S.$ This implies that, at any vertex $x \in P^{l}(S)$, any value $d_{k}$ such that $o(x;1,k)>l_{k}$ appears only in $S$. Then, since by (17) a value $d_k$ appears $p(|S|,k)$ times in $S$, it follows that $o(x;1,k)=p(|S|,k)$ for any value $d_{k}$ such that $o(x;1,k)>l_{k}$. Let $K_{S}=\{k\in K:d_k \text { appears only in } S\}$ and notice that the above imply

$$\begin{aligned} n&= \mathop {\sum }\limits _{k\in K}o(x;1,k)=\mathop {\sum }\limits _{k\in K_{S}}o(x;1,k)+\mathop {\sum }\limits _{k\in K\backslash K_{S}}o(x;1,k)\nonumber \\&= \mathop {\sum }\limits _{k\in K_{S}}p(|S|,k)+\mathop {\sum }\limits _{k\in K\backslash K_{S}}l_{k}. \end{aligned}$$

(24)

By Corollary 6i, $p(k)\ge p(|S|,k)\ge l_{k}$ for all $k\in K.$ It must be that $p(k)=p(|S|,k)$ for all $k\in K_{S}$ and $p(k)=l_{k}$ for all $k\in K\backslash K_{S}$ since the opposite (i.e., $p(k^{\prime })>p(|S|,k^{\prime })$ for some $k^{\prime }\in K_{S}$ or $p(k^{\prime })>l_{k^{\prime }}$ for some $k^{\prime }\in K\backslash K_{S}$) yields through (24) and Corollary 6iii,

$$\begin{aligned} n=\mathop {\sum }\limits _{k\in K}p(k)=\mathop {\sum }\limits _{k\in K_{S}}p(k)+\mathop {\sum }\limits _{k\in K\backslash K_{S}}p(k)>\mathop {\sum }\limits _{k\in K_{S}}p(|S|,k)+\mathop {\sum }\limits _{k\in K\backslash K_{S}}l_{k}=n, \end{aligned}$$

a contradiction. But then, at any vertex $x\in P^{l}(S),$ each value $d_{k}$ appears $p(k)$ times in $J_1$ thus $x\in P^{l}(J_{1}).$ It follows that $P^{l}(S)\subseteq P^{l}(J_{1})$, which, given $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$, contradicts Definition 9ii. $\square$

Proposition 12

For $c\in C,$ let $S\subseteq J_{c}$ be non-dominated. If $|J_{c}\backslash S|\ge 2$ (resp. $|I_{c}\backslash S|\ge 2$), there is a vertex of $P^{l}(S)$ at which two different values appear in $J_{c}\backslash S$ (resp. $I_{c}\backslash S$).

Proof

Let $c=1$, $S\subseteq J_{1}$, $|J_{1}\backslash S|\ge 2$ and $|I_{1}\backslash S|\ge 2$. We first show that there is a vertex of $P^{l}(S)$ at which two different values appear in $J_{1}\backslash S.$

For $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$, Corollary 6i yields $l_k=p(k)=u_k$ for all $k \in K$. That is, at any vertex $x \in P^l(S)$, each value $d_k$ appears exactly $p_k=u_k \ge 1$ times in $J_1$, hence value $d_{|K|-1}$ appears at least once in $J_1$. Since $P^l(S)$ contains the vertices minimizing the sum of variables indexed by $S$, value $d_{|K|-1}$ appears in $J_1 \backslash S$ because it is the largest domain value (hence the last one considered by (17)). Also, since value $d_{|K|-1}$ appears $p(|K|-1)$ times in $J_1$, while the set $J_1 \backslash S$ contains $|J_1| - |S|=n - |S|$ variables and $n-|S|>p(|K|-1)$ (by Definition 9i), not all variables in $J_1 \backslash S$ can receive value $d_{|K|-1}$. Thus, $d_{|K|-1}$ and some other value appear in $J_1 \backslash S$.

For $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$, Lemma 11 implies that there is a vertex $x \in P^{l}(S)$ such that $o(x;1,k^{\prime })>l_{k^{\prime }}$ for some value $d_{k^{\prime }}$ appearing in $J_1 \backslash S$. Then, Lemma 4 implies that there is a $\tilde{k}\in K\backslash \{k^{\prime }\}$ such that $o(x;1,\tilde{k})<u_{\tilde{k}}.$ The vertex $\check{x}$ with $\check{x}_{j}=x_{j},j\in J_{1},$ and $\check{x}_{|I_{1}|+|T|+j}=x_{j},j=1,\ldots ,|I_{1}|,$ also belongs to $P^{l}(S)$ since all variables indexed by $S\subseteq J_{1}$ are as in $x\in P^{l}(S).$ By construction of $\check{x}$, $o(\check{x};1,k)=o(\check{x};2,k)$ for all $k\in K,$ hence $o(\check{x};1,k^{\prime })=o(\check{x};2,k^{\prime })>l_{k^{\prime }}$ and $o(\check{x};1,\tilde{k})=o(\check{x};2,\tilde{k})<u_{\tilde{k}}$. If a single value appears in $J_1 \backslash S$ at $\check{x}$ then $\check{x}_{j_{1}}=\check{x}_{j_{2}}=d_{k^{\prime }}$ for some $j_{1},j_{2}\in J_{1}\backslash S$ ($j_{1},j_{2}$ exist because $|J_{1}\backslash S| \ge 2$). The vertex $\bar{x}=\check{x}(j_{1};d_{k^{\prime }}\rightarrow d_{\tilde{k}})$ belongs to $P^{l}(S)$ since all variables indexed by $S$ are as in $\check{x}\in P^{l}(S).$ Moreover, $\bar{x}_{j_{1}}=d_{\tilde{k}}$ and $\bar{x}_{j_{1}}=d_{k^{\prime }}$ thus two different values appear in $J_{1}\backslash S$ at vertex $\bar{x}\in P^{l}(S).$

Hence, let $\bar{x}\in P^{l}(S)$ denote a vertex at which two different values appear in $J_{1}\backslash S.$ It remains to show that there is a vertex of $P^{l}(S)$ at which two different values appear in $I_{1}\backslash S.$ Assume that this does not hold for vertex $\bar{x}.$ Consider the vertex $x^{\prime }\in P^{l}(S)$ with $x_{j}^{\prime }=\bar{x}_{j},j\in J_{1},$ and $x_{|I_{1}|+|T|+j}^{\prime }=\bar{x}_{j},j=1,\ldots ,|I_{1}|;$ i.e., $o(x^{\prime };1,k)=o(x^{\prime };2,k)$ for all $k\in K.$ Since at vertex $x^{\prime }$ two different values appear in $J_{1}\backslash S$ but not in $I_{1}\backslash S,$ a value appearing in $T\backslash S$ differs from a value appearing in $I_{1}\backslash S.$ Hence let $x_{i_{1}}^{\prime }=x_{i_{2}}^{\prime }=d_{k^{\prime }}$ and $x_{t}^{\prime }=d_{\tilde{k}}\ne d_{k^{\prime }},$ where $i_{1},i_{2}\in I_{1}\backslash S$ (since $|I_{1}\backslash S|\ge 2$) and $t\in T\backslash S.\,\$By construction of $x^{\prime },x_{|I_{1}|+|T|+i_{1}}^{\prime }=d_{k^{\prime }}$ hence the vertex $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},|I_{1}|+|T|+i_{1}\})$ belongs to $P^{l}(S)$ and has $\tilde{x}_{i_{1}}=d_{\tilde{k}}$ and $\tilde{x}_{i_{2}}=d_{k^{\prime }}.$ $\square$

Proposition 13

For $c\in C,$ let $S\subseteq J_{c}$ be non-dominated. If $\alpha x=\alpha _{0}$ for all $x\in P^{l}(S)$ then

$\begin{array}{ll} (i) &{} \alpha _{i}=\lambda _{c},i\in I_{c}\backslash S, \\ (ii)\text { } &{} \alpha _{t}=\lambda _{1}+\lambda _{2},t\in T\backslash S, \\ (iii) &{} \alpha _{i}=\lambda _{c}+\mu ,i\in I_{c}\cap S,\text { } \\ (iv) &{} \alpha _{t}=\lambda _{1}+\lambda _{2}+\mu ,t\in T\cap S.\end{array}$

Proof

Let $S\subseteq J_{1}.$

• (i) $\alpha _{i}=\lambda _{1},i\in I_{1}\backslash S$

Take vertex $\tilde{x}$ from the proof of Proposition 12. It is clear that the vertex $\bar{x}=\tilde{x}(i_{1}\leftrightarrow i_{2})\in P^{l}(S).$ Since $\alpha x=\alpha _{0}$ for all $x\in P^{l}(S),\alpha x^{\prime }=\alpha \tilde{x}$ yields, after deleting identical terms,

$$\begin{aligned} \alpha _{i_{1}}(d_{k^{\prime }}-d_{\tilde{k}})=\alpha _{i_{2}}(d_{k^{\prime }}-d_{\tilde{k}}). \end{aligned}$$

Therefore, $\alpha _{i_{1}}=\alpha _{i_{2}}$ since $d_{\tilde{k}}\ne d_{k^{\prime }}.$ Since index $i_{2}$ could have been assigned to any variable in $(I_{1}\backslash S)\backslash \{i_{1}\},$ all of the coefficients of the variables in $I_{1}\backslash S$ must be equal to $\alpha _{i_{1}}.$

Regarding the coefficients associated with the variables in $I_{2},$ let $i_{3}=|I_{1}|+|T|+i_{1}$ and $i_{4}=|I_{1}|+|T|+i_{2}.$ Recall that, by construction of $\tilde{x},\tilde{x}_{i_{3}}=\tilde{x}_{i_{1}}=d_{\tilde{k}}$ and $\tilde{x}_{i_{4}}=\tilde{x}_{i_{2}}=d_{k^{\prime }}.$ Since the vertex $\bar{x}=\tilde{x}(i_{3}\leftrightarrow i_{4})\in P^{l}(S),\alpha x=\alpha _{0}$ yields $\alpha _{i_{3}}=\alpha _{i_{4}}.$ Since $i_{4}$ could have been assigned to any variable in $I_{2}\backslash \{i_{3}\},$ all of the coefficients of the variables in $I_{2}$ must be equal to $\alpha _{i_{3}}.$

Therefore, let $\lambda _{1}$ and $\lambda _{2}$ be the coefficients of the variables in $I_{1}$ and $I_{2},$ respectively.

• (ii) $\alpha _{t}=\lambda _{1}+\lambda _{2},t\in T\backslash S$

Take vertices $x^{\prime },\tilde{x}\in P^{l}(S)$ from the proof of Proposition 12. Since $\alpha x=\alpha _{0}$ for all $x\in P^{l}(S),\alpha x^{\prime }=\alpha \tilde{x}$ yields, after deleting identical terms,

$$\begin{aligned} \alpha _{t}(d_{k^{\prime }}-d_{\tilde{k}})=\left( \alpha _{i_{1}}+\alpha _{|I_{1}|+|T|+i_{1}}\right) (d_{k^{\prime }}-d_{\tilde{k}}). \end{aligned}$$

Therefore, $d_{\tilde{k}}\ne d_{k^{\prime }}$ implies $\alpha _{t}=\lambda _{1}+\lambda _{2}.$ As any variable with index in $T\backslash S$ could be chosen as $x_{t},$ each such variable’s coefficient must be $\lambda _{1}+\lambda _{2}.$

• (iii) $\alpha _{i}=\lambda _{1}+\mu ,i\in I_{1}\cap S$

The proof for $|I_{1}\cap S|=1$ is trivial, thus assume $|I_{1}\cap S|\ge 2.$ Take vertex $x^{\prime }\in P^{l}(S)$ from the proof of Proposition 12. Definition 9i (i.e., $p(0)<|S|$) yields that $d_{0}$ and some other value, say $d_{1},$ appear in $J_{1}\cap S$ at $x^{\prime }.$ Thus let $x_{i_{1}}^{\prime }=d_{0},i_{1}\in I_{1}\cap S$ and $i_{2}\in (I_{1}\cap S)\backslash \{i_{1}\}.\$

If value $d_{1}$ appears in $I_{1}\cap S,$ consider $x_{i_{2}}^{\prime }.$ If $x_{i_{2}}^{\prime }=d_{1},$ the vertex $\bar{x}=x^{\prime }(i_{1}\leftrightarrow i_{2})\in P^{l}(S),$ since the values appearing in $S$ are as in $x^{\prime }.$ Since $\alpha x=\alpha _{0}$ for all $x\in P^{l}(S),\alpha x^{\prime }=\alpha \bar{x}$ yields

$$\begin{aligned} \alpha _{i_{1}}(d_{0}-d_{1})=\alpha _{i_{2}}(d_{0}-d_{1}) \end{aligned}$$

(25)

Otherwise, let $i_{3}\in (I_{1}\cap S)\backslash \{i_{1},i_{2}\}$ such that $x_{i_{3}}^{\prime }=d_{1}.$ The vertex $\check{x}=x^{\prime }(i_{2}\leftrightarrow i_{3})\in P^{l}(S)$ has $\check{x}_{i_{1}}=d_{0}$ and $\check{x}_{i_{2}}=d_{1}.$ After deriving the vertex $\bar{x}=\check{x}(i_{1}\leftrightarrow i_{2})\in P^{l}(S),$ $\alpha \check{x}=\alpha \bar{x}$ yields (25).

If value $d_{1}$ appears in $T\cap S,$ let $x_{t}^{\prime }=d_{1},t\in (T\cap S).$ Recall that, by construction of $x^{\prime },$ $x_{|I_{1}|+|T|+i_{1}}^{\prime }=x_{i_{1}}^{\prime }=d_{0}.$ Thus, the vertex $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},|I_{1}|+|T|+i_{1}\})$ belongs to $P^{l}(S)$ and has $\tilde{x}_{i_{1}}=d_{1}$ and $\tilde{x}_{i_{2}}=d_{0}.$ After deriving the vertex $\bar{x}=\tilde{x}(i_{1}\leftrightarrow i_{2})\in P^{l}(S),\alpha \tilde{x}=\alpha \bar{x}$ yields (25).

For all cases, (25) implies $\alpha _{i_{1}}=\alpha _{i_{2}}.$ Since index $i_{2}$ could have been assigned to any variable in $(I_{1}\cap S)\backslash \{i_{1}\},$ all of the coefficients of the variables in $I_{1}\cap S$ must be equal to $\alpha _{i_{1}}.$

• (iv) $\alpha _{t}=\lambda _{1}+\lambda _{2}+\mu ,t\in T\cap S$

Take the vertices $x^{\prime }$ and $\tilde{x}$ from the proof of (iii). Since $\alpha x=\alpha _{0}$ for all $x\in P^{l}(S),\alpha x^{\prime }=\alpha \tilde{x}$ yields $\alpha _{t}=\alpha _{i_{1}}+\alpha _{|I_{1}|+|T|+i_{1}}.$ Because $i_{1}\in I_{1}\cap S$ and $|I_{1}|+|T|+i_{1}\in I_{2},$ the result follows from (i) and (iii). $\square$

Example 2

(cont.) Considering Table 1, for $l=[0,0,2,0]$ and $u=[2,2,3,1],$ recall that no inequality (19) for $|S|=2,3,4$ is facet-defining. Hence let $S=J_{1}.$ The vertex $\check{x},$ appearing last in Table 1, belongs to $P^{l}(S)$ thus let $\check{x}$ play the role of $x^{\prime }$ in the proof of Proposition 13. After deriving vertex $\bar{x}=\check{x}(1\leftrightarrow 3),$ $\alpha \check{x}=\alpha \bar{x}$ yields $\alpha _{1}=\alpha _{3}.$ After deriving vertex $\tilde{x}=\check{x}(4\leftrightarrow \{1,6\}),\alpha \check{x}=\alpha \tilde{x}$ yields $\alpha _{4}=\alpha _{1}+\alpha _{6}.$ Notice that all vertices derived belong to $P^{l}(S).$

Proposition 14

For $c\in C,$ let $S\subseteq J_{c}$ be non-dominated. If $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$ and $\alpha x=\alpha _{0}$ is satisfied by all $x\in P^{l}(S)$ then $\alpha _{i}=0$ for all $i\in I_{c}\backslash S.$

Proof

Let $c=1$ and $S\subseteq J_1$. Since $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$, Lemma 11 implies that there is a vertex $x \in P^{l}(S)$ such that some value $d_{k^{\prime }}$ appears in $J_1 \backslash S$ and $o(x;1,k^{\prime })<l_{k^{\prime }}, k^{\prime }\in K$. Then, Lemma 4 implies that that $o(x;1,\tilde{k})<u_{\tilde{k}}$ for some value $d_{\tilde{k}}\ne d_{k^{\prime }}.$

Consider the vertex $x^{\prime }\in P^{l}(S)$ with $x_{j}^{\prime }=x_{j},j\in J_{1}$ and $x_{|I_{1}|+|T|+j}^{\prime }=x_{j}^{\prime },j=1,\ldots ,|I_{1}|.$ If value $d_{k^{\prime }}$ appears in $I_{1}\backslash S$ let $x_{i_{1}}^{\prime }=d_{k^{\prime }},i_{1}\in I_{1}\backslash S,$ and observe that $\tilde{x}=x^{\prime }(i_{1};d_{k^{\prime }}\rightarrow d_{\tilde{k}})\in P^{l}(S)$ since no variable indexed by $S$ changes its value. Since $\alpha x=\alpha _{0}$ is satisfied by all $x\in P^{l}(S),\alpha x^{\prime }=\alpha \tilde{x}$ yields, after deleting identical terms,

$$\begin{aligned} \alpha _{i_{1}}d_{k^{\prime }}=\alpha _{i_{1}}d_{\tilde{k}}. \end{aligned}$$

(26)

Otherwise, value $d_{k^{\prime }}$ appears in $T\backslash S$ hence $x_{t}^{\prime }=d_{k^{\prime }},t\in T\backslash S$ and $x_{i_{1}}^{\prime }\ne d_{k^{\prime }}.$ By construction of $x^{\prime },x_{|I_{1}|+|T|+i_{1}}^{\prime }=x_{i_{1}}^{\prime }\ne d_{k^{\prime }}$ hence the vertex $\bar{x}=x^{\prime }(t\leftrightarrow \{i_{1},|I_{1}|+|T|+i_{1}\})\in P^{l}(S)$ has $\bar{x}_{i_{1}}=d_{k^{\prime }}.$ It is clear that the vertex $\tilde{x}=\bar{x}(i_{1};d_{k^{\prime }}\rightarrow d_{\tilde{k}})\in P^{l}(S),$ thus $\alpha \bar{x}=\alpha \tilde{x}$ yields (26).

Thus, (26) yields $\alpha _{i_{1}}=0.$ By Proposition 13i, $\lambda _{1}=0$ hence $\alpha _{i}=0$ for all $i\in I_{1}\backslash S.$ $\square$

Let us now show the proof of Theorem 10.

Proof (Theorem 10)

Assume that $\alpha x=\alpha _{0}$ holds for all $x\in P^{l}(S)$.

For $\sum _{k\in K}l_{k}<n<\sum _{k\in K}u_{k}$, Proposition 14 yields that $\alpha _{i}=0,i\in (I_{1}\cup I_{2})\backslash S,$ hence $\lambda _{1}=\lambda _{2}=0$ by Proposition 13i and $\alpha _{t}=0,t\in T\backslash S$ by Proposition 13ii; i.e., $\alpha _{j}=0$ for all $j\in J\backslash S.$ Also, Proposition 13iii–iv yield that $\alpha _{j}=\mu$ for all $j\in S.$ Therefore, (19) is the only equality (up to scalar multiplication) satisfied by all $x\in P^{l}(S),$ thus $\dim P^{l}(S)=\dim P_{I}-1.$

For $\sum _{k\in K}l_{k}=n=\sum _{k\in K}u_{k}$, recall that equality (8) (which coincides with (9)) holds for both $J_1$ and $J_2$. We show that $\alpha x=\alpha _{0}$ is a linear combination of (8) for $J_1,J_2$ and (19) taken as equality. Since $\alpha _j,j \in J$, can be expressed in terms of scalars $\lambda _{1},\lambda _{2}$ and $\mu$ as in Proposition 13i–iv, it remains to show that, using these scalars, $\alpha _{0}$ is a linear combination of the right-hand sides of equality (19) and equalities (8) for $J_1$, $J_2$. Notice that $S=J_{1}$ and $S=J_{2}$ are dominated in this case, since falsifying Definition 9iii. Thus, let without loss of generality $S\subset J_{1}$ hence $I_{2}\cap S=\emptyset$. Then, given that each value $d_{k}$ appears exactly $l_{k}$ times in both $J_{1}$ in $J_{2}$,

$$\begin{aligned} \alpha _{0}&= \alpha x=\mathop {\sum }\nolimits _{j\in I_{1}}\alpha _{j}x_{j}+\mathop {\sum }\nolimits _{j\in T}\alpha _{j}x+\mathop {\sum }\nolimits _{j\in I_{2}}\alpha _{j}x_{j}\\&= \mathop {\sum }\nolimits _{j\in I_{1}\cap S}\alpha _{j}x_{j}+\mathop {\sum }\nolimits _{j\in I_{1}\backslash S}\alpha _{j}x_{j}+\mathop {\sum }\nolimits _{j\in T\cap S}\alpha _{j}x_{j}\\&+\mathop {\sum }\nolimits _{j\in T\backslash S}\alpha _{j}x +\mathop {\sum }\nolimits _{j\in I_{2}}\alpha _{j}x_{j} \\&= (\lambda _{1}+\mu )\mathop {\sum }\nolimits _{j\in I_{1}\cap S}x_{j}+\lambda _{1}\mathop {\sum }\nolimits _{j\in I_{1}\backslash S}x_{j}+(\lambda _{1}+\lambda _{2}+\mu )\mathop {\sum }\nolimits _{j\in T\cap S}x_{j}+(\lambda _{1}\\&+\lambda _{2})\mathop {\sum }\nolimits _{j\in T\backslash S}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in I_{2}}x_{j}\\&= \lambda _{1}\mathop {\sum }\nolimits _{j\in I_{1}}x_{j}+\mu \mathop {\sum }\nolimits _{j\in I_{1}\cap S}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in I_{2}}x_{j}+(\lambda _{1}\\&+\lambda _{2})\mathop {\sum }\nolimits _{j\in T}x_{j}+\mu \mathop {\sum }\nolimits _{j\in T\cap S}x_{j}\\&= \lambda _{1}\mathop {\sum }\nolimits _{j\in I_{1}\cup T}x_{j}+\lambda _{2}\mathop {\sum }\nolimits _{j\in I_{2}\cup T}x_{j}+\mu \mathop {\sum }\nolimits _{j\in S}x_{j}=\lambda _{1}\mathop {\sum }\nolimits _{j\in J_{1}}x_{j}\\&+\lambda _{2}\mathop {\sum }\nolimits _{j\in J_{2}}x_{j}+\mu \mathop {\sum }\nolimits _{j\in S}x_{j}\\&= \lambda _{1}\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}\\&+\lambda _{2}\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}+\mu \mathop {\sum }\nolimits _{k\in K}p(|S|,k)\cdot d_{k}. \end{aligned}$$

It follows that $\alpha x=\alpha _{0}$ is a linear combination of $\mathop {\sum }\nolimits _{j\in J_{1}}x_{j}=\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k}$, $\mathop {\sum }\nolimits _{j\in J_{2}}x_{j}=\mathop {\sum }\nolimits _{k\in K}l_{k}d_{k},$ and (19) taken as equality. Thus, these are the only three equalities (up to scalar multiplication) satisfied by all $x\in P^{l}(S)$. Since they are also linearly independent, the minimum equation system for $P^{l}(S)$ is of rank $3$ and $\dim P^{l}(S)=|J|-3=\dim P_{I}-1,$ by Theorem 2. $\square$

4 A convex hull relaxation

In this section we show the following.

Theorem 15

If $l_{k}=0$ for all $k\in K,P_{I}$ is described by inequalities (19) and (20).

To prove this, we show that the face of $P_{I}$ defined by any inequality, which is valid for $P_I$, is contained in a face defined by (19) or (20). We illustrate the result with respect to an inequality $\alpha x\ge \beta$ ($\alpha \in \mathbb {R}^{\left| J\right| },\beta \in \mathbb {R}^{+}$), since the proof for an inequality $\alpha x\le \beta$ ($\alpha \in \mathbb {R}^{\left| J\right| },\beta \in \mathbb {R}^{+}$) is analogous. Let $P^{(\alpha ,\beta )}=\{x\in P_{I}:\alpha x=\beta \}$ be the face of $P_{I}$ induced by $\alpha x\ge \beta .$ To prove Theorem 15, it suffices to show that all vertices in $P^{(\alpha ,\beta )}$ also satisfy at equality one of (19) or (20), since any face of $P_{I}$ is the convex hull of vertices appearing in it.

Let $J_{1}^{*}, J_{2}^{*}, T^{*}$ and $J_{2}^{\prime }$ be subsets of variables that, as shown later in this section, are defined in terms of vector $\alpha$ (for simplicity, we omit $\alpha$ from the notation).

Theorem 16

Assume $l_{k}=0$ for all $k\in K.$ If $J_{2}^{*}\not \subset J_{1}^{*}$ or $|J_{1}^{*}|+|J_{2}^{\prime }\backslash T^{*}|\le \mathop {\sum }\nolimits _{k\in K}u_{k}-1,$ all vertices of $P^{(\alpha ,\beta )}$ satisfy at equality (19) for $S=J_{1}^{*}.$

Notice that the negation of the condition in Theorem 16 reads ‘if $J_{2}^{*}\subset J_{1}^{*}$ and $|J_{1}^{*}|+|J_{2}^{\prime }\backslash T^{*}|\ge \mathop {\sum }\nolimits _{k\in K}u_{k}$’. Thus, the following result completes the proof of Theorem 15.

Theorem 17

Assume $l_{k}=0$ for all $k\in K.$ If $J_{2}^{*}\subset J_{1}^{*}$ and $|J_{1}^{*}|+|J_{2}^{\prime }\backslash T^{*}|\ge \mathop {\sum }\nolimits _{k\in K}u_{k},$ all vertices of $P^{(\alpha ,\beta )}$ satisfy (20) for $S=J_{2}^{\prime }\backslash T^{*}$ at equality.

That is, given any $\alpha x\ge \beta$, all vertices in $P^{(\alpha ,\beta )}$ satisfy Eq. (19) with $S=J_1^{*}$ or Eq. (20) with $S = J_2^{\prime } \backslash T^{*}$, based on the conditions of Theorems 16 and 17, respectively.

To introduce the notation that is necessary for showing these theorems, define

$$\begin{aligned} \gamma _{T}(\alpha )&= \max \{0,\max \{\alpha _{t}:t\in T\}\}, \end{aligned}$$

(27)

$$\begin{aligned} \gamma _{c}(\alpha )&= \max \{0,\max \{\alpha _{i}:i\in I_{c}\}\},c\in C, \end{aligned}$$

(28)

$$\begin{aligned} \gamma (\alpha )&= \max \{\gamma _{T}(\alpha ),\gamma _{1}(\alpha )+\gamma _{2}(\alpha )\}. \end{aligned}$$

(29)

Notice that at least one entry of vector $\alpha$ must be positive, since otherwise the inequality is of the ‘$\le$’ type. This implies that at least one of $\gamma _{T}(\alpha ),\gamma _{1}(\alpha )$ or $\gamma _{2}(\alpha )$ is positive, thus $\gamma (\alpha )>0$. Since $\gamma _{T}(\alpha )$ and $\gamma _{c}(\alpha )$ denote the maximum coefficient in $T$ and $I_{c},$ respectively, $\gamma (\alpha )$ is the maximum sum of coefficients of any $J^{\prime }\subseteq J$ that includes at most one variable per constraint; i.e.,

$$\begin{aligned} \gamma (\alpha )=\max \{\mathop {\sum }\nolimits _{j\in J^{\prime }\subseteq J}\alpha _{j}:\left| J^{\prime }\cap J_{c}\right| \le 1\}. \end{aligned}$$

Since all the following proofs examine an arbitrary, yet given, face $P^{(\alpha ,\beta )}$, we omit $\alpha$ from our notation hereafter, e.g., we write $\gamma$ instead of $\gamma (\alpha ).$ Let us define $J^{*}$ as the set of variables that appear in some $J^{\prime }\subseteq J$ such that $\left| J^{\prime }\cap J_{c}\right| \le 1$ and $\mathop {\sum }\nolimits _{j\in J^{\prime }}\alpha _{j}=\gamma .$ Formally,

$$\begin{aligned} J^{*}=\mathop {\bigcup }\nolimits _{c\in C}\{i\in I_{c}:\alpha _{i}>0,\alpha _{i}+\gamma _{C\backslash \{c\}}=\gamma \}\cup \{t\in T:\alpha _{t}=\gamma \}. \end{aligned}$$

(30)

Notice that $J^{*}\ne \emptyset$ follows from $\gamma >0$. For $c\in C,$ define $J_{c}^{*}=J^{*}\cap J_{c}$ and, accordingly, $I_{c}^{*}=J^{*}\cap I_{c},T^{*}=$ $J^{*}\cap T.$ Thus, $J_{1}^{*}\not \subset J_{2}^{*}$ implies $J_{1}^{*}\backslash J_{2}^{*}=I_{1}^{*}\ne \emptyset$ or $J_{1}^{*}=J_{2}^{*}=T^{*}.$

Since $J_{1}^{*}\subset J_{2}^{*}$ and $J_{2}^{*}\subset J_{1}^{*}$ cannot hold simultaneously, we adopt the convention that $J_{1}^{*}\not \subset J_{2}^{*}$ and either $J_{2}^{*}\subset J_{1}^{*}$ or $J_{2}^{*}\not \subset J_{1}^{*}.$ In addition:

• for $J_{2}^{*}\subset J_{1}^{*},$ define the set $I_{2}^{\prime }=I_{2}\backslash \{i\in I_{2}:\alpha _{i}=0\}$ and $J_{2}^{\prime }=I_{2}^{\prime }\cup T$, i.e., $I_{2}^{\prime }$ and $J_{2}^{\prime }$ exclude variables in $I_{2}$ with a zero coefficient in $\alpha x\ge \beta$;

• for $J_{2}^{*}\not \subset J_{1}^{*}$, assume that $|J_{1}^{*}|\le |J_{2}^{*}|$.

That is, if none of the $J_{1}^{*}$, $J_{2}^{*}$ is a proper subset the other, $J_{1}^{*}$ is the set with the smallest cardinality, whereas if $J_{2}^{*}\subset J_{1}^{*}$ clearly $J_{1}^{*}$ is the set with the largest cardinality. All the above can be made without loss of generality since the roles of the two constraints can be interchanged.

Example 3

For the system of Table 1 and $l=[0,0,2,0],u=[2,2,3,1]$, Table 2 shows the vector $\alpha$ of a valid inequality $\alpha x\ge \beta .$ Based on (27)–(30), $\gamma =\gamma _{T}=\gamma _{1}=2$ and $\gamma _{2}=0.$ Also, $J^{*}=\{1,2,4\}$ thus $J_{2}^{*}\subset J_{1}^{*}$. Observe that $\alpha _{i}\le 0$ for all $i\in I_{2}.$ For this vector $\alpha$, Theorem 16 yields $P^{(\alpha ,\beta )}\subseteq P^{l}(J_{1}^{*}).$

Table 2 A cardinality system and a vector $\alpha$

Lemma 18

(i) $j\in J^{*}$ implies $\alpha _{j}>0;$

• (ii) for $c\in C,$ $i_{1}\in I_{c}^{*}$ and $i_{2}\in I_{c}\backslash I_{c}^{*}$ imply $\alpha _{i_{2}}<\alpha _{i_{1}};$

• (iii) $t_{1}\in T^{*},t_{2}\in T\backslash T^{*}$ imply $\alpha _{t_{1}}>\alpha _{t_{2}};$

• (iv) $t\in T^{*},i_{1}\in I_{1}\backslash I_{1}^{*}$ and $i_{2}\in I_{2}\backslash I_{2}^{*}$ imply $\alpha _{t}>\alpha _{i_{1}}+\alpha _{i_{2}};$

• (v) $t\in T \backslash T^{*},i_{1}\in I_{1}^{*}$ and $i_{2}\in I_{2}^{*}$ imply $\alpha _{t}<\alpha _{i_{1}}+\alpha _{i_{2}};$

• (vi) $I_{1}^{*}\ne \emptyset =I_{2}^{*}$ implies $\alpha _{i}\le 0$ for all $i\in I_{2}$ and $\alpha _{t}<\alpha _{i_{1}}$ for all $t\in T\backslash T^{*},i_{1}\in I_{1}^{*};$

• (vii) $t\in T^{*}$ implies $\alpha _{t}>\gamma _{1}$ if $J_{2}^{*}\not \subset J_{1}^{*}$ and $\alpha _{t}=\gamma _{1}$ if $J_{2}^{*}\subset J_{1}^{*}.$

Proof

Notice that (i) follows from (30) for $j\in I_{c}^{*},c\in C$. For $j\in T^{*},$ assuming to the contrary that $\alpha _{j}\le 0$ yields $\gamma \le 0$ by (30) hence a contradiction to $\gamma >0.$

To show (ii), let $c=1$. Observe that $i_1 \in I_1^{*}$ yields $\alpha _{i_{1}}+\gamma _{2}=\gamma$ by (30). Then, assuming to the contrary that $\alpha _{i_{2}}\ge \alpha _{i_{1}}$ yields $\alpha _{i_{2}}+\gamma _{2}\ge \alpha _{i_{1}}+\gamma _{2}=\gamma ,$ thus implying $i_{2}\in I_{1}^{*}$ by (30), a contradiction. In an similar manner one can prove (iii).

To prove (iv), observe that $t\in T^{*}$ yields $\alpha _{t} = \gamma$ by (30), while $\gamma _{2} \ge \alpha _{i_{2}}$ by (28). Thus, assuming to the contrary that $\alpha _{i_{1}}+\alpha _{i_{2}}\ge \alpha _t$ yields $\alpha _{i_{1}}+\gamma _{2}\ge \gamma$ hence $i_{1}\in I_{1}^{*},$ a contradiction to $i_{1}\in I_{1}\backslash I_{1}^{*}.$

To prove (v), notice that $i_{1}\in I_{1}^{*}$ and $i_{2}\in I_{2}^{*}$ imply, respectively, $\alpha _{i_{1}}=\gamma _1$ and $\alpha _{i_{2}}=\gamma _2$. Hence $\alpha _{i_{1}}+\alpha _{i_{2}}=\gamma$. Thus, assuming to the contrary that $\alpha _{t}\ge \alpha _{i_{1}}+\alpha _{i_{2}}$ yields $\alpha _{t}\ge \gamma$ hence $t \in T ^{*}$, a contradiction to $t \in T \backslash T ^{*}$.

To show (vi), let to the contrary $\alpha _{i}>0$ for some $i\in I_{2}$. This yields $\gamma _{2}>0$ (by (28)), hence there is $i_2 \in I_{2}$ such that $\alpha _{i_2}=\gamma _2=max\{a_i:i \in I_2\}>0$. Since $I_1^{*} \ne \emptyset$, there is also $i_1 \in I_1^{*}$ such that $\alpha _{i_1}=\gamma _1>0$ and $\alpha _{i_1}+\gamma _2=\gamma$ by (30). The latter is equivalent to $\gamma _1 + \alpha _{i_2}=\gamma$, thus yielding $i_2 \in I_2^{*}$ by (30), a contradiction to $I_2^{*} = \emptyset$.

Since $\alpha _i\le 0$ for all $i \in I_2$, $\gamma _{2}=0$. Then, assuming to the contrary that $\alpha _{t}\ge \alpha _{i_{1}}$ yields $\alpha _{t} \ge \alpha _{i_{1}}+\gamma _{2}=\gamma$ hence $t\in T^{*},$ a contradiction to $t\in T\backslash T^{*}.$

To show (vii) for $J_{2}^{*}\not \subset J_{1}^{*},$ let to the contrary $\alpha _{t}\le \gamma _{1}$ and notice that $I_{1}^{*}\ne \emptyset$ and $J_{2}^{*}\not \subset J_{1}^{*}$ yield $I_{2}^{*}\ne \emptyset$ and, hence, $\gamma _{2}>0$ (by (28) and (i) shown above); then, $\alpha _{t}\le \gamma _{1}<\gamma _{1}+\gamma _{2}=\gamma$ yields $t\in T\backslash T^{*}$ by (30), a contradiction to $t\in T^{*}$. For $J_{2}^{*}\subset J_{1}^{*},$ observe $I_{1}^{*}\ne \emptyset$ yields $I_{2}^{*}=\emptyset ,$ therefore $\alpha _i\le 0$ for all $i \in I_2$ (by (vi) shown above) hence $\gamma _{2}=0$; then, (30) yields $\gamma =\alpha _{t}=$ $\gamma _{1}.$ $\square$

In several of the following proofs, the result is established by assuming $x^{\prime }\in P^{(\alpha ,\beta )}$ and then deriving a vertex $\tilde{x}\in P_{I}$ such that $\alpha \tilde{x}<\alpha x^{\prime }=\beta ,$ thus showing a contradiction to the hypothesis that $\alpha x\ge \beta$ is valid for $P_{I}.$ To avoid repeating the same argument, we show only the derivation of vertex $\tilde{x}$ from $x^{\prime }$ and then establish that $\alpha \tilde{x}-\alpha x^{\prime }<0.$

We list two intermediate lemmas, whose proofs appear in the Appendix. The first lemma applies always to $J_1^{*}$ and also to $J_2^{*}$ if $J_2^{*} \not \subset J_1^{*}$. The second lemma applies only to $J_2^{*}$ if $J_2^{*} \subset J_1^{*}$.

Lemma 19

Assume $l_{k}=0$ for all $k\in K.$ For any vertex $x^{\prime }\in P^{(\alpha ,\beta )}$ and $c \in C$ such that $J_c^{*} \not \subset J_{C \backslash \{c \}}^{*}$,

• (i) if $x_{i}^{\prime }=$ $d_{k},i\in I_{c}^{*},$ any value $d_{k^{\prime }}<d_{k}$ appears $u_{k^{\prime }}$ times in $J_{c}^{*}\cup T;$

• (ii) if $x_{t}^{\prime }=$ $d_{k},t\in T^{*},$ any value $d_{k^{\prime }}<d_{k}$ appears $u_{k^{\prime }}$ times in $J_{c}^{*}.$

Example 3

(cont.) In Table 2, vertex $x^{\prime }$ violates Lemma 19i: although $x_{4}^{\prime }=2$, $\{4\}=T^{*}$, value $1<2$ appears fewer than $u_{1}=2$ times in $J_{1}^{*}.$ To show that $x^{\prime }$ cannot belong to $P^{(\alpha ,\beta )},$ notice that $l_{2}=0<2=o(x^{\prime };1,2)=o(x^{\prime };2,2)\,\$and, in addition, $o(x^{\prime };1,1)<2=o(x^{\prime };2,1).$ Then, the vertex $\tilde{x}=x^{\prime }(4\leftrightarrow 7)$ belongs to $P_{I},$ while $\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{4}-\alpha _{7})\cdot (1-2)=(2+1)\cdot (-1)<0.$ Thus, $x^{\prime }\in P^{(\alpha ,\beta )}$ would yield $\alpha \tilde{x}<\beta ,$ a contradiction to $\alpha x\ge \beta$ being valid for $P_{I}.$ In fact, $\alpha _{4}>\alpha _{7}$ holds because $\alpha _{4}>0$ (by Lemma 18i) and $\alpha _{7}\le 0$ (by Lemma 18vi since $J_{2}^{*}\subset J_{1}^{*}$ yields $I_{2}^{*}=\emptyset$).

Lemma 20

Assume $l_{k}=0$ for all $k\in K.$ For any vertex $x^{\prime }\in P^{(\alpha ,\beta )}$ and $J_{2}^{*}\subset J_{1}^{*},$ if $x_{i}^{\prime }=d_{k},i\in I_{2}^{\prime },$ any value $d_{k^{\prime }}>d_{k}$ appears $u_{k^{\prime }}$ times in $J_{2}^{\prime }\backslash T^{*}.$

Example 3

(cont.) In Table 2, vertex $\bar{x}$ violates Lemma 20: although $J_{2}^{*}\subset J_{1}^{*},I_{2}^{\prime }=\{7,8\}$ and $\bar{x}_{8}=1,$ value $2>1$ appears fewer than $u_{2}=3$ times in $J_{2}^{\prime }\backslash T^{*}=\{5,7,8\}.$ Since $l_{1}=0\,$and $o(\bar{x};2,2)<3,$ the vertex $\check{x}=\bar{x}(8;1\rightarrow 2)$ belongs to $P_{I},$ while $\alpha \check{x}-\alpha \bar{x}=\alpha _{8}\cdot (2-1)=(-1)\cdot 1<0;$ in fact, $\alpha _{8}<0$ by Lemma 18vi and the definition of $I_{2}^{\prime }.$ Alternatively, the vertex $\mathring{x}=\bar{x}(6\leftrightarrow 8)$ (not shown in Table 2) also yields $\alpha \mathring{x}-\alpha \bar{x}<0$ since $\alpha _{6}=0;$ i.e., $6\in I_{2}\backslash I_{2}^{\prime }.$

Let us outline of the proof of Theorem 16. This theorem holds if and only if, at any vertex of $P^{(\alpha ,\beta )}$, all values $d_{k}$ ($k\in K$) appear $p(|J_{1}^{*}|,k)$ times in $J_{1}^{*}$. Hence, it suffices to show a contradiction if a vertex $x^{\prime }\in P^{(\alpha ,\beta )}$ does not have this property; i.e., if $\sum _{j\in J_{1}^{*}}x_{j}^{\prime }>\mathop {\sum }\nolimits _{k\in K}p(|J_{1}^{*}|,k)\cdot d_{k}$. Then, at vertex $x^{\prime }$, some value $d_{k^{\prime }}$ appears fewer than $p(|J_{1}^{*}|,k^{\prime })$ times in $J_{1}^{*}$, whereas some value $d_{k}>d_{k^{\prime }}$ appears more than $p(|J_{1}^{*}|,k)$ times (i.e., at least once) in $J_{1}^{*}$. Then, if $d_{\tilde{k}}$ is the maximum value appearing in $J_{1}^{*}$, it must be $d_{\tilde{k}}>d_{k^{\prime }}$. Using Lemma 19 for $J_1^{*}$, we prove that $d_{\tilde{k}}$ appears in $I_{1}^{*}$ and $d_{k^{\prime }}$ appears in $T\backslash T^{*}$. Then, we distinguish two cases, defined by whether $J_{2}^{*}\not \subset J_{1}^{*}$.

For $J_{2}^{*}\not \subset J_{1}^{*}$, notice that Lemma 19 applies to both $J_{1}^{*}$ and $J_{2}^{*}$. Then, if $d_{\tilde{k}}$ appears also in $I_{2}^{*}$, we show the contradiction directly by obtaining a vertex $\tilde{x} \in P_I$ such that $\alpha \tilde{x} < \alpha x^{\prime }$. For $d_{\tilde{k}}$ not appearing in $I_{2}^{*}$, we establish a contradiction to Lemma 19i for $J_2^{*}$ by showing that some value $d_{\hat{k}}>d_{\tilde{k}}$ appears in $I_2^{*}$ and that the value $d_{\tilde{k}}$ (smaller than $d_{\hat{k}}$) appears fewer than $u_{\tilde{k}}$ times in $J_{2}^{*}\cup T$. This is done by a combinatorial argument relying on $|J_1^{*}| \le |J_2^{*}|$, Lemma 19i for $J_1^{*}$ (‘any value $d_k<d_{\tilde{k}}$ appear $u_k$ times in $J_{1}^{*}\cup T$’) and the fact that $d_{\tilde{k}}$ appears in $I_{1}^{*}$ but not in $I_{2}^{*}$.

For $J_{2}^{*}\subset J_{1}^{*}$, we show the contradiction directly or through Lemma 20 by showing that $d_{\tilde{k}}$ appears in $I_2^{\prime }$ and some value $d_{\hat{k}}>d_{\tilde{k}}$ appears fewer than $u_{\hat{k}}$ times in $J_{2}^{\prime }\backslash T^{*}$.

Example 3

(cont.) In Table 2, vertex $\hat{x}$ belongs not to $P^{l}(J_{1}^{*}).$ Then, value $0$ appears fewer than $p(|J_{1}^{*}|,0)=p(3,0)=2$ times in $J_{1}^{*},$ while value $1$ appears more than $p(|J_{1}^{*}|,1)=1$ times in $J_{1}^{*}.$ Observe that $\hat{x}_{1}=1$ ($1\in I_{1}^{*}$) and $\hat{x}_{5}=0$ ($5\in T\backslash T^{*}$), thus Lemma 18vi yields $\alpha _{5}=1<\alpha _{1}=2$ (since $J_{2}^{*}\subset J_{1}^{*}$ yields $I_{2}^{*}=\emptyset$). Moreover, $\hat{x}_{6}=1$ ($6\in I_{2}\backslash I_{2}^{\prime }$ and $\alpha _{6}=0$). Then, $\dot{x}=\hat{x}(5\leftrightarrow \{1,6\})$ is a vertex of $P_{I}$ while $\alpha \dot{x}-\alpha \hat{x}=(\alpha _{5}-\alpha _{1}-\alpha _{6})\cdot (1-0)=(-1)\cdot 1<0,$ a contradiction to $\alpha x\ge \beta$ being valid for $P_{I}.$ That is, vertex $\hat{x}$ not belonging to $P^{l}(J_{1}^{*})$ implies that $\hat{x}$ cannot belong to $P^{(\alpha ,\beta )}.$

Proof of Theorem 16

Assume to the contrary that there is a vertex $x^{\prime }\in P^{(\alpha ,\beta )}$ such that $\sum _{j\in J_{1}^{*}}x_{j}^{\prime }>\mathop {\sum }\nolimits _{k\in K}p(|J_{1}^{*}|,k)\cdot d_{k}.$ Then, there is a value $d_{k^{\prime }}$ that appears fewer than $p(|J_{1}^{*}|,k^{\prime })$ times in $J_{1}^{*}$. As discussed above, if $d_{\tilde{k}}=\max \{x_{j}^{\prime }:j\in J_{1}^{*}\}$, then it must be $d_{\tilde{k}}>d_{k^{\prime }}$. The value $d_{\tilde{k}}$ cannot appear in $T^{*},$ since that would contradict Lemma 19ii for $J_1^{*}$ because the value $d_{k^{\prime }}<d_{\tilde{k}}$ appears fewer than $p(|J_{1}^{*}|,k^{\prime })\le u_{k^{\prime }}$ times in $J_{1}^{*}$. Thus, let $x_{i_{i}}^{\prime }=d_{\tilde{k}}$ for some $i_{1}\in I_{1}^{*}.$ Also by Lemma 19i, value $d_{k^{\prime }}<d_{\tilde{k}}$ appears $u_{k^{\prime }}$ times in $J_{1}^{*}\cup T$. Then, since $d_{k^{\prime }}$ appears fewer than $p(|J_{1}^{*}|,k^{\prime })\le u_{k^{\prime }}$ times in $J_{1}^{*}$, $d_{k^{\prime }}$ must appear in $T\backslash T^{*};$ i.e., $x_{t}^{\prime }=d_{k^{\prime }}$ for some $t\in T\backslash T^{*}.$

Case 16.1 :

$J_{2}^{*}\not \subset J_{1}^{*}$

Since $i_{1}\in I_{1}^{*}\ne \emptyset ,J_{2}^{*}\not \subset J_{1}^{*}$ yields $I_{2}^{*}\ne \emptyset .$

If $d_{\tilde{k}}$ appears also in $I_{2}^{*},$ let $i_{2}\in I_{2}^{*}$ be an index where this occurs, i.e., $x_{i_{2}}^{\prime }=d_{\tilde{k}}$. Then, for the vertex $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},i_{2}\})\in P_{I},$ it holds that $\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t}-\alpha _{i_{1}}-\alpha _{i_{2}})\cdot (d_{\tilde{k}}-d_{k^{\prime }})<0,$ because $d_{\tilde{k}}>d_{k^{\prime }}$ and $\alpha _{t_{1}}<\alpha _{i_{1}}+\alpha _{i_{2}}$ by Lemma 18v (since $i_{1}\in I_{1}^{*}$, $i_{2}\in I_{2}^{*}$ and $t\in T\backslash T^{*}$).

Otherwise, $x_{i}^{\prime }\ne d_{\tilde{k}}$ for all $i\in I_{2}^{*}$. Then, $J_{2}^{*}\not \subset J_{1}^{*}$ together with the definition of $J_{1}^{*}$ imply $|J_{1}^{*}|\le |J_{2}^{*}|$ (recall that, if $J_{2}^{*}\not \subset J_{1}^{*}$, $J_{1}^{*}$ is the set having the smallest cardinality). Since $T\backslash T^{*}\,\$is a subset of neither $J_{1}^{*}$ nor $J_{2}^{*},$ it follows that $|J_{1}^{*}\cup (T\backslash T^{*})|\le |J_{2}^{*}\cup (T\backslash T^{*})|;$ i.e., $|J_{1}^{*}\cup T|\le |J_{2}^{*}\cup T|.$ Since, by Lemma 19i for $J_1^{*}$, all values smaller than $d_{\tilde{k}}$ appear the maximum number of times in $J_{1}^{*}\cup T$ (and $d_{\tilde{k}}$ appears in $I_{1}^{*}$), and at least as many values appear in $J_{2}^{*}\cup T$ but $d_{\tilde{k}}$ appears not in $I_{2}^{*},$ some value $d_{\hat{k}}>d_{\tilde{k}}$ appears in $I_{2}^{*}.$ That is, $x_{i_{2}}^{\prime }=d_{\hat{k}},i_{2}\in I_{2}^{*}.$ Also, $d_{\tilde{k}}$ appearing in $I_{1}^{*}$ but not in $I_{2}^{*}$ and $|J_{1}^{*}\cup T|\le |J_{2}^{*}\cup T|$ together imply that the value $d_{\tilde{k}}<d_{\hat{k}}$ appears fewer than $u_{\tilde{k}}$ times in $J_{2}^{*}\cup T,$ a contradiction to Lemma 19i for $J_2^{*}$.

Case 16.2 :

$J_{2}^{*}\subset J_{1}^{*}$

It is clear that $J_{2}^{*}\subset J_{1}^{*}$ yields $I_{2}^{*}=\emptyset .$ In that case, $i_{1}\in I_{1}^{*}$ implies $\alpha _{t}<\alpha _{i_{1}}$ (by Lemma 18vi).

If $o(x^{\prime };2,\tilde{k})<u_{\tilde{k}},$ then $\tilde{x}=x^{\prime }(t\leftrightarrow i_{1})$ is a vertex of $P_{I}$ satisfying $\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t}-\alpha _{i_{1}})\cdot (d_{\tilde{k}}-d_{k^{\prime }})<0$, since $d_{\tilde{k}}>d_{k^{\prime }}$ and $\alpha _{t_{1}}<\alpha _{i_{1}}.$

Otherwise $o(x^{\prime };2,\tilde{k})=u_{\tilde{k}}.$ This, together with $d_{\tilde{k}}$ appearing in $I_{1},$ imply that $d_{\tilde{k}}$ also appears in $I_{2}.$ Thus, let $x_{i_{2}}^{\prime }=d_{\tilde{k}},i_{2}\in I_{2},$ where $\alpha _{i_{2}}\le 0$ by Lemma 18vi. For $\alpha _{i_{2}}=0,$ derive $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},i_{2}\})\in P_{I}$ and notice that, as above, $\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t}-\alpha _{i_{1}})\cdot (d_{\tilde{k}}-d_{k^{\prime }})<0.$

For $\alpha _{i_{2}}<0,i_{2}\in I_{2}^{\prime }$ by the definition of $I_{2}^{\prime }$. We show that there is a value $d_{\hat{k}}>d_{\tilde{k}}$ appearing fewer than $u_{\hat{k}}$ times in $J_{2}^{\prime }\backslash T^{*}$ thus contradicting Lemma 20. Observe that $I_{2}^{*}=\emptyset$ implies $J_{2}^{*}=T^{*}.$ Then, the hypothesis $|J_{1}^{*}|+|J_{2}^{\prime }\backslash T^{*}|\le \mathop {\sum }\nolimits _{k\in K}u_{k}-1,$ using the fact that $T\backslash T^{*}$ is not a subset of $J_{1}^{*}$ but $T\backslash T^{*}\subset J_{2}^{\prime }\backslash T^{*},$ yields $|J_{1}^{*}\cup (T\backslash T^{*})|+$ $|J_{2}^{\prime }\backslash T|\le \mathop {\sum }\nolimits _{k\in K}u_{k}-1;$ i.e., $|J_{1}^{*}\cup T|+|I_{2}^{\prime }|\le \mathop {\sum }\nolimits _{k\in K}u_{k}-1.$ That is, some value $d_{\hat{k}}$ appears fewer than $u_{\hat{k}}$ times in $J_{1}^{*}\cup T\cup I_{2}^{\prime }\supset J_{2}^{\prime }$ (where $d_{\hat{k}}\ne d_{\tilde{k}}$ since $o(x^{\prime };2,\tilde{k})=u_{\tilde{k}}$) thus appearing fewer than $u_{\hat{k}}$ times in $J_{2}^{\prime }$ (and hence in $J_{2}^{\prime }\backslash T^{*}$). Since all values smaller than $d_{\tilde{k}}$ appear the maximum number of times in $J_{1}^{*}\cup T$ (by Lemma 19i), it must be $d_{\hat{k}}>d_{\tilde{k}}.$ The proof is now complete. $\square$

The proof of Theorem 17 is quite similar, hence appearing in the Appendix.

Notice that Theorem 15 holds also for the case of a single cardinality constraint. That is, if $l_k=0$ for all $k \in K$, inequalities (19) and (20) describe the polytope defined as the convex hull of vectors satisfying a single cardinality constraint. For the same case, it has been claimed (Hooker 2012, Sect. 4.13.1)without a proof, that the polytope is completely described by inequalities (19) and (20), irrespectively of the values of $l_{k},k\in K.$ However, if some of the $l_{k}$s are strictly positive, the polytope associated with a single cardinality constraint has further facets not induced by (19) and (20) and, therefore, the result claimed in (Hooker 2012, Sect. 4.13.1) does not hold. An example suffices to show that.

Example 4

Consider the constraint $cardinality(x,\{1,2,3,4\};[0,1,0],[2,2,2])$ and let $P_{I}$ denote the polytope defined by the convex hull of integer vectors satisfying that constraint. Notice that $l_{1}=1$ while $l_{0}=l_{2}=0.$ By Theorem 2, $\dim P_{I}=4,$ thus any inequality satisfied at equality by $4$ affinely independent points of $P_{I}$ is facet-defining. The inequality

$$\begin{aligned} x_{1}+x_{2}-x_{3}-x_{4}\le 3 \end{aligned}$$

is satisfied at equality by the vertices $\check{x}=(2,1,0,0),$ $\bar{x}=(1,2,0,0),$ $\check{x}=(2,2,1,0),$ and $\hat{x}=(2,2,0,1).$ The matrix $D=[\begin{array}{cccc} \check{x}^{T}&\bar{x}^{T}&\check{x}^{T}&\hat{x}^{T}\end{array}],$ after deducting from the second row its first row multiplied by $0.5$ (and replacing the second row by the result), becomes upper triangular hence non-singular. It follows that these four vertices are linearly, and thus affinely, independent.

A second counter-example of two cardinality constraints is

$$\begin{aligned}&cardinality(x,\{1,2,3\};[0,1,0],[2,2,2]), \\&cardinality(x,\{3,4,5\};[0,1,0],[2,2,2]). \end{aligned}$$

In this case, Theorem 2 yields $\dim P_{I}=5,$ while the inequality $x_{1}+x_{2}-x_{3}\ge 1$ becomes facet-defining. Overall, the polyhedral study of the cardinality constraint (and system) requires further investigation for arbitrary values of $l_{k},k\in K.$

5 Concluding remarks

In this paper, we advance the polyhedral study of the cardinality system, thus offering also a polyhedral approach to systems of restricted representatives. For the case of two cardinality constraints, apart from providing necessary and sufficient conditions for known families of valid inequalities to be facet-defining, we show a condition under which these families completely describe the associated polytope $P_{I}.$ This condition, together with the polytime separability of these inequalities (Hooker 2012, Sect. 7.10.1), establishes polynomial solvability for the problem of optimizing a linear function over $P_{I}$ (Grötschel et al. 1981).

Motivated by the relationship between the alldifferent system and graph coloring (Magos and Mourtos 2011), we may also consider the following representation for the cardinality system (1) Define the constraint graph $G^{\#}(V_{G^{\#}},E_{G^{\#}})$ as $V_{G^{\#}}=J$ and $E_{G^{\#}}=\{(i,j):i,j\in J_{c}\,\$for some $c\in C\};$ i.e., $G^{\#}$ has one node per variable and two nodes are connected if and only if the associated variables appear together in some cardinality constraint. Then, any $c\in C$ can be associated with a complete subgraph in $G^{\#}$ in the sense that $J_{c}$ is a set of pairwise connected nodes. Then, if $D$ is regarded as a set of colors, we may define the cardinality coloring of $G^{\#}$ as a coloring in which color $d$ is received by at least $l_{d}$ and at most $u_{d}$ nodes in any maximal clique of $G^{\#}$. Thus, the solutions to the cardinality system are exactly the cardinality colorings of $G^{\#}.$ Whether this relationship can be insightful for the facietal structure of the cardinality system or for graph coloring remains to be investigated.

Appendix

Proof of Lemma 19

• (i) $x_{i_{1}}^{\prime }=$ $d_{k},i\in I_{1}^{*}$

Assume to the contrary that some value $d_{k^{\prime }}<d_{k}$ appears fewer than $u_{k^{\prime }}$ times in $J_{1}^{*}\cup T.$ If $o(x^{\prime };1,k^{\prime })<u_{k^{\prime }}$ and given $l_{k}=0,$ derive the vertex $\tilde{x}=x^{\prime }(i_{1};d_{k}\rightarrow d_{k^{\prime }})\in P_{I};$ $\alpha \tilde{x}-\alpha x^{\prime }=\alpha _{i_{1}}\cdot (d_{k^{\prime }}-d_{k})<0$ since $i_{1}\in I_{1}^{*}$ yields $\alpha _{i_{1}}>0$ (by Lemma 18i) and $d_{k^{\prime }}<d_{k}.$

Otherwise, $o(x^{\prime };1,k^{\prime })=u_{k^{\prime }}.$ Then, value $d_{k^{\prime }}$ appearing fewer than $u_{k^{\prime }}$ times in $J_{1}^{*}\cup T$ implies that $d_{k^{\prime }}$ appears in $I_{1}\backslash I_{1}^{*};$ i.e., $x_{i_{2}}^{\prime }=d_{k^{\prime }}$ for some $i_{2}\in I_{1}\backslash I_{1}^{*}.$ Then, for the vertex $\tilde{x}=x^{\prime }(i_{1}\leftrightarrow i_{2})\in P_{I},\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{i_{1}}-\alpha _{i_{2}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{i_{1}}>\alpha _{i_{2}}$ (by Lemma 18ii) and $d_{k^{\prime }}<d_{k}.$

• (ii) $x_{t_{1}}^{\prime }=$ $d_{k},t_{1}\in T^{*}$

Assume to the contrary that some value $d_{k^{\prime }}<d_{k}$ appears fewer than $u_{k^{\prime }}$ times in $J_{1}^{*}.$

If $x_{t_{2}}^{\prime }=d_{k^{\prime }}$ for some $t_{2}\in T\backslash T^{*},$ then for the vertex $\tilde{x}=x^{\prime }(t_{1}\leftrightarrow t_{2})\in P_{I},\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t_{1}}-\alpha _{t_{2}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{t_{1}}>\alpha _{t_{2}}$ (by Lemma 18iii) and $d_{k^{\prime }}<d_{k}.$

Otherwise, $x_{t}^{\prime }\ne d_{k^{\prime }}$ for all $t\in T\backslash T^{*}$. Then, four cases are defined by whether $o(x^{\prime };1,k^{\prime })$ or $o(x^{\prime };2,k^{\prime })$ is less than $u_{k^{\prime }}$ (recall that $l_{k}=0$).

Case 19.1 :

($o(x^{\prime };1,k^{\prime })<u_{k^{\prime }},o(x^{\prime };2,k^{\prime })<u_{k^{\prime }}$):] For $\tilde{x}=x^{\prime }(t_{1};d_{k}\rightarrow d_{k^{\prime }}),\alpha \tilde{x}-\alpha x^{\prime }=\alpha _{t_{1}}\cdot (d_{k^{\prime }}-d_{k})<0$ since $t_{1}\in T^{*}$ yields $\alpha _{t_{1}}>0$ (by Lemma 18i).

Case 19.2 :

($o(x^{\prime };1,k^{\prime })<u_{k^{\prime }},o(x^{\prime };2,k^{\prime })=u_{k^{\prime }}$): Since $d_{k^{\prime }}$ appears more times in $J_{2}$ than in $J_{1}$, it appears in $I_{2};$ i.e., $x_{i_{2}}^{\prime }=d_{k^{\prime }}$ for some $i_{2}\in I_{2}.$ For $\tilde{x}=x^{\prime }(t_{1}\leftrightarrow i_{2}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t_{1}}-\alpha _{i_{2}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{t_{1}}>\alpha _{i_{2}}.$ The latter follows from Lemma 18vii for $I_{2}^{*}\ne \emptyset$ (since $\alpha _{t_1}>\gamma _{2}\ge \alpha _{i_{2}}$) and from Lemma 18i and 18vi for $I_{2}^{*}= \emptyset$ (since $\alpha _{t_{1}}>0\ge \alpha _{i_{2}}$).

Case 19.3 :

($o(x^{\prime };1,k^{\prime })=u_{k^{\prime }},o(x^{\prime };2,k^{\prime })<u_{k^{\prime }}$): Since value $d_{k^{\prime }}$ appears $u_k$ times in $J_1$ but not in $T \backslash T^{*}$ and appears fewer than $u_k$ times in $J_{1}^{*}= I_{1}^{*} \cup T^{*}$, it must appear in $I_{1}\backslash I_{1}^{*};$ i.e., $x_{i_{1}}^{\prime }=d_{k^{\prime }}$ for some $i_{1}\in I_{1}\backslash I_{1}^{*}.$ For $\tilde{x}=x^{\prime }(t_{1}\leftrightarrow i_{1}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t_{1}}-\alpha _{i_{1}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{t_{1}}>\alpha _{i_{1}}$. The latter holds because the opposite, i.e., $\alpha _{t_{1}}\le \alpha _{i_{1}}$, implies $\gamma \le \alpha _{i_{1}}$ hence $i_{1}\in I_{1}^{*},$ a contradiction to $i_{1}\in I_{1}\backslash I_{1}^{*}$.

Case 19.4 :

($o(x^{\prime };1,k^{\prime })=u_{k^{\prime }},o(x^{\prime };2,k^{\prime })=u_{k^{\prime }}$): As in Case 19.3, $o(x^{\prime };1,k^{\prime })=u_{k^{\prime }}$ implies that $x_{i_{1}}^{\prime }=d_{k^{\prime }}$ for some $i_{1}\in I_{1}\backslash I_{1}^{*}.$ This, together with $o(x^{\prime };1,k^{\prime })=u_{k^{\prime }}=o(x^{\prime };2,k^{\prime })$ imply that $x_{i_{2}}^{\prime }=d_{k^{\prime }}$ for some $i_{2}\in I_{2}.$ For $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},i_{2}\}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t_{1}}-\alpha _{i_{1}}-\alpha _{i_{2}})\cdot (d_{k^{\prime }}-d_{k})<0,$ since $\alpha _{t_{1}}-\alpha _{i_{1}}-\alpha _{i_{2}}>0.$ If $i_{2}\in I_{2}\backslash I_{2}^{*},$ the latter holds by Lemma 18iv. If $i_{2}\in I_{2}^{*}$, it holds because the opposite, i.e., $\alpha _{t_{1}}\le \alpha _{i_{1}}+\alpha _{i_{2}},$ implies $i_{1}\in I_{1}^{*},$ a contradiction to $i_{1}\in I_{1}\backslash I_{1}^{*}.$

$\square$

Proof of Lemma 20

Let $x_{i_{2}}^{\prime }=d_{k}$ for some $i_{2}\in I_{2}^{\prime }$. $J_{2}^{*}\subset J_{1}^{*}$ implies $I_{1}^{*}\ne \emptyset$ and $I_{2}^{*}=\emptyset ,$ hence $i_{2}\in I_{2}^{\prime }$ implies $\alpha _{i_{2}}<0$ (by Lemma 18vi and the definition of $I_{2}^{\prime }$). Assume to the contrary that some value $d_{k^{\prime }}>d_{k}$ appears fewer than $u_{k^{\prime }}$ times in $J_{2}^{\prime }\backslash T_{2}^{*}.$ Recall that $l_k=0$.

If $o(x^{\prime };2,k^{\prime })<u_{k^{\prime }},$ the vertex $\tilde{x}$ $=x^{\prime }(i_{2};d_{k}\rightarrow d_{k^{\prime }})\in P_{I}$ since $l_{k}=0$. Then, $\alpha \tilde{x}-\alpha x^{\prime }=\alpha _{i_{2}}\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{i_{2}}<0$ and $d_{k^{\prime }}>d_{k}.$

Otherwise, $o(x^{\prime };2,k^{\prime })=u_{k^{\prime }}.$ Then, value $d_{k^{\prime }}$ appears $u_{k^{\prime }}$ times in $J_{2}$ but fewer than $u_{k^{\prime }}$ times in $J_{2}^{\prime }\backslash T^{*},$ hence it appears in $I_{2}\backslash I_{2}^{\prime }=\{i\in I_{2}:\alpha _{i}=0\}$ or in $T^{*}.$

Case 20.1 :

($x_{i_{3}}^{\prime }=d_{k^{\prime }},i_{3}\in I_{2}\backslash I_{2}^{\prime }$): Recall that $x_{i_{2}}^{\prime }=d_{k}$, $i_{2}\in I_{2}^{\prime }$. For $\tilde{x}=x^{\prime }(i_{2}\leftrightarrow i_{3}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{i_{2}}-\alpha _{i_{3}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{i_{2}}<0=\alpha _{i_{3}}$ and $d_{k^{\prime }}>d_{k}.$

Case 20.2 :

($x_{t}^{\prime }=d_{k^{\prime }},t\in T^{*}$): If value $d_{k}$ appears also in $I_{1}$, let $i_{1}\in I_{1}$ be an index where this occurs; i.e., $x_{i_{1}}^{\prime }=d_{k}$. Also, $\alpha _{t_{1}}=\gamma _{1}$ by Lemma 18vii (because $I_{1}^{*}\ne \emptyset = I_{2}^{*}$) and $\alpha _{i_{1}} \le \gamma _{1}$ by (28), thus $\alpha _{i_{1}} \le \alpha _{t_{1}}$. Then, for $\tilde{x}=x^{\prime }(t\leftrightarrow \{i_{1},i_{2}\}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{i_{1}}+\alpha _{i_{2}}-\alpha _{t_{1}})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{i_{1}} \le \alpha _{t_{1}},\alpha _{i_{2}}<0$ and $d_{k^{\prime }}>d_{k}.$

Otherwise, value $d_{k}$ appears not in $I_{1}$ but appears in $I_2$ (because $x_{i_{2}}^{\prime }=d_{k},i_{2}\in I_{2}^{\prime }$) hence $o(x^{\prime };1,k)<u_{k}$. Then, the vertex $\tilde{x}=x^{\prime }(i_{2}\leftrightarrow t)\in P_{I}$ yields $\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{i_{2}}-\alpha _{t})\cdot (d_{k^{\prime }}-d_{k})<0$ since $\alpha _{i_{2}}<0$ and $\alpha _{t}>0$ by Lemma 18i (because $t \in T^{*}$).

$\square$

Proof of Theorem 17

Observe that $J_{1}^{*}\supset J_{2}^{*}$ implies $I_{1}^{*}\ne \emptyset$ and $I_{2}^{*}=\emptyset ,$ hence $\alpha _{i}\le 0$ for all $i\in I_{2}$ by Lemma 18vi. The result holds if and only if all values $d_{k},k\in K$ appear $q(|J_{2}^{\prime }\backslash T^{*}|,k)$ times in $J_{2}^{\prime }\backslash T^{*},$ at all vertices of $P^{(\alpha ,\beta )}.$

Assume to the contrary that there is a vertex $x^{\prime }\in P^{(\alpha ,\beta )}$ with $\sum _{j\in J_{2}^{\prime }\backslash T^{*}}x_{j}^{\prime }<\mathop {\sum }\nolimits _{k\in K}q(|J_{2}^{\prime }\backslash T^{*}|,k)\cdot d_{k}.$ Then, at vertex $x^{\prime },$ some value $d_{\tilde{k}}$ appears fewer than $q(|J_{2}^{\prime }\backslash T^{*}|,\tilde{k})$ times in $J_{2}^{\prime }\backslash T^{*}$, whereas some other value $d_{k}<d_{\tilde{k}}$ appears more than $q(|J_{2}^{\prime }\backslash T^{*}|,k)$ times in $J_{2}^{\prime }\backslash T^{*}.$ Then, if $d_{k^{\prime }}=\min \{x_{j}^{\prime }:j\in J_{2}^{\prime }\backslash T^{*}\}$ it must be $d_{k^{\prime }}<d_{\tilde{k}}.$ Since $q(|J_{2}^{\prime }\backslash T^{*}|,\tilde{k})\le u_{\tilde{k}},$ value $d_{\tilde{k}}$ appears fewer than $u_{\tilde{k}}$ times in $J_{2}^{\prime }\backslash T^{*}.$ Thus, if $d_{k^{\prime }}$ appears in $I_{2}^{\prime }$ (i.e., if $x_{i_{2}}^{\prime }=d_{k^{\prime }}$ for some $i_{2}\in$ $I_{2}^{\prime }$), Lemma 20 is contradicted.

Hence let $x_{t_{2}}^{\prime }=d_{k^{\prime }},t_{2}\in T\backslash T^{*}.$ The hypothesis $|J_{1}^{*}|+|J_{2}^{\prime }\backslash T^{*}|\ge \mathop {\sum }\nolimits _{k\in K}u_{k}$ yields that each value $d_{k}$ occurs $u_{k}$ times in $J_{1}^{*}\cup (J_{2}^{\prime }\backslash T^{*}).$ Therefore, value $d_{\tilde{k}},$ since appearing fewer than $u_{\tilde{k}}$ times in $J_{2}^{\prime }\backslash T^{*}$ must appear in $J_{1}^{*};$ i.e., $x_{t_{1}}^{\prime }=d_{\tilde{k}}$ for some $t_{1}\in T^{*}$ or $x_{i_{1}}^{\prime }=d_{\tilde{k}}$ for some $i_{1}\in I_{1}^{*}.$ In the former case, for $\tilde{x}=x^{\prime }(t_{1}\leftrightarrow t_{2}),\alpha \tilde{x}-\alpha x^{\prime }=(\alpha _{t_{2}}-\alpha _{t_{1}})\cdot (d_{\tilde{k}}-d_{k^{\prime }})<0$ since $\alpha _{t_{1}}>\alpha _{t_{2}}$ (by Lemma 18iii) and $d_{\tilde{k}}>d_{k^{\prime }}.$ In the latter case, $\alpha _{t_2} < \alpha _{i_1}$ (by Lemma 18vi) and the contradiction is established by using the vertex $\tilde{x}=x^{\prime }(t_{2}\leftrightarrow \{i_{1},i_{2}\})$ (if $x_{i_{2}}^{\prime }=d_{\tilde{k}},$ for some $i_{2}\in I_{2}$) or the vertex $\tilde{x}=x^{\prime }(t_{2}\leftrightarrow i_{1})$ (if $d_{\tilde{k}}\,\$appears not in $I_{2}$). $\square$