Conditional constraints in Integer Linear Programming

Question

I think it's rather a simple question. I'm trying to construct a reduction from graph problem to ILP. When I have variables $x_1, x_2, \dots ,x_n \in \{0, 1\}$ for every vertex, can I create constrains only for variables that have specific value? For example: $$\forall [x_i|x_i=1]\sum_{j\in N(i)}x_j=some\_value$$

Is this a legal in ILP? Thanks for answers!

Answer 1

You want to enforce the logical implication $$x_i = 1 \implies \sum_{j\in N(i)} x_j = k.$$ This is not a linear constraint, but you can linearize it via linear "big-M" constraints $$-k(1-x_i) \le \sum_{j\in N(i)} x_j - k \le (|N(i)|-k)(1-x_i)$$

• If $x_i=1$, then $$0 \le \sum_{j\in N(i)} x_j - k \le 0,$$ equivalently, $$\sum_{j\in N(i)} x_j = k,$$ as desired.
• If $x_i=0$, then $$-k \le \sum_{j\in N(i)} x_j - k \le |N(i)|-k,$$ equivalently, $$0 \le \sum_{j\in N(i)} x_j \le |N(i)|,$$ which is redundant, as desired.