ILP constraint on sum of k variables out n

96 Views Asked by At

Say I have $n$ variables, denoted $v_n$ and I want to constrain them in the following way $\sum_{j=1}^{j=k}v_j\le1$ $\forall$ groups of $v$ with cardinality $k$. Obviously there are $n \choose k$ groups, which would lead to a naive implementations with $n \choose k$ constraints. This does not scale and I was wondering if there is a better way of encoding this in ILP or SAT formulation. Thanks.

1

There are 1 best solutions below

3
On BEST ANSWER

The single constraint $$\sum_{j=1}^n v_j \le 1$$ suffices. If more than one $v_j=1$, you would have a $k$-subset that violates one of your required constraints.