OR-Tools  8.2
pseudo_costs.h
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 
14 #ifndef OR_TOOLS_SAT_PSEUDO_COSTS_H_
15 #define OR_TOOLS_SAT_PSEUDO_COSTS_H_
16 
17 #include <vector>
18 
20 #include "ortools/sat/integer.h"
21 #include "ortools/sat/util.h"
22 
23 namespace operations_research {
24 namespace sat {
25 
26 // Pseudo cost of a variable is measured as average observed change in the
27 // objective bounds per unit change in the variable bounds.
28 class PseudoCosts {
29  public:
30  // Helper struct to get information relavant for pseudo costs from branching
31  // decisions.
33  IntegerVariable var = kNoIntegerVariable;
34  IntegerValue lower_bound_change = IntegerValue(0);
35  };
36  explicit PseudoCosts(Model* model);
37 
38  // Updates the pseudo costs for the given decision.
39  void UpdateCost(const std::vector<VariableBoundChange>& bound_changes,
40  IntegerValue obj_bound_improvement);
41 
42  // Returns the variable with best reliable pseudo cost that is not fixed.
43  IntegerVariable GetBestDecisionVar();
44 
45  // Returns the pseudo cost of given variable. Currently used for testing only.
46  double GetCost(IntegerVariable var) const {
47  CHECK_LT(var, pseudo_costs_.size());
48  return pseudo_costs_[var].CurrentAverage();
49  }
50 
51  // Returns the number of recordings of given variable. Currently used for
52  // testing only.
53  int GetRecordings(IntegerVariable var) const {
54  CHECK_LT(var, pseudo_costs_.size());
55  return pseudo_costs_[var].NumRecords();
56  }
57 
58  private:
59  // Updates the cost of a given variable.
60  void UpdateCostForVar(IntegerVariable var, double new_cost);
61 
62  // Reference of integer trail to access the current bounds of variables.
63  const IntegerTrail& integer_trail_;
64 
65  const SatParameters& parameters_;
66 
68 };
69 
70 // Returns extracted information to update pseudo costs from the given
71 // branching decision.
72 std::vector<PseudoCosts::VariableBoundChange> GetBoundChanges(
73  LiteralIndex decision, Model* model);
74 
75 } // namespace sat
76 } // namespace operations_research
77 
78 #endif // OR_TOOLS_SAT_PSEUDO_COSTS_H_
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
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 IntegerVariable kNoIntegerVariable(-1)
std::vector< PseudoCosts::VariableBoundChange > GetBoundChanges(LiteralIndex decision, Model *model)
Definition: pseudo_costs.cc:99
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...