19#include "absl/memory/memory.h"
20#include "absl/strings/str_format.h"
29#include "ortools/sat/boolean_problem.pb.h"
35using ::operations_research::sat::LinearBooleanProblem;
36using ::operations_research::sat::LinearObjective;
39void BuildObjectiveTerms(
const LinearBooleanProblem& problem,
41 CHECK(objective_terms !=
nullptr);
43 if (!objective_terms->empty())
return;
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) {
50 CHECK_NE(objective.coefficients(i), 0);
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));
64 const BopSolverOptimizerSet& optimizer_set,
const std::string&
name)
75 number_of_consecutive_failing_optimizers_(0) {
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);
87 if (!stats_string.empty()) {
88 LOG(
INFO) <<
"Stats. #new_solutions/#calls by optimizer:\n" +
100 if (state_update_stamp_ == problem_state.
update_stamp()) {
106 const bool first_time = (sat_propagator_.
NumVariables() == 0);
127 CHECK(learned_info !=
nullptr);
129 learned_info->
Clear();
132 SynchronizeIfNeeded(problem_state);
137 for (OptimizerIndex i(0); i < optimizers_.size(); ++i) {
138 selector_->SetOptimizerRunnability(
145 const double init_deterministic_time =
148 const OptimizerIndex selected_optimizer_id = selector_->SelectOptimizer();
150 LOG(
INFO) <<
"All the optimizers are done.";
154 optimizers_[selected_optimizer_id];
156 LOG(
INFO) <<
" " << lower_bound_ <<
" .. " << upper_bound_ <<
" "
157 <<
name() <<
" - " << selected_optimizer->
name()
158 <<
". Time limit: " <<
time_limit->GetTimeLeft() <<
" -- "
167 selector_->TemporarilyMarkOptimizerAsUnselectable(selected_optimizer_id);
179 const double spent_deterministic_time =
180 time_limit->GetElapsedDeterministicTime() - init_deterministic_time;
181 selector_->UpdateScore(gain, spent_deterministic_time);
185 return optimization_status;
189 if (
parameters.has_max_number_of_consecutive_failing_optimizer_calls() &&
191 number_of_consecutive_failing_optimizers_ =
194 : number_of_consecutive_failing_optimizers_ + 1;
195 if (number_of_consecutive_failing_optimizers_ >
196 parameters.max_number_of_consecutive_failing_optimizer_calls()) {
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:
215 case BopOptimizerMethod::SAT_LINEAR_SEARCH:
219 case BopOptimizerMethod::LINEAR_RELAXATION:
220 optimizers_.push_back(
223 case BopOptimizerMethod::LOCAL_SEARCH: {
224 for (
int i = 1; i <=
parameters.max_num_decisions_in_ls(); ++i) {
226 absl::StrFormat(
"LS_%d", i), i, &sat_propagator_));
229 case BopOptimizerMethod::RANDOM_FIRST_SOLUTION:
230 optimizers_.push_back(
new BopRandomFirstSolutionGenerator(
231 "SATRandomFirstSolution",
parameters, &sat_propagator_,
234 case BopOptimizerMethod::RANDOM_VARIABLE_LNS:
235 BuildObjectiveTerms(problem, &objective_terms_);
236 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
239 new ObjectiveBasedNeighborhood(&objective_terms_, random_.get()),
242 case BopOptimizerMethod::RANDOM_VARIABLE_LNS_GUIDED_BY_LP:
243 BuildObjectiveTerms(problem, &objective_terms_);
244 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
245 "RandomVariableLnsWithLp",
247 new ObjectiveBasedNeighborhood(&objective_terms_, random_.get()),
250 case BopOptimizerMethod::RANDOM_CONSTRAINT_LNS:
251 BuildObjectiveTerms(problem, &objective_terms_);
252 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
253 "RandomConstraintLns",
255 new ConstraintBasedNeighborhood(&objective_terms_, random_.get()),
258 case BopOptimizerMethod::RANDOM_CONSTRAINT_LNS_GUIDED_BY_LP:
259 BuildObjectiveTerms(problem, &objective_terms_);
260 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
261 "RandomConstraintLnsWithLp",
263 new ConstraintBasedNeighborhood(&objective_terms_, random_.get()),
266 case BopOptimizerMethod::RELATION_GRAPH_LNS:
267 BuildObjectiveTerms(problem, &objective_terms_);
268 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
271 new RelationGraphBasedNeighborhood(problem, random_.get()),
274 case BopOptimizerMethod::RELATION_GRAPH_LNS_GUIDED_BY_LP:
275 BuildObjectiveTerms(problem, &objective_terms_);
276 optimizers_.push_back(
new BopAdaptiveLNSOptimizer(
277 "RelationGraphLnsWithLp",
279 new RelationGraphBasedNeighborhood(problem, random_.get()),
282 case BopOptimizerMethod::COMPLETE_LNS:
283 BuildObjectiveTerms(problem, &objective_terms_);
284 optimizers_.push_back(
285 new BopCompleteLNSOptimizer(
"LNS", objective_terms_));
287 case BopOptimizerMethod::USER_GUIDED_FIRST_SOLUTION:
288 optimizers_.push_back(
new GuidedSatFirstSolutionGenerator(
289 "SATUserGuidedFirstSolution",
292 case BopOptimizerMethod::LP_FIRST_SOLUTION:
293 optimizers_.push_back(
new GuidedSatFirstSolutionGenerator(
294 "SATLPFirstSolution",
297 case BopOptimizerMethod::OBJECTIVE_FIRST_SOLUTION:
298 optimizers_.push_back(
new GuidedSatFirstSolutionGenerator(
299 "SATObjectiveFirstSolution",
303 LOG(
FATAL) <<
"Unknown optimizer type.";
307void PortfolioOptimizer::CreateOptimizers(
308 const LinearBooleanProblem& problem,
const BopParameters&
parameters,
309 const BopSolverOptimizerSet& optimizer_set) {
310 random_ = absl::make_unique<MTRandom>(
parameters.random_seed());
313 VLOG(1) <<
"Finding symmetries of the problem.";
314 std::vector<std::unique_ptr<SparsePermutation>> 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]));
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);
333 selector_ = absl::make_unique<OptimizerSelector>(optimizers_);
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()));
353 }
while (selected_index_ < run_infos_.size() &&
354 !run_infos_[selected_index_].RunnableAndSelectable());
356 if (selected_index_ >= run_infos_.size()) {
358 selected_index_ = -1;
359 for (
int i = 0; i < run_infos_.size(); ++i) {
360 if (run_infos_[i].RunnableAndSelectable()) {
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;
381 if (too_much_time_spent) {
389 ++run_infos_[selected_index_].num_calls;
390 return run_infos_[selected_index_].optimizer_index;
394 const bool new_solution_found = gain != 0;
395 if (new_solution_found) NewSolutionFound(gain);
396 UpdateDeterministicTime(time_spent);
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;
402 RunInfo& info = run_infos_[selected_index_];
403 const double old_score = info.score;
405 std::max(kMinScore, old_score * (1 - kErosion) + kErosion * new_score);
407 if (new_solution_found) {
409 selected_index_ = run_infos_.size();
414 OptimizerIndex optimizer_index) {
415 run_infos_[info_positions_[optimizer_index]].selectable =
false;
420 run_infos_[info_positions_[optimizer_index]].runnable = runnable;
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 "
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);
435 OptimizerIndex optimizer_index)
const {
436 const RunInfo& info = run_infos_[info_positions_[optimizer_index]];
437 return info.num_calls;
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;
450void OptimizerSelector::NewSolutionFound(int64_t gain) {
451 run_infos_[selected_index_].num_successes++;
452 run_infos_[selected_index_].total_gain += gain;
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;
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;
465void OptimizerSelector::UpdateOrder() {
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;
475 for (
int i = 0; i < run_infos_.size(); ++i) {
476 info_positions_[run_infos_[i].optimizer_index] = i;
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define CHECK_NE(val1, val2)
#define VLOG(verboselevel)
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...
const std::string & name() const
virtual Status Optimize(const BopParameters ¶meters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit)=0
double GetScaledCost() const
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)
OptimizerIndex SelectOptimizer()
void TemporarilyMarkOptimizerAsUnselectable(OptimizerIndex optimizer_index)
void SetOptimizerRunnability(OptimizerIndex optimizer_index, bool runnable)
~PortfolioOptimizer() override
bool ShouldBeRun(const ProblemState &problem_state) const override
Status Optimize(const BopParameters ¶meters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
PortfolioOptimizer(const ProblemState &problem_state, const BopParameters ¶meters, const BopSolverOptimizerSet &optimizer_set, const std::string &name)
const BopSolution & solution() const
const sat::LinearBooleanProblem & original_problem() const
int64_t update_stamp() const
double GetScaledLowerBound() const
void AddPropagator(SatPropagator *propagator)
void TakePropagatorOwnership(std::unique_ptr< SatPropagator > propagator)
SharedTimeLimit * time_limit
void STLDeleteElements(T *container)
BopOptimizerBase::Status LoadStateProblemToSatSolver(const ProblemState &problem_state, sat::SatSolver *sat_solver)
const OptimizerIndex kInvalidOptimizerIndex(-1)
absl::StrongVector< SparseIndex, BopConstraintTerm > BopConstraintTerms
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...
BaseVariableAssignmentSelector *const selector_
#define VLOG_IS_ON(verboselevel)