C++ Reference: class MinPropagator
This documentation is automatically generated.A min (resp max) contraint of the form min == MIN(vars) can be decomposed into two inequalities: 1/ min <= MIN(vars), which is the same as for all v in vars, "min <= v". This can be taken care of by the LowerOrEqual(min, v) constraint. 2/ min >= MIN(vars).
And in turn, 2/ can be decomposed in: a) lb(min) >= lb(MIN(vars)) = MIN(lb(var)); b) ub(min) >= ub(MIN(vars)) and we can't propagate anything here unless there is just one possible variable 'v' that can be the min: for all u != v, lb(u) > ub(min); In this case, ub(min) >= ub(v).
This constraint take care of a) and b). That is:
- If the min of the lower bound of the vars increase, then the lower bound of the min_var will be >= to it.
- If there is only one candidate for the min, then if the ub(min) decrease, the ub of the only candidate will be <= to it.
Complexity: This is a basic implementation in O(num_vars) on each call to Propagate(), which will happen each time one or more variables in vars_ changed.
TODO(user): Implement a more efficient algorithm when the need arise.