OR-Tools  8.1
trace.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 
14 #include <algorithm>
15 #include <cmath>
16 #include <stack>
17 #include <string>
18 #include <utility>
19 
20 #include "absl/container/flat_hash_map.h"
21 #include "absl/strings/str_format.h"
22 #include "absl/strings/str_join.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/base/map_util.h"
29 
30 ABSL_FLAG(bool, cp_full_trace, false,
31  "Display all trace information, even if the modifiers has no effect");
32 
33 namespace operations_research {
34 namespace {
35 // ---------- Code Instrumentation ----------
36 class TraceIntVar : public IntVar {
37  public:
38  TraceIntVar(Solver* const solver, IntVar* const inner)
39  : IntVar(solver), inner_(inner) {
40  if (inner->HasName()) {
41  set_name(inner->name());
42  }
43  CHECK_NE(inner->VarType(), TRACE_VAR);
44  }
45 
46  ~TraceIntVar() override {}
47 
48  int64 Min() const override { return inner_->Min(); }
49 
50  void SetMin(int64 m) override {
51  if (m > inner_->Min()) {
52  solver()->GetPropagationMonitor()->SetMin(inner_, m);
53  inner_->SetMin(m);
54  }
55  }
56 
57  int64 Max() const override { return inner_->Max(); }
58 
59  void SetMax(int64 m) override {
60  if (m < inner_->Max()) {
61  solver()->GetPropagationMonitor()->SetMax(inner_, m);
62  inner_->SetMax(m);
63  }
64  }
65 
66  void Range(int64* l, int64* u) override { inner_->Range(l, u); }
67 
68  void SetRange(int64 l, int64 u) override {
69  if (l > inner_->Min() || u < inner_->Max()) {
70  if (l == u) {
71  solver()->GetPropagationMonitor()->SetValue(inner_, l);
72  inner_->SetValue(l);
73  } else {
74  solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
75  inner_->SetRange(l, u);
76  }
77  }
78  }
79 
80  bool Bound() const override { return inner_->Bound(); }
81 
82  bool IsVar() const override { return true; }
83 
84  IntVar* Var() override { return this; }
85 
86  int64 Value() const override { return inner_->Value(); }
87 
88  void RemoveValue(int64 v) override {
89  if (inner_->Contains(v)) {
90  solver()->GetPropagationMonitor()->RemoveValue(inner_, v);
91  inner_->RemoveValue(v);
92  }
93  }
94 
95  void SetValue(int64 v) override {
96  solver()->GetPropagationMonitor()->SetValue(inner_, v);
97  inner_->SetValue(v);
98  }
99 
100  void RemoveInterval(int64 l, int64 u) override {
101  solver()->GetPropagationMonitor()->RemoveInterval(inner_, l, u);
102  inner_->RemoveInterval(l, u);
103  }
104 
105  void RemoveValues(const std::vector<int64>& values) override {
106  solver()->GetPropagationMonitor()->RemoveValues(inner_, values);
107  inner_->RemoveValues(values);
108  }
109 
110  void SetValues(const std::vector<int64>& values) override {
111  solver()->GetPropagationMonitor()->SetValues(inner_, values);
112  inner_->SetValues(values);
113  }
114 
115  void WhenRange(Demon* d) override { inner_->WhenRange(d); }
116 
117  void WhenBound(Demon* d) override { inner_->WhenBound(d); }
118 
119  void WhenDomain(Demon* d) override { inner_->WhenDomain(d); }
120 
121  uint64 Size() const override { return inner_->Size(); }
122 
123  bool Contains(int64 v) const override { return inner_->Contains(v); }
124 
125  IntVarIterator* MakeHoleIterator(bool reversible) const override {
126  return inner_->MakeHoleIterator(reversible);
127  }
128 
129  IntVarIterator* MakeDomainIterator(bool reversible) const override {
130  return inner_->MakeDomainIterator(reversible);
131  }
132 
133  int64 OldMin() const override { return inner_->OldMin(); }
134 
135  int64 OldMax() const override { return inner_->OldMax(); }
136 
137  int VarType() const override { return TRACE_VAR; }
138 
139  void Accept(ModelVisitor* const visitor) const override {
140  IntExpr* const cast_expr =
141  solver()->CastExpression(const_cast<TraceIntVar*>(this));
142  if (cast_expr != nullptr) {
143  visitor->VisitIntegerVariable(this, cast_expr);
144  } else {
145  visitor->VisitIntegerVariable(this, ModelVisitor::kTraceOperation, 0,
146  inner_);
147  }
148  }
149 
150  std::string DebugString() const override { return inner_->DebugString(); }
151 
152  IntVar* IsEqual(int64 constant) override { return inner_->IsEqual(constant); }
153 
154  IntVar* IsDifferent(int64 constant) override {
155  return inner_->IsDifferent(constant);
156  }
157 
158  IntVar* IsGreaterOrEqual(int64 constant) override {
159  return inner_->IsGreaterOrEqual(constant);
160  }
161 
162  IntVar* IsLessOrEqual(int64 constant) override {
163  return inner_->IsLessOrEqual(constant);
164  }
165 
166  private:
167  IntVar* const inner_;
168 };
169 
170 class TraceIntExpr : public IntExpr {
171  public:
172  TraceIntExpr(Solver* const solver, IntExpr* const inner)
173  : IntExpr(solver), inner_(inner) {
174  CHECK(!inner->IsVar());
175  if (inner->HasName()) {
176  set_name(inner->name());
177  }
178  }
179 
180  ~TraceIntExpr() override {}
181 
182  int64 Min() const override { return inner_->Min(); }
183 
184  void SetMin(int64 m) override {
185  solver()->GetPropagationMonitor()->SetMin(inner_, m);
186  inner_->SetMin(m);
187  }
188 
189  int64 Max() const override { return inner_->Max(); }
190 
191  void SetMax(int64 m) override {
192  solver()->GetPropagationMonitor()->SetMax(inner_, m);
193  inner_->SetMax(m);
194  }
195 
196  void Range(int64* l, int64* u) override { inner_->Range(l, u); }
197 
198  void SetRange(int64 l, int64 u) override {
199  if (l > inner_->Min() || u < inner_->Max()) {
200  solver()->GetPropagationMonitor()->SetRange(inner_, l, u);
201  inner_->SetRange(l, u);
202  }
203  }
204 
205  bool Bound() const override { return inner_->Bound(); }
206 
207  bool IsVar() const override {
208  DCHECK(!inner_->IsVar());
209  return false;
210  }
211 
212  IntVar* Var() override { return solver()->RegisterIntVar(inner_->Var()); }
213 
214  void WhenRange(Demon* d) override { inner_->WhenRange(d); }
215 
216  void Accept(ModelVisitor* const visitor) const override {
217  visitor->BeginVisitIntegerExpression(ModelVisitor::kTrace, this);
218  visitor->VisitIntegerExpressionArgument(ModelVisitor::kExpressionArgument,
219  inner_);
220  visitor->EndVisitIntegerExpression(ModelVisitor::kTrace, this);
221  }
222 
223  std::string DebugString() const override { return inner_->DebugString(); }
224 
225  private:
226  IntExpr* const inner_;
227 };
228 
229 class TraceIntervalVar : public IntervalVar {
230  public:
231  TraceIntervalVar(Solver* const solver, IntervalVar* const inner)
232  : IntervalVar(solver, ""), inner_(inner) {
233  if (inner->HasName()) {
234  set_name(inner->name());
235  }
236  }
237  ~TraceIntervalVar() override {}
238 
239  int64 StartMin() const override { return inner_->StartMin(); }
240 
241  int64 StartMax() const override { return inner_->StartMax(); }
242 
243  void SetStartMin(int64 m) override {
244  if (inner_->MayBePerformed() && (m > inner_->StartMin())) {
245  solver()->GetPropagationMonitor()->SetStartMin(inner_, m);
246  inner_->SetStartMin(m);
247  }
248  }
249 
250  void SetStartMax(int64 m) override {
251  if (inner_->MayBePerformed() && (m < inner_->StartMax())) {
252  solver()->GetPropagationMonitor()->SetStartMax(inner_, m);
253  inner_->SetStartMax(m);
254  }
255  }
256 
257  void SetStartRange(int64 mi, int64 ma) override {
258  if (inner_->MayBePerformed() &&
259  (mi > inner_->StartMin() || ma < inner_->StartMax())) {
260  solver()->GetPropagationMonitor()->SetStartRange(inner_, mi, ma);
261  inner_->SetStartRange(mi, ma);
262  }
263  }
264 
265  int64 OldStartMin() const override { return inner_->OldStartMin(); }
266 
267  int64 OldStartMax() const override { return inner_->OldStartMax(); }
268 
269  void WhenStartRange(Demon* const d) override { inner_->WhenStartRange(d); }
270 
271  void WhenStartBound(Demon* const d) override { inner_->WhenStartBound(d); }
272 
273  int64 EndMin() const override { return inner_->EndMin(); }
274 
275  int64 EndMax() const override { return inner_->EndMax(); }
276 
277  void SetEndMin(int64 m) override {
278  if (inner_->MayBePerformed() && (m > inner_->EndMin())) {
279  solver()->GetPropagationMonitor()->SetEndMin(inner_, m);
280  inner_->SetEndMin(m);
281  }
282  }
283 
284  void SetEndMax(int64 m) override {
285  if (inner_->MayBePerformed() && (m < inner_->EndMax())) {
286  solver()->GetPropagationMonitor()->SetEndMax(inner_, m);
287  inner_->SetEndMax(m);
288  }
289  }
290 
291  void SetEndRange(int64 mi, int64 ma) override {
292  if (inner_->MayBePerformed() &&
293  (mi > inner_->EndMin() || ma < inner_->EndMax())) {
294  solver()->GetPropagationMonitor()->SetEndRange(inner_, mi, ma);
295  inner_->SetEndRange(mi, ma);
296  }
297  }
298 
299  int64 OldEndMin() const override { return inner_->OldEndMin(); }
300 
301  int64 OldEndMax() const override { return inner_->OldEndMax(); }
302 
303  void WhenEndRange(Demon* const d) override { inner_->WhenEndRange(d); }
304 
305  void WhenEndBound(Demon* const d) override { inner_->WhenStartBound(d); }
306 
307  int64 DurationMin() const override { return inner_->DurationMin(); }
308 
309  int64 DurationMax() const override { return inner_->DurationMax(); }
310 
311  void SetDurationMin(int64 m) override {
312  if (inner_->MayBePerformed() && (m > inner_->DurationMin())) {
313  solver()->GetPropagationMonitor()->SetDurationMin(inner_, m);
314  inner_->SetDurationMin(m);
315  }
316  }
317 
318  void SetDurationMax(int64 m) override {
319  if (inner_->MayBePerformed() && (m < inner_->DurationMax())) {
320  solver()->GetPropagationMonitor()->SetDurationMax(inner_, m);
321  inner_->SetDurationMax(m);
322  }
323  }
324 
325  void SetDurationRange(int64 mi, int64 ma) override {
326  if (inner_->MayBePerformed() &&
327  (mi > inner_->DurationMin() || ma < inner_->DurationMax())) {
328  solver()->GetPropagationMonitor()->SetDurationRange(inner_, mi, ma);
329  inner_->SetDurationRange(mi, ma);
330  }
331  }
332 
333  int64 OldDurationMin() const override { return inner_->OldDurationMin(); }
334 
335  int64 OldDurationMax() const override { return inner_->OldDurationMax(); }
336 
337  void WhenDurationRange(Demon* const d) override {
338  inner_->WhenDurationRange(d);
339  }
340 
341  void WhenDurationBound(Demon* const d) override {
342  inner_->WhenDurationBound(d);
343  }
344 
345  bool MustBePerformed() const override { return inner_->MustBePerformed(); }
346 
347  bool MayBePerformed() const override { return inner_->MayBePerformed(); }
348 
349  void SetPerformed(bool value) override {
350  if ((value && !inner_->MustBePerformed()) ||
351  (!value && inner_->MayBePerformed())) {
352  solver()->GetPropagationMonitor()->SetPerformed(inner_, value);
353  inner_->SetPerformed(value);
354  }
355  }
356 
357  bool WasPerformedBound() const override {
358  return inner_->WasPerformedBound();
359  }
360 
361  void WhenPerformedBound(Demon* const d) override {
362  inner_->WhenPerformedBound(d);
363  }
364 
365  IntExpr* StartExpr() override { return inner_->StartExpr(); }
366  IntExpr* DurationExpr() override { return inner_->DurationExpr(); }
367  IntExpr* EndExpr() override { return inner_->EndExpr(); }
368  IntExpr* PerformedExpr() override { return inner_->PerformedExpr(); }
369  IntExpr* SafeStartExpr(int64 unperformed_value) override {
370  return inner_->SafeStartExpr(unperformed_value);
371  }
372  IntExpr* SafeDurationExpr(int64 unperformed_value) override {
373  return inner_->SafeDurationExpr(unperformed_value);
374  }
375  IntExpr* SafeEndExpr(int64 unperformed_value) override {
376  return inner_->SafeEndExpr(unperformed_value);
377  }
378 
379  void Accept(ModelVisitor* const visitor) const override {
380  inner_->Accept(visitor);
381  }
382 
383  std::string DebugString() const override { return inner_->DebugString(); }
384 
385  private:
386  IntervalVar* const inner_;
387 };
388 
389 // ---------- PrintTrace ----------
390 
391 class PrintTrace : public PropagationMonitor {
392  public:
393  struct Info {
394  explicit Info(const std::string& m) : message(m), displayed(false) {}
395  std::string message;
396  bool displayed;
397  };
398 
399  struct Context {
400  Context()
401  : initial_indent(0),
402  indent(0),
403  in_demon(false),
404  in_constraint(false),
405  in_decision_builder(false),
406  in_decision(false),
407  in_objective(false) {}
408 
409  explicit Context(int start_indent)
410  : initial_indent(start_indent),
411  indent(start_indent),
412  in_demon(false),
413  in_constraint(false),
414  in_decision_builder(false),
415  in_decision(false),
416  in_objective(false) {}
417 
418  bool TopLevel() const { return initial_indent == indent; }
419 
420  void Clear() {
422  in_demon = false;
423  in_constraint = false;
424  in_decision_builder = false;
425  in_decision = false;
426  in_objective = false;
427  delayed_info.clear();
428  }
429 
431  int indent;
432  bool in_demon;
437  std::vector<Info> delayed_info;
438  };
439 
440  explicit PrintTrace(Solver* const s) : PropagationMonitor(s) {
441  contexes_.push(Context());
442  }
443 
444  ~PrintTrace() override {}
445 
446  // ----- Search events -----
447 
448  void BeginInitialPropagation() override {
449  CheckNoDelayed();
450  DisplaySearch("Root Node Propagation");
451  IncreaseIndent();
452  }
453  void EndInitialPropagation() override {
454  DecreaseIndent();
455  DisplaySearch("Starting Tree Search");
456  }
457 
458  void BeginNextDecision(DecisionBuilder* const b) override {
459  DisplaySearch(absl::StrFormat("DecisionBuilder(%s)", b->DebugString()));
460  IncreaseIndent();
461  contexes_.top().in_decision_builder = true;
462  }
463 
464  // After calling DecisionBuilder::Next, along with the returned decision.
465  void EndNextDecision(DecisionBuilder* const b, Decision* const d) override {
466  contexes_.top().in_decision_builder = false;
467  DecreaseIndent();
468  }
469 
470  void BeginFail() override {
471  contexes_.top().Clear();
472  while (!contexes_.top().TopLevel()) {
473  DecreaseIndent();
474  LOG(INFO) << Indent() << "}";
475  }
476  DisplaySearch(
477  absl::StrFormat("Failure at depth %d", solver()->SearchDepth()));
478  }
479 
480  bool AtSolution() override {
481  DisplaySearch(
482  absl::StrFormat("Solution found at depth %d", solver()->SearchDepth()));
483  return false;
484  }
485 
486  void ApplyDecision(Decision* const decision) override {
487  DisplaySearch(
488  absl::StrFormat("ApplyDecision(%s)", decision->DebugString()));
489  IncreaseIndent();
490  contexes_.top().in_decision = true;
491  }
492 
493  void RefuteDecision(Decision* const decision) override {
494  if (contexes_.top().in_objective) {
495  DecreaseIndent();
496  contexes_.top().in_objective = false;
497  }
498  DisplaySearch(
499  absl::StrFormat("RefuteDecision(%s)", decision->DebugString()));
500  IncreaseIndent();
501  contexes_.top().in_decision = true;
502  }
503 
504  void AfterDecision(Decision* const decision, bool direction) override {
505  DecreaseIndent();
506  contexes_.top().in_decision = false;
507  }
508 
509  void EnterSearch() override {
510  if (solver()->SolveDepth() == 0) {
511  CHECK_EQ(1, contexes_.size());
512  contexes_.top().Clear();
513  } else {
514  PrintDelayedString();
515  PushNestedContext();
516  }
517  DisplaySearch("Enter Search");
518  }
519 
520  void ExitSearch() override {
521  DisplaySearch("Exit Search");
522  CHECK(contexes_.top().TopLevel());
523  if (solver()->SolveDepth() > 1) {
524  contexes_.pop();
525  }
526  }
527 
528  void RestartSearch() override { CHECK(contexes_.top().TopLevel()); }
529 
530  // ----- Propagation events -----
531 
532  void BeginConstraintInitialPropagation(
533  Constraint* const constraint) override {
534  PushDelayedInfo(
535  absl::StrFormat("Constraint(%s)", constraint->DebugString()));
536  contexes_.top().in_constraint = true;
537  }
538 
539  void EndConstraintInitialPropagation(Constraint* const constraint) override {
540  PopDelayedInfo();
541  contexes_.top().in_constraint = false;
542  }
543 
544  void BeginNestedConstraintInitialPropagation(
545  Constraint* const parent, Constraint* const nested) override {
546  PushDelayedInfo(absl::StrFormat("Constraint(%s)", nested->DebugString()));
547  contexes_.top().in_constraint = true;
548  }
549  void EndNestedConstraintInitialPropagation(Constraint* const,
550  Constraint* const) override {
551  PopDelayedInfo();
552  contexes_.top().in_constraint = false;
553  }
554 
555  void RegisterDemon(Demon* const demon) override {}
556 
557  void BeginDemonRun(Demon* const demon) override {
558  if (demon->priority() != Solver::VAR_PRIORITY) {
559  contexes_.top().in_demon = true;
560  PushDelayedInfo(absl::StrFormat("Demon(%s)", demon->DebugString()));
561  }
562  }
563 
564  void EndDemonRun(Demon* const demon) override {
565  if (demon->priority() != Solver::VAR_PRIORITY) {
566  contexes_.top().in_demon = false;
567  PopDelayedInfo();
568  }
569  }
570 
571  void StartProcessingIntegerVariable(IntVar* const var) override {
572  PushDelayedInfo(absl::StrFormat("StartProcessing(%s)", var->DebugString()));
573  }
574 
575  void EndProcessingIntegerVariable(IntVar* const var) override {
576  PopDelayedInfo();
577  }
578 
579  void PushContext(const std::string& context) override {
580  PushDelayedInfo(context);
581  }
582 
583  void PopContext() override { PopDelayedInfo(); }
584 
585  // ----- IntExpr modifiers -----
586 
587  void SetMin(IntExpr* const expr, int64 new_min) override {
588  DisplayModification(
589  absl::StrFormat("SetMin(%s, %d)", expr->DebugString(), new_min));
590  }
591 
592  void SetMax(IntExpr* const expr, int64 new_max) override {
593  DisplayModification(
594  absl::StrFormat("SetMax(%s, %d)", expr->DebugString(), new_max));
595  }
596 
597  void SetRange(IntExpr* const expr, int64 new_min, int64 new_max) override {
598  DisplayModification(absl::StrFormat("SetRange(%s, [%d .. %d])",
599  expr->DebugString(), new_min, new_max));
600  }
601 
602  // ----- IntVar modifiers -----
603 
604  void SetMin(IntVar* const var, int64 new_min) override {
605  DisplayModification(
606  absl::StrFormat("SetMin(%s, %d)", var->DebugString(), new_min));
607  }
608 
609  void SetMax(IntVar* const var, int64 new_max) override {
610  DisplayModification(
611  absl::StrFormat("SetMax(%s, %d)", var->DebugString(), new_max));
612  }
613 
614  void SetRange(IntVar* const var, int64 new_min, int64 new_max) override {
615  DisplayModification(absl::StrFormat("SetRange(%s, [%d .. %d])",
616  var->DebugString(), new_min, new_max));
617  }
618 
619  void RemoveValue(IntVar* const var, int64 value) override {
620  DisplayModification(
621  absl::StrFormat("RemoveValue(%s, %d)", var->DebugString(), value));
622  }
623 
624  void SetValue(IntVar* const var, int64 value) override {
625  DisplayModification(
626  absl::StrFormat("SetValue(%s, %d)", var->DebugString(), value));
627  }
628 
629  void RemoveInterval(IntVar* const var, int64 imin, int64 imax) override {
630  DisplayModification(absl::StrFormat("RemoveInterval(%s, [%d .. %d])",
631  var->DebugString(), imin, imax));
632  }
633 
634  void SetValues(IntVar* const var, const std::vector<int64>& values) override {
635  DisplayModification(absl::StrFormat("SetValues(%s, %s)", var->DebugString(),
636  absl::StrJoin(values, ", ")));
637  }
638 
639  void RemoveValues(IntVar* const var,
640  const std::vector<int64>& values) override {
641  DisplayModification(absl::StrFormat("RemoveValues(%s, %s)",
642  var->DebugString(),
643  absl::StrJoin(values, ", ")));
644  }
645 
646  // ----- IntervalVar modifiers -----
647 
648  void SetStartMin(IntervalVar* const var, int64 new_min) override {
649  DisplayModification(
650  absl::StrFormat("SetStartMin(%s, %d)", var->DebugString(), new_min));
651  }
652 
653  void SetStartMax(IntervalVar* const var, int64 new_max) override {
654  DisplayModification(
655  absl::StrFormat("SetStartMax(%s, %d)", var->DebugString(), new_max));
656  }
657 
658  void SetStartRange(IntervalVar* const var, int64 new_min,
659  int64 new_max) override {
660  DisplayModification(absl::StrFormat("SetStartRange(%s, [%d .. %d])",
661  var->DebugString(), new_min, new_max));
662  }
663 
664  void SetEndMin(IntervalVar* const var, int64 new_min) override {
665  DisplayModification(
666  absl::StrFormat("SetEndMin(%s, %d)", var->DebugString(), new_min));
667  }
668 
669  void SetEndMax(IntervalVar* const var, int64 new_max) override {
670  DisplayModification(
671  absl::StrFormat("SetEndMax(%s, %d)", var->DebugString(), new_max));
672  }
673 
674  void SetEndRange(IntervalVar* const var, int64 new_min,
675  int64 new_max) override {
676  DisplayModification(absl::StrFormat("SetEndRange(%s, [%d .. %d])",
677  var->DebugString(), new_min, new_max));
678  }
679 
680  void SetDurationMin(IntervalVar* const var, int64 new_min) override {
681  DisplayModification(
682  absl::StrFormat("SetDurationMin(%s, %d)", var->DebugString(), new_min));
683  }
684 
685  void SetDurationMax(IntervalVar* const var, int64 new_max) override {
686  DisplayModification(
687  absl::StrFormat("SetDurationMax(%s, %d)", var->DebugString(), new_max));
688  }
689 
690  void SetDurationRange(IntervalVar* const var, int64 new_min,
691  int64 new_max) override {
692  DisplayModification(absl::StrFormat("SetDurationRange(%s, [%d .. %d])",
693  var->DebugString(), new_min, new_max));
694  }
695 
696  void SetPerformed(IntervalVar* const var, bool value) override {
697  DisplayModification(
698  absl::StrFormat("SetPerformed(%s, %d)", var->DebugString(), value));
699  }
700 
701  void RankFirst(SequenceVar* const var, int index) override {
702  DisplayModification(
703  absl::StrFormat("RankFirst(%s, %d)", var->DebugString(), index));
704  }
705 
706  void RankNotFirst(SequenceVar* const var, int index) override {
707  DisplayModification(
708  absl::StrFormat("RankNotFirst(%s, %d)", var->DebugString(), index));
709  }
710 
711  void RankLast(SequenceVar* const var, int index) override {
712  DisplayModification(
713  absl::StrFormat("RankLast(%s, %d)", var->DebugString(), index));
714  }
715 
716  void RankNotLast(SequenceVar* const var, int index) override {
717  DisplayModification(
718  absl::StrFormat("RankNotLast(%s, %d)", var->DebugString(), index));
719  }
720 
721  void RankSequence(SequenceVar* const var, const std::vector<int>& rank_first,
722  const std::vector<int>& rank_last,
723  const std::vector<int>& unperformed) override {
724  DisplayModification(absl::StrFormat(
725  "RankSequence(%s, forward [%s], backward[%s], unperformed[%s])",
726  var->DebugString(), absl::StrJoin(rank_first, ", "),
727  absl::StrJoin(rank_last, ", "), absl::StrJoin(unperformed, ", ")));
728  }
729 
730  void Install() override {
732  if (solver()->SolveDepth() <= 1) {
733  solver()->AddPropagationMonitor(this);
734  }
735  }
736 
737  std::string DebugString() const override { return "PrintTrace"; }
738 
739  private:
740  void PushDelayedInfo(const std::string& delayed) {
741  if (absl::GetFlag(FLAGS_cp_full_trace)) {
742  LOG(INFO) << Indent() << delayed << " {";
743  IncreaseIndent();
744  } else {
745  contexes_.top().delayed_info.push_back(Info(delayed));
746  }
747  }
748 
749  void PopDelayedInfo() {
750  if (absl::GetFlag(FLAGS_cp_full_trace)) {
751  DecreaseIndent();
752  LOG(INFO) << Indent() << "}";
753  } else {
754  CHECK(!contexes_.top().delayed_info.empty());
755  if (contexes_.top().delayed_info.back().displayed &&
756  !contexes_.top().TopLevel()) {
757  DecreaseIndent();
758  LOG(INFO) << Indent() << "}";
759  } else {
760  contexes_.top().delayed_info.pop_back();
761  }
762  }
763  }
764 
765  void CheckNoDelayed() { CHECK(contexes_.top().delayed_info.empty()); }
766 
767  void PrintDelayedString() {
768  const std::vector<Info>& infos = contexes_.top().delayed_info;
769  for (int i = 0; i < infos.size(); ++i) {
770  const Info& info = infos[i];
771  if (!info.displayed) {
772  LOG(INFO) << Indent() << info.message << " {";
773  IncreaseIndent();
774  // Marks it as displayed.
775  contexes_.top().delayed_info[i].displayed = true;
776  }
777  }
778  }
779 
780  void DisplayModification(const std::string& to_print) {
781  if (absl::GetFlag(FLAGS_cp_full_trace)) {
782  LOG(INFO) << Indent() << to_print;
783  } else {
784  PrintDelayedString();
785  if (contexes_.top().in_demon || contexes_.top().in_constraint ||
786  contexes_.top().in_decision_builder || contexes_.top().in_decision ||
787  contexes_.top().in_objective) {
788  // Inside a demon, constraint, decision builder -> normal print.
789  LOG(INFO) << Indent() << to_print;
790  } else {
791  // Top level, modification pushed by the objective. This is a
792  // hack. The SetMax or SetMin done by the objective happens in
793  // the RefuteDecision callback of search monitors. We cannot
794  // easily differentiate that from the actual modifications done
795  // by the Refute() call itself. To distinguish that, we force
796  // the print trace to be last in the list of monitors. Thus
797  // modifications that happens at the top level before the
798  // RefuteDecision() callbacks must be from the objective.
799  // In that case, we push the in_objective context.
800  CHECK(contexes_.top().TopLevel());
801  DisplaySearch(absl::StrFormat("Objective -> %s", to_print));
802  IncreaseIndent();
803  contexes_.top().in_objective = true;
804  }
805  }
806  }
807 
808  void DisplaySearch(const std::string& to_print) {
809  const int solve_depth = solver()->SolveDepth();
810  if (solve_depth <= 1) {
811  LOG(INFO) << Indent() << "######## Top Level Search: " << to_print;
812  } else {
813  LOG(INFO) << Indent() << "######## Nested Search(" << solve_depth - 1
814  << "): " << to_print;
815  }
816  }
817 
818  std::string Indent() {
819  CHECK_GE(contexes_.top().indent, 0);
820  std::string output = " @ ";
821  for (int i = 0; i < contexes_.top().indent; ++i) {
822  output.append(" ");
823  }
824  return output;
825  }
826 
827  void IncreaseIndent() { contexes_.top().indent++; }
828 
829  void DecreaseIndent() {
830  if (contexes_.top().indent > 0) {
831  contexes_.top().indent--;
832  }
833  }
834 
835  void PushNestedContext() {
836  const int initial_indent = contexes_.top().indent;
837  contexes_.push(Context(initial_indent));
838  }
839 
840  std::stack<Context> contexes_;
841 };
842 } // namespace
843 
845  if (InstrumentsVariables()) {
846  if (expr->IsVar()) {
847  return RegisterIntVar(expr->Var());
848  } else {
849  return RevAlloc(new TraceIntExpr(this, expr));
850  }
851  } else {
852  return expr;
853  }
854 }
855 
857  if (InstrumentsVariables() && var->VarType() != TRACE_VAR) { // Not already a
858  // trace var.
859  return RevAlloc(new TraceIntVar(this, var));
860  } else {
861  return var;
862  }
863 }
864 
866  if (InstrumentsVariables()) {
867  return RevAlloc(new TraceIntervalVar(this, var));
868  } else {
869  return var;
870  }
871 }
872 
874  return s->RevAlloc(new PrintTrace(s));
875 }
876 } // namespace operations_research
operations_research::IntVar
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3992
var
IntVar * var
Definition: expr_array.cc:1858
INFO
const int INFO
Definition: log_severity.h:31
integral_types.h
map_util.h
in_objective
bool in_objective
Definition: trace.cc:436
LOG
#define LOG(severity)
Definition: base/logging.h:420
in_decision_builder
bool in_decision_builder
Definition: trace.cc:434
CHECK_GE
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
message
std::string message
Definition: trace.cc:395
operations_research::Solver::RevAlloc
T * RevAlloc(T *object)
Registers the given object as being reversible.
Definition: constraint_solver.h:791
logging.h
value
int64 value
Definition: demon_profiler.cc:43
operations_research::IntExpr::IsVar
virtual bool IsVar() const
Returns true if the expression is indeed a variable.
Definition: constraint_solver.h:3860
in_demon
bool in_demon
Definition: trace.cc:432
operations_research::SearchMonitor::Install
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
Definition: constraint_solver.cc:2892
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
int64
int64_t int64
Definition: integral_types.h:34
constraint_solveri.h
operations_research::ModelVisitor::kTraceOperation
static const char kTraceOperation[]
Definition: constraint_solver.h:3501
operations_research::Solver::RegisterIntervalVar
IntervalVar * RegisterIntervalVar(IntervalVar *const var)
Registers a new IntervalVar and wraps it inside a TraceIntervalVar if necessary.
Definition: trace.cc:865
index
int index
Definition: pack.cc:508
operations_research::RegisterDemon
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
Definition: demon_profiler.cc:460
context
GurobiMPCallbackContext * context
Definition: gurobi_interface.cc:509
in_constraint
bool in_constraint
Definition: trace.cc:433
constraint_solver.h
operations_research::TRACE_VAR
@ TRACE_VAR
Definition: constraint_solveri.h:132
initial_indent
int initial_indent
Definition: trace.cc:430
CHECK_EQ
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
operations_research::Solver::RegisterIntVar
IntVar * RegisterIntVar(IntVar *const var)
Registers a new IntVar and wraps it inside a TraceIntVar if necessary.
Definition: trace.cc:856
uint64
uint64_t uint64
Definition: integral_types.h:39
operations_research::sat::Value
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1470
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::IntervalVar
Interval variables are often used in scheduling.
Definition: constraint_solver.h:4389
operations_research::Solver
Solver Class.
Definition: constraint_solver.h:248
operations_research::PropagationMonitor
Definition: constraint_solveri.h:1851
operations_research::ModelVisitor::kExpressionArgument
static const char kExpressionArgument[]
Definition: constraint_solver.h:3447
operations_research::Solver::VAR_PRIORITY
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
Definition: constraint_solver.h:614
operations_research::Solver::InstrumentsVariables
bool InstrumentsVariables() const
Returns whether we are tracing variables.
Definition: constraint_solver.cc:183
delayed_info
std::vector< Info > delayed_info
Definition: trace.cc:437
in_decision
bool in_decision
Definition: trace.cc:435
b
int64 b
Definition: constraint_solver/table.cc:43
operations_research::IntExpr
The class IntExpr is the base of all integer expressions in constraint programming.
Definition: constraint_solver.h:3831
indent
int indent
Definition: trace.cc:431
displayed
bool displayed
Definition: trace.cc:396
CHECK_NE
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
CHECK
#define CHECK(condition)
Definition: base/logging.h:495
commandlineflags.h
operations_research::IntExpr::Var
virtual IntVar * Var()=0
Creates a variable from the expression.
operations_research::BuildPrintTrace
PropagationMonitor * BuildPrintTrace(Solver *const s)
Definition: trace.cc:873
operations_research::ModelVisitor::kTrace
static const char kTrace[]
Definition: constraint_solver.h:3409
operations_research::Solver::RegisterIntExpr
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
Definition: trace.cc:844
ABSL_FLAG
ABSL_FLAG(bool, cp_full_trace, false, "Display all trace information, even if the modifiers has no effect")