#include <constraint_violation.h>

Public Member Functions
	LsEvaluator (const CpModelProto &cp_model, const SatParameters &params)
	The cp_model must outlive this class.

	LsEvaluator (const CpModelProto &cp_model, const SatParameters &params, const std::vector< bool > &ignored_constraints, const std::vector< ConstraintProto > &additional_constraints)

bool	ReduceObjectiveBounds (int64_t lb, int64_t ub)

void	ComputeAllViolations (absl::Span< const int64_t > solution)
	Recomputes the violations of all constraints (resp only non-linear one).

void	ComputeAllNonLinearViolations (absl::Span< const int64_t > solution)

void	UpdateNonLinearViolations (int var, int64_t old_value, absl::Span< const int64_t > new_solution)
	Recomputes the violations of all impacted non linear constraints.

void	UpdateLinearScores (int var, int64_t old_value, int64_t new_value, absl::Span< const double > weights, absl::Span< const int64_t > jump_deltas, absl::Span< double > jump_scores)
	Function specific to the linear only feasibility jump.

void	UpdateViolatedList ()

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

int64_t	SumOfViolations ()
	Simple summation metric for the constraint and objective violations.

int64_t	ObjectiveActivity () const
	Returns the objective activity in the current state.

bool	IsObjectiveConstraint (int c) const

int64_t	ObjectiveCoefficient (int var) const

int	NumLinearConstraints () const

int	NumNonLinearConstraints () const

int	NumEvaluatorConstraints () const

int	NumInfeasibleConstraints () const

int64_t	Violation (int c) const

bool	IsViolated (int c) const

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

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

const LinearIncrementalEvaluator &	LinearEvaluator ()

LinearIncrementalEvaluator *	MutableLinearEvaluator ()

void	RecomputeViolatedList (bool linear_only)

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

int	NumViolatedConstraintsForVarIgnoringObjective (int var) const
	Returns the number of constraints in ViolatedConstraints containing `var`.

bool	VariableOnlyInLinearConstraintWithConvexViolationChange (int var) const
	Indicates if the computed jump value is always the best choice.

const std::vector< int > &	last_update_violation_changes () const

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

absl::Span< const int >	VarToGeneralConstraints (int var) const

absl::Span< const int >	GeneralConstraintToVars (int general_c) const

double	DeterministicTime () const

Detailed Description

Evaluation container for the local search.

Todo: (user): Ideas for constraint generated moves or sequences of moves?

Note(user): This class do not handle ALL constraint yet. So it is not because there is no violation here that the solution will be feasible. It is important to check feasibility once this is used. Note that in practice, we can be lucky, and feasible on a subset of hard constraint is enough.

Definition at line 306 of file constraint_violation.h.

Constructor & Destructor Documentation

◆ LsEvaluator() [1/2]

operations_research::sat::LsEvaluator::LsEvaluator	(	const CpModelProto &	cp_model,
		const SatParameters &	params )

The cp_model must outlive this class.

--— LsEvaluator --—

Definition at line 1490 of file constraint_violation.cc.

◆ LsEvaluator() [2/2]

operations_research::sat::LsEvaluator::LsEvaluator	(	const CpModelProto &	cp_model,
		const SatParameters &	params,
		const std::vector< bool > &	ignored_constraints,
		const std::vector< ConstraintProto > &	additional_constraints )

Definition at line 1505 of file constraint_violation.cc.

Member Function Documentation

◆ ComputeAllNonLinearViolations()

void operations_research::sat::LsEvaluator::ComputeAllNonLinearViolations ( absl::Span< const int64_t > solution )

Generic constraints.

Definition at line 1868 of file constraint_violation.cc.

◆ ComputeAllViolations()

void operations_research::sat::LsEvaluator::ComputeAllViolations ( absl::Span< const int64_t > solution )

Recomputes the violations of all constraints (resp only non-linear one).

Linear constraints.

Generic constraints.

Definition at line 1856 of file constraint_violation.cc.

◆ ConstraintToVars()

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

inline

Definition at line 408 of file constraint_violation.h.

◆ DeterministicTime()

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

inline

Todo: (user): Properly account all big time consumers.

Definition at line 425 of file constraint_violation.h.

◆ GeneralConstraintToVars()

absl::Span< const int > operations_research::sat::LsEvaluator::GeneralConstraintToVars ( int general_c ) const

inline

Definition at line 420 of file constraint_violation.h.

◆ IsObjectiveConstraint()

bool operations_research::sat::LsEvaluator::IsObjectiveConstraint ( int c ) const

inline

Definition at line 346 of file constraint_violation.h.

◆ IsViolated()

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

Definition at line 1970 of file constraint_violation.cc.

◆ last_update_violation_changes()

const std::vector< int > & operations_research::sat::LsEvaluator::last_update_violation_changes ( ) const

inline

Definition at line 404 of file constraint_violation.h.

◆ LinearEvaluator()

const LinearIncrementalEvaluator & operations_research::sat::LsEvaluator::LinearEvaluator ( )

inline

Definition at line 378 of file constraint_violation.h.

◆ MutableLinearEvaluator()

LinearIncrementalEvaluator * operations_research::sat::LsEvaluator::MutableLinearEvaluator ( )

inline

Definition at line 382 of file constraint_violation.h.

◆ NumEvaluatorConstraints()

int operations_research::sat::LsEvaluator::NumEvaluatorConstraints ( ) const

Definition at line 1942 of file constraint_violation.cc.

◆ NumInfeasibleConstraints()

int operations_research::sat::LsEvaluator::NumInfeasibleConstraints ( ) const

Definition at line 1947 of file constraint_violation.cc.

◆ NumLinearConstraints()

int operations_research::sat::LsEvaluator::NumLinearConstraints ( ) const

The number of "internal" constraints in the evaluator. This might not be the same as the number of initial constraints of the model.

Definition at line 1934 of file constraint_violation.cc.

◆ NumNonLinearConstraints()

int operations_research::sat::LsEvaluator::NumNonLinearConstraints ( ) const

Definition at line 1938 of file constraint_violation.cc.

◆ NumViolatedConstraintsForVarIgnoringObjective()

int operations_research::sat::LsEvaluator::NumViolatedConstraintsForVarIgnoringObjective ( int var ) const

inline

Returns the number of constraints in ViolatedConstraints containing var.

Definition at line 397 of file constraint_violation.h.

◆ ObjectiveActivity()

int64_t operations_research::sat::LsEvaluator::ObjectiveActivity ( ) const

Returns the objective activity in the current state.

Definition at line 1929 of file constraint_violation.cc.

◆ ObjectiveCoefficient()

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

inline

Definition at line 350 of file constraint_violation.h.

◆ RecomputeViolatedList()

void operations_research::sat::LsEvaluator::RecomputeViolatedList ( bool linear_only )

List of the currently violated constraints.

It is initialized by RecomputeViolatedList()
And incrementally maintained by UpdateVariableValue()

The order depends on the algorithm used and shouldn't be relied on.

Definition at line 2024 of file constraint_violation.cc.

◆ ReduceObjectiveBounds()

bool operations_research::sat::LsEvaluator::ReduceObjectiveBounds	(	int64_t	lb,
		int64_t	ub )

Intersects the domain of the objective with [lb..ub]. It returns true if a reduction of the domain took place.

Definition at line 1847 of file constraint_violation.cc.

◆ SumOfViolations()

int64_t operations_research::sat::LsEvaluator::SumOfViolations ( )

Simple summation metric for the constraint and objective violations.

Process the linear part.

Process the generic constraint part.

Definition at line 1912 of file constraint_violation.cc.

◆ UpdateLinearScores()

void operations_research::sat::LsEvaluator::UpdateLinearScores	(	int	var,
		int64_t	old_value,
		int64_t	new_value,
		absl::Span< const double >	weights,
		absl::Span< const int64_t >	jump_deltas,
		absl::Span< double >	jump_scores )

Function specific to the linear only feasibility jump.

Definition at line 1890 of file constraint_violation.cc.

◆ UpdateNonLinearViolations()

void operations_research::sat::LsEvaluator::UpdateNonLinearViolations	(	int	var,
		int64_t	old_value,
		absl::Span< const int64_t >	new_solution )

Recomputes the violations of all impacted non linear constraints.

Definition at line 1876 of file constraint_violation.cc.

◆ UpdateViolatedList()

void operations_research::sat::LsEvaluator::UpdateViolatedList ( )

Must be called after UpdateLinearScores() / UpdateNonLinearViolations() in order to update the ViolatedConstraints().

Maintain the list of violated constraints.

Definition at line 1904 of file constraint_violation.cc.

◆ VariableOnlyInLinearConstraintWithConvexViolationChange()

bool operations_research::sat::LsEvaluator::VariableOnlyInLinearConstraintWithConvexViolationChange ( int var ) const

Indicates if the computed jump value is always the best choice.

Definition at line 2019 of file constraint_violation.cc.

◆ VariablesAffectedByLastLinearUpdate()

absl::Span< const int > operations_research::sat::LsEvaluator::VariablesAffectedByLastLinearUpdate ( ) const

inline

Definition at line 336 of file constraint_violation.h.

◆ VarToGeneralConstraints()

absl::Span< const int > operations_research::sat::LsEvaluator::VarToGeneralConstraints ( int var ) const

inline

Note: the constraint indexing is different here than in the other functions.

Definition at line 417 of file constraint_violation.h.

◆ ViolatedConstraints()

absl::Span< const int > operations_research::sat::LsEvaluator::ViolatedConstraints ( ) const

inline

Definition at line 392 of file constraint_violation.h.

◆ Violation()

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

Returns the weighted sum of violation. The weights must have the same size as NumEvaluatorConstraints().

Definition at line 1962 of file constraint_violation.cc.

◆ WeightedViolation()

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

Definition at line 1979 of file constraint_violation.cc.

◆ WeightedViolationDelta()

double operations_research::sat::LsEvaluator::WeightedViolationDelta	(	bool	linear_only,
		absl::Span< const double >	weights,
		int	var,
		int64_t	delta,
		absl::Span< int64_t >	mutable_solution ) const

Computes the delta in weighted violation if solution[var] += delta. We need a temporary mutable solution to evaluate the violation of generic constraints. If linear_only is true, only the linear violation will be used.

We change the mutable solution here, and restore it after the evaluation.

We assume linear time delta computation in number of variables.

Todo: (user): refine on a per constraint basis.

Restore.

Definition at line 1991 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

◆ LsEvaluator() [1/2]

◆ LsEvaluator() [2/2]

Member Function Documentation

◆ ComputeAllNonLinearViolations()

◆ ComputeAllViolations()

◆ ConstraintToVars()

◆ DeterministicTime()

◆ GeneralConstraintToVars()

◆ IsObjectiveConstraint()

◆ IsViolated()

◆ last_update_violation_changes()

◆ LinearEvaluator()

◆ MutableLinearEvaluator()

◆ NumEvaluatorConstraints()

◆ NumInfeasibleConstraints()

◆ NumLinearConstraints()

◆ NumNonLinearConstraints()

◆ NumViolatedConstraintsForVarIgnoringObjective()

◆ ObjectiveActivity()

◆ ObjectiveCoefficient()

◆ RecomputeViolatedList()

◆ ReduceObjectiveBounds()

◆ SumOfViolations()

◆ UpdateLinearScores()

◆ UpdateNonLinearViolations()

◆ UpdateViolatedList()

◆ VariableOnlyInLinearConstraintWithConvexViolationChange()

◆ VariablesAffectedByLastLinearUpdate()

◆ VarToGeneralConstraints()

◆ ViolatedConstraints()

◆ Violation()

◆ WeightedViolation()

◆ WeightedViolationDelta()