Search code examples
treeconstraintsgraph-theoryinteger-programming

Conditional Constraint for Interger Linear Programming

I'm working on a problem on Trees. I'm trying to write an ILP formulation. I have a tree T=(V,E) V are vertices E are edges. One of my constraints is about connectivity and i want to formulate my statement which is: if X[i,j] =1; then X[parent_i,i] = 1. X is binary variable indicating we select that node in solution if it's in solution 1 else 0. i,j are elements of V How can i formulate this?

Thanks in advance.

Solution

  • For A, B in {0, 1}, [A = 1 ⇒ B = 1] ⇔ [A ≤ B].