OR-Tools  8.2
pseudo_costs.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <cmath>
17#include <vector>
18
19#include "ortools/sat/integer.h"
21#include "ortools/sat/sat_parameters.pb.h"
22#include "ortools/sat/util.h"
23
24namespace operations_research {
25namespace sat {
26
28 : integer_trail_(*model->GetOrCreate<IntegerTrail>()),
29 parameters_(*model->GetOrCreate<SatParameters>()) {
30 const int num_vars = integer_trail_.NumIntegerVariables().value();
31 pseudo_costs_.resize(num_vars);
32}
33
34void PseudoCosts::UpdateCostForVar(IntegerVariable var, double new_cost) {
35 if (var >= pseudo_costs_.size()) {
36 // Create space for new variable and its negation.
37 const int new_size = std::max(var, NegationOf(var)).value() + 1;
38 pseudo_costs_.resize(new_size, IncrementalAverage(0.0));
39 }
40 DCHECK_LT(var, pseudo_costs_.size());
41 pseudo_costs_[var].AddData(new_cost);
42}
43
45 const std::vector<VariableBoundChange>& bound_changes,
46 const IntegerValue obj_bound_improvement) {
47 DCHECK_GE(obj_bound_improvement, 0);
48 if (obj_bound_improvement == IntegerValue(0)) return;
49
50 for (const VariableBoundChange& decision : bound_changes) {
51 if (integer_trail_.IsCurrentlyIgnored(decision.var)) continue;
52 if (decision.lower_bound_change == IntegerValue(0)) continue;
53
54 const double current_pseudo_cost =
55 ToDouble(obj_bound_improvement) / ToDouble(decision.lower_bound_change);
56 UpdateCostForVar(decision.var, current_pseudo_cost);
57 }
58}
59
61 if (pseudo_costs_.empty()) return kNoIntegerVariable;
62
63 const double epsilon = 1e-6;
64
65 double best_cost = -std::numeric_limits<double>::infinity();
66 IntegerVariable chosen_var = kNoIntegerVariable;
67
68 for (IntegerVariable positive_var(0); positive_var < pseudo_costs_.size();
69 positive_var += 2) {
70 const IntegerVariable negative_var = NegationOf(positive_var);
71 if (integer_trail_.IsCurrentlyIgnored(positive_var)) continue;
72 const IntegerValue lb = integer_trail_.LowerBound(positive_var);
73 const IntegerValue ub = integer_trail_.UpperBound(positive_var);
74 if (lb >= ub) continue;
75 if (GetRecordings(positive_var) + GetRecordings(negative_var) <
76 parameters_.pseudo_cost_reliability_threshold()) {
77 continue;
78 }
79
80 // TODO(user): Experiment with different ways to merge the costs.
81 const double current_merged_cost =
82 std::max(GetCost(positive_var), epsilon) *
83 std::max(GetCost(negative_var), epsilon);
84
85 if (current_merged_cost > best_cost) {
86 chosen_var = positive_var;
87 best_cost = current_merged_cost;
88 }
89 }
90
91 // Pick the direction with best pseudo cost.
92 if (chosen_var != kNoIntegerVariable &&
93 GetCost(chosen_var) < GetCost(NegationOf(chosen_var))) {
94 chosen_var = NegationOf(chosen_var);
95 }
96 return chosen_var;
97}
98
99std::vector<PseudoCosts::VariableBoundChange> GetBoundChanges(
100 LiteralIndex decision, Model* model) {
101 std::vector<PseudoCosts::VariableBoundChange> bound_changes;
102 if (decision == kNoLiteralIndex) return bound_changes;
103 auto* encoder = model->GetOrCreate<IntegerEncoder>();
104 auto* integer_trail = model->GetOrCreate<IntegerTrail>();
105 // NOTE: We ignore negation of equality decisions.
106 for (const IntegerLiteral l :
107 encoder->GetAllIntegerLiterals(Literal(decision))) {
108 if (l.var == kNoIntegerVariable) continue;
109 if (integer_trail->IsCurrentlyIgnored(l.var)) continue;
110 PseudoCosts::VariableBoundChange var_bound_change;
111 var_bound_change.var = l.var;
112 var_bound_change.lower_bound_change =
113 l.bound - integer_trail->LowerBound(l.var);
114 bound_changes.push_back(var_bound_change);
115 }
116
117 return bound_changes;
118}
119
120} // namespace sat
121} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
bool IsCurrentlyIgnored(IntegerVariable i) const
Definition: integer.h:625
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1304
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1300
IntegerVariable NumIntegerVariables() const
Definition: integer.h:565
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
int GetRecordings(IntegerVariable var) const
Definition: pseudo_costs.h:53
void UpdateCost(const std::vector< VariableBoundChange > &bound_changes, IntegerValue obj_bound_improvement)
Definition: pseudo_costs.cc:44
double GetCost(IntegerVariable var) const
Definition: pseudo_costs.h:46
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
const LiteralIndex kNoLiteralIndex(-1)
const IntegerVariable kNoIntegerVariable(-1)
std::vector< PseudoCosts::VariableBoundChange > GetBoundChanges(LiteralIndex decision, Model *model)
Definition: pseudo_costs.cc:99
double ToDouble(IntegerValue value)
Definition: integer.h:69
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.cc:27
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...