1
$\begingroup$

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!

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Thanks! It works as expected. I was also trying to come up with similar equation but for inequality where $\sum_{j\in N(i)} x_j \leq k$ but i failed. If you know the answer could you also provide it? Thank you in advance. $\endgroup$ Commented Feb 12, 2023 at 19:25
  • 1
    $\begingroup$ To enforce just the $\le k$ inequality, omit the $-k(1-x_i)\le$ part. $\endgroup$ Commented Feb 12, 2023 at 20:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.