Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class PrecedencesPropagator
Note: This documentation is automatically generated.
This class implement a propagator on simple inequalities between integer
variables of the form (i1 + offset <= i2). The offset can be constant or
given by the value of a third integer variable. Offsets can also be negative.
The algorithm works by mapping the problem onto a graph where the edges carry
the offset and the nodes correspond to one of the two bounds of an integer
variable (lower_bound or -upper_bound). It then find the fixed point using an
incremental variant of the Bellman-Ford(-Tarjan) algorithm.
This is also known as an "integer difference logic theory" in the SMT world.
Another word is "separation logic".
TODO(user): We could easily generalize the code to support any relation of
the form a*X + b*Y + c*Z >= rhs (or <=). Do that since this class should be
a lot faster at propagating small linear inequality than the generic
propagator and the overhead of supporting coefficient should not be too bad.
Advanced usage. To be called once all the constraints have been added to
the model. This will loop over all "node" in this class, and if one of its
optional incoming arcs must be chosen, it will add a corresponding
GreaterThanAtLeastOneOfConstraint(). Returns the number of added
constraint.
TODO(user): This can be quite slow, add some kind of deterministic limit
so that we can use it all the time.
Add a precedence relation (i1 + offset <= i2) between integer variables.
Important: The optionality of the variable should be marked BEFORE this
is called.
Propagates all the outgoing arcs of the given variable (and only those). It
is more efficient to do all these propagation in one go by calling
Propagate(), but for scheduling problem, we wants to propagate right away
the end of an interval when its start moved.
[[["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."],[[["The `PrecedencesPropagator` class handles simple inequalities between integer variables, specifically those in the form (i1 + offset ≤ i2), where the offset can be a constant or another integer variable."],["It uses a graph-based approach, mapping the problem onto a graph and applying an incremental Bellman-Ford-like algorithm to find a solution."],["This propagator is particularly efficient for handling small linear inequalities, outperforming generic propagators in these scenarios."],["The class supports conditional precedences, where the relation is only active when a specific literal is true, offering greater flexibility in constraint modeling."],["While currently limited to specific inequality forms, there's potential for expansion to support more general linear inequalities (e.g., a\\*X + b\\*Y + c\\*Z ≥ rhs)."]]],["The `PrecedencesPropagator` class manages inequalities between integer variables (i1 + offset \u003c= i2). It uses a graph-based approach and the Bellman-Ford(-Tarjan) algorithm to find fixed points. Key actions include adding precedence relations via `AddPrecedence`, `AddPrecedenceWithOffset`, `AddConditionalPrecedence`, and others. `Propagate` performs constraint propagation, and `PropagateOutgoingArcs` handles specific variable propagations. It also includes methods to compute and add constraints like `ComputePrecedences` and `AddGreaterThanAtLeastOneOfConstraints`.\n"]]
