C++ Reference: class VarDomination

This documentation is automatically generated.

A variable X is say to dominate a variable Y if, from any feasible solution, doing X++ and Y-- is also feasible (modulo the domain of X and Y) and has the same or a better objective value.

Note that we also look for dominance between the negation of the variables. So we detect all (X++, Y++), (X--, Y--), (X++, Y--) and (X--, Y++) cases. We reuse both ref / Negated(ref) and translate that to IntegerVariable for indexing vectors.

Once detected, dominance relation can lead to more propagation. Note however, that we will loose feasible solution that are dominated by better solutions. In particular, in a linear constraint sum coeff * Xi <= rhs with positive coeff, if an X is dominated by a set of other variable in the constraint, then its upper bound can be propagated assuming the dominating variables are at their upper bound. This can in many case result in X being fixed to its lower bound.

TODO(user): We have a lot of benchmarks and tests that shows that we don't report wrong relations, but we lack unit test that make sure we don't miss any. Try to improve the situation.
Method
ActivityShouldNotChange

Return type: void

Arguments: absl::Span<const int> refs, absl::Span<const int64_t> coeffs

ActivityShouldNotDecrease

Return type: void

Arguments: absl::Span<const int> enforcements, absl::Span<const int> refs, absl::Span<const int64_t> coeffs

ActivityShouldNotIncrease

Return type: void

Arguments: absl::Span<const int> enforcements, absl::Span<const int> refs, absl::Span<const int64_t> coeffs

CanFreelyDecrease

Return type: bool

Arguments: int ref

This is true if this variable was never restricted by any call. We can thus fix it to its lower bound.

CanFreelyDecrease

Return type: bool

Arguments: IntegerVariable var

CanOnlyDominateEachOther

Return type: void

Arguments: absl::Span<const int> refs

These functions are used to encode all of our constraints. The algorithm work in two passes, so one should do: - 1/ Convert all problem constraints to one or more calls - 2/ Call EndFirstPhase() - 3/ Redo 1. Only the one sided constraint need to be processed again. But calling the others will just do nothing, so it is fine too. - 4/ Call EndSecondPhase() The names are pretty self-explanatory. A few linear constraint ex: - To encode terms = cte, one should call ActivityShouldNotChange() - To encode terms >= cte, one should call ActivityShouldNotDecrease() - To encode terms <= cte, one should call ActivityShouldNotIncrease() The coeffs vector can be left empty, in which case all variable are assumed to have the same coefficients. CanOnlyDominateEachOther() is basically the same as ActivityShouldNotChange() without any coefficients. Note(user): It is better complexity wise to first refine the underlying partition as much as possible, and then process all ActivityShouldNotIncrease() and ActivityShouldNotDecrease() in two passes. Experiment with it, it might require changing the API slightly since the increase / decrease functions also refine the partition.

DominatingVariables

Return type: absl::Span<const IntegerVariable>

Arguments: int ref

Returns a set of variable dominating the given ones. Note that to keep the algo efficient, this might not include all the possible dominations. Note: we never include as part of the dominating candidate variables that can freely increase.

DominatingVariables

Return type: absl::Span<const IntegerVariable>

Arguments: IntegerVariable var

DominationDebugString

Return type: std::string

Arguments: IntegerVariable var

Returns readable string with the possible valid combinations of the form (var++/--, dom++/--) to facilitate debugging.

EndFirstPhase

Return type: void

EndFirstPhase() must be called once all constraints have been processed once. One then needs to redo the calls to ActivityShouldNotIncrease() and ActivityShouldNotDecrease(). And finally call EndSecondPhase() before querying the domination information.

EndSecondPhase

Return type: void

IntegerVariableToRef

Return type: static int

Arguments: IntegerVariable var

RefToIntegerVariable

Return type: static IntegerVariable

Arguments: int ref

This is the translation used from "ref" to IntegerVariable. The API understand the cp_mode.proto ref, but internally we only store IntegerVariable.

Reset

Return type: void

Arguments: int num_variables

Reset the class to a clean state. At the beginning, we assume that there is no constraint.

VarDomination