Interger 선형 프로그래밍을위한 조건부 제한

Question

나무에 문제가 있습니다. ILP 공식을 쓰려고합니다. 나는 나무가있다. T = (V, E) V는 정점이다. E는 모서리이다. 내 제약 중 하나는 연결성에 관한 것이고 나는 다음과 같은 문장을 작성하려고합니다. if X [i, j] = 1; 그러면 X [parent_i, i] = 1입니다. X는 솔루션 1에있는 노드가 솔루션에서 선택되었다는 것을 나타내는 이진 변수입니다. i, j는 V의 요소입니다. 어떻게 공식화 할 수 있습니까?

미리 감사드립니다.

Answer 1

{0, 1}의 A, B, [A = 1 ⇒ B = 1] ⇔ [A ≤ B]의 경우.

Answer 2

해결 방법은 노드와 부모 관계를 사용했습니다. 해결책은 X (parent [parent [i]], parent [i]) - X (Parent [i], i)> = 0입니다. fisrtly k, i와 i, j 둘 다 0 일 수 있고 둘째로 둘 다 1 일 수 있습니다. 마지막 k에서 i는 1 일 수 있고 i, j는 0 일 수 있습니다. 그러나 k, i, j가 1 일 때 i는 0이 될 수 없습니다. 그래서 (k, i) - (i, j)는 0.