Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
shaving_solver.cc
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
15
16#include <cstdint>
17#include <functional>
18#include <memory>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/base/thread_annotations.h"
24#include "absl/flags/flag.h"
25#include "absl/log/check.h"
26#include "absl/log/log.h"
27#include "absl/log/vlog_is_on.h"
28#include "absl/random/distributions.h"
29#include "absl/strings/str_cat.h"
30#include "absl/synchronization/mutex.h"
38#include "ortools/sat/model.h"
42#include "ortools/sat/util.h"
45
46namespace operations_research {
47namespace sat {
48
50 const SatParameters& local_parameters, NeighborhoodGeneratorHelper* helper,
51 SharedClasses* shared)
52 : SubSolver(local_parameters.name(), FULL_PROBLEM),
53 local_params_(local_parameters),
54 helper_(helper),
55 shared_(shared),
56 local_proto_(shared->model_proto) {}
57
59 shared_->stat_tables->AddTimingStat(*this);
60}
61
63 if (shared_->SearchIsDone()) return false;
64
65 // We only support one task at the time.
66 absl::MutexLock mutex_lock(&mutex_);
67 return !task_in_flight_;
68}
69
70std::function<void()> ObjectiveShavingSolver::GenerateTask(int64_t task_id) {
71 {
72 absl::MutexLock mutex_lock(&mutex_);
73 stop_current_chunk_.store(false);
74 task_in_flight_ = true;
75 objective_lb_ = shared_->response->GetInnerObjectiveLowerBound();
76 objective_ub_ = shared_->response->GetInnerObjectiveUpperBound();
77 }
78 return [this, task_id]() {
79 if (ResetAndSolveModel(task_id)) {
80 const CpSolverResponse local_response =
81 local_sat_model_->GetOrCreate<SharedResponseManager>()->GetResponse();
82
83 if (local_response.status() == CpSolverStatus::OPTIMAL ||
84 local_response.status() == CpSolverStatus::FEASIBLE) {
85 std::vector<int64_t> solution_values(local_response.solution().begin(),
86 local_response.solution().end());
87 if (local_params_.cp_model_presolve()) {
88 const int num_original_vars = shared_->model_proto.variables_size();
89 PostsolveResponseWrapper(local_params_, num_original_vars,
90 mapping_proto_, postsolve_mapping_,
91 &solution_values);
92 }
93 shared_->response->NewSolution(solution_values, Info());
94 } else if (local_response.status() == CpSolverStatus::INFEASIBLE) {
95 absl::MutexLock mutex_lock(&mutex_);
96 shared_->response->UpdateInnerObjectiveBounds(
97 Info(), current_objective_target_ub_ + 1, objective_ub_);
98 }
99 }
100
101 absl::MutexLock mutex_lock(&mutex_);
102 task_in_flight_ = false;
103 if (local_sat_model_ != nullptr) {
104 const double dtime = local_sat_model_->GetOrCreate<TimeLimit>()
105 ->GetElapsedDeterministicTime();
107 shared_->time_limit->AdvanceDeterministicTime(dtime);
108 }
109 };
110}
111
113 absl::MutexLock mutex_lock(&mutex_);
114 if (!task_in_flight_) return;
115
116 // We are just waiting for the inner code to check the time limit or
117 // to return nicely.
118 if (stop_current_chunk_) return;
119
120 // TODO(user): Also stop if we have enough newly fixed / improved root level
121 // bounds so that we think it is worth represolving and restarting.
122 if (shared_->SearchIsDone()) {
123 stop_current_chunk_.store(true);
124 }
125
126 // The current objective lower bound has been improved, restarting.
127 if (shared_->response->GetInnerObjectiveLowerBound() > objective_lb_) {
128 stop_current_chunk_.store(true);
129 }
130
131 // A solution has been found that is better than the current target
132 // objective upper bound. Restarting to use a smaller delta.
133 if (shared_->response->GetInnerObjectiveUpperBound() <=
134 current_objective_target_ub_ &&
135 current_objective_target_ub_ != objective_lb_) {
136 stop_current_chunk_.store(true);
137 }
138
139 // If the range has been reduced enough to warrant a delta of 1, while the
140 // current search uses a delta > 1. Restarting to switch to the delta of 1.
141 if (current_objective_target_ub_ != objective_lb_ &&
142 shared_->response->GetInnerObjectiveUpperBound() -
143 shared_->response->GetInnerObjectiveLowerBound() <=
144 local_params_.shaving_search_threshold()) {
145 stop_current_chunk_.store(true);
146 }
147}
148
149std::string ObjectiveShavingSolver::Info() {
150 return absl::StrCat(name(), " (vars=", local_proto_.variables().size(),
151 " csts=", local_proto_.constraints().size(), ")");
152}
153
154bool ObjectiveShavingSolver::ResetAndSolveModel(int64_t task_id) {
155 local_sat_model_ = std::make_unique<Model>(name());
156 *local_sat_model_->GetOrCreate<SatParameters>() = local_params_;
157 local_sat_model_->GetOrCreate<SatParameters>()->set_random_seed(
158 CombineSeed(local_params_.random_seed(), task_id));
159
160 auto* time_limit = local_sat_model_->GetOrCreate<TimeLimit>();
162 time_limit->RegisterSecondaryExternalBooleanAsLimit(&stop_current_chunk_);
163
164 auto* random = local_sat_model_->GetOrCreate<ModelRandomGenerator>();
165
166 // We copy the model.
167 local_proto_ = shared_->model_proto;
168 *local_proto_.mutable_variables() =
169 helper_->FullNeighborhood().delta.variables();
170
171 // Store the current lb in local variable.
172 IntegerValue objective_lb;
173 IntegerValue chosen_objective_ub;
174 {
175 absl::MutexLock mutex_lock(&mutex_);
176 objective_lb = objective_lb_;
177 if (objective_ub_ - objective_lb <=
178 local_params_.shaving_search_threshold()) {
179 current_objective_target_ub_ = objective_lb;
180 } else {
181 const IntegerValue mid = (objective_ub_ - objective_lb) / 2;
182 current_objective_target_ub_ =
183 objective_lb + absl::LogUniform<int64_t>(*random, 0, mid.value());
184 }
185 chosen_objective_ub = current_objective_target_ub_;
186 VLOG(2) << name() << ": from [" << objective_lb.value() << ".."
187 << objective_ub_.value() << "] <= " << chosen_objective_ub.value();
188 }
189
190 // We replace the objective by a constraint, objective in [lb, target_ub].
191 // We modify local_proto_ to a pure feasibility problem.
192 // Not having the objective open up more presolve reduction.
193 Domain obj_domain = Domain(objective_lb.value(), chosen_objective_ub.value());
194 if (local_proto_.objective().domain_size() > 1) {
195 // Intersect with the first interval of the objective domain.
196 obj_domain =
197 obj_domain.IntersectionWith(Domain(local_proto_.objective().domain(0),
198 local_proto_.objective().domain(1)));
199 }
200 if (local_proto_.objective().vars().size() == 1 &&
201 local_proto_.objective().coeffs(0) == 1) {
202 auto* obj_var =
203 local_proto_.mutable_variables(local_proto_.objective().vars(0));
204 const Domain reduced_var_domain = obj_domain.IntersectionWith(
205 Domain(obj_var->domain(0), obj_var->domain(1)));
206 if (reduced_var_domain.IsEmpty()) {
207 return false;
208 }
209 FillDomainInProto(reduced_var_domain, obj_var);
210 } else {
211 auto* obj = local_proto_.add_constraints()->mutable_linear();
212 *obj->mutable_vars() = local_proto_.objective().vars();
213 *obj->mutable_coeffs() = local_proto_.objective().coeffs();
214 if (obj_domain.IsEmpty()) {
215 return false;
216 }
217 FillDomainInProto(obj_domain, obj);
218 }
219
220 // Clear the objective.
221 local_proto_.clear_objective();
222 local_proto_.set_name(
223 absl::StrCat(local_proto_.name(), "_obj_shaving_", objective_lb.value()));
224
225 // Dump?
226 if (absl::GetFlag(FLAGS_cp_model_dump_submodels)) {
227 const std::string name =
228 absl::StrCat(absl::GetFlag(FLAGS_cp_model_dump_prefix),
229 "objective_shaving_", objective_lb.value(), ".pb.txt");
230 LOG(INFO) << "Dumping objective shaving model to '" << name << "'.";
231 CHECK(WriteModelProtoToFile(local_proto_, name));
232 }
233
234 // Presolve if asked.
235 if (local_params_.cp_model_presolve()) {
236 mapping_proto_.Clear();
237 postsolve_mapping_.clear();
238 auto context = std::make_unique<PresolveContext>(
239 local_sat_model_.get(), &local_proto_, &mapping_proto_);
240 const CpSolverStatus presolve_status =
241 PresolveCpModel(context.get(), &postsolve_mapping_);
242 if (presolve_status == CpSolverStatus::INFEASIBLE) {
243 absl::MutexLock mutex_lock(&mutex_);
244 shared_->response->UpdateInnerObjectiveBounds(
245 Info(), chosen_objective_ub + 1, kMaxIntegerValue);
246 return false;
247 }
248 }
249
250 // Tricky: If we aborted during the presolve above, some constraints might
251 // be in a non-canonical form (like having duplicates, etc...) and it seem
252 // not all our propagator code deal with that properly. So it is important
253 // to abort right away here.
254 //
255 // We had a bug when the LoadCpModel() below was returning infeasible on
256 // such non fully-presolved model.
257 if (time_limit->LimitReached()) return false;
258
259 LoadCpModel(local_proto_, local_sat_model_.get());
260 return true;
261}
262
264 const SatParameters& local_parameters, NeighborhoodGeneratorHelper* helper,
265 SharedClasses* shared)
266 : SubSolver(local_parameters.name(), INCOMPLETE),
267 local_params_(local_parameters),
268 shared_(shared),
269 stop_current_chunk_(false),
270 model_proto_(shared->model_proto) {
271 if (shared_->bounds != nullptr) {
272 shared_bounds_id_ = shared_->bounds->RegisterNewId();
273 }
274
275 absl::MutexLock mutex_lock(&mutex_);
276 for (const IntegerVariableProto& var_proto : model_proto_.variables()) {
277 var_domains_.push_back(ReadDomainFromProto(var_proto));
278 }
279}
280
282 shared_->stat_tables->AddTimingStat(*this);
283
284 if (!VLOG_IS_ON(1)) return;
285 if (shared_ == nullptr || shared_->stats == nullptr) return;
286 std::vector<std::pair<std::string, int64_t>> stats;
287 absl::MutexLock mutex_lock(&mutex_);
288 stats.push_back({"variable_shaving/num_vars_tried", num_vars_tried_});
289 stats.push_back({"variable_shaving/num_vars_shaved", num_vars_shaved_});
290 stats.push_back(
291 {"variable_shaving/num_infeasible_found", num_infeasible_found_});
292 shared_->stats->AddStats(stats);
293}
294
296 return !shared_->SearchIsDone();
297}
298
300 const CpSolverResponse& local_response, const State& state) {
301 if (shared_->bounds == nullptr) return;
302 if (state.shave_using_objective) {
303 if (local_response.status() == CpSolverStatus::INFEASIBLE) return;
304 const int64_t obj_lb = local_response.inner_objective_lower_bound();
305
306 absl::MutexLock lock(&mutex_);
307 const Domain domain = var_domains_[state.var_index];
308 if (state.minimize) {
309 const int64_t lb = obj_lb;
310 if (lb > domain.Min()) {
311 ++num_vars_shaved_;
312 shared_->bounds->ReportPotentialNewBounds(name(), {state.var_index},
313 {lb}, {domain.Max()});
314 VLOG(1) << name() << ": var(" << state.var_index << ") " << domain
315 << " >= " << lb;
316 }
317 } else {
318 const int64_t ub = -obj_lb;
319 if (ub < domain.Max()) {
320 ++num_vars_shaved_;
321 shared_->bounds->ReportPotentialNewBounds(name(), {state.var_index},
322 {domain.Min()}, {ub});
323 VLOG(1) << name() << ": var(" << state.var_index << ") " << domain
324 << " <= " << ub;
325 }
326 }
327 return;
328 }
329
330 if (local_response.status() != CpSolverStatus::INFEASIBLE) return;
331 absl::MutexLock lock(&mutex_);
332 const Domain domain = var_domains_[state.var_index];
333 Domain new_domain = domain;
334 ++num_infeasible_found_;
335 new_domain = domain.IntersectionWith(state.reduced_domain.Complement());
336 VLOG(1) << name() << ": var(" << state.var_index << ") " << domain << " ==> "
337 << new_domain;
338
339 if (domain != new_domain) {
340 ++num_vars_shaved_;
341 if (!new_domain.IsEmpty()) {
342 shared_->bounds->ReportPotentialNewBounds(
343 name(), {state.var_index}, {new_domain.Min()}, {new_domain.Max()});
344 }
345 var_domains_[state.var_index] = new_domain;
346 if (var_domains_[state.var_index].IsEmpty()) {
347 shared_->response->NotifyThatImprovingProblemIsInfeasible(
348 "Unsat during variables shaving");
349 return;
350 }
351 }
352}
353
354std::function<void()> VariablesShavingSolver::GenerateTask(int64_t task_id) {
355 return [this, task_id]() mutable {
356 Model local_sat_model;
357 CpModelProto shaving_proto;
358 State state;
359 if (ResetAndSolveModel(task_id, &state, &local_sat_model, &shaving_proto)) {
360 const CpSolverResponse local_response =
361 local_sat_model.GetOrCreate<SharedResponseManager>()->GetResponse();
362 ProcessLocalResponse(local_response, state);
363 }
364
365 absl::MutexLock mutex_lock(&mutex_);
366 const double dtime =
367 local_sat_model.GetOrCreate<TimeLimit>()->GetElapsedDeterministicTime();
369 shared_->time_limit->AdvanceDeterministicTime(dtime);
370 };
371}
372
374 absl::MutexLock mutex_lock(&mutex_);
375 // We are just waiting for the inner code to check the time limit or
376 // to return nicely.
377 if (stop_current_chunk_) return;
378
379 if (shared_->SearchIsDone()) {
380 stop_current_chunk_.store(true);
381 }
382
383 if (shared_->bounds != nullptr) {
384 std::vector<int> model_variables;
385 std::vector<int64_t> new_lower_bounds;
386 std::vector<int64_t> new_upper_bounds;
387 shared_->bounds->GetChangedBounds(shared_bounds_id_, &model_variables,
388 &new_lower_bounds, &new_upper_bounds);
389
390 for (int i = 0; i < model_variables.size(); ++i) {
391 const int var = model_variables[i];
392 const int64_t new_lb = new_lower_bounds[i];
393 const int64_t new_ub = new_upper_bounds[i];
394 const Domain& old_domain = var_domains_[var];
395 const Domain new_domain =
396 old_domain.IntersectionWith(Domain(new_lb, new_ub));
397 if (new_domain.IsEmpty()) {
398 shared_->response->NotifyThatImprovingProblemIsInfeasible(
399 "Unsat during variables shaving");
400 continue;
401 }
402 var_domains_[var] = new_domain;
403 }
404 }
405}
406
407std::string VariablesShavingSolver::Info() {
408 return absl::StrCat(name(), " (vars=", model_proto_.variables().size(),
409 " csts=", model_proto_.constraints().size(), ")");
410}
411
412int64_t VariablesShavingSolver::DomainSize(int var) const
413 ABSL_SHARED_LOCKS_REQUIRED(mutex_) {
414 return var_domains_[var].Size();
415}
416
417bool VariablesShavingSolver::VarIsFixed(int int_var) const
418 ABSL_SHARED_LOCKS_REQUIRED(mutex_) {
419 return var_domains_[int_var].IsFixed();
420}
421
422bool VariablesShavingSolver::ConstraintIsInactive(int c) const
423 ABSL_SHARED_LOCKS_REQUIRED(mutex_) {
424 for (const int ref : model_proto_.constraints(c).enforcement_literal()) {
425 const int var = PositiveRef(ref);
426 if (VarIsFixed(var) && var_domains_[var].Min() == (var == ref ? 0 : 1)) {
427 return true;
428 }
429 }
430 return false;
431}
432
433bool VariablesShavingSolver::FindNextVar(State* state)
434 ABSL_SHARED_LOCKS_REQUIRED(mutex_) {
435 const int num_vars = var_domains_.size();
436 ++current_index_;
437
438 // We start by shaving the objective in order to increase the lower bound.
439 if (model_proto_.has_objective()) {
440 const int num_obj_vars = model_proto_.objective().vars().size();
441 if (num_obj_vars > 1) {
442 while (current_index_ < num_obj_vars) {
443 const int var = model_proto_.objective().vars(current_index_);
444 if (VarIsFixed(var)) {
445 ++current_index_;
446 continue;
447 }
448 state->var_index = var;
449 state->minimize = model_proto_.objective().coeffs(current_index_) > 0;
450 state->shave_using_objective = true;
451 return true;
452 }
453 }
454 }
455
456 // Otherwise loop over all variables.
457 // TODO(user): maybe we should just order all possible State, putting the
458 // objective first, and just loop.
459 for (int i = 0; i < num_vars; ++i) {
460 const int var = (current_index_ / 2 + i) % num_vars;
461 if (VarIsFixed(var)) {
462 ++current_index_;
463 continue;
464 }
465
466 // Let's not shave the single var objective. There are enough workers
467 // looking at it.
468 if (model_proto_.has_objective() &&
469 model_proto_.objective().vars_size() == 1 &&
470 var == model_proto_.objective().vars(0)) {
471 continue;
472 }
473
474 state->var_index = var;
475 state->minimize = current_index_ % 2 == 0;
476 state->shave_using_objective = current_index_ / num_vars < 2;
477 return true;
478 }
479 return false;
480}
481
482void VariablesShavingSolver::CopyModelConnectedToVar(
483 State* state, Model* local_model, CpModelProto* shaving_proto,
484 bool* has_no_overlap_2d) ABSL_SHARED_LOCKS_REQUIRED(mutex_) {
485 auto var_to_node = [](int var) { return var; };
486 auto ct_to_node = [num_vars = model_proto_.variables_size()](int c) {
487 return c + num_vars;
488 };
489
490 // Heuristic: we will ignore some complex constraint and "RELAX" them.
491 const int root_index = var_to_node(state->var_index);
492 std::vector<int> ignored_constraints;
493
494 // Build the connected component graph.
495 //
496 // TODO(user): Add some kind of difficulty, and do a BFS instead so that
497 // we don't pull in the full model when everything is connected. We can
498 // reuse the helper_ graph for this.
499 DenseConnectedComponentsFinder cc_finder;
500 cc_finder.SetNumberOfNodes(model_proto_.constraints_size() +
501 model_proto_.variables_size());
502 for (int c = 0; c < model_proto_.constraints_size(); ++c) {
503 if (ConstraintIsInactive(c)) continue;
504
505 const ConstraintProto& ct = model_proto_.constraints(c);
506 if (ct.constraint_case() == ConstraintProto::kNoOverlap2D) {
507 // Make sure x and y part are connected.
508 *has_no_overlap_2d = true;
509 const int num_intervals = ct.no_overlap_2d().x_intervals().size();
510 for (int i = 0; i < num_intervals; ++i) {
511 const int x_interval = ct.no_overlap_2d().x_intervals(i);
512 const int y_interval = ct.no_overlap_2d().y_intervals(i);
513 cc_finder.AddEdge(ct_to_node(x_interval), ct_to_node(y_interval));
514 }
515 ignored_constraints.push_back(c);
516 continue;
517 }
518
519 const int ct_node = ct_to_node(c);
520 for (const int var : UsedVariables(ct)) {
521 if (VarIsFixed(var)) continue;
522 cc_finder.AddEdge(ct_node, var_to_node(var));
523 }
524 for (const int interval : UsedIntervals(ct)) {
525 cc_finder.AddEdge(ct_node, ct_to_node(interval));
526 }
527 }
528
529 DCHECK(shaving_proto->variables().empty());
530 DCHECK(shaving_proto->constraints().empty());
531
532 const auto active_constraints = [&cc_finder, root_index, &ct_to_node](int c) {
533 return cc_finder.Connected(root_index, ct_to_node(c));
534 };
535
536 PresolveContext context(local_model, shaving_proto, nullptr);
537 std::vector<int> interval_mapping;
539 model_proto_, var_domains_, active_constraints, &context,
540 &interval_mapping);
541
542 // Now copy the ignored constraints "partially".
543 for (const int c : ignored_constraints) {
544 CHECK(!active_constraints(c));
545 const ConstraintProto& ct = model_proto_.constraints(c);
546
547 // We will only include non-ignored intervals there !
548 if (ct.constraint_case() == ConstraintProto::kNoOverlap2D) {
549 NoOverlap2DConstraintProto* new_no_overlap_2d =
550 shaving_proto->add_constraints()->mutable_no_overlap_2d();
551 const int num_intervals = ct.no_overlap_2d().x_intervals().size();
552 for (int i = 0; i < num_intervals; ++i) {
553 const int x_interval = ct.no_overlap_2d().x_intervals(i);
554 const int y_interval = ct.no_overlap_2d().y_intervals(i);
555 if (!active_constraints(x_interval)) continue;
556 if (!active_constraints(y_interval)) continue;
557
558 new_no_overlap_2d->add_x_intervals(interval_mapping[x_interval]);
559 new_no_overlap_2d->add_y_intervals(interval_mapping[y_interval]);
560 }
561 }
562 }
563
564 if (VLOG_IS_ON(2)) {
565 int num_active_variables = 0;
566 for (int i = 0; i < model_proto_.variables().size(); ++i) {
567 if (cc_finder.Connected(root_index, var_to_node(i))) {
568 ++num_active_variables;
569 }
570 }
571 int num_active_constraints = 0;
572 for (int c = 0; c < model_proto_.constraints().size(); ++c) {
573 if (cc_finder.Connected(root_index, ct_to_node(c))) {
574 ++num_active_constraints;
575 }
576 }
577
578 LOG(INFO) << "#shaving_constraints:" << shaving_proto->constraints_size()
579 << " #active_constraints:" << num_active_constraints << "/"
580 << model_proto_.constraints_size()
581 << " #active_variables:" << num_active_variables << "/"
582 << model_proto_.variables_size();
583 }
584
585 shaving_proto->clear_objective();
586
587 if (state->shave_using_objective) {
588 if (state->minimize) {
589 shaving_proto->mutable_objective()->add_vars(state->var_index);
590 shaving_proto->mutable_objective()->add_coeffs(1);
591 } else {
592 shaving_proto->mutable_objective()->add_vars(state->var_index);
593 shaving_proto->mutable_objective()->add_coeffs(-1);
594 }
595 } else {
596 const Domain domain =
597 ReadDomainFromProto(shaving_proto->variables(state->var_index));
598
599 int64_t delta = 0;
600 if (domain.Size() > local_params_.shaving_search_threshold()) {
601 const int64_t mid_range = (domain.Max() - domain.Min()) / 2;
602 auto* random = local_model->GetOrCreate<ModelRandomGenerator>();
603 delta = absl::LogUniform<int64_t>(*random, 0, mid_range);
604 }
605
606 if (state->minimize) {
607 state->reduced_domain =
608 domain.IntersectionWith({domain.Min(), domain.Min() + delta});
609 } else {
610 state->reduced_domain =
611 domain.IntersectionWith({domain.Max() - delta, domain.Max()});
612 }
613 FillDomainInProto(state->reduced_domain,
614 shaving_proto->mutable_variables(state->var_index));
615 }
616}
617
618bool VariablesShavingSolver::ResetAndSolveModel(int64_t task_id, State* state,
619 Model* local_model,
620 CpModelProto* shaving_proto) {
621 SatParameters* params = local_model->GetOrCreate<SatParameters>();
622 *params = local_params_;
623 params->set_random_seed(CombineSeed(local_params_.random_seed(), task_id));
624
625 bool has_no_overlap_2d = false;
626 {
627 absl::MutexLock lock(&mutex_);
628 if (!FindNextVar(state)) return false;
629 CopyModelConnectedToVar(state, local_model, shaving_proto,
630 &has_no_overlap_2d);
631 ++num_vars_tried_;
632 }
633
634 // Use the current best solution as hint.
635 {
636 auto sols = shared_->response->SolutionsRepository().GetBestNSolutions(1);
637 if (!sols.empty()) {
638 const std::vector<int64_t>& solution = sols[0]->variable_values;
639 auto* hint = shaving_proto->mutable_solution_hint();
640 hint->clear_vars();
641 hint->clear_values();
642 for (int var = 0; var < solution.size(); ++var) {
643 hint->add_vars(var);
644 hint->add_values(solution[var]);
645 }
646 }
647 }
648
649 auto* time_limit = local_model->GetOrCreate<TimeLimit>();
650 shared_->time_limit->UpdateLocalLimit(time_limit);
651 time_limit->RegisterSecondaryExternalBooleanAsLimit(&stop_current_chunk_);
652 time_limit->ChangeDeterministicLimit(
653 time_limit->GetElapsedDeterministicTime() +
654 local_params_.shaving_search_deterministic_time());
655
656 shaving_proto->set_name(absl::StrCat("shaving_var_", state->var_index,
657 (state->minimize ? "_min" : "_max")));
658
659 // Presolve if asked.
660 if (local_params_.cp_model_presolve()) {
661 std::vector<int> postsolve_mapping;
662 CpModelProto mapping_proto;
663 auto context = std::make_unique<PresolveContext>(local_model, shaving_proto,
664 &mapping_proto);
665 const CpSolverStatus presolve_status =
666 PresolveCpModel(context.get(), &postsolve_mapping);
667 if (presolve_status == CpSolverStatus::INFEASIBLE) {
668 CpSolverResponse tmp_response;
669 tmp_response.set_status(CpSolverStatus::INFEASIBLE);
670 ProcessLocalResponse(tmp_response, *state);
671 return false;
672 }
673 }
674
675 // Hack: remove "non useful interval" from scheduling constraints.
676 // For now we only do that for no-overlap 2d, but we should generalize.
677 if (has_no_overlap_2d) {
678 std::vector<int> postsolve_mapping;
679 CpModelProto mapping_proto;
680 auto context = std::make_unique<PresolveContext>(local_model, shaving_proto,
681 &mapping_proto);
682 context->InitializeNewDomains();
683 context->UpdateNewConstraintsVariableUsage();
684 const int num_constraints = shaving_proto->constraints().size();
685 std::vector<bool> useful_interval(num_constraints, false);
686 std::vector<int> no_overalp_2d;
687 for (int c = 0; c < num_constraints; ++c) {
688 const ConstraintProto& ct = shaving_proto->constraints(c);
689 if (ct.constraint_case() == ConstraintProto::kInterval) {
690 for (const int var : UsedVariables(ct)) {
691 if (context->VarToConstraints(var).size() > 1) {
692 useful_interval[c] = true;
693 break;
694 }
695 }
696 } else if (ct.constraint_case() == ConstraintProto::kNoOverlap2D) {
697 no_overalp_2d.push_back(c);
698 }
699 }
700 for (const int c : no_overalp_2d) {
701 NoOverlap2DConstraintProto* data =
702 shaving_proto->mutable_constraints(c)->mutable_no_overlap_2d();
703 int new_size = 0;
704 const int num_intervals = data->x_intervals().size();
705 for (int i = 0; i < num_intervals; ++i) {
706 const int x = data->x_intervals(i);
707 const int y = data->y_intervals(i);
708 if (!useful_interval[x] && !useful_interval[y]) continue;
709 data->set_x_intervals(new_size, x);
710 data->set_y_intervals(new_size, y);
711 ++new_size;
712 }
713 data->mutable_x_intervals()->Truncate(new_size);
714 data->mutable_y_intervals()->Truncate(new_size);
715 }
716 }
717
718 if (absl::GetFlag(FLAGS_cp_model_dump_submodels)) {
719 const std::string shaving_name = absl::StrCat(
720 absl::GetFlag(FLAGS_cp_model_dump_prefix), "shaving_var_",
721 state->var_index, (state->minimize ? "_min" : "_max"), ".pb.txt");
722 LOG(INFO) << "Dumping shaving model to '" << shaving_name << "'.";
723 CHECK(WriteModelProtoToFile(*shaving_proto, shaving_name));
724 }
725
726 auto* local_response_manager =
727 local_model->GetOrCreate<SharedResponseManager>();
728 local_response_manager->InitializeObjective(*shaving_proto);
729 local_response_manager->SetSynchronizationMode(true);
730
731 // Tricky: If we aborted during the presolve above, some constraints might
732 // be in a non-canonical form (like having duplicates, etc...) and it seem
733 // not all our propagator code deal with that properly. So it is important
734 // to abort right away here.
735 //
736 // We had a bug when the LoadCpModel() below was returning infeasible on
737 // such non fully-presolved model.
738 if (time_limit->LimitReached()) return false;
739
740 LoadCpModel(*shaving_proto, local_model);
741 QuickSolveWithHint(*shaving_proto, local_model);
742 SolveLoadedCpModel(*shaving_proto, local_model);
743 return true;
744}
745
746} // namespace sat
747} // namespace operations_research
bool Connected(int node1, int node2)
bool AddEdge(int node1, int node2)
Domain IntersectionWith(const Domain &domain) const
void UpdateLocalLimit(TimeLimit *local_limit)
Definition time_limit.h:355
const ::operations_research::sat::IntegerVariableProto & variables(int index) const
const ::operations_research::sat::ConstraintProto & constraints(int index) const
::operations_research::sat::IntegerVariableProto *PROTOBUF_NONNULL mutable_variables(int index)
::operations_research::sat::CpSolverStatus status() const
Neighborhood FullNeighborhood() const
Returns a neighborhood that correspond to the full problem.
ObjectiveShavingSolver(const SatParameters &local_parameters, NeighborhoodGeneratorHelper *helper, SharedClasses *shared)
std::function< void()> GenerateTask(int64_t task_id) override
SubSolver(absl::string_view name, SubsolverType type)
Definition subsolver.h:48
void AddTaskDeterministicDuration(double deterministic_duration)
Definition subsolver.h:114
std::string name() const
Returns the name of this SubSolver. Used in logs.
Definition subsolver.h:95
std::function< void()> GenerateTask(int64_t task_id) override
VariablesShavingSolver(const SatParameters &local_parameters, NeighborhoodGeneratorHelper *helper, SharedClasses *shared)
void ProcessLocalResponse(const CpSolverResponse &local_response, const State &state)
time_limit
Definition solve.cc:22
void SolveLoadedCpModel(const CpModelProto &model_proto, Model *model)
constexpr IntegerValue kMaxIntegerValue(std::numeric_limits< IntegerValue::ValueType >::max() - 1)
int CombineSeed(int base_seed, int64_t delta)
We assume delta >= 0 and we only use the low bit of delta.
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
CpSolverStatus PresolveCpModel(PresolveContext *context, std::vector< int > *postsolve_mapping)
Convenient wrapper to call the full presolve.
std::vector< int > UsedVariables(const ConstraintProto &ct)
std::vector< int > UsedIntervals(const ConstraintProto &ct)
Returns the sorted list of interval used by a constraint.
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Serializes a Domain into the domain field of a proto.
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Reads a Domain from the domain field of a proto.
void QuickSolveWithHint(const CpModelProto &model_proto, Model *model)
bool ImportModelAndDomainsWithBasicPresolveIntoContext(const CpModelProto &in_model, absl::Span< const Domain > domains, std::function< bool(int)> active_constraints, PresolveContext *context, std::vector< int > *interval_mapping)
void PostsolveResponseWrapper(const SatParameters &params, int num_variable_in_original_model, const CpModelProto &mapping_proto, absl::Span< const int > postsolve_mapping, std::vector< int64_t > *solution)
void LoadCpModel(const CpModelProto &model_proto, Model *model)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
int64_t Max() const
Returns the max of the domain.
Definition model.cc:346
int64_t Min() const
Returns the min of the domain.
Definition model.cc:340
const CpModelProto & model_proto
These are never nullptr.