#include <var_domination.h>

Public Member Functions
	VarDomination ()=default

void	Reset (int num_variables)

void	CanOnlyDominateEachOther (absl::Span< const int > refs)

void	ActivityShouldNotChange (absl::Span< const int > refs, absl::Span< const int64_t > coeffs)

void	ActivityShouldNotDecrease (absl::Span< const int > enforcements, absl::Span< const int > refs, absl::Span< const int64_t > coeffs)

void	ActivityShouldNotIncrease (absl::Span< const int > enforcements, absl::Span< const int > refs, absl::Span< const int64_t > coeffs)

bool	EndFirstPhase ()

void	EndSecondPhase ()

bool	CanFreelyDecrease (int ref) const

bool	CanFreelyDecrease (IntegerVariable var) const

absl::Span< const IntegerVariable >	DominatingVariables (int ref) const

absl::Span< const IntegerVariable >	DominatingVariables (IntegerVariable var) const

std::string	DominationDebugString (IntegerVariable var) const

Static Public Member Functions
static IntegerVariable	RefToIntegerVariable (int ref)

static int	IntegerVariableToRef (IntegerVariable var)

Detailed Description

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

Definition at line 52 of file var_domination.h.

Constructor & Destructor Documentation

◆ VarDomination()

operations_research::sat::VarDomination::VarDomination ( )

default

Member Function Documentation

◆ ActivityShouldNotChange()

void operations_research::sat::VarDomination::ActivityShouldNotChange	(	absl::Span< const int >	refs,
		absl::Span< const int64_t >	coeffs )

Definition at line 93 of file var_domination.cc.

◆ ActivityShouldNotDecrease()

void operations_research::sat::VarDomination::ActivityShouldNotDecrease	(	absl::Span< const int >	enforcements,
		absl::Span< const int >	refs,
		absl::Span< const int64_t >	coeffs )

Definition at line 145 of file var_domination.cc.

◆ ActivityShouldNotIncrease()

void operations_research::sat::VarDomination::ActivityShouldNotIncrease	(	absl::Span< const int >	enforcements,
		absl::Span< const int >	refs,
		absl::Span< const int64_t >	coeffs )

Definition at line 152 of file var_domination.cc.

◆ CanFreelyDecrease() [1/2]

bool operations_research::sat::VarDomination::CanFreelyDecrease ( int ref ) const

This is true if this variable was never restricted by any call. We can thus fix it to its lower bound. Note that we don't do that here as the DualBoundStrengthening class will take care of that.

Definition at line 519 of file var_domination.cc.

◆ CanFreelyDecrease() [2/2]

bool operations_research::sat::VarDomination::CanFreelyDecrease ( IntegerVariable var ) const

Definition at line 523 of file var_domination.cc.

◆ CanOnlyDominateEachOther()

void operations_research::sat::VarDomination::CanOnlyDominateEachOther ( 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.

Definition at line 83 of file var_domination.cc.

◆ DominatingVariables() [1/2]

absl::Span< const IntegerVariable > operations_research::sat::VarDomination::DominatingVariables ( int ref ) const

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.

Definition at line 535 of file var_domination.cc.

◆ DominatingVariables() [2/2]

absl::Span< const IntegerVariable > operations_research::sat::VarDomination::DominatingVariables ( IntegerVariable var ) const

Definition at line 540 of file var_domination.cc.

◆ DominationDebugString()

std::string operations_research::sat::VarDomination::DominationDebugString ( IntegerVariable var ) const

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

Definition at line 547 of file var_domination.cc.

◆ EndFirstPhase()

bool operations_research::sat::VarDomination::EndFirstPhase ( )

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.

If EndFirstPhase() return false, there is no point continuing.

Todo: (user): Use more heuristics to not miss as much dominance relation when we crop initial lists.

Some initial lists ar too long and will be cropped to this size. We will handle them slightly differently.

Todo: (user): Tune the initial size, 50 might be a bit large, since our complexity is borned by this number times the number of entries in the constraints. Still we should in most situation be a lot lower than that.

Fill the initial domination candidates.

Two modes, either we scan the full list, or a small subset of it. Not that low variable indices should appear first, so it is better not to randomize.

Heuristic: To try not to remove domination relations corresponding to short lists during transposition (see EndSecondPhase()), we fill the cropped list with the transpose of the short list relations. This helps finding more relation in the presence of cropped lists.

Compute how many extra space we need for transposed values.

Note: it cannot be more than twice.

Copy into a new buffer.

Fill the free spaces with transposed values. But do not use new values !

Remove any duplicates.

Todo: (user): Maybe we should do that with all lists in case the input function are called with duplicates too.

We no longer need the first phase memory.

A second phase is only needed if there are some potential dominance relations.

Definition at line 217 of file var_domination.cc.

◆ EndSecondPhase()

void operations_research::sat::VarDomination::EndSecondPhase ( )

Perform intersection with transpose.

Pass 1: count.

Pass 2: compute starts.

Pass 3: transpose.

Pass 4: intersect.

Definition at line 359 of file var_domination.cc.

◆ IntegerVariableToRef()

static int operations_research::sat::VarDomination::IntegerVariableToRef ( IntegerVariable var )

inlinestatic

Definition at line 63 of file var_domination.h.

◆ RefToIntegerVariable()

static IntegerVariable operations_research::sat::VarDomination::RefToIntegerVariable ( int ref )

inlinestatic

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

Definition at line 59 of file var_domination.h.

◆ Reset()

void operations_research::sat::VarDomination::Reset ( int num_variables )

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

Definition at line 52 of file var_domination.cc.

The documentation for this class was generated from the following files:

ortools/sat/var_domination.h
ortools/sat/var_domination.cc

Public Member Functions

Static Public Member Functions