OR-Tools  8.2
bop_portfolio.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_BOP_BOP_PORTFOLIO_H_
15 #define OR_TOOLS_BOP_BOP_PORTFOLIO_H_
16 
17 #include <cstdint>
18 
20 #include "ortools/bop/bop_base.h"
21 #include "ortools/bop/bop_lns.h"
22 #include "ortools/bop/bop_parameters.pb.h"
24 #include "ortools/bop/bop_types.h"
25 #include "ortools/glop/lp_solver.h"
26 #include "ortools/sat/boolean_problem.pb.h"
27 #include "ortools/sat/sat_solver.h"
28 #include "ortools/util/stats.h"
30 
31 namespace operations_research {
32 namespace bop {
33 
34 DEFINE_INT_TYPE(OptimizerIndex, int);
35 const OptimizerIndex kInvalidOptimizerIndex(-1);
36 
37 // Forward declaration.
38 class OptimizerSelector;
39 
40 // This class implements a portfolio optimizer.
41 // The portfolio currently includes all the following optimizers:
42 // - SAT_CORE_BASED
43 // - SAT_LINEAR_SEARCH
44 // - LINEAR_RELAXATION
45 // - LOCAL_SEARCH
46 // - RANDOM_FIRST_SOLUTION
47 // - RANDOM_CONSTRAINT_LNS
48 // - RANDOM_VARIABLE_LNS
49 // - COMPLETE_LNS
50 // - LP_FIRST_SOLUTION
51 // - OBJECTIVE_FIRST_SOLUTION
52 // - USER_GUIDED_FIRST_SOLUTION
53 // - FEASIBILITY_PUMP_FIRST_SOLUTION
54 // - RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP
55 // - RANDOM_VARIABLE_LNS_GUIDED_BY_LP
56 // - RELATION_GRAPH_LNS
57 // - RELATION_GRAPH_LNS_GUIDED_BY_LP
58 //
59 // At each call of Optimize(), the portfolio optimizer selects the next
60 // optimizer to run and runs it. The selection is auto-adaptative, meaning that
61 // optimizers that succeeded more in the previous calls to Optimizer() are more
62 // likely to be selected.
64  public:
65  PortfolioOptimizer(const ProblemState& problem_state,
66  const BopParameters& parameters,
67  const BopSolverOptimizerSet& optimizer_set,
68  const std::string& name);
69  ~PortfolioOptimizer() override;
70 
71  bool ShouldBeRun(const ProblemState& problem_state) const override {
72  return true;
73  }
74  Status Optimize(const BopParameters& parameters,
75  const ProblemState& problem_state, LearnedInfo* learned_info,
76  TimeLimit* time_limit) override;
77 
78  private:
79  BopOptimizerBase::Status SynchronizeIfNeeded(
80  const ProblemState& problem_state);
81  void AddOptimizer(const sat::LinearBooleanProblem& problem,
82  const BopParameters& parameters,
83  const BopOptimizerMethod& optimizer_method);
84  void CreateOptimizers(const sat::LinearBooleanProblem& problem,
85  const BopParameters& parameters,
86  const BopSolverOptimizerSet& optimizer_set);
87 
88  std::unique_ptr<MTRandom> random_;
89  int64_t state_update_stamp_;
90  BopConstraintTerms objective_terms_;
91  std::unique_ptr<OptimizerSelector> selector_;
93  sat::SatSolver sat_propagator_;
94  BopParameters parameters_;
95  double lower_bound_;
96  double upper_bound_;
97  int number_of_consecutive_failing_optimizers_;
98 };
99 
100 // This class is providing an adaptative selector for optimizers based on
101 // their past successes and deterministic time spent.
103  public:
104  // Note that the list of optimizers is only used to get the names for
105  // debug purposes, the ownership of the optimizers is not transferred.
106  explicit OptimizerSelector(
108 
109  // Selects the next optimizer to run based on the user defined order and
110  // history of success. Returns kInvalidOptimizerIndex if no optimizer is
111  // selectable and runnable (see the functions below).
112  //
113  // The optimizer is selected using the following algorithm (L being the
114  // sorted list of optimizers, and l the position of the last selected
115  // optimizer):
116  // a- If a new solution has been found by optimizer l, select the first
117  // optimizer l' in L, l' >= 0, that can run.
118  // b- If optimizer l didn't find a new solution, select the first
119  // optimizer l', with l' > l, such that its deterministic time spent
120  // since last solution is smaller than the deterministic time spent
121  // by any runnable optimizer in 1..l since last solution.
122  // If no such optimizer is available, go to option a.
123  OptimizerIndex SelectOptimizer();
124 
125  // Updates the internal metrics to decide which optimizer to select.
126  // This method should be called each time the selected optimizer is run.
127  //
128  // The gain corresponds to the reward to assign to the solver; It could for
129  // instance be the difference in cost between the last and the current
130  // solution.
131  //
132  // The time spent corresponds to the time the optimizer spent; To make the
133  // behavior deterministic, it is recommended to use the deterministic time
134  // instead of the elapsed time.
135  //
136  // The optimizers are sorted based on their score each time a new solution is
137  // found.
138  void UpdateScore(int64_t gain, double time_spent);
139 
140  // Marks the given optimizer as not selectable until UpdateScore() is called
141  // with a positive gain. In which case, all optimizer will become selectable
142  // again.
143  void TemporarilyMarkOptimizerAsUnselectable(OptimizerIndex optimizer_index);
144 
145  // Sets whether or not an optimizer is "runnable". Like a non-selectable one,
146  // a non-runnable optimizer will never be returned by SelectOptimizer().
147  //
148  // TODO(user): Maybe we should simply have the notion of selectability here
149  // and let the client handle the logic to decide what optimizer are selectable
150  // or not.
151  void SetOptimizerRunnability(OptimizerIndex optimizer_index, bool runnable);
152 
153  // Returns statistics about the given optimizer.
154  std::string PrintStats(OptimizerIndex optimizer_index) const;
155  int NumCallsForOptimizer(OptimizerIndex optimizer_index) const;
156 
157  // Prints some debug information. Should not be used in production.
158  void DebugPrint() const;
159 
160  private:
161  // Updates internals when a solution has been found using the selected
162  // optimizer.
163  void NewSolutionFound(int64_t gain);
164 
165  // Updates the deterministic time spent by the selected optimizer.
166  void UpdateDeterministicTime(double time_spent);
167 
168  // Sorts optimizers based on their scores.
169  void UpdateOrder();
170 
171  struct RunInfo {
172  RunInfo(OptimizerIndex i, const std::string& n)
173  : optimizer_index(i),
174  name(n),
175  num_successes(0),
176  num_calls(0),
177  total_gain(0),
178  time_spent(0.0),
179  time_spent_since_last_solution(0),
180  runnable(true),
181  selectable(true),
182  score(0.0) {}
183 
184  bool RunnableAndSelectable() const { return runnable && selectable; }
185 
186  OptimizerIndex optimizer_index;
187  std::string name;
188  int num_successes;
189  int num_calls;
190  int64_t total_gain;
191  double time_spent;
192  double time_spent_since_last_solution;
193  bool runnable;
194  bool selectable;
195  double score;
196  };
197 
198  std::vector<RunInfo> run_infos_;
200  int selected_index_;
201 };
202 
203 } // namespace bop
204 } // namespace operations_research
205 #endif // OR_TOOLS_BOP_BOP_PORTFOLIO_H_
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
const std::string & name() const
Definition: bop_base.h:49
void UpdateScore(int64_t gain, double time_spent)
std::string PrintStats(OptimizerIndex optimizer_index) const
int NumCallsForOptimizer(OptimizerIndex optimizer_index) const
OptimizerSelector(const absl::StrongVector< OptimizerIndex, BopOptimizerBase * > &optimizers)
void TemporarilyMarkOptimizerAsUnselectable(OptimizerIndex optimizer_index)
void SetOptimizerRunnability(OptimizerIndex optimizer_index, bool runnable)
bool ShouldBeRun(const ProblemState &problem_state) const override
Definition: bop_portfolio.h:71
Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
PortfolioOptimizer(const ProblemState &problem_state, const BopParameters &parameters, const BopSolverOptimizerSet &optimizer_set, const std::string &name)
SatParameters parameters
SharedTimeLimit * time_limit
const std::string name
const OptimizerIndex kInvalidOptimizerIndex(-1)
DEFINE_INT_TYPE(OptimizerIndex, int)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...