Nevertheless, the ILP in GNF is simpler than (1), since we consider only candidate edges involving v. Figure 4 illustrates the three types of possible transitivity constraint violations when reattaching v. The left side depicts a violation when (i, k) / ∈ E, expressed by the constraint in (9) below, and the middle and right depict two violations when the edge (i, k) ∈ E, expressed by the constraints in (10).
the ILP is formulated by adding the following constraints to the objective function (3): Complexity is exponential due to the ILP solver; however, the ILP size is reduced by an order of magnitude to O(|V |) variables and O(|V | 2 ) constraints.