Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class AllDifferentBoundsPropagator
Note: This documentation is automatically generated.
Implements the all different bound consistent propagator with explanation.
That is, given n affine expressions that must take different values, this
propagates the bounds of each expression as much as possible. The key is to
detect the so called Hall interval which are interval of size k that contains
the domain of k expressinos. Because all the variables must take different
values, we can deduce that the domain of the other variables cannot contains
such Hall interval.
We use a "fast" O(n log n) algorithm.
TODO(user): It might be difficult to find something faster than what is
implemented here. Some related reference:
https://cs.uwaterloo.ca/~vanbeek/Publications/ijcai03_TR.pdf
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[[["\u003cp\u003eThe \u003ccode\u003eAllDifferentBoundsPropagator\u003c/code\u003e enforces the constraint that a set of affine expressions must take distinct values by propagating bounds efficiently.\u003c/p\u003e\n"],["\u003cp\u003eIt leverages Hall intervals, intervals containing the domain of k expressions of size k, to deduce bounds on other variables.\u003c/p\u003e\n"],["\u003cp\u003eThe propagator uses a "fast" O(n log n) algorithm for bound propagation.\u003c/p\u003e\n"],["\u003cp\u003eIt's implemented with methods for initialization, propagation, and registration with a watcher.\u003c/p\u003e\n"]]],["The `AllDifferentBoundsPropagator` class in C++ enforces that a set of affine expressions take distinct values. It achieves this by identifying \"Hall intervals,\" where *k* expressions' domains are within an interval of size *k*. If found, it deduces that other expressions cannot reside in these intervals. The algorithm used has O(n log n) time complexity. Key methods include the constructor, `Propagate` (for bound propagation), and `RegisterWith` (for integrating with a watcher).\n"],null,["# AllDifferentBoundsPropagator\n\nC++ Reference: class AllDifferentBoundsPropagator\n=================================================\n\n\nNote: This documentation is automatically generated.\nImplements the all different bound consistent propagator with explanation. That is, given n affine expressions that must take different values, this propagates the bounds of each expression as much as possible. The key is to detect the so called Hall interval which are interval of size k that contains the domain of k expressinos. Because all the variables must take different values, we can deduce that the domain of the other variables cannot contains such Hall interval. \n\nWe use a \"fast\" O(n log n) algorithm. \n\nTODO(user): It might be difficult to find something faster than what is implemented here. Some related reference: [https://cs.uwaterloo.ca/\\~vanbeek/Publications/ijcai03_TR.pdf](https://cs.uwaterloo.ca/~vanbeek/Publications/ijcai03_TR.pdf)\n\n| Method ||\n|-----------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------|\n| [`AllDifferentBoundsPropagator`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/all_different.h#L155) | \u003cbr /\u003e Arguments: `const std::vector\u003cAffineExpression\u003e& expressions, IntegerTrail* integer_trail` \u003cbr /\u003e |\n| [`Propagate`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/all_different.h#L158) | Return type: `bool ` \u003cbr /\u003e |\n| [`RegisterWith`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/all_different.h#L159) | Return type: `void ` Arguments: `GenericLiteralWatcher* watcher` \u003cbr /\u003e |"]]
