Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class MinPropagator
Note: This documentation is automatically generated.
A min (resp max) constraint 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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe \u003ccode\u003eMinPropagator\u003c/code\u003e constraint ensures that \u003ccode\u003emin_var\u003c/code\u003e represents the minimum value among a set of \u003ccode\u003evars\u003c/code\u003e.\u003c/p\u003e\n"],["\u003cp\u003eIt achieves this by maintaining lower and upper bounds on \u003ccode\u003emin_var\u003c/code\u003e based on the bounds of \u003ccode\u003evars\u003c/code\u003e.\u003c/p\u003e\n"],["\u003cp\u003eThe current implementation has O(num_vars) complexity for each propagation call, triggered by changes in \u003ccode\u003evars\u003c/code\u003e.\u003c/p\u003e\n"],["\u003cp\u003eThere's potential for future optimization with a more efficient algorithm.\u003c/p\u003e\n"]]],["The `MinPropagator` class handles constraints where `min` equals the minimum of a set of variables (`vars`). It enforces two conditions: the lower bound of `min` is greater than or equal to the minimum of the lower bounds of `vars`, and if only one variable remains a candidate for the minimum, the upper bound of `min` is greater than or equal to that candidate's upper bound. These rules are ensured by `Propagate`, this happen in `O(num_vars)` time.\n"],null,[]]
