Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class PresolveContext

Note: This documentation is automatically generated.

Wrap the CpModelProto we are presolving with extra data structure like the in-memory domain of each variables and the constraint variable graph.
Method
AddImplication

Return type: void

Arguments: int a, int b

a => b.

AddImplyInDomain

Return type: void

Arguments: int b, int x, const Domain& domain

b => x in [lb, ub].

AddLiteralToObjective

Return type: void

Arguments: int ref, int64_t value

AddToObjective

Return type: void

Arguments: int var, int64_t value

AddToObjectiveOffset

Return type: void

Arguments: int64_t delta

AffineRelationDebugString

Return type: std::string

Arguments: int ref

CanBeUsedAsLiteral

Return type: bool

Arguments: int ref

CanonicalizeAffineVariable

Return type: bool

Arguments: int ref, int64_t coeff, int64_t mod, int64_t rhs

Given the relation (X * coeff % mod = rhs % mod), this creates a new variable so that X = mod * Y + cte. This requires mod != 0 and coeff != 0. Note that the new variable will have a canonical domain (i.e. min == 0). We also do not create anything if this fixes the given variable or the relation simplifies. Returns false if the model is infeasible.

CanonicalizeDomainOfSizeTwo

Return type: void

Arguments: int var

If not already done, adds a Boolean to represent any integer variables that take only two values. Make sure all the relevant affine and encoding relations are updated. Note that this might create a new Boolean variable.

CanonicalizeObjective

Return type: ABSL_MUST_USE_RESULT bool

Arguments: bool simplify_domain = true

CanonicalizeOneObjectiveVariable

Return type: ABSL_MUST_USE_RESULT bool

Arguments: int var

CanonicalizeVariable

Return type: void

Arguments: int ref

A "canonical domain" always have a MinOf() equal to zero. If needed we introduce a new variable with such canonical domain and add the relation X = Y + offset. This is useful in some corner case to avoid overflow. TODO(user): When we can always get rid of affine relation, it might be good to do a final pass to canonicalize all domains in a model after presolve.

ClearPrecedenceCache

Return type: void

Clear the precedence cache.

ClearStats

Return type: void

Clears the "rules" statistics.

ConstraintIsInactive

Return type: bool

Arguments: int ct_index

Checks if a constraint contains an enforcement literal set to false, or if it has been cleared.

ConstraintIsOptional

Return type: bool

Arguments: int ct_ref

Checks if a constraint contains an enforcement literal not fixed, and no enforcement literals set to false.

ConstraintToVars

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

Arguments: int c

ConstraintVariableGraphIsUpToDate

Return type: bool

At the beginning of the presolve, we delay the costly creation of this "graph" until we at least ran some basic presolve. This is because during a LNS neighbhorhood, many constraints will be reduced significantly by this "simple" presolve.

ConstraintVariableUsageIsConsistent

Return type: bool

Returns true if our current constraints <-> variables graph is ok. This is meant to be used in DEBUG mode only.

DomainContains

Return type: bool

Arguments: int ref, int64_t value

DomainContains

Return type: bool

Arguments: const LinearExpressionProto& expr, int64_t value

This methods only works for affine expressions (checked).

DomainIsEmpty

Return type: bool

Arguments: int ref

Helpers to query the current domain of a variable.

DomainOf

Return type: Domain

Arguments: int ref

DomainOfVarIsIncludedIn

Return type: bool

Arguments: int var, const Domain& domain

This function takes a positive variable reference.

DomainSuperSetOf

Return type: Domain

Arguments: const LinearExpressionProto& expr

Return a super-set of the domain of the linear expression.

EndMax

Return type: int64_t

Arguments: int ct_ref

EndMin

Return type: int64_t

Arguments: int ct_ref

ExploitExactlyOneInObjective

Return type: bool

Arguments: absl::Span<const int> exactly_one

Checks if the given exactly_one is included in the objective, and simplify the objective by adding a constant value to all the exactly one terms. Returns true if a simplification was done.

ExpressionIsAffineBoolean

Return type: bool

Arguments: const LinearExpressionProto& expr

Returns true iff the expr is of the form a * literal + b. The other function can be used to get the literal that achieve MaxOf().

ExpressionIsALiteral

Return type: bool

Arguments: const LinearExpressionProto& expr, int* literal = nullptr

Returns true iff the expr is a literal (x or not(x)).

ExpressionIsSingleVariable

Return type: bool

Arguments: const LinearExpressionProto& expr

Returns true iff the expr is of the form 1 * var + 0.

FixedValue

Return type: int64_t

Arguments: int ref

FixedValue

Return type: int64_t

Arguments: const LinearExpressionProto& expr

GetAbsRelation

Return type: bool

Arguments: int target_ref, int* ref

GetAffineRelation

Return type: AffineRelation::Relation

Arguments: int ref

Returns the representative of ref under the affine relations.

GetFalseLiteral

Return type: int

GetLiteralRepresentative

Return type: int

Arguments: int ref

Returns the representative of a literal.

GetOrCreateAffineValueEncoding

Return type: int

Arguments: const LinearExpressionProto& expr, int64_t value

Gets the associated literal if it is already created. Otherwise create it, add the corresponding constraints and returns it. Important: This does not update the constraint<->variable graph, so ConstraintVariableGraphIsUpToDate() will be false until UpdateNewConstraintsVariableUsage() is called.

GetOrCreateReifiedPrecedenceLiteral

Return type: int

Arguments: const LinearExpressionProto& time_i, const LinearExpressionProto& time_j, int active_i, int active_j

The following helper adds the following constraint: result <=> (time_i <= time_j && active_i is true && active_j is true) and returns the (cached) literal result. Note that this cache should just be used temporarily and then cleared with ClearPrecedenceCache() because there is no mechanism to update the cached literals when literal equivalence are detected.

GetOrCreateVarValueEncoding

Return type: int

Arguments: int ref, int64_t value

Gets the associated literal if it is already created. Otherwise create it, add the corresponding constraints and returns it. Important: This does not update the constraint<->variable graph, so ConstraintVariableGraphIsUpToDate() will be false until UpdateNewConstraintsVariableUsage() is called.

GetReifiedPrecedenceKey

Arguments: const LinearExpressionProto& time_i, const LinearExpressionProto& time_j, int active_i, int active_j

GetTrueLiteral

Return type: int

Some expansion code use constant literal to be simpler to write. This will create a NewBoolVar() the first time, but later call will just returns it.

GetVariableRepresentative

Return type: int

Arguments: int ref

Returns another reference with exactly the same value.

HasVarValueEncoding

Return type: bool

Arguments: int ref, int64_t value, int* literal = nullptr

Returns true if a literal attached to ref == var exists. It assigns the corresponding to `literal` if non null.

InitializeNewDomains

Return type: void

Creates the internal structure for any new variables in working_model.

InsertVarValueEncoding

Return type: bool

Arguments: int literal, int ref, int64_t value

Inserts the given literal to encode ref == value. If an encoding already exists, it adds the two implications between the previous encoding and the new encoding. Important: This does not update the constraint<->variable graph, so ConstraintVariableGraphIsUpToDate() will be false until UpdateNewConstraintsVariableUsage() is called. Returns false if the model become UNSAT. TODO(user): This function is not always correct if !context->DomainOf(ref).contains(value), we could make it correct but it might be a bit expansive to do so. For now we just have a DCHECK().

IntersectDomainWith

Return type: ABSL_MUST_USE_RESULT bool

Arguments: int ref, const Domain& domain, bool* domain_modified = nullptr

Returns false if the new domain is empty. Sets 'domain_modified' (if provided) to true iff the domain is modified otherwise does not change it.

IntersectDomainWith

Return type: ABSL_MUST_USE_RESULT bool

Arguments: const LinearExpressionProto& expr, const Domain& domain, bool* domain_modified = nullptr

Same as IntersectDomainWith() but take a linear expression as input. If this expression if of size > 1, this does nothing for now, so it will only propagates for constant and affine expression.

IntervalDebugString

Return type: std::string

Arguments: int ct_ref

IntervalIsConstant

Return type: bool

Arguments: int ct_ref

Helper to query the state of an interval.

IntervalUsage

Return type: int

Arguments: int c

IsFixed

Return type: bool

Arguments: int ref

IsFixed

Return type: bool

Arguments: const LinearExpressionProto& expr

IsFullyEncoded

Return type: bool

Arguments: int ref

Returns true if we have literal <=> var = value for all values of var. TODO(user): If the domain was shrunk, we can have a false positive. Still it means that the number of values removed is greater than the number of values not encoded.

IsFullyEncoded

Return type: bool

Arguments: const LinearExpressionProto& expr

This methods only works for affine expressions (checked). It returns true iff the expression is constant or its one variable is full encoded.

LiteralForExpressionMax

Return type: int

Arguments: const LinearExpressionProto& expr

LiteralIsFalse

Return type: bool

Arguments: int lit

LiteralIsTrue

Return type: bool

Arguments: int lit

logger

Return type: SolverLogger*

LogInfo

Return type: void

Logs stats to the logger.

MarkVariableAsRemoved

Return type: void

Arguments: int ref

Functions to make sure that once we remove a variable, we no longer reuse it.

MaxOf

Return type: int64_t

Arguments: int ref

MaxOf

Return type: int64_t

Arguments: const LinearExpressionProto& expr

MinOf

Return type: int64_t

Arguments: int ref

MinOf

Return type: int64_t

Arguments: const LinearExpressionProto& expr

Helpers to query the current domain of a linear expression. This doesn't check for integer overflow, but our linear expression should be such that this cannot happen (tested at validation).

ModelIsExpanded

Return type: bool

The "expansion" phase should be done once and allow to transform complex constraints into basic ones (see cp_model_expand.h). Some presolve rules need to know if the expansion was ran before beeing applied.

ModelIsUnsat

Return type: bool

NewBoolVar

Return type: int

NewIntVar

Return type: int

Arguments: const Domain& domain

Helpers to adds new variables to the presolved model. TODO(user): We should control more how this is called so we can update a solution hint accordingly.

NotifyThatModelIsExpanded

Return type: void

NotifyThatModelIsUnsat

Return type: ABSL_MUST_USE_RESULT bool

Arguments: const std::string& message = ""

This function always return false. It is just a way to make a little bit more sure that we abort right away when infeasibility is detected.

NumAffineRelations

Return type: int

Used for statistics.

ObjectiveCoeff

Return type: int64_t

Arguments: int var

ObjectiveDomain

Return type: const Domain&

Objective getters.

ObjectiveDomainIsConstraining

Return type: bool

ObjectiveMap

Return type: const absl::flat_hash_map<int, int64_t>&

params

Return type: const SatParameters&

PresolveContext

Arguments: Model* model, CpModelProto* cp_model, CpModelProto* mapping

PropagateAffineRelation

Return type: bool

Arguments: int ref

Makes sure the domain of ref and of its representative are in sync. Returns false on unsat.

random

Return type: ModelRandomGenerator*

ReadObjectiveFromProto

Return type: void

Objective handling functions. We load it at the beginning so that during presolve we can work on the more efficient hash_map representation. Note that ReadObjectiveFromProto() makes sure that var_to_constraints of all the variable that appear in the objective contains -1. This is later enforced by all the functions modifying the objective. Note(user): Because we process affine relation only on CanonicalizeObjective(), it is possible that when processing a canonicalized linear constraint, we don't detect that a variable in affine relation is in the objective. For now this is fine, because when this is the case, we also have an affine linear constraint, so we can't really do anything with that variable since it appear in at least two constraints.

RecomputeSingletonObjectiveDomain

Return type: bool

When the objective is singleton, we can always restrict the domain of var so that the current objective domain is non-constraining. Returns false on UNSAT.

RefDebugString

Return type: std::string

Arguments: int ref

To facilitate debugging.

RegisterVariablesUsedInAssumptions

Return type: void

Make sure we never delete an "assumption" literal by using a special constraint for that.

RemoveAllVariablesFromAffineRelationConstraint

Return type: void

RemoveVariableFromAffineRelation

Return type: void

Arguments: int var

Advanced usage. This should be called when a variable can be removed from the problem, so we don't count it as part of an affine relation anymore.

RemoveVariableFromObjective

Return type: void

Arguments: int ref

Allows to manipulate the objective coefficients.

ScaleFloatingPointObjective

Return type: ABSL_MUST_USE_RESULT bool

SetLiteralToFalse

Return type: ABSL_MUST_USE_RESULT bool

Arguments: int lit

Returns false if the 'lit' doesn't have the desired value in the domain.

SetLiteralToTrue

Return type: ABSL_MUST_USE_RESULT bool

Arguments: int lit

ShiftCostInExactlyOne

Return type: void

Arguments: absl::Span<const int> exactly_one, int64_t shift

SizeMax

Return type: int64_t

Arguments: int ct_ref

SizeMin

Return type: int64_t

Arguments: int ct_ref

StartMax

Return type: int64_t

Arguments: int ct_ref

StartMin

Return type: int64_t

Arguments: int ct_ref

StoreAbsRelation

Return type: bool

Arguments: int target_ref, int ref

Stores/Get the relation target_ref = abs(ref); The first function returns false if it already exist and the second false if it is not present.

StoreAffineRelation

Return type: bool

Arguments: int ref_x, int ref_y, int64_t coeff, int64_t offset, bool debug_no_recursion = false

Adds the relation (ref_x = coeff * ref_y + offset) to the repository. Returns false if we detect infeasability because of this. Once the relation is added, it doesn't need to be enforced by a constraint in the model proto, since we will propagate such relation directly and add them to the proto at the end of the presolve. Note that this should always add a relation, even though it might need to create a new representative for both ref_x and ref_y in some cases. Like if x = 3z and y = 5t are already added, if we add x = 2y, we have 3z = 10t and can only resolve this by creating a new variable r such that z = 10r and t = 3r. All involved variables will be marked to appear in the special kAffineRelationConstraint. This will allow to identify when a variable is no longer needed (only appear there and is not a representative).

StoreBooleanEqualityRelation

Return type: bool

Arguments: int ref_a, int ref_b

Adds the fact that ref_a == ref_b using StoreAffineRelation() above. Returns false if this makes the problem infeasible.

StoreLiteralImpliesVarEqValue

Return type: bool

Arguments: int literal, int var, int64_t value

Stores the fact that literal implies var == value. It returns true if that information is new.

StoreLiteralImpliesVarNEqValue

Return type: bool

Arguments: int literal, int var, int64_t value

Stores the fact that literal implies var != value. It returns true if that information is new.

SubstituteVariableInObjective

Return type: ABSL_MUST_USE_RESULT bool

Arguments: int var_in_equality, int64_t coeff_in_equality, const ConstraintProto& equality, std::vector<int>* new_vars_in_objective = nullptr

Given a variable defined by the given inequality that also appear in the objective, remove it from the objective by transferring its cost to other variables in the equality. If new_vars_in_objective is not nullptr, it will be filled with "new" variables that where not in the objective before and are after substitution. Returns false, if the substitution cannot be done. This is the case if the model become UNSAT or if doing it will result in an objective that do not satisfy our overflow preconditions. Note that this can only happen if the substitued variable is not implied free (i.e. if its domain is smaller than the implied domain from the equality).

time_limit

Return type: TimeLimit*

UpdateConstraintVariableUsage

Return type: void

Arguments: int c

Updates the constraints <-> variables graph. This needs to be called each time a constraint is modified.

UpdateNewConstraintsVariableUsage

Return type: void

Calls UpdateConstraintVariableUsage() on all newly created constraints.

UpdateRuleStats

Return type: void

Arguments: const std::string& name, int num_times = 1

Stores a description of a rule that was just applied to have a summary of what the presolve did at the end.

VariableIsNotUsedAnymore

Return type: bool

Arguments: int ref

Returns true if this ref no longer appears in the model.

VariableIsOnlyUsedInEncodingAndMaybeInObjective

Return type: bool

Arguments: int ref

Returns true if an integer variable is only appearing in the rhs of constraints of the form lit => var in domain. When this is the case, then we can usually remove this variable and replace these constraints with the proper constraints on the enforcement literals.

VariableIsUniqueAndRemovable

Return type: bool

Arguments: int ref

Returns true if this ref only appear in one constraint.

VariableWasRemoved

Return type: bool

Arguments: int ref

VariableWithCostIsUnique

Return type: bool

Arguments: int ref

Same as VariableIsUniqueAndRemovable() except that in this case the variable also appear in the objective in addition to a single constraint.

VariableWithCostIsUniqueAndRemovable

Return type: bool

Arguments: int ref

VarToConstraints

Return type: const absl::flat_hash_set<int>&

Arguments: int var

WriteObjectiveToProto

Return type: void

WriteVariableDomainsToProto

Return type: void

Some function need the domain to be up to date in the proto. This make sures our in-memory domain are writted back to the proto.