Knapsack cover inequalities for a particular covering problem

169 Views Asked by At

The Knapsack cover inequalities for a constraint $ A_i x \geq b$ where $x_{j}\in\{0,1\}$ are: $$\sum_{ j \notin S} \tilde{ a}_j x_j \geq b_i −\sum_{ j \in S } 1 $$ with $\tilde{ a}_j = \min \{a_j , b_i − \sum_{ j \in S } 1 \}$. Given a covering polyhedron $P$ given by $ \{ x \ : \ Ax \geq b, \ \ \ 0 \leq x \leq 1 \} $ it is known that the integrality gap of $P'$ (given by constraints in $P$ and additional knapsack cover inequalites) and the integral hull of $P$ is at most 2.

Suppose our covering polyhedron is given, that $x\in\{0,1\}^n$ with $n$ even and large, and that the rows of A are all vectors with $n/2$ ones. How would one go about finding a knapsack cover inequality that cuts the point 0.1 * $\mathbb{1}$ (with $\mathbb{1}$ the all ones vector)? I understand one can do this with iterative Chvátal cuts, but I'm wondering how one would use knapsack cover inequalities to cut such a point.