#include <constraint_violation.h>

Public Member Functions
	LinearIncrementalEvaluator ()=default

int	NewConstraint (Domain domain)
	Returns the index of the new constraint.

void	AddEnforcementLiteral (int ct_index, int lit)

void	AddLiteral (int ct_index, int lit, int64_t coeff=1)

void	AddTerm (int ct_index, int var, int64_t coeff, int64_t offset=0)

void	AddOffset (int ct_index, int64_t offset)

void	AddLinearExpression (int ct_index, const LinearExpressionProto &expr, int64_t multiplier)

void	PrecomputeCompactView (absl::Span< const int64_t > var_max_variation)

void	ComputeInitialActivities (absl::Span< const int64_t > solution)
	Compute activities.

void	UpdateVariableAndScores (int var, int64_t delta, absl::Span< const double > weights, absl::Span< const int64_t > jump_deltas, absl::Span< double > jump_scores, std::vector< int > *constraints_with_changed_violations)

void	UpdateScoreOnWeightUpdate (int c, absl::Span< const int64_t > jump_deltas, absl::Span< double > var_to_score_change)
	Also for feasibility jump.

void	ClearAffectedVariables ()

absl::Span< const int >	VariablesAffectedByLastUpdate () const

int64_t	Activity (int c) const
	Query violation.

int64_t	Violation (int c) const

bool	IsViolated (int c) const

bool	AppearsInViolatedConstraints (int var) const

bool	VarIsConsistent (int var) const
	Used to DCHECK the state of the evaluator.

bool	ReduceBounds (int c, int64_t lb, int64_t ub)

int	num_constraints () const
	Model getters.

double	WeightedViolation (absl::Span< const double > weights) const

double	WeightedViolationDelta (absl::Span< const double > weights, int var, int64_t delta) const

std::vector< int64_t >	SlopeBreakpoints (int var, int64_t current_value, const Domain &var_domain) const

bool	ViolationChangeIsConvex (int var) const
	Checks if the jump value of a variable is always optimal.

double	DeterministicTime () const

int64_t	ObjectiveCoefficient (int var) const

absl::Span< const int >	ConstraintToVars (int c) const

Detailed Description

Definition at line 35 of file constraint_violation.h.

Constructor & Destructor Documentation

◆ LinearIncrementalEvaluator()

operations_research::sat::LinearIncrementalEvaluator::LinearIncrementalEvaluator ( )

default

Member Function Documentation

◆ Activity()

int64_t operations_research::sat::LinearIncrementalEvaluator::Activity ( int c ) const

Query violation.

Definition at line 679 of file constraint_violation.cc.

◆ AddEnforcementLiteral()

void operations_research::sat::LinearIncrementalEvaluator::AddEnforcementLiteral	(	int	ct_index,
		int	lit )

Incrementaly build the constraint.

In case of duplicate variables on the same constraint, the code assumes constraints are built in-order as it checks for duplication.

Note: the code assume that a Boolean variable DO NOT appear both in the enforcement list and in the constraint. Otherwise the update will just be wrong. This should be enforced by our presolve.

Definition at line 145 of file constraint_violation.cc.

◆ AddLinearExpression()

void operations_research::sat::LinearIncrementalEvaluator::AddLinearExpression	(	int	ct_index,
		const LinearExpressionProto &	expr,
		int64_t	multiplier )

Definition at line 192 of file constraint_violation.cc.

◆ AddLiteral()

void operations_research::sat::LinearIncrementalEvaluator::AddLiteral	(	int	ct_index,
		int	lit,
		int64_t	coeff = 1 )

Definition at line 155 of file constraint_violation.cc.

◆ AddOffset()

void operations_research::sat::LinearIncrementalEvaluator::AddOffset	(	int	ct_index,
		int64_t	offset )

Definition at line 187 of file constraint_violation.cc.

◆ AddTerm()

void operations_research::sat::LinearIncrementalEvaluator::AddTerm	(	int	ct_index,
		int	var,
		int64_t	coeff,
		int64_t	offset = 0 )

Definition at line 165 of file constraint_violation.cc.

◆ AppearsInViolatedConstraints()

bool operations_research::sat::LinearIncrementalEvaluator::AppearsInViolatedConstraints ( int var ) const

Definition at line 766 of file constraint_violation.cc.

◆ ClearAffectedVariables()

void operations_research::sat::LinearIncrementalEvaluator::ClearAffectedVariables ( )

Variables whose score/jump might have changed since the last clear.

Note: because we reason on a per-constraint basis, this is actually independent of the set of positive constraint weight used.

Sparse.

Dense.

Definition at line 258 of file constraint_violation.cc.

◆ ComputeInitialActivities()

void operations_research::sat::LinearIncrementalEvaluator::ComputeInitialActivities ( absl::Span< const int64_t > solution )

Compute activities.

Resets the activity as the offset and the number of false enforcement to 0.

Update these numbers for all columns.

Cache violations (not counting enforcement).

Definition at line 212 of file constraint_violation.cc.

◆ ConstraintToVars()

absl::Span< const int > operations_research::sat::LinearIncrementalEvaluator::ConstraintToVars ( int c ) const

inline

Definition at line 137 of file constraint_violation.h.

◆ DeterministicTime()

double operations_research::sat::LinearIncrementalEvaluator::DeterministicTime ( ) const

inline

Definition at line 123 of file constraint_violation.h.

◆ IsViolated()

bool operations_research::sat::LinearIncrementalEvaluator::IsViolated ( int c ) const

Definition at line 687 of file constraint_violation.cc.

◆ NewConstraint()

int operations_research::sat::LinearIncrementalEvaluator::NewConstraint ( Domain domain )

Returns the index of the new constraint.

-— LinearIncrementalEvaluator --—

Definition at line 134 of file constraint_violation.cc.

◆ num_constraints()

int operations_research::sat::LinearIncrementalEvaluator::num_constraints ( ) const

inline

Model getters.

Definition at line 100 of file constraint_violation.h.

◆ ObjectiveCoefficient()

int64_t operations_research::sat::LinearIncrementalEvaluator::ObjectiveCoefficient ( int var ) const

inline

Definition at line 127 of file constraint_violation.h.

◆ PrecomputeCompactView()

void operations_research::sat::LinearIncrementalEvaluator::PrecomputeCompactView ( absl::Span< const int64_t > var_max_variation )

Important: this needs to be called after all constraint has been added and before the class starts to be used. This is DCHECKed.

Compute the total size.

Note: at this point the constraint indices are not "encoded" yet.

Compactify for faster WeightedViolationDelta().

We do not need var_entries_ or literal_entries_ anymore.

Todo: (user): We could delete them before. But at the time of this optimization, I didn't want to change the behavior of the algorithm at all.

Initialize the SpanData. Transform tmp_row_sizes_ to starts in the row_var_buffer_. Transform tmp_row_num_linear_entries_ to starts in the row_coeff_buffer_.

Copy data.

Definition at line 821 of file constraint_violation.cc.

◆ ReduceBounds()

bool operations_research::sat::LinearIncrementalEvaluator::ReduceBounds	(	int	c,
		int64_t	lb,
		int64_t	ub )

Intersect constraint bounds with [lb..ub]. It returns true if a reduction of the domain took place.

Definition at line 692 of file constraint_violation.cc.

◆ SlopeBreakpoints()

std::vector< int64_t > operations_research::sat::LinearIncrementalEvaluator::SlopeBreakpoints	(	int	var,
		int64_t	current_value,
		const Domain &	var_domain ) const

The violation for each constraint is a piecewise linear function. This computes and aggregates all the breakpoints for the given variable and its domain.

Note: if the domain contains less than two values, we return an empty vector. This function is not meant to be used for such domains.

We only consider min / max. There is a change when we cross the slack.

Todo: (user): Deal with holes?

Definition at line 774 of file constraint_violation.cc.

◆ UpdateScoreOnWeightUpdate()

void operations_research::sat::LinearIncrementalEvaluator::UpdateScoreOnWeightUpdate	(	int	c,
		absl::Span< const int64_t >	jump_deltas,
		absl::Span< double >	var_to_score_change )

Also for feasibility jump.

Tricky: Here we re-use in_last_affected_variables_ to resest var_to_score_change. And in particular we need to list all variable whose score changed here. Not just the one for which we have a decrease.

Update enforcement part. Because we only update weight of currently infeasible constraint, all change are 0 -> 1 transition and change by the same amount, which is the current distance.

Update linear part.

Computing general Domain distance is slow.

Todo: (user): optimize even more for one sided constraints. Note(user): I tried to factor the two usage of this, but it is slower.

Definition at line 278 of file constraint_violation.cc.

◆ UpdateVariableAndScores()

void operations_research::sat::LinearIncrementalEvaluator::UpdateVariableAndScores	(	int	var,
		int64_t	delta,
		absl::Span< const double >	weights,
		absl::Span< const int64_t >	jump_deltas,
		absl::Span< double >	jump_scores,
		std::vector< int > *	constraints_with_changed_violation )

Update the activities of each constraints. Also update the current score for the given deltas.

Note: the score of the changed variable will not be updated correctly!; the code assumes that a column has no duplicates ct indices.

Only the 1 -> 0 are impacted. This is the same as the 1->2 transition, but the old 1->0 needs to be changed from - weight * distance to - weight * new_distance.

Definition at line 572 of file constraint_violation.cc.

◆ VariablesAffectedByLastUpdate()

absl::Span< const int > operations_research::sat::LinearIncrementalEvaluator::VariablesAffectedByLastUpdate ( ) const

inline

Definition at line 82 of file constraint_violation.h.

◆ VarIsConsistent()

bool operations_research::sat::LinearIncrementalEvaluator::VarIsConsistent ( int var ) const

Used to DCHECK the state of the evaluator.

Definition at line 202 of file constraint_violation.cc.

◆ Violation()

int64_t operations_research::sat::LinearIncrementalEvaluator::Violation ( int c ) const

Definition at line 683 of file constraint_violation.cc.

◆ ViolationChangeIsConvex()

bool operations_research::sat::LinearIncrementalEvaluator::ViolationChangeIsConvex ( int var ) const

Checks if the jump value of a variable is always optimal.

Definition at line 954 of file constraint_violation.cc.

◆ WeightedViolation()

double operations_research::sat::LinearIncrementalEvaluator::WeightedViolation ( absl::Span< const double > weights ) const

Returns the weighted sum of the violation.

Note: weights might have more entries than the number of constraints.

Definition at line 699 of file constraint_violation.cc.

◆ WeightedViolationDelta()

double operations_research::sat::LinearIncrementalEvaluator::WeightedViolationDelta	(	absl::Span< const double >	weights,
		int	var,
		int64_t	delta ) const

Computes how much the weighted violation will change if var was changed from its old value by += delta.

Most of the time is spent in this function.

Todo

(user): We can safely abort early if we know that delta will be >= 0.

(user): Maybe we can compute an absolute value instead of removing old_distance.

Since delta != 0, we are sure this is an enforced -> unenforced change.

Definition at line 715 of file constraint_violation.cc.

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

ortools/sat/constraint_violation.h
ortools/sat/constraint_violation.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LinearIncrementalEvaluator()

Member Function Documentation

◆ Activity()

◆ AddEnforcementLiteral()

◆ AddLinearExpression()

◆ AddLiteral()

◆ AddOffset()

◆ AddTerm()

◆ AppearsInViolatedConstraints()

◆ ClearAffectedVariables()

◆ ComputeInitialActivities()

◆ ConstraintToVars()

◆ DeterministicTime()

◆ IsViolated()

◆ NewConstraint()

◆ num_constraints()

◆ ObjectiveCoefficient()

◆ PrecomputeCompactView()

◆ ReduceBounds()

◆ SlopeBreakpoints()

◆ UpdateScoreOnWeightUpdate()

◆ UpdateVariableAndScores()

◆ VariablesAffectedByLastUpdate()

◆ VarIsConsistent()

◆ Violation()

◆ ViolationChangeIsConvex()

◆ WeightedViolation()

◆ WeightedViolationDelta()