Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class IntegerSumLE
Note: This documentation is automatically generated.
A really basic implementation of an upper-bounded sum of integer variables.
The complexity is in O(num_variables) at each propagation.
Note that we assume that there can be NO integer overflow. This must be
checked at model validation time before this is even created.
TODO(user): If one has many such constraint, it will be more efficient to
propagate all of them at once rather than doing it one at the time.
TODO(user): Explore tree structure to get a log(n) complexity.
TODO(user): When the variables are Boolean, use directly the pseudo-Boolean
constraint implementation. But we do need support for enforcement literals
there.
This is a pretty usage specific function. Returns the implied lower bound
on target_var if the given integer literal is false (resp. true). If the
variables do not appear both in the linear inequality, this returns two
kMinIntegerValue.
If refied_literal is kNoLiteralIndex then this is a normal constraint,
otherwise we enforce the implication refied_literal => constraint is true.
Note that we don't do the reverse implication here, it is usually done by
another IntegerSumLE constraint on the negated variables.
We propagate:
- If the sum of the individual lower-bound is > upper_bound, we fail.
- For all i, upper-bound of i
<= upper_bound - Sum {individual lower-bound excluding i).
Same as Propagate() but only consider current root level bounds. This is
mainly useful for the LP propagator since it can find relevant optimal
really late in the search tree.
[[["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."],[[["`IntegerSumLE` is a constraint implementation in C++ that enforces an upper bound on the sum of integer variables."],["The current implementation has a time complexity of O(num_variables) for each propagation."],["Potential optimizations include batch propagation for multiple constraints and exploring tree structures for logarithmic time complexity."],["Special handling for Boolean variables using pseudo-Boolean constraints is planned but requires support for enforcement literals."],["The constraint assumes no integer overflow, which must be validated before its creation."]]],["The `IntegerSumLE` class implements an upper-bounded sum of integer variables, with O(num_variables) complexity per propagation. Key actions include: `Propagate`, which checks for failures if the sum of lower bounds exceeds the upper bound and adjusts individual upper bounds; `PropagateAtLevelZero`, which performs similar checks at the root level; `RegisterWith`, which registers the constraint; and `IntegerSumLE`, which creates the constraint with optional enforcement literals. Additionally `ConditionalLb` computes the implied lower bound.\n"]]
