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