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.

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.


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.


Return type: void

Arguments: Literal literal, IntegerVariable var, IntegerValue value

Adds literal => var == value.


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.


Return type: const std::vector<IntegerVariable>&

Get an unsorted set of variables appearing in element encodings.


Arguments: IntegerVariable var


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.


Return type: const absl::flat_hash_map<IntegerVariable, IntegerValue>&

Arguments: Literal literal

Returns all the implied values stored for a given literal.


Return type: explicit

Arguments: Model* model



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.


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).


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.