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.
| Method |
Add | Return type: void Arguments: Literal literal, IntegerLiteral integer_literal 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.
|
AddElementEncoding | Return type: void 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.
|
AddLiteralImpliesVarEqValue | Return type: void Arguments: Literal literal, IntegerVariable var,
IntegerValue value Adds literal => var == value.
|
EnqueueNewDeductions | Return type: bool 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.
|
GetElementEncodedVariables | Return type: const std::vector<IntegerVariable>& Get an unsorted set of variables appearing in element encodings.
|
GetElementEncodings | Arguments: IntegerVariable var |
GetImpliedBounds | Return type: const std::vector<ImpliedBoundEntry>& Arguments: IntegerVariable var Returns all the implied bounds stored for the given variable.
Note that only literal with an IntegerView are considered here.
|
GetImpliedValues | Return type: const absl::flat_hash_map<IntegerVariable, IntegerValue>& Arguments:
Literal literal Returns all the implied values stored for a given literal.
|
ImpliedBounds | Return type: explicit Arguments: Model* model |
~ImpliedBounds | |
NotifyNewIntegerView | Return type: void Arguments: Literal literal 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.
|
ProcessIntegerTrail | Return type: void Arguments: Literal first_decision 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).
|
VariablesWithImpliedBounds | Return type: const std::vector<IntegerVariable>& 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.
|
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\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,["# ImpliedBounds\n\nC++ Reference: class ImpliedBounds\n==================================\n\n\nNote: This documentation is automatically generated.\nMaintains all the implications of the form Literal =\\\u003e IntegerLiteral. We collect these implication at model loading, during probing and during search. \n\nTODO(user): This can quickly use up too much memory. Add some limit in place. In particular, each time we have literal =\\\u003e integer_literal we should avoid storing the same integer_literal for all other_literal for which other_literal =\\\u003e literal. For this we need to interact with the BinaryImplicationGraph. \n\nTODO(user): This is a bit of a duplicate with the Literal \\\u003c=\\\u003e IntegerLiteral stored in the IntegerEncoder class. However we only need one side here. \n\nTODO(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). \n\nTODO(user): Add an implied bound cut generator to add these simple constraints to the LP when needed.\n\n| Method ||\n|----------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`Add`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L96) | Return type: `void ` Arguments: `Literal literal, IntegerLiteral integer_literal` Adds literal =\\\u003e 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. |\n| [`AddElementEncoding`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L131) | Return type: `void ` Arguments: `IntegerVariable var, const std::vector\u003cValueLiteralPair\u003e& 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. |\n| [`AddLiteralImpliesVarEqValue`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L99) | Return type: `void ` Arguments: `Literal literal, IntegerVariable var, IntegerValue value` Adds literal =\\\u003e var == value. |\n| [`EnqueueNewDeductions`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L145) | Return type: `bool ` 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. |\n| [`GetElementEncodedVariables`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L140) | Return type: `const std::vector\u003cIntegerVariable\u003e& ` Get an unsorted set of variables appearing in element encodings. |\n| [`GetElementEncodings`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L137) | \u003cbr /\u003e Arguments: `IntegerVariable var` \u003cbr /\u003e |\n| [`GetImpliedBounds`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L111) | Return type: `const std::vector\u003cImpliedBoundEntry\u003e& ` Arguments: `IntegerVariable var` Returns all the implied bounds stored for the given variable. Note that only literal with an IntegerView are considered here. |\n| [`GetImpliedValues`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L121) | Return type: `const absl::flat_hash_map\u003cIntegerVariable, IntegerValue\u003e& ` Arguments: ` Literal literal` Returns all the implied values stored for a given literal. |\n| [`ImpliedBounds`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L84) | Return type: `explicit ` Arguments: `Model* model` \u003cbr /\u003e |\n| [`~ImpliedBounds`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L89) | \u003cbr /\u003e |\n| [`NotifyNewIntegerView`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L153) | Return type: `void ` Arguments: `Literal literal` 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. |\n| [`ProcessIntegerTrail`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L107) | Return type: `void ` Arguments: `Literal first_decision` 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). |\n| [`VariablesWithImpliedBounds`](https://github.com/google/or-tools/blob/v9.4/ortools/sat/implied_bounds.h#L116) | Return type: `const std::vector\u003cIntegerVariable\u003e& ` 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. |"]]
