OR-Tools  8.2
bop_portfolio.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 <cstdint>
17#include <limits>
18
19#include "absl/memory/memory.h"
20#include "absl/strings/str_format.h"
23#include "ortools/bop/bop_fs.h"
24#include "ortools/bop/bop_lns.h"
25#include "ortools/bop/bop_ls.h"
29#include "ortools/sat/boolean_problem.pb.h"
31
32namespace operations_research {
33namespace bop {
34
35using ::operations_research::sat::LinearBooleanProblem;
36using ::operations_research::sat::LinearObjective;
37
38namespace {
39void BuildObjectiveTerms(const LinearBooleanProblem& problem,
40 BopConstraintTerms* objective_terms) {
41 CHECK(objective_terms != nullptr);
42
43 if (!objective_terms->empty()) return;
44
45 const LinearObjective& objective = problem.objective();
46 const size_t num_objective_terms = objective.literals_size();
47 CHECK_EQ(num_objective_terms, objective.coefficients_size());
48 for (int i = 0; i < num_objective_terms; ++i) {
49 CHECK_GT(objective.literals(i), 0);
50 CHECK_NE(objective.coefficients(i), 0);
51
52 const VariableIndex var_id(objective.literals(i) - 1);
53 const int64_t weight = objective.coefficients(i);
54 objective_terms->push_back(BopConstraintTerm(var_id, weight));
55 }
56}
57} // anonymous namespace
58
59//------------------------------------------------------------------------------
60// PortfolioOptimizer
61//------------------------------------------------------------------------------
63 const ProblemState& problem_state, const BopParameters& parameters,
64 const BopSolverOptimizerSet& optimizer_set, const std::string& name)
66 random_(),
67 state_update_stamp_(ProblemState::kInitialStampValue),
68 objective_terms_(),
69 selector_(),
70 optimizers_(),
71 sat_propagator_(),
72 parameters_(parameters),
73 lower_bound_(-glop::kInfinity),
74 upper_bound_(glop::kInfinity),
75 number_of_consecutive_failing_optimizers_(0) {
76 CreateOptimizers(problem_state.original_problem(), parameters, optimizer_set);
77}
78
80 if (parameters_.log_search_progress() || VLOG_IS_ON(1)) {
81 std::string stats_string;
82 for (OptimizerIndex i(0); i < optimizers_.size(); ++i) {
83 if (selector_->NumCallsForOptimizer(i) > 0) {
84 stats_string += selector_->PrintStats(i);
85 }
86 }
87 if (!stats_string.empty()) {
88 LOG(INFO) << "Stats. #new_solutions/#calls by optimizer:\n" +
89 stats_string;
90 }
91 }
92
93 // Note that unique pointers are not used due to unsupported emplace_back
94 // in ITIVectors.
95 gtl::STLDeleteElements(&optimizers_);
96}
97
98BopOptimizerBase::Status PortfolioOptimizer::SynchronizeIfNeeded(
99 const ProblemState& problem_state) {
100 if (state_update_stamp_ == problem_state.update_stamp()) {
102 }
103 state_update_stamp_ = problem_state.update_stamp();
104
105 // Load any new information into the sat_propagator_.
106 const bool first_time = (sat_propagator_.NumVariables() == 0);
107 const BopOptimizerBase::Status status =
108 LoadStateProblemToSatSolver(problem_state, &sat_propagator_);
109 if (status != BopOptimizerBase::CONTINUE) return status;
110 if (first_time) {
111 // We configure the sat_propagator_ to use the objective as an assignment
112 // preference
114 &sat_propagator_);
115 }
116
117 lower_bound_ = problem_state.GetScaledLowerBound();
118 upper_bound_ = problem_state.solution().IsFeasible()
119 ? problem_state.solution().GetScaledCost()
122}
123
125 const BopParameters& parameters, const ProblemState& problem_state,
126 LearnedInfo* learned_info, TimeLimit* time_limit) {
127 CHECK(learned_info != nullptr);
128 CHECK(time_limit != nullptr);
129 learned_info->Clear();
130
131 const BopOptimizerBase::Status sync_status =
132 SynchronizeIfNeeded(problem_state);
133 if (sync_status != BopOptimizerBase::CONTINUE) {
134 return sync_status;
135 }
136
137 for (OptimizerIndex i(0); i < optimizers_.size(); ++i) {
138 selector_->SetOptimizerRunnability(
139 i, optimizers_[i]->ShouldBeRun(problem_state));
140 }
141
142 const int64_t init_cost = problem_state.solution().IsFeasible()
143 ? problem_state.solution().GetCost()
145 const double init_deterministic_time =
146 time_limit->GetElapsedDeterministicTime();
147
148 const OptimizerIndex selected_optimizer_id = selector_->SelectOptimizer();
149 if (selected_optimizer_id == kInvalidOptimizerIndex) {
150 LOG(INFO) << "All the optimizers are done.";
152 }
153 BopOptimizerBase* const selected_optimizer =
154 optimizers_[selected_optimizer_id];
155 if (parameters.log_search_progress() || VLOG_IS_ON(1)) {
156 LOG(INFO) << " " << lower_bound_ << " .. " << upper_bound_ << " "
157 << name() << " - " << selected_optimizer->name()
158 << ". Time limit: " << time_limit->GetTimeLeft() << " -- "
159 << time_limit->GetDeterministicTimeLeft();
160 }
161 const BopOptimizerBase::Status optimization_status =
162 selected_optimizer->Optimize(parameters, problem_state, learned_info,
163 time_limit);
164
165 // ABORT means that this optimizer can't be run until we found a new solution.
166 if (optimization_status == BopOptimizerBase::ABORT) {
167 selector_->TemporarilyMarkOptimizerAsUnselectable(selected_optimizer_id);
168 }
169
170 // The gain is defined as 1 for the first solution.
171 // TODO(user): Is 1 the right value? It might be better to use a percentage
172 // of the gap, or use the same gain as for the second solution.
173 const int64_t gain =
174 optimization_status == BopOptimizerBase::SOLUTION_FOUND
175 ? (init_cost == std::numeric_limits<int64_t>::max()
176 ? 1
177 : init_cost - learned_info->solution.GetCost())
178 : 0;
179 const double spent_deterministic_time =
180 time_limit->GetElapsedDeterministicTime() - init_deterministic_time;
181 selector_->UpdateScore(gain, spent_deterministic_time);
182
183 if (optimization_status == BopOptimizerBase::INFEASIBLE ||
184 optimization_status == BopOptimizerBase::OPTIMAL_SOLUTION_FOUND) {
185 return optimization_status;
186 }
187
188 // Stop the portfolio optimizer after too many unsuccessful calls.
189 if (parameters.has_max_number_of_consecutive_failing_optimizer_calls() &&
190 problem_state.solution().IsFeasible()) {
191 number_of_consecutive_failing_optimizers_ =
192 optimization_status == BopOptimizerBase::SOLUTION_FOUND
193 ? 0
194 : number_of_consecutive_failing_optimizers_ + 1;
195 if (number_of_consecutive_failing_optimizers_ >
196 parameters.max_number_of_consecutive_failing_optimizer_calls()) {
198 }
199 }
200
201 // TODO(user): don't penalize the SatCoreBasedOptimizer or the
202 // LinearRelaxation when they improve the lower bound.
203 // TODO(user): Do we want to re-order the optimizers in the selector when
204 // the status is BopOptimizerBase::INFORMATION_FOUND?
206}
207
208void PortfolioOptimizer::AddOptimizer(
209 const LinearBooleanProblem& problem, const BopParameters& parameters,
210 const BopOptimizerMethod& optimizer_method) {
211 switch (optimizer_method.type()) {
212 case BopOptimizerMethod::SAT_CORE_BASED:
213 optimizers_.push_back(new SatCoreBasedOptimizer("SatCoreBasedOptimizer"));
214 break;
215 case BopOptimizerMethod::SAT_LINEAR_SEARCH:
216 optimizers_.push_back(new GuidedSatFirstSolutionGenerator(
218 break;
219 case BopOptimizerMethod::LINEAR_RELAXATION:
220 optimizers_.push_back(
221 new LinearRelaxation(parameters, "LinearRelaxation"));
222 break;
223 case BopOptimizerMethod::LOCAL_SEARCH: {
224 for (int i = 1; i <= parameters.max_num_decisions_in_ls(); ++i) {
225 optimizers_.push_back(new LocalSearchOptimizer(
226 absl::StrFormat("LS_%d", i), i, &sat_propagator_));
227 }
228 } break;
229 case BopOptimizerMethod::RANDOM_FIRST_SOLUTION:
230 optimizers_.push_back(new BopRandomFirstSolutionGenerator(
231 "SATRandomFirstSolution", parameters, &sat_propagator_,
232 random_.get()));
233 break;
234 case BopOptimizerMethod::RANDOM_VARIABLE_LNS:
235 BuildObjectiveTerms(problem, &objective_terms_);
236 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
237 "RandomVariableLns",
238 /*use_lp_to_guide_sat=*/false,
239 new ObjectiveBasedNeighborhood(&objective_terms_, random_.get()),
240 &sat_propagator_));
241 break;
242 case BopOptimizerMethod::RANDOM_VARIABLE_LNS_GUIDED_BY_LP:
243 BuildObjectiveTerms(problem, &objective_terms_);
244 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
245 "RandomVariableLnsWithLp",
246 /*use_lp_to_guide_sat=*/true,
247 new ObjectiveBasedNeighborhood(&objective_terms_, random_.get()),
248 &sat_propagator_));
249 break;
250 case BopOptimizerMethod::RANDOM_CONSTRAINT_LNS:
251 BuildObjectiveTerms(problem, &objective_terms_);
252 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
253 "RandomConstraintLns",
254 /*use_lp_to_guide_sat=*/false,
255 new ConstraintBasedNeighborhood(&objective_terms_, random_.get()),
256 &sat_propagator_));
257 break;
258 case BopOptimizerMethod::RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP:
259 BuildObjectiveTerms(problem, &objective_terms_);
260 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
261 "RandomConstraintLnsWithLp",
262 /*use_lp_to_guide_sat=*/true,
263 new ConstraintBasedNeighborhood(&objective_terms_, random_.get()),
264 &sat_propagator_));
265 break;
266 case BopOptimizerMethod::RELATION_GRAPH_LNS:
267 BuildObjectiveTerms(problem, &objective_terms_);
268 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
269 "RelationGraphLns",
270 /*use_lp_to_guide_sat=*/false,
271 new RelationGraphBasedNeighborhood(problem, random_.get()),
272 &sat_propagator_));
273 break;
274 case BopOptimizerMethod::RELATION_GRAPH_LNS_GUIDED_BY_LP:
275 BuildObjectiveTerms(problem, &objective_terms_);
276 optimizers_.push_back(new BopAdaptiveLNSOptimizer(
277 "RelationGraphLnsWithLp",
278 /*use_lp_to_guide_sat=*/true,
279 new RelationGraphBasedNeighborhood(problem, random_.get()),
280 &sat_propagator_));
281 break;
282 case BopOptimizerMethod::COMPLETE_LNS:
283 BuildObjectiveTerms(problem, &objective_terms_);
284 optimizers_.push_back(
285 new BopCompleteLNSOptimizer("LNS", objective_terms_));
286 break;
287 case BopOptimizerMethod::USER_GUIDED_FIRST_SOLUTION:
288 optimizers_.push_back(new GuidedSatFirstSolutionGenerator(
289 "SATUserGuidedFirstSolution",
291 break;
292 case BopOptimizerMethod::LP_FIRST_SOLUTION:
293 optimizers_.push_back(new GuidedSatFirstSolutionGenerator(
294 "SATLPFirstSolution",
296 break;
297 case BopOptimizerMethod::OBJECTIVE_FIRST_SOLUTION:
298 optimizers_.push_back(new GuidedSatFirstSolutionGenerator(
299 "SATObjectiveFirstSolution",
301 break;
302 default:
303 LOG(FATAL) << "Unknown optimizer type.";
304 }
305}
306
307void PortfolioOptimizer::CreateOptimizers(
308 const LinearBooleanProblem& problem, const BopParameters& parameters,
309 const BopSolverOptimizerSet& optimizer_set) {
310 random_ = absl::make_unique<MTRandom>(parameters.random_seed());
311
312 if (parameters.use_symmetry()) {
313 VLOG(1) << "Finding symmetries of the problem.";
314 std::vector<std::unique_ptr<SparsePermutation>> generators;
315 sat::FindLinearBooleanProblemSymmetries(problem, &generators);
316 std::unique_ptr<sat::SymmetryPropagator> propagator(
317 new sat::SymmetryPropagator);
318 for (int i = 0; i < generators.size(); ++i) {
319 propagator->AddSymmetry(std::move(generators[i]));
320 }
321 sat_propagator_.AddPropagator(propagator.get());
322 sat_propagator_.TakePropagatorOwnership(std::move(propagator));
323 }
324
325 const int max_num_optimizers =
326 optimizer_set.methods_size() + parameters.max_num_decisions_in_ls() - 1;
327 optimizers_.reserve(max_num_optimizers);
328 for (const BopOptimizerMethod& optimizer_method : optimizer_set.methods()) {
329 const OptimizerIndex old_size(optimizers_.size());
330 AddOptimizer(problem, parameters, optimizer_method);
331 }
332
333 selector_ = absl::make_unique<OptimizerSelector>(optimizers_);
334}
335
336//------------------------------------------------------------------------------
337// OptimizerSelector
338//------------------------------------------------------------------------------
341 : run_infos_(), selected_index_(optimizers.size()) {
342 for (OptimizerIndex i(0); i < optimizers.size(); ++i) {
343 info_positions_.push_back(run_infos_.size());
344 run_infos_.push_back(RunInfo(i, optimizers[i]->name()));
345 }
346}
347
349 CHECK_GE(selected_index_, 0);
350
351 do {
352 ++selected_index_;
353 } while (selected_index_ < run_infos_.size() &&
354 !run_infos_[selected_index_].RunnableAndSelectable());
355
356 if (selected_index_ >= run_infos_.size()) {
357 // Select the first possible optimizer.
358 selected_index_ = -1;
359 for (int i = 0; i < run_infos_.size(); ++i) {
360 if (run_infos_[i].RunnableAndSelectable()) {
361 selected_index_ = i;
362 break;
363 }
364 }
365 if (selected_index_ == -1) return kInvalidOptimizerIndex;
366 } else {
367 // Select the next possible optimizer. If none, select the first one.
368 // Check that the time is smaller than all previous optimizers which are
369 // runnable.
370 bool too_much_time_spent = false;
371 const double time_spent =
372 run_infos_[selected_index_].time_spent_since_last_solution;
373 for (int i = 0; i < selected_index_; ++i) {
374 const RunInfo& info = run_infos_[i];
375 if (info.RunnableAndSelectable() &&
376 info.time_spent_since_last_solution < time_spent) {
377 too_much_time_spent = true;
378 break;
379 }
380 }
381 if (too_much_time_spent) {
382 // TODO(user): Remove this recursive call, even if in practice it's
383 // safe because the max depth is the number of optimizers.
384 return SelectOptimizer();
385 }
386 }
387
388 // Select the optimizer.
389 ++run_infos_[selected_index_].num_calls;
390 return run_infos_[selected_index_].optimizer_index;
391}
392
393void OptimizerSelector::UpdateScore(int64_t gain, double time_spent) {
394 const bool new_solution_found = gain != 0;
395 if (new_solution_found) NewSolutionFound(gain);
396 UpdateDeterministicTime(time_spent);
397
398 const double new_score = time_spent == 0.0 ? 0.0 : gain / time_spent;
399 const double kErosion = 0.2;
400 const double kMinScore = 1E-6;
401
402 RunInfo& info = run_infos_[selected_index_];
403 const double old_score = info.score;
404 info.score =
405 std::max(kMinScore, old_score * (1 - kErosion) + kErosion * new_score);
406
407 if (new_solution_found) { // Solution found
408 UpdateOrder();
409 selected_index_ = run_infos_.size();
410 }
411}
412
414 OptimizerIndex optimizer_index) {
415 run_infos_[info_positions_[optimizer_index]].selectable = false;
416}
417
418void OptimizerSelector::SetOptimizerRunnability(OptimizerIndex optimizer_index,
419 bool runnable) {
420 run_infos_[info_positions_[optimizer_index]].runnable = runnable;
421}
422
424 OptimizerIndex optimizer_index) const {
425 const RunInfo& info = run_infos_[info_positions_[optimizer_index]];
426 return absl::StrFormat(
427 " %40s : %3d/%-3d (%6.2f%%) Total gain: %6d Total Dtime: %0.3f "
428 "score: %f\n",
429 info.name, info.num_successes, info.num_calls,
430 100.0 * info.num_successes / info.num_calls, info.total_gain,
431 info.time_spent, info.score);
432}
433
435 OptimizerIndex optimizer_index) const {
436 const RunInfo& info = run_infos_[info_positions_[optimizer_index]];
437 return info.num_calls;
438}
439
441 std::string str;
442 for (int i = 0; i < run_infos_.size(); ++i) {
443 const RunInfo& info = run_infos_[i];
444 LOG(INFO) << " " << info.name << " " << info.total_gain
445 << " / " << info.time_spent << " = " << info.score << " "
446 << info.selectable << " " << info.time_spent_since_last_solution;
447 }
448}
449
450void OptimizerSelector::NewSolutionFound(int64_t gain) {
451 run_infos_[selected_index_].num_successes++;
452 run_infos_[selected_index_].total_gain += gain;
453
454 for (int i = 0; i < run_infos_.size(); ++i) {
455 run_infos_[i].time_spent_since_last_solution = 0;
456 run_infos_[i].selectable = true;
457 }
458}
459
460void OptimizerSelector::UpdateDeterministicTime(double time_spent) {
461 run_infos_[selected_index_].time_spent += time_spent;
462 run_infos_[selected_index_].time_spent_since_last_solution += time_spent;
463}
464
465void OptimizerSelector::UpdateOrder() {
466 // Re-sort optimizers.
467 std::stable_sort(run_infos_.begin(), run_infos_.end(),
468 [](const RunInfo& a, const RunInfo& b) -> bool {
469 if (a.total_gain == 0 && b.total_gain == 0)
470 return a.time_spent < b.time_spent;
471 return a.score > b.score;
472 });
473
474 // Update the positions.
475 for (int i = 0; i < run_infos_.size(); ++i) {
476 info_positions_[run_infos_[i].optimizer_index] = i;
477 }
478}
479
480} // namespace bop
481} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define LOG(severity)
Definition: base/logging.h:420
#define VLOG(verboselevel)
Definition: base/logging.h:978
size_type size() const
void push_back(const value_type &x)
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
virtual Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit)=0
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)
const BopSolution & solution() const
Definition: bop_base.h:196
const sat::LinearBooleanProblem & original_problem() const
Definition: bop_base.h:201
void AddPropagator(SatPropagator *propagator)
Definition: sat_solver.cc:405
void TakePropagatorOwnership(std::unique_ptr< SatPropagator > propagator)
Definition: sat_solver.h:142
SatParameters parameters
SharedTimeLimit * time_limit
const std::string name
const int INFO
Definition: log_severity.h:31
const int FATAL
Definition: log_severity.h:32
void STLDeleteElements(T *container)
Definition: stl_util.h:372
BopOptimizerBase::Status LoadStateProblemToSatSolver(const ProblemState &problem_state, sat::SatSolver *sat_solver)
Definition: bop_util.cc:88
const OptimizerIndex kInvalidOptimizerIndex(-1)
absl::StrongVector< SparseIndex, BopConstraintTerm > BopConstraintTerms
Definition: bop_types.h:87
const double kInfinity
Definition: lp_types.h:83
void UseObjectiveForSatAssignmentPreference(const LinearBooleanProblem &problem, SatSolver *solver)
void FindLinearBooleanProblemSymmetries(const LinearBooleanProblem &problem, std::vector< std::unique_ptr< SparsePermutation > > *generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 weight
Definition: pack.cc:509
BaseVariableAssignmentSelector *const selector_
Definition: search.cc:1856
#define VLOG_IS_ON(verboselevel)
Definition: vlog_is_on.h:41