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,["# MinPropagator\n\nC++ Reference: class MinPropagator\n==================================\n\n\nNote: This documentation is automatically generated.\nA min (resp max) constraint of the form min == MIN(vars) can be decomposed into two inequalities: 1/ min \\\u003c= MIN(vars), which is the same as for all v in vars, \"min \\\u003c= v\". This can be taken care of by the LowerOrEqual(min, v) constraint. 2/ min \\\u003e= MIN(vars). \n\nAnd in turn, 2/ can be decomposed in: a) lb(min) \\\u003e= lb(MIN(vars)) = MIN(lb(var)); b) ub(min) \\\u003e= 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) \\\u003e ub(min); In this case, ub(min) \\\u003e= ub(v). \n\nThis constraint take care of a) and b). That is: \n- If the min of the lower bound of the vars increase, then the lower bound of the min_var will be \\\u003e= to it. \n- If there is only one candidate for the min, then if the ub(min) decrease, the ub of the only candidate will be \\\u003c= to it. \n\n\u003cbr /\u003e\n\nComplexity: 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. \n\nTODO(user): Implement a more efficient algorithm when the need arise.\n\n| Method ||\n|-------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------|\n| [`MinPropagator`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/integer_expr.h#L182) | \u003cbr /\u003e Arguments: `const std::vector\u003cIntegerVariable\u003e& vars, IntegerVariable min_var, IntegerTrail* integer_trail` \u003cbr /\u003e |\n| [`Propagate`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/integer_expr.h#L185) | Return type: `bool ` \u003cbr /\u003e |\n| [`RegisterWith`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/integer_expr.h#L186) | Return type: `void ` Arguments: `GenericLiteralWatcher* watcher` \u003cbr /\u003e |"]]
