0-1 Knapsack problem, dependent sets, unclear proof

Question

We consider the constrained set of a $0-1$ knapsack problem

$$S=\{x\in B^n\mid \sum_{j\in \{1,\ldots,n\}}a_j x_j\leq b\}$$

where $a_j\in \mathbb{Z}_+$, for $j\in \{1,2,\ldots,n\}$ and $b\in \mathbb{Z}_+$.

We represent elements of $B^n$ by characteristic vectors so that $R\subseteq \{1,\ldots,n\}$ the vector $x^R$ has components $x_j^R=1$ if $j\in R$ and $x_j^R=0$ otherwise. If $x^C\in S,$ then we say $C$ is an independent set, otherwise $C$ is a dependent set.

Proposition whose proof is completely unclear to me follows.

If $C$ is a dependent set, then

$$\sum_{j\in C}x_j\leq|C|-1$$

is a valid inequality for $S$.

The unclear proof: Suppose $x^R\in S$ and $\sum_{j\in C}x_j\geq|C|.$ This means that $R\supseteq C$ so that $R$ is dependent, which contradicts $x^R\in S \;\;\Box$

Questions: why such a $x^R$ exists, why can we assume the cardinality condition, why $R \supseteq C$ and how do we obtain the contradiction and even what is a valid inequality in the relation to the given data?

These questions are even longer than the proof itself! I'm sure that there is hidden some nice idea in the proof, so I'm trying to understand it correctly.As well I do understand the surrounding of this theorem. Try this pages 265,266 for more surroundings.

Answer 1

From the book Integer and Combinatorial Optimization by George Nemhauser and Laurence Wolsey, p.265-266:

$$ S = \{ x\in B^n =\{0,1\}^n \mid \sum_{j\in N} a_j x_j \leq b \} \tag{2.1} $$ where $N=\{1,\dotsc,n\}$, $a_j\in\mathbb{Z}_+$ for $j\in N$, and $b\in\mathbb{Z}_+$.

Proposition 2.1. If $C$ is a dependent set, then $$ \sum_{j\in C} x_j \leq |C|-1 \tag{2.2} $$ is a valid inequality for $S$.

Proof. Suppose $x^R\in S$ and $\sum_{j\in C} x^R_j\geq|C|$. This means that $R\supseteq C$ so that $R$ is dependent, which contradicts $x^R\in S$.

The proof in the book does not look perfect. I think that the author missed something. Here is my proof:

Proof. Suppose there is an $x\in S$ such that $\displaystyle\sum_{j\in C}x_j\geq|C|$. It is trivial that $\displaystyle\sum_{j\in C}x_j\leq\sum_{j\in C}x^C_j$. So we have $\displaystyle\sum_{j\in C}x_j=\sum_{j\in C}x^C_j=|C|$, and it implies that $x_j=x^C_j=1$ for all $j\in C$. Since $x\in S$, we must have $$ \sum_{1\leq j\leq n}a_jx^C_j=\sum_{j\in C}a_jx^C_j=\sum_{j\in C}a_jx_j\leq\sum_{1\leq j\leq n}a_j x_j \leq b $$ which contradicts that $C$ is dependent.

[Update] OP wanted a more detailed proof.

Notice that $x\in S$ means "$x=(x_1,x_2,\dotsc,x_n)$ satisfies the inequality (2.1)."

Proof. We will use contraposition, that is, we first assume the inequality (2.2) does not hold, and then will show $C$ is not a dependent set, i.e., $x^C\in S$.

Assume that the inequality (2.2) doe not hold. Then there is $y=(y_1,y_2,\dotsc,y_n)\in S$ satisfying $\displaystyle\sum_{j\in C}y_j>|C|-1$, i.e., $\displaystyle\sum_{j\in C}y_j\geq|C|$.

Let $x^C=(x^C_1,x^C_2,\dotsc,x^C_n)$ be the characteristic vector such that $x^C_j=1$ if $j\in C$ and $x^C_j=0$ otherwise. It is trivial that $\displaystyle\sum_{j\in C}y_j\leq\sum_{j\in C}x^C_j=|C|$ (because, for $j\in C$, $y_j\in\{0,1\}$, but $x^C_j=1$ by definition.)

Now we have $\displaystyle |C|\leq\sum_{j\in C}y_j\leq\sum_{j\in C}x^C_j=|C|$, that is, $\displaystyle \sum_{j\in C}y_j=\sum_{j\in C}x^C_j=|C|$. It implies that $y_j=x^C_j=1$ for all $j\in C$.

Remember that we chose $y\in S$. So we must have $$ \sum_{j\in N}a_jx^C_j=\sum_{j\in C}a_jx^C_j=\sum_{j\in C}a_jy_j\leq\sum_{j\in N}a_j y_j \leq b \tag{*} $$

1. The first equality follows from the definition of $x^C$: $x^C_j=1$ if $j\in C$ and $x^C=0$ otherwise.
2. The second equality follows from the fact that $y_j=x^C_j=1$ for all $j\in C$ (see above).
3. The third inequality is trivial, since $C\subseteq N$.
4. The fourth inequality follows from the fact that $y\in S$.

Now the inequality (*) shows that $\displaystyle\sum_{j\in N}a_jx^C_j\leq b$ which means the characteristic vector $x^C=(x^C_1,x^C_2,\dotsc,x^C_n)\in S$, that is what we wanted finally.

Answer 2

The proof is by contradiction. If the proposition is incorrect, then there is some dependent set $C$ for which the specified cardinality constraint is not a valid inequality for $S$. If it is not a valid inequality, then there is some feasible solution $x^R$ that violates it. So:

• why such a $x^R$ exists: in order to attempt to violate the conclusion of the proposition, we have to assume this (and then arrive at a contradiction);
• why can we assume the cardinality condition: same answer;
• why $R \supseteq C$: $\sum_{j\in C} x^R_j$ is the number of elements in $C$ that also belong to $R$, i.e., the cardinality of $R\cap C$; if that is greater than or equal to the cardinality of $C$, then every element of $C$ belongs to $R$;
• how do we obtain the contradiction: $C$ is a dependent set, meaning infeasible, meaning it "weighs" too much, and $R$ contains it, so $R$ also "weighs" too much -> is infeasible, contradicting the assumption $x^R\in S$;
• and even what is a valid inequality in the relation to the given data: A valid inequality is one satisfied by every feasible solution $x\in S$.