OR-Tools  8.1
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"
22 #include "ortools/sat/util.h"
23 
24 namespace operations_research {
25 namespace 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 
34 void 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 
99 std::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
operations_research::sat::PseudoCosts::GetCost
double GetCost(IntegerVariable var) const
Definition: pseudo_costs.h:45
var
IntVar * var
Definition: expr_array.cc:1858
DCHECK_LT
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
operations_research::sat::IntegerTrail
Definition: integer.h:533
operations_research::sat::kNoIntegerVariable
const IntegerVariable kNoIntegerVariable(-1)
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::sat::kNoLiteralIndex
const LiteralIndex kNoLiteralIndex(-1)
pseudo_costs.h
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
sat_decision.h
operations_research::sat::NegationOf
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
Definition: integer.cc:27
operations_research::sat::PseudoCosts::GetRecordings
int GetRecordings(IntegerVariable var) const
Definition: pseudo_costs.h:52
operations_research::sat::IntegerTrail::NumIntegerVariables
IntegerVariable NumIntegerVariables() const
Definition: integer.h:558
operations_research::sat::PseudoCosts::PseudoCosts
PseudoCosts(Model *model)
Definition: pseudo_costs.cc:27
operations_research::sat::IncrementalAverage
Definition: sat/util.h:103
operations_research::sat::GetBoundChanges
std::vector< PseudoCosts::VariableBoundChange > GetBoundChanges(LiteralIndex decision, Model *model)
Definition: pseudo_costs.cc:99
sat_parameters.pb.h
operations_research::sat::IntegerTrail::UpperBound
IntegerValue UpperBound(IntegerVariable i) const
Definition: integer.h:1287
operations_research::sat::PseudoCosts::UpdateCost
void UpdateCost(const std::vector< VariableBoundChange > &bound_changes, IntegerValue obj_bound_improvement)
Definition: pseudo_costs.cc:44
operations_research::sat::PseudoCosts::GetBestDecisionVar
IntegerVariable GetBestDecisionVar()
Definition: pseudo_costs.cc:60
operations_research::sat::Model
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
operations_research::sat::IntegerLiteral
Definition: integer.h:153
operations_research::sat::PseudoCosts::VariableBoundChange::lower_bound_change
IntegerValue lower_bound_change
Definition: pseudo_costs.h:33
DCHECK_GE
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
model
GRBmodel * model
Definition: gurobi_interface.cc:269
operations_research::sat::Literal
Definition: sat_base.h:64
operations_research::sat::ToDouble
double ToDouble(IntegerValue value)
Definition: integer.h:69
util.h
operations_research::sat::PseudoCosts::VariableBoundChange
Definition: pseudo_costs.h:31
operations_research::sat::IntegerTrail::LowerBound
IntegerValue LowerBound(IntegerVariable i) const
Definition: integer.h:1283
operations_research::sat::IntegerTrail::IsCurrentlyIgnored
bool IsCurrentlyIgnored(IntegerVariable i) const
Definition: integer.h:618
operations_research::sat::PseudoCosts::VariableBoundChange::var
IntegerVariable var
Definition: pseudo_costs.h:32
operations_research::sat::IntegerEncoder
Definition: integer.h:276
integer.h