Условное ограничение для промежуточного линейного программирования

Question

Я работаю над проблемой на деревьях. Я пытаюсь написать формулировку ILP. У меня есть дерево T = (V, E) V - вершины E - ребра. Одно из моих ограничений связано с связностью, и я хочу сформулировать свой оператор, который есть: если X [i, j] = 1; то X [parent_i, i] = 1. X - двоичная переменная, указывающая, что мы выбираем этот узел в решении, если он находится в решении 1 else 0. i, j являются элементами V. Как я могу сформулировать это?

Заранее спасибо.

Answer 1

Для A, B в {0, 1}, [A = 1 ⇒ B = 1] ⇔ [A ≤ B].

Answer 2

Я пришел с решением, я использовал родительское отношение с узлами. Решение: X (parent [parent [i]], parent [i]) - X (Parent [i], i)> = 0. Допустим, что k -> i -> j hierachy есть 3 возможности: fisrtly k, i и i, j оба могут быть 0, во-вторых, оба могут быть равны 1; наконец, k, i может быть 1 и i, j может быть 0. Но k, i не может быть 0, когда i, j равно 1. Итак, (k, i) - (i, j) должно быть больше и равно 0.