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"
21 #include "ortools/base/stl_util.h"
23 #include "ortools/bop/bop_fs.h"
24 #include "ortools/bop/bop_lns.h"
25 #include "ortools/bop/bop_ls.h"
26 #include "ortools/bop/bop_util.h"
29 #include "ortools/sat/boolean_problem.pb.h"
30 #include "ortools/sat/symmetry.h"
31 
32 namespace operations_research {
33 namespace bop {
34 
35 using ::operations_research::sat::LinearBooleanProblem;
36 using ::operations_research::sat::LinearObjective;
37 
38 namespace {
39 void 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 
98 BopOptimizerBase::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()
120  : glop::kInfinity;
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 
208 void 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 
307 void 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 
393 void 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 
418 void 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 
450 void 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 
460 void 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 
465 void 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
virtual Status Optimize(const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit)=0
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)
const sat::LinearBooleanProblem & original_problem() const
Definition: bop_base.h:201
const BopSolution & solution() const
Definition: bop_base.h:196
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