18 #include "absl/container/flat_hash_map.h"
19 #include "absl/strings/str_format.h"
43 const absl::flat_hash_map<
int, std::pair<int64, int64>>&
44 var_to_coeff_offset_pair,
45 const std::vector<Strategy>& strategies,
Model*
model) {
51 return [integer_encoder, integer_trail, strategies, var_to_coeff_offset_pair,
53 const SatParameters*
const parameters =
model->GetOrCreate<SatParameters>();
55 for (
const Strategy& strategy : strategies) {
58 IntegerValue candidate_lb;
59 IntegerValue candidate_ub;
65 std::vector<VarValue> active_vars;
67 for (
const IntegerVariable
var : strategy.variables) {
68 if (integer_trail->IsCurrentlyIgnored(
var))
continue;
69 const IntegerValue lb = integer_trail->LowerBound(
var);
70 const IntegerValue ub = integer_trail->UpperBound(
var);
71 if (lb == ub)
continue;
72 IntegerValue
value(0);
73 IntegerValue coeff(1);
74 IntegerValue offset(0);
76 const auto coeff_offset =
78 coeff = coeff_offset.first;
79 offset = coeff_offset.second;
85 switch (strategy.var_strategy) {
86 case DecisionStrategyProto::CHOOSE_FIRST:
88 case DecisionStrategyProto::CHOOSE_LOWEST_MIN:
89 value = coeff * lb + offset;
91 case DecisionStrategyProto::CHOOSE_HIGHEST_MAX:
92 value = -(coeff * ub + offset);
94 case DecisionStrategyProto::CHOOSE_MIN_DOMAIN_SIZE:
96 value = coeff * (ub - lb + 1);
98 case DecisionStrategyProto::CHOOSE_MAX_DOMAIN_SIZE:
100 value = -coeff * (ub - lb + 1);
103 LOG(
FATAL) <<
"Unknown VariableSelectionStrategy "
104 << strategy.var_strategy;
106 if (
value < candidate_value) {
110 candidate_value =
value;
112 if (strategy.var_strategy == DecisionStrategyProto::CHOOSE_FIRST &&
116 if (active_vars.empty() ||
117 value <= candidate_value +
118 parameters->search_randomization_tolerance()) {
119 active_vars.push_back({
var,
value});
125 CHECK(!active_vars.empty());
126 const IntegerValue threshold(
127 candidate_value +
parameters->search_randomization_tolerance());
128 auto is_above_tolerance = [threshold](
const VarValue& entry) {
129 return entry.value > threshold;
132 active_vars.erase(std::remove_if(active_vars.begin(), active_vars.end(),
136 std::uniform_int_distribution<int>(0, active_vars.size() - 1)(
138 candidate = active_vars[winner].var;
139 candidate_lb = integer_trail->LowerBound(candidate);
140 candidate_ub = integer_trail->UpperBound(candidate);
144 switch (strategy.domain_strategy) {
145 case DecisionStrategyProto::SELECT_MIN_VALUE:
148 case DecisionStrategyProto::SELECT_MAX_VALUE:
151 case DecisionStrategyProto::SELECT_LOWER_HALF:
153 candidate, candidate_lb + (candidate_ub - candidate_lb) / 2);
155 case DecisionStrategyProto::SELECT_UPPER_HALF:
157 candidate, candidate_ub - (candidate_ub - candidate_lb) / 2);
159 case DecisionStrategyProto::SELECT_MEDIAN_VALUE:
164 LOG(
FATAL) <<
"Unknown DomainReductionStrategy "
165 << strategy.domain_strategy;
174 const CpModelProto& cp_model_proto,
175 const std::vector<IntegerVariable>& variable_mapping,
176 IntegerVariable objective_var,
Model*
model) {
179 const bool instantiate_all_variables =
180 model->GetOrCreate<SatParameters>()->instantiate_all_variables();
182 if (instantiate_all_variables) {
183 std::vector<IntegerVariable> decisions;
184 for (
const IntegerVariable
var : variable_mapping) {
189 decisions.push_back(objective_var);
191 decisions.push_back(
var);
194 default_search_strategy =
198 std::vector<Strategy> strategies;
199 absl::flat_hash_map<int, std::pair<int64, int64>> var_to_coeff_offset_pair;
200 for (
const DecisionStrategyProto&
proto : cp_model_proto.search_strategy()) {
202 Strategy& strategy = strategies.back();
203 for (
const int ref :
proto.variables()) {
210 for (
const auto& transform :
proto.transformations()) {
211 const int ref = transform.var();
212 const IntegerVariable
var =
216 var_to_coeff_offset_pair[
var.value()] = {transform.positive_coeff(),
221 if (instantiate_all_variables) {
223 var_to_coeff_offset_pair, strategies,
model),
224 default_search_strategy});
232 const CpModelProto& cp_model_proto,
233 const std::vector<IntegerVariable>& variable_mapping,
236 std::vector<int> ref_to_display;
237 for (
int i = 0; i < cp_model_proto.variables_size(); ++i) {
239 if (cp_model_proto.variables(i).name().empty())
continue;
240 ref_to_display.push_back(i);
242 std::sort(ref_to_display.begin(), ref_to_display.end(), [&](
int i,
int j) {
243 return cp_model_proto.variables(i).name() <
244 cp_model_proto.variables(j).name();
247 std::vector<std::pair<int64, int64>> old_domains(variable_mapping.size());
248 return [instrumented_strategy,
model, variable_mapping, cp_model_proto,
249 old_domains, ref_to_display]()
mutable {
251 if (!decision.
HasValue())
return decision;
255 LOG(
INFO) <<
"Boolean decision " << l;
258 LOG(
INFO) <<
" - associated with " << i_lit;
263 const int level =
model->Get<
Trail>()->CurrentDecisionLevel();
264 std::string to_display =
265 absl::StrCat(
"Diff since last call, level=", level,
"\n");
267 for (
const int ref : ref_to_display) {
268 const IntegerVariable
var = variable_mapping[ref];
269 const std::pair<int64, int64> new_domain(
272 if (new_domain != old_domains[ref]) {
273 absl::StrAppend(&to_display, cp_model_proto.variables(ref).name(),
" [",
274 old_domains[ref].first,
",", old_domains[ref].second,
275 "] -> [", new_domain.first,
",", new_domain.second,
277 old_domains[ref] = new_domain;
293 const SatParameters& base_params,
const CpModelProto& cp_model,
294 const int num_workers) {
297 std::map<std::string, SatParameters> strategies;
301 SatParameters new_params = base_params;
302 new_params.set_linearization_level(0);
303 strategies[
"no_lp"] = new_params;
304 new_params.set_linearization_level(1);
305 strategies[
"default_lp"] = new_params;
306 new_params.set_linearization_level(2);
307 new_params.set_add_lp_constraints_lazily(
false);
308 strategies[
"max_lp"] = new_params;
318 SatParameters new_params = base_params;
319 new_params.set_search_branching(SatParameters::AUTOMATIC_SEARCH);
320 new_params.set_optimize_with_core(
true);
321 new_params.set_linearization_level(0);
322 strategies[
"core"] = new_params;
327 SatParameters new_params = base_params;
328 new_params.set_search_branching(SatParameters::AUTOMATIC_SEARCH);
329 new_params.set_optimize_with_core(
true);
330 new_params.set_linearization_level(1);
331 strategies[
"core_default_lp"] = new_params;
335 SatParameters new_params = base_params;
336 new_params.set_search_branching(SatParameters::AUTOMATIC_SEARCH);
337 new_params.set_optimize_with_core(
true);
338 new_params.set_linearization_level(2);
339 strategies[
"core_max_lp"] = new_params;
343 SatParameters new_params = base_params;
344 new_params.set_search_branching(SatParameters::AUTOMATIC_SEARCH);
345 new_params.set_use_probing_search(
true);
346 strategies[
"probing"] = new_params;
351 SatParameters new_params = base_params;
352 new_params.set_search_branching(SatParameters::AUTOMATIC_SEARCH);
353 strategies[
"auto"] = new_params;
355 new_params.set_search_branching(SatParameters::FIXED_SEARCH);
356 strategies[
"fixed"] = new_params;
358 new_params.set_search_branching(
359 SatParameters::PORTFOLIO_WITH_QUICK_RESTART_SEARCH);
360 strategies[
"quick_restart"] = new_params;
362 new_params.set_search_branching(
363 SatParameters::PORTFOLIO_WITH_QUICK_RESTART_SEARCH);
364 new_params.set_linearization_level(0);
365 strategies[
"quick_restart_no_lp"] = new_params;
368 new_params.set_linearization_level(2);
369 new_params.set_search_branching(SatParameters::LP_SEARCH);
370 strategies[
"reduced_costs"] = new_params;
373 new_params.set_linearization_level(2);
374 new_params.set_search_branching(SatParameters::PSEUDO_COST_SEARCH);
375 new_params.set_exploit_best_solution(
true);
376 strategies[
"pseudo_costs"] = new_params;
381 SatParameters new_params = base_params;
382 new_params.set_boolean_encoding_level(0);
383 strategies[
"less_encoding"] = new_params;
390 std::vector<std::string> names;
391 if (base_params.reduce_memory_usage_in_interleave_mode() &&
392 base_params.interleave_search()) {
394 if (cp_model.has_objective()) {
395 names.push_back(
"default_lp");
396 names.push_back(!cp_model.search_strategy().empty() ?
"fixed"
398 names.push_back(cp_model.objective().vars_size() > 1 ?
"core" :
"no_lp");
399 names.push_back(
"max_lp");
401 names.push_back(
"default_lp");
402 names.push_back(cp_model.search_strategy_size() > 0 ?
"fixed" :
"no_lp");
403 names.push_back(
"less_encoding");
404 names.push_back(
"max_lp");
405 names.push_back(
"quick_restart");
407 }
else if (cp_model.has_objective()) {
408 names.push_back(
"default_lp");
409 names.push_back(!cp_model.search_strategy().empty() ?
"fixed"
411 names.push_back(
"pseudo_costs");
412 names.push_back(
"no_lp");
413 names.push_back(
"max_lp");
414 if (cp_model.objective().vars_size() > 1) names.push_back(
"core");
418 if (num_workers > 8 || base_params.interleave_search()) {
419 names.push_back(
"quick_restart");
421 if (num_workers > 10) {
422 names.push_back(
"quick_restart_no_lp");
425 names.push_back(
"default_lp");
426 if (cp_model.search_strategy_size() > 0) names.push_back(
"fixed");
427 names.push_back(
"less_encoding");
428 names.push_back(
"no_lp");
429 names.push_back(
"max_lp");
430 names.push_back(
"quick_restart");
431 if (num_workers > 10) {
432 names.push_back(
"quick_restart_no_lp");
435 if (num_workers > 12) {
436 names.push_back(
"probing");
441 std::vector<SatParameters> result;
442 for (
const std::string&
name : names) {
443 SatParameters new_params = strategies.at(
name);
444 new_params.set_name(
name);
445 new_params.set_random_seed(result.size() + 1);
446 result.push_back(new_params);
451 if (!cp_model.has_objective()) {
452 int target = num_workers;
456 if (!base_params.interleave_search() &&
457 (base_params.use_rins_lns() || base_params.use_relaxation_lns() ||
458 base_params.use_feasibility_pump())) {
459 target =
std::max(1, num_workers - 1);
463 while (result.size() < target) {
465 SatParameters new_params = base_params;
466 new_params.set_search_branching(SatParameters::FIXED_SEARCH);
467 new_params.set_randomize_search(
true);
468 new_params.set_search_randomization_tolerance(
index);
469 new_params.set_random_seed(result.size() + 1);
470 new_params.set_name(absl::StrCat(
"random_",
index));
471 result.push_back(new_params);
480 if (!base_params.interleave_search() && result.size() > num_workers) {
481 result.resize(num_workers);
#define DCHECK_GT(val1, val2)
const InlinedIntegerLiteralVector & GetAllIntegerLiterals(Literal lit) const
IntegerValue UpperBound(IntegerVariable i) const
IntegerValue LowerBound(IntegerVariable i) const
Class that owns everything related to a particular optimization model.
bool ContainsKey(const Collection &collection, const Key &key)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
std::function< BooleanOrIntegerLiteral()> FirstUnassignedVarAtItsMinHeuristic(const std::vector< IntegerVariable > &vars, Model *model)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
bool RefIsPositive(int ref)
const LiteralIndex kNoLiteralIndex(-1)
const IntegerVariable kNoIntegerVariable(-1)
const std::function< BooleanOrIntegerLiteral()> ConstructSearchStrategyInternal(const absl::flat_hash_map< int, std::pair< int64, int64 >> &var_to_coeff_offset_pair, const std::vector< Strategy > &strategies, Model *model)
std::vector< IntegerVariable > NegationOf(const std::vector< IntegerVariable > &vars)
std::function< BooleanOrIntegerLiteral()> SequentialSearch(std::vector< std::function< BooleanOrIntegerLiteral()>> heuristics)
std::vector< SatParameters > GetDiverseSetOfParameters(const SatParameters &base_params, const CpModelProto &cp_model, const int num_workers)
std::function< BooleanOrIntegerLiteral()> ConstructSearchStrategy(const CpModelProto &cp_model_proto, const std::vector< IntegerVariable > &variable_mapping, IntegerVariable objective_var, Model *model)
std::function< BooleanOrIntegerLiteral()> InstrumentSearchStrategy(const CpModelProto &cp_model_proto, const std::vector< IntegerVariable > &variable_mapping, const std::function< BooleanOrIntegerLiteral()> &instrumented_strategy, Model *model)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
LiteralIndex boolean_literal_index
IntegerLiteral integer_literal
static IntegerLiteral LowerOrEqual(IntegerVariable i, IntegerValue bound)
static IntegerLiteral GreaterOrEqual(IntegerVariable i, IntegerValue bound)
DecisionStrategyProto::VariableSelectionStrategy var_strategy
std::vector< IntegerVariable > variables
DecisionStrategyProto::DomainReductionStrategy domain_strategy