Detailed Description

Definition at line 39 of file constraint_violation.h.

#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

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 639 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 135 of file constraint_violation.cc.

◆ AddLinearExpression()

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

Definition at line 182 of file constraint_violation.cc.

◆ AddLiteral()

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

Definition at line 145 of file constraint_violation.cc.

◆ AddOffset()

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

Definition at line 177 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 155 of file constraint_violation.cc.

◆ AppearsInViolatedConstraints()

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

Definition at line 726 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.

Definition at line 248 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 202 of file constraint_violation.cc.

◆ ConstraintToVars()

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

inline

Definition at line 141 of file constraint_violation.h.

◆ DeterministicTime()

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

inline

Definition at line 127 of file constraint_violation.h.

◆ IsViolated()

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

Definition at line 647 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 124 of file constraint_violation.cc.

◆ num_constraints()

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

inline

Model getters.

Definition at line 104 of file constraint_violation.h.

◆ ObjectiveCoefficient()

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

inline

Definition at line 131 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 781 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 652 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 734 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 reuse last_affected_variables_ to reset 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 255 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 532 of file constraint_violation.cc.

◆ VariablesAffectedByLastUpdate()

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

inline

Definition at line 86 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 192 of file constraint_violation.cc.

◆ Violation()

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

Definition at line 643 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 914 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 659 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 675 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

Detailed Description

Public Member Functions

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