In the presence of at_most_ones_ constraints, expanding them implicitly to implications in the SCC computation can result in a quadratic complexity rather than a linear one in term of the input data structure size. So this test here is critical on problem with large at_most ones like the "ivu06-big.mps.gz" where without it, the full FindStronglyConnectedComponents() take more than on hour instead of less than a second!
We never expand a node twice.
If the first node is not settled, then we do explore the at_most_one constraint again. In "Mixed-Integer-Programming:
Analyzing 12 years of progress", Tobias Achterberg and Roland Wunderling explains that an at most one need to be looped over at most twice. I am not sure exactly how that works, so for now we are not fully linear, but on actual instances, we only rarely run into this case.
- Note
- we change the previous node to explore at most one since the current node will be settled before the old ones.
- Todo
- (user): avoid looping more than twice on the same at most one constraints? Note that the second time we loop we have x => y => not(x), so we can already detect that x must be false which we detect below.
The first node is already settled and so are all its child. Only not(first_node) might still need exploring.
Definition at line 1201 of file clause.cc.
1.14.0