A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$.

I have a set of points defined as the knapsack constraint

$$ \mathcal{X} = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \} $$ where $\mathcal{Z}^n$ is the n-dimensional 0-1 vectors and $w \in \Re^n_+$ and $b \in \Re_+$.

I read that one possible relaxation of the above set is $$ \mathcal{X} = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \} $$

where $\lfloor \rfloor$ represents the floor function.

It is very counter-intuitive to me. $w^\top x \leq b$ represents a half space with left or lower space of the hyperplane defined by $w^\top x = b$. By taking the floor function, we are in fact moving the hyperplane lower and shrinking the size of the set.

Can anyone explain to me why the floor function terms represent a relaxed set ?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top