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 309 of file constraint_violation.h.

#include <constraint_violation.h>

Public Member Functions
	LsEvaluator (const CpModelProto &cp_model, const SatParameters &params, TimeLimit *time_limit)
	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, TimeLimit *time_limit)
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

Constructor & Destructor Documentation

◆ LsEvaluator() [1/2]

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

The cp_model must outlive this class.

--— LsEvaluator --—

Definition at line 1484 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,
		TimeLimit *	time_limit )

Definition at line 1500 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 1891 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 1879 of file constraint_violation.cc.

◆ ConstraintToVars()

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

inline

Definition at line 413 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 430 of file constraint_violation.h.

◆ GeneralConstraintToVars()

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

inline

Definition at line 425 of file constraint_violation.h.

◆ IsObjectiveConstraint()

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

inline

Definition at line 351 of file constraint_violation.h.

◆ IsViolated()

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

Definition at line 1993 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 409 of file constraint_violation.h.

◆ LinearEvaluator()

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

inline

Definition at line 383 of file constraint_violation.h.

◆ MutableLinearEvaluator()

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

inline

Definition at line 387 of file constraint_violation.h.

◆ NumEvaluatorConstraints()

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

Definition at line 1965 of file constraint_violation.cc.

◆ NumInfeasibleConstraints()

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

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

◆ NumNonLinearConstraints()

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

Definition at line 1961 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 402 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 1952 of file constraint_violation.cc.

◆ ObjectiveCoefficient()

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

inline

Definition at line 355 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 2048 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 1870 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 1935 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 1913 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 1899 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 1927 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 2043 of file constraint_violation.cc.

◆ VariablesAffectedByLastLinearUpdate()

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

inline

Definition at line 341 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 422 of file constraint_violation.h.

◆ ViolatedConstraints()

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

inline

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

◆ WeightedViolation()

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

Definition at line 2002 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 2014 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

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