0-1 Knapsack problem, minimal dependent sets,another unclear proof

119 Views Asked by At

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. $C$ is a minimal depenedent set if all its subsets are dependent. The extension $E(C)$ of a minimal dependent set $C$ is the set $$C\cup \{ k\in \{1,2,...,n\}\setminus C\ |\ a_k\geq a_j \text{ for all } j \in C\}$$

Proposition whose proof is completely unclear to me follows. If $C$ is a minimal dependent set, then $$\sum _{j\in E(C)}x_j\leq|C|-1 $$ is a valid inequality for S.

Proof. Suppose $x^R\in S$ and $\sum_{j\in E(C)} x_j^R\geq|C|$ so that $|R\cap E(C)|\geq |C|$. Now $\sum_{j\in R}a_j\geq\sum_{j\in R\cap E(C)}a_j$ and by definition of $E(C)$ we obtain $\sum_{j\in R\cap E(C)}a_j\geq\sum_{j\in C}a_j>b$, which contradicts $x^R\in S$.

For details see page 266 proposition 2.2 here.

I would like to see how did we use those k's in $C\cup \{k\in \{1,...,n\}\setminus C$ with $a_k \geq a_j$ for all $j\in C\}.$ Note that I would like to get explained the proof rather then being given a new one.

1

There are 1 best solutions below

6
On BEST ANSWER

It's proof by contradiction. They start by assuming the existence of a feasible solution ($x^R$) that violates the inequality for some minimal dependent set $C$. The key step is the inequality $$\sum_{j\in R\cap E(C)}a_j \ge \sum_{j\in C} a_j.$$

We can rewrite the left sum as $\sum_{j\in R\cap C} a_j + \sum_{j\in R\cap [E(C)\backslash C]} a_j$. For every index $j$ in the second term, $a_j \ge a_k \,\forall k\in C$. Let $m$ be the number of terms in the first sum. They have already established that the number of terms on the left is at least $|C|$, so $|C|-m\ge 0$. Replace any $|C|-m$ indices in the second sum with the $|C|-m$ indices from $C$ that did not appear in the first sum, observing that the revised second sum is no greater than the original second sum. If there are any remaining indices $j\notin C$ in the second sum, drop those terms, again noting that $a_j\ge 0$ means the second sum does not increase. What's left reduces to $\sum_{j\in C}a_j$, giving us the key inequality.