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
21#include "ortools/bop/bop_lns.h"
22#include "ortools/bop/bop_parameters.pb.h"
26#include "ortools/sat/boolean_problem.pb.h"
28#include "ortools/util/stats.h"
30
31namespace operations_research {
32namespace bop {
33
34DEFINE_INT_TYPE(OptimizerIndex, int);
35const OptimizerIndex kInvalidOptimizerIndex(-1);
36
37// Forward declaration.
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...