21 #include "absl/container/flat_hash_map.h"
22 #include "absl/status/status.h"
23 #include "absl/strings/str_format.h"
24 #include "absl/time/clock.h"
25 #include "absl/time/time.h"
34 #include "ortools/constraint_solver/demon_profiler.pb.h"
39 Container(
const Constraint* ct_,
int64 value_) :
ct(ct_),
value(value_) {}
40 bool operator<(
const Container& c)
const {
return value > c.value; }
54 active_constraint_(nullptr),
55 active_demon_(nullptr),
56 start_time_ns_(
absl::GetCurrentTimeNanos()) {}
60 constraint_map_.end());
66 return (absl::GetCurrentTimeNanos() - start_time_ns_) / 1000;
75 CHECK(active_constraint_ ==
nullptr);
76 CHECK(active_demon_ ==
nullptr);
77 CHECK(constraint !=
nullptr);
78 ConstraintRuns*
const ct_run =
new ConstraintRuns;
79 ct_run->set_constraint_id(constraint->
DebugString());
80 ct_run->add_initial_propagation_start_time(
CurrentTime());
81 active_constraint_ = constraint;
82 constraint_map_[constraint] = ct_run;
86 CHECK(active_constraint_ !=
nullptr);
87 CHECK(active_demon_ ==
nullptr);
88 CHECK(constraint !=
nullptr);
89 CHECK_EQ(constraint, active_constraint_);
90 ConstraintRuns*
const ct_run = constraint_map_[constraint];
91 if (ct_run !=
nullptr) {
92 ct_run->add_initial_propagation_end_time(
CurrentTime());
93 ct_run->set_failures(0);
95 active_constraint_ =
nullptr;
104 CHECK(active_constraint_ ==
nullptr);
105 CHECK(active_demon_ ==
nullptr);
106 CHECK(constraint !=
nullptr);
107 CHECK(delayed !=
nullptr);
108 ConstraintRuns*
const ct_run = constraint_map_[constraint];
109 ct_run->add_initial_propagation_start_time(
CurrentTime());
110 active_constraint_ = constraint;
115 CHECK(active_constraint_ !=
nullptr);
116 CHECK(active_demon_ ==
nullptr);
117 CHECK(constraint !=
nullptr);
118 CHECK(delayed !=
nullptr);
119 CHECK_EQ(constraint, active_constraint_);
120 ConstraintRuns*
const ct_run = constraint_map_[constraint];
121 if (ct_run !=
nullptr) {
122 ct_run->add_initial_propagation_end_time(
CurrentTime());
123 ct_run->set_failures(0);
125 active_constraint_ =
nullptr;
133 if (demon_map_.find(demon) == demon_map_.end()) {
134 CHECK(active_constraint_ !=
nullptr);
135 CHECK(active_demon_ ==
nullptr);
136 CHECK(demon !=
nullptr);
137 ConstraintRuns*
const ct_run = constraint_map_[active_constraint_];
138 DemonRuns*
const demon_run = ct_run->add_demons();
140 demon_run->set_failures(0);
141 demon_map_[demon] = demon_run;
142 demons_per_constraint_[active_constraint_].push_back(demon_run);
147 CHECK(demon !=
nullptr);
151 CHECK(active_demon_ ==
nullptr);
152 active_demon_ = demon;
153 DemonRuns*
const demon_run = demon_map_[active_demon_];
154 if (demon_run !=
nullptr) {
160 CHECK(demon !=
nullptr);
165 DemonRuns*
const demon_run = demon_map_[active_demon_];
166 if (demon_run !=
nullptr) {
169 active_demon_ =
nullptr;
178 if (active_demon_ !=
nullptr) {
179 DemonRuns*
const demon_run = demon_map_[active_demon_];
180 if (demon_run !=
nullptr) {
182 demon_run->set_failures(demon_run->failures() + 1);
184 active_demon_ =
nullptr;
186 active_constraint_ =
nullptr;
187 }
else if (active_constraint_ !=
nullptr) {
188 ConstraintRuns*
const ct_run = constraint_map_[active_constraint_];
189 if (ct_run !=
nullptr) {
190 ct_run->add_initial_propagation_end_time(
CurrentTime());
191 ct_run->set_failures(1);
193 active_constraint_ =
nullptr;
200 constraint_map_.end());
201 constraint_map_.clear();
203 demons_per_constraint_.clear();
220 const std::vector<int64>& values)
override {}
225 int64 new_max)
override {}
229 int64 new_max)
override {}
233 int64 new_max)
override {}
240 const std::vector<int>& rank_last,
241 const std::vector<int>& unperformed)
override {}
246 CHECK(demon !=
nullptr);
247 DemonRuns*
const demon_run = demon_map_[demon];
248 CHECK(demon_run !=
nullptr);
249 demon_run->add_start_time(start_time);
250 demon_run->add_end_time(end_time);
252 demon_run->set_failures(demon_run->failures() + 1);
258 const char*
const kConstraintFormat =
259 " - Constraint: %s\n failures=%d, initial propagation "
260 "runtime=%d us, demons=%d, demon invocations=%d, total demon "
262 const char*
const kDemonFormat =
263 " --- Demon: %s\n invocations=%d, failures=%d, total "
264 "runtime=%d us, [average=%.2lf, median=%.2lf, stddev=%.2lf]\n";
266 const std::string
model =
270 std::vector<Container> to_sort;
272 ConstraintRuns*>::const_iterator it =
273 constraint_map_.begin();
274 it != constraint_map_.end(); ++it) {
277 int64 demon_invocations = 0;
278 int64 initial_propagation_runtime = 0;
279 int64 total_demon_runtime = 0;
282 &demon_invocations, &total_demon_runtime,
285 Container(
ct, total_demon_runtime + initial_propagation_runtime));
287 std::sort(to_sort.begin(), to_sort.end());
289 for (
int i = 0; i < to_sort.size(); ++i) {
292 int64 demon_invocations = 0;
293 int64 initial_propagation_runtime = 0;
294 int64 total_demon_runtime = 0;
297 &demon_invocations, &total_demon_runtime,
299 const std::string constraint_message =
300 absl::StrFormat(kConstraintFormat,
ct->DebugString(), fails,
301 initial_propagation_runtime, demon_count,
302 demon_invocations, total_demon_runtime);
305 const std::vector<DemonRuns*>& demons = demons_per_constraint_[
ct];
306 const int demon_size = demons.size();
307 for (
int demon_index = 0; demon_index < demon_size; ++demon_index) {
308 DemonRuns*
const demon_runs = demons[demon_index];
309 int64 invocations = 0;
312 double mean_runtime = 0;
313 double median_runtime = 0;
314 double standard_deviation = 0.0;
316 &mean_runtime, &median_runtime,
317 &standard_deviation);
318 const std::string
runs = absl::StrFormat(
319 kDemonFormat, demon_runs->demon_id(), invocations, fails, runtime,
320 mean_runtime, median_runtime, standard_deviation);
330 int64*
const initial_propagation_runtime,
331 int64*
const demon_invocations,
332 int64*
const total_demon_runtime,
int* demons) {
333 CHECK(constraint !=
nullptr);
334 ConstraintRuns*
const ct_run = constraint_map_[constraint];
335 CHECK(ct_run !=
nullptr);
336 *demon_invocations = 0;
337 *fails = ct_run->failures();
338 *initial_propagation_runtime = 0;
339 for (
int i = 0; i < ct_run->initial_propagation_start_time_size(); ++i) {
340 *initial_propagation_runtime += ct_run->initial_propagation_end_time(i) -
341 ct_run->initial_propagation_start_time(i);
343 *total_demon_runtime = 0;
346 *demons = ct_run->demons_size();
347 CHECK_EQ(*demons, demons_per_constraint_[constraint].size());
348 for (
int demon_index = 0; demon_index < *demons; ++demon_index) {
349 const DemonRuns& demon_runs = ct_run->demons(demon_index);
350 *fails += demon_runs.failures();
351 CHECK_EQ(demon_runs.start_time_size(), demon_runs.end_time_size());
352 const int runs = demon_runs.start_time_size();
353 *demon_invocations +=
runs;
354 for (
int run_index = 0; run_index <
runs; ++run_index) {
355 const int64 demon_time =
356 demon_runs.end_time(run_index) - demon_runs.start_time(run_index);
357 *total_demon_runtime += demon_time;
363 int64*
const demon_invocations,
int64*
const fails,
364 int64*
const total_demon_runtime,
365 double*
const mean_demon_runtime,
366 double*
const median_demon_runtime,
367 double*
const stddev_demon_runtime) {
368 CHECK(demon_runs !=
nullptr);
369 CHECK_EQ(demon_runs->start_time_size(), demon_runs->end_time_size());
371 const int runs = demon_runs->start_time_size();
372 *demon_invocations =
runs;
373 *fails = demon_runs->failures();
374 *total_demon_runtime = 0;
375 *mean_demon_runtime = 0.0;
376 *median_demon_runtime = 0.0;
377 *stddev_demon_runtime = 0.0;
378 std::vector<double> runtimes;
379 for (
int run_index = 0; run_index <
runs; ++run_index) {
380 const int64 demon_time =
381 demon_runs->end_time(run_index) - demon_runs->start_time(run_index);
382 *total_demon_runtime += demon_time;
383 runtimes.push_back(demon_time);
386 if (!runtimes.empty()) {
387 *mean_demon_runtime = (1.0L * *total_demon_runtime) / runtimes.size();
390 std::sort(runtimes.begin(), runtimes.end());
391 const int pivot = runtimes.size() / 2;
393 if (runtimes.size() == 1) {
394 *median_demon_runtime = runtimes[0];
396 *median_demon_runtime =
397 runtimes.size() % 2 == 1
399 : (runtimes[pivot - 1] + runtimes[pivot]) / 2.0;
403 double total_deviation = 0.0f;
405 for (
int i = 0; i < runtimes.size(); ++i) {
406 total_deviation += pow(runtimes[i] - *mean_demon_runtime, 2);
409 *stddev_demon_runtime = sqrt(total_deviation / runtimes.size());
418 std::string
DebugString()
const override {
return "DemonProfiler"; }
422 Demon* active_demon_;
423 const int64 start_time_ns_;
424 absl::flat_hash_map<const Constraint*, ConstraintRuns*> constraint_map_;
425 absl::flat_hash_map<const Demon*, DemonRuns*> demon_map_;
426 absl::flat_hash_map<const Constraint*, std::vector<DemonRuns*> >
427 demons_per_constraint_;
431 if (demon_profiler_ !=
nullptr) {
451 CHECK(demon !=
nullptr);
453 propagation_monitor_->RegisterDemon(demon);
466 int64 start_time,
int64 end_time,
bool is_fail) {
467 monitor->
AddFakeRun(demon, start_time, end_time, is_fail);
473 int64*
const initial_propagation_runtime,
474 int64*
const demon_invocations,
475 int64*
const total_demon_runtime,
476 int*
const demon_count) {
478 demon_invocations, total_demon_runtime,
#define CHECK_EQ(val1, val2)
A constraint is the main modeling object.
std::string DebugString() const override
A Demon is the base element of a propagation queue.
virtual Solver::DemonPriority priority() const
This method returns the priority of the demon.
std::string DebugString() const override
void BeginFail() override
Just when the failure occurs.
void SetStartMin(IntervalVar *const var, int64 new_min) override
IntervalVar modifiers.
void Install() override
Install itself on the solver.
int64 CurrentTime() const
void RestartSearch() override
Restart the search.
void SetRange(IntVar *const var, int64 new_min, int64 new_max) override
void PopContext() override
void SetEndMin(IntervalVar *const var, int64 new_min) override
void SetDurationMax(IntervalVar *const var, int64 new_max) override
void EndProcessingIntegerVariable(IntVar *const var) override
void SetDurationRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void SetPerformed(IntervalVar *const var, bool value) override
void BeginConstraintInitialPropagation(Constraint *const constraint) override
Propagation events.
void EndConstraintInitialPropagation(Constraint *const constraint) override
void SetValues(IntVar *const var, const std::vector< int64 > &values) override
void RemoveInterval(IntVar *const var, int64 imin, int64 imax) override
void StartProcessingIntegerVariable(IntVar *const var) override
void RemoveValues(IntVar *const var, const std::vector< int64 > &values) override
void ExportInformation(const DemonRuns *const demon_runs, int64 *const demon_invocations, int64 *const fails, int64 *const total_demon_runtime, double *const mean_demon_runtime, double *const median_demon_runtime, double *const stddev_demon_runtime)
void SetEndMax(IntervalVar *const var, int64 new_max) override
void RegisterDemon(Demon *const demon) override
void EndDemonRun(Demon *const demon) override
void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed) override
void SetRange(IntExpr *const expr, int64 new_min, int64 new_max) override
void BeginDemonRun(Demon *const demon) override
void SetMax(IntVar *const var, int64 new_max) override
void RemoveValue(IntVar *const var, int64 value) override
void SetValue(IntVar *const var, int64 value) override
void AddFakeRun(Demon *const demon, int64 start_time, int64 end_time, bool is_fail)
void SetMin(IntExpr *const expr, int64 new_min) override
IntExpr modifiers.
void SetEndRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void RankLast(SequenceVar *const var, int index) override
void PushContext(const std::string &context) override
void EndNestedConstraintInitialPropagation(Constraint *const constraint, Constraint *const delayed) override
void RankNotLast(SequenceVar *const var, int index) override
void ExportInformation(const Constraint *const constraint, int64 *const fails, int64 *const initial_propagation_runtime, int64 *const demon_invocations, int64 *const total_demon_runtime, int *demons)
void SetMin(IntVar *const var, int64 new_min) override
IntVar modifiers.
void SetStartMax(IntervalVar *const var, int64 new_max) override
void SetStartRange(IntervalVar *const var, int64 new_min, int64 new_max) override
void BeginNestedConstraintInitialPropagation(Constraint *const constraint, Constraint *const delayed) override
void SetMax(IntExpr *const expr, int64 new_max) override
DemonProfiler(Solver *const solver)
~DemonProfiler() override
void RankFirst(SequenceVar *const var, int index) override
SequenceVar modifiers.
std::string DebugString() const override
void RankNotFirst(SequenceVar *const var, int index) override
void SetDurationMin(IntervalVar *const var, int64 new_min) override
void PrintOverview(Solver *const solver, const std::string &filename)
The class IntExpr is the base of all integer expressions in constraint programming.
The class IntVar is a subset of IntExpr.
Interval variables are often used in scheduling.
virtual void Install()
Registers itself on the solver such that it gets notified of the search and propagation events.
A sequence variable is a variable whose domain is a set of possible orderings of the interval variabl...
@ VAR_PRIORITY
VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.
@ IN_SEARCH
Executing the search code.
bool IsProfilingEnabled() const
Returns whether we are profiling the solver.
Demon * RegisterDemon(Demon *const demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
std::string model_name() const
Returns the name of the model.
void ExportProfilingOverview(const std::string &filename)
Exports the profiling information in a human readable overview.
bool InstrumentsDemons() const
Returns whether we are instrumenting demons.
GurobiMPCallbackContext * context
absl::Status WriteString(File *file, const absl::string_view &contents, int flags)
absl::Status Open(const absl::string_view &filename, const absl::string_view &mode, File **f, int flags)
void STLDeleteContainerPairSecondPointers(ForwardIterator begin, ForwardIterator end)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void InstallDemonProfiler(DemonProfiler *const monitor)
void DemonProfilerEndInitialPropagation(DemonProfiler *const monitor, Constraint *const constraint)
void DemonProfilerAddFakeRun(DemonProfiler *const monitor, Demon *const demon, int64 start_time, int64 end_time, bool is_fail)
void RegisterDemon(Solver *const solver, Demon *const demon, DemonProfiler *const monitor)
void DemonProfilerBeginInitialPropagation(DemonProfiler *const monitor, Constraint *const constraint)
DemonProfiler * BuildDemonProfiler(Solver *const solver)
void DemonProfilerExportInformation(DemonProfiler *const monitor, const Constraint *const constraint, int64 *const fails, int64 *const initial_propagation_runtime, int64 *const demon_invocations, int64 *const total_demon_runtime, int *const demon_count)
void DeleteDemonProfiler(DemonProfiler *const monitor)