Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class ImpliedBounds
Note: This documentation is automatically generated.
Maintains all the implications of the form Literal => IntegerLiteral. We
collect these implication at model loading, during probing and during search.
TODO(user): This can quickly use up too much memory. Add some limit in place.
In particular, each time we have literal => integer_literal we should avoid
storing the same integer_literal for all other_literal for which
other_literal => literal. For this we need to interact with the
BinaryImplicationGraph.
TODO(user): This is a bit of a duplicate with the Literal <=> IntegerLiteral
stored in the IntegerEncoder class. However we only need one side here.
TODO(user): Do like in the DomainDeductions class and allow to process
clauses (or store them) to perform more level zero deductions. Note that this
is again a slight duplicate with what we do there (except that we work at the
Domain level in that presolve class).
TODO(user): Add an implied bound cut generator to add these simple
constraints to the LP when needed.
Adds literal => integer_literal to the repository.
Not that it checks right aways if there is another bound on the same
variable involving literal.Negated(), in which case we can improve the
level zero lower bound of the variable.
Arguments: IntegerVariable var,
const std::vector<ValueLiteralPair>& encoding,
int exactly_one_index
Register the fact that var = sum literal * value with sum literal == 1.
Note that we call this an "element" encoding because a value can appear
more than once.
Adds to the integer trail all the new level-zero deduction made here.
This can only be called at decision level zero. Returns false iff the model
is infeasible.
When a literal does not have an integer view, we do not add any
ImpliedBoundEntry. This allows to create missing entries for a literal for
which a view was just created.
TODO(user): Implement and call when we create new views in the linear
relaxation.
This must be called after first_decision has been enqueued and propagated.
It will inspect the trail and add all new implied bounds.
Preconditions: The decision level must be one (CHECKed). And the decision
must be equal to first decision (we currently do not CHECK that).
Returns all the variables for which GetImpliedBounds(var) is not empty. Or
at least that was not empty at some point, because we lazily remove bounds
that become trivial as the search progress.
[[["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\u003eImpliedBounds\u003c/code\u003e class in OR-Tools stores and manages implications of the form "Literal => IntegerLiteral", which represent constraints on variable values based on literal assignments.\u003c/p\u003e\n"],["\u003cp\u003eIt provides methods to add and retrieve implied bounds, element encodings (for representing variables as sums of literals), and implied values for literals.\u003c/p\u003e\n"],["\u003cp\u003eThe class also includes functionality to process the integer trail and deduce new implied bounds during search, potentially improving the lower bounds of variables.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eImpliedBounds\u003c/code\u003e has methods to handle new integer views of literals and to enqueue new deductions derived from implied bounds, which can be used for constraint propagation and conflict analysis.\u003c/p\u003e\n"],["\u003cp\u003eSeveral TODOs highlight areas for improvement, including memory management, interaction with other constraint data structures, and potential cut generation for the LP relaxation.\u003c/p\u003e\n"]]],["The `ImpliedBounds` class manages implications of the form `Literal =\u003e IntegerLiteral`. Key actions include: adding such implications (`Add`), registering variable encodings (`AddElementEncoding`), and adding literal implications for variable equality (`AddLiteralImpliesVarEqValue`). It also handles deductions at level zero (`EnqueueNewDeductions`), retrieves encoded variables (`GetElementEncodedVariables`), and accesses implied bounds (`GetImpliedBounds`) and values (`GetImpliedValues`). It has the capability to process the integer trail and add new implied bounds (`ProcessIntegerTrail`). It has also features to handle integer views (`NotifyNewIntegerView`).\n"],null,[]]
