![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#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 |
Definition at line 39 of file constraint_violation.h.
|
default |
int64_t operations_research::sat::LinearIncrementalEvaluator::Activity | ( | int | c | ) | const |
Query violation.
Definition at line 639 of file constraint_violation.cc.
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.
Definition at line 135 of file constraint_violation.cc.
void operations_research::sat::LinearIncrementalEvaluator::AddLinearExpression | ( | int | ct_index, |
const LinearExpressionProto & | expr, | ||
int64_t | multiplier ) |
Definition at line 182 of file constraint_violation.cc.
void operations_research::sat::LinearIncrementalEvaluator::AddLiteral | ( | int | ct_index, |
int | lit, | ||
int64_t | coeff = 1 ) |
Definition at line 145 of file constraint_violation.cc.
void operations_research::sat::LinearIncrementalEvaluator::AddOffset | ( | int | ct_index, |
int64_t | offset ) |
Definition at line 177 of file constraint_violation.cc.
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.
bool operations_research::sat::LinearIncrementalEvaluator::AppearsInViolatedConstraints | ( | int | var | ) | const |
Definition at line 726 of file constraint_violation.cc.
void operations_research::sat::LinearIncrementalEvaluator::ClearAffectedVariables | ( | ) |
Variables whose score/jump might have changed since the last clear.
Definition at line 248 of file constraint_violation.cc.
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.
|
inline |
Definition at line 141 of file constraint_violation.h.
|
inline |
Definition at line 127 of file constraint_violation.h.
bool operations_research::sat::LinearIncrementalEvaluator::IsViolated | ( | int | c | ) | const |
Definition at line 647 of file constraint_violation.cc.
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.
|
inline |
Model getters.
Definition at line 104 of file constraint_violation.h.
|
inline |
Definition at line 131 of file constraint_violation.h.
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.
Compactify for faster WeightedViolationDelta().
We do not need var_entries_ or literal_entries_ anymore.
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.
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.
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.
We only consider min / max. There is a change when we cross the slack.
Definition at line 734 of file constraint_violation.cc.
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.
Definition at line 255 of file constraint_violation.cc.
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.
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.
|
inline |
Definition at line 86 of file constraint_violation.h.
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.
int64_t operations_research::sat::LinearIncrementalEvaluator::Violation | ( | int | c | ) | const |
Definition at line 643 of file constraint_violation.cc.
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.
double operations_research::sat::LinearIncrementalEvaluator::WeightedViolation | ( | absl::Span< const double > | weights | ) | const |
Returns the weighted sum of the violation.
Definition at line 659 of file constraint_violation.cc.
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.
(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.
Since delta != 0, we are sure this is an enforced -> unenforced change.
Definition at line 675 of file constraint_violation.cc.