1

2

3

4

5

6

7

8

9

10

11

12

13

14#include <cstddef>

15#include <cstdint>

16#include <functional>

17#include <limits>

18#include <memory>

19#include <random>

20#include <string>

21#include <utility>

22#include <vector>

23

24#include "absl/container/flat_hash_set.h"

25#include "absl/strings/str_format.h"

34

35ABSL_FLAG(int, cp_impact_divider, 10, "Divider for continuous update.");

36

38

39namespace {

40

41const int kDefaultNumberOfSplits = 100;

42const int kDefaultHeuristicPeriod = 100;

43const int kDefaultHeuristicNumFailuresLimit = 30;

44const bool kDefaultUseLastConflict = true;

45}

46

59

60namespace {

61

62

63

64

65class DomainWatcher {

66 public:

67 DomainWatcher(const std::vector<IntVar*>& vars, int cache_size)

68 : vars_(vars) {

69 cached_log_.Init(cache_size);

70 }

71

72

73 DomainWatcher(const DomainWatcher&) = delete;

74 DomainWatcher& operator=(const DomainWatcher&) = delete;

75

76 double LogSearchSpaceSize() {

77 double result = 0.0;

78 for (int index = 0; index < vars_.size(); ++index) {

79 result += cached_log_.Log2(vars_[index]->Size());

80 }

81 return result;

82 }

83

84 double Log2(int64_t size) const { return cached_log_.Log2(size); }

85

86 private:

87 std::vector<IntVar*> vars_;

88 CachedLog cached_log_;

89};

90

91

92

94 public:

95 enum Operation { NONE, ASSIGN, SPLIT_LOW, SPLIT_HIGH };

96

97 FindVar() : var_(nullptr), value_(0), operation_(NONE) {}

98

99 ~FindVar() override {}

100

101 void VisitSetVariableValue(IntVar* var, int64_t value) override {

102 var_ = var;

103 value_ = value;

104 operation_ = ASSIGN;

105 }

106

107 void VisitSplitVariableDomain(IntVar* var, int64_t value,

108 bool start_with_lower_half) override {

109 var_ = var;

110 value_ = value;

111 operation_ = start_with_lower_half ? SPLIT_LOW : SPLIT_HIGH;

112 }

113

114 void VisitScheduleOrPostpone(IntervalVar* const var, int64_t est) override {

115 operation_ = NONE;

116 }

117

118 virtual void VisitTryRankFirst(SequenceVar* const sequence, int index) {

119 operation_ = NONE;

120 }

121

122 virtual void VisitTryRankLast(SequenceVar* const sequence, int index) {

123 operation_ = NONE;

124 }

125

126 void VisitUnknownDecision() override { operation_ = NONE; }

127

128

129 IntVar* var() const {

130 CHECK_NE(operation_, NONE);

131 return var_;

132 }

133

134

135 int64_t value() const {

136 CHECK_NE(operation_, NONE);

137 return value_;

138 }

139

140 Operation operation() const { return operation_; }

141

142 std::string DebugString() const override {

143 return "FindVar decision visitor";

144 }

145

146 private:

147 IntVar* var_;

148 int64_t value_;

149 Operation operation_;

150};

151

152

153

154

155

157 public:

158

159 InitVarImpacts()

160 : var_(nullptr),

161 update_impact_callback_(nullptr),

162 new_start_(false),

163 var_index_(0),

164 value_index_(-1),

165 update_impact_closure_([this]() { UpdateImpacts(); }),

166 updater_(update_impact_closure_) {

167 CHECK(update_impact_closure_ != nullptr);

168 }

169

170 ~InitVarImpacts() override {}

171

172 void UpdateImpacts() {

173

174 update_impact_callback_(var_index_, var_->Min());

175 }

176

177 void Init(IntVar* const var, IntVarIterator* const iterator, int var_index) {

178 var_ = var;

179 iterator_ = iterator;

180 var_index_ = var_index;

181 new_start_ = true;

182 value_index_ = 0;

183 }

184

185 Decision* Next(Solver* const solver) override {

186 CHECK(var_ != nullptr);

187 CHECK(iterator_ != nullptr);

188 if (new_start_) {

189 active_values_.clear();

190 for (const int64_t value : InitAndGetValues(iterator_)) {

191 active_values_.push_back(value);

192 }

193 new_start_ = false;

194 }

195 if (value_index_ == active_values_.size()) {

196 return nullptr;

197 }

198 updater_.var_ = var_;

199 updater_.value_ = active_values_[value_index_];

200 value_index_++;

201 return &updater_;

202 }

203

204 void set_update_impact_callback(std::function<void(int, int64_t)> callback) {

205 update_impact_callback_ = std::move(callback);

206 }

207

208 private:

209

210 class AssignCallFail : public Decision {

211 public:

212 explicit AssignCallFail(const std::function<void()>& update_impact_closure)

213 : var_(nullptr),

214 value_(0),

215 update_impact_closure_(update_impact_closure) {

216 CHECK(update_impact_closure_ != nullptr);

217 }

218

219

220 AssignCallFail(const AssignCallFail&) = delete;

221 AssignCallFail& operator=(const AssignCallFail&) = delete;

222 ~AssignCallFail() override {}

223 void Apply(Solver* const solver) override {

224 CHECK(var_ != nullptr);

225 var_->SetValue(value_);

226

227 update_impact_closure_();

228 solver->Fail();

229 }

230 void Refute(Solver* const solver) override {}

231

232 IntVar* var_;

233 int64_t value_;

234

235 private:

236 const std::function<void()>& update_impact_closure_;

237 };

238

239 IntVar* var_;

240 std::function<void(int, int64_t)> update_impact_callback_;

241 bool new_start_;

242 IntVarIterator* iterator_;

243 int var_index_;

244 std::vector<int64_t> active_values_;

245 int value_index_;

246 std::function<void()> update_impact_closure_;

247 AssignCallFail updater_;

248};

249

250

251

252

254 public:

255

256 class AssignIntervalCallFail : public Decision {

257 public:

258 explicit AssignIntervalCallFail(

259 const std::function<void()>& update_impact_closure)

260 : var_(nullptr),

261 value_min_(0),

262 value_max_(0),

263 update_impact_closure_(update_impact_closure) {

264 CHECK(update_impact_closure_ != nullptr);

265 }

266

267

268 AssignIntervalCallFail(const AssignIntervalCallFail&) = delete;

269 AssignIntervalCallFail& operator=(const AssignIntervalCallFail&) = delete;

270 ~AssignIntervalCallFail() override {}

271 void Apply(Solver* const solver) override {

272 CHECK(var_ != nullptr);

273 var_->SetRange(value_min_, value_max_);

274

275 update_impact_closure_();

276 solver->Fail();

277 }

278 void Refute(Solver* const solver) override {}

279

280

281 IntVar* var_;

282 int64_t value_min_;

283 int64_t value_max_;

284

285 private:

286 const std::function<void()>& update_impact_closure_;

287 };

288

289

290

291 explicit InitVarImpactsWithSplits(int split_size)

292 : var_(nullptr),

293 update_impact_callback_(nullptr),

294 new_start_(false),

295 var_index_(0),

296 min_value_(0),

297 max_value_(0),

298 split_size_(split_size),

299 split_index_(-1),

300 update_impact_closure_([this]() { UpdateImpacts(); }),

301 updater_(update_impact_closure_) {

302 CHECK(update_impact_closure_ != nullptr);

303 }

304

305 ~InitVarImpactsWithSplits() override {}

306

307 void UpdateImpacts() {

308 for (const int64_t value : InitAndGetValues(iterator_)) {

309 update_impact_callback_(var_index_, value);

310 }

311 }

312

313 void Init(IntVar* const var, IntVarIterator* const iterator, int var_index) {

314 var_ = var;

315 iterator_ = iterator;

316 var_index_ = var_index;

317 new_start_ = true;

318 split_index_ = 0;

319 }

320

321 int64_t IntervalStart(int index) const {

322 const int64_t length = max_value_ - min_value_ + 1;

323 return (min_value_ + length * index / split_size_);

324 }

325

326 Decision* Next(Solver* const solver) override {

327 if (new_start_) {

328 min_value_ = var_->Min();

329 max_value_ = var_->Max();

330 new_start_ = false;

331 }

332 if (split_index_ == split_size_) {

333 return nullptr;

334 }

335 updater_.var_ = var_;

336 updater_.value_min_ = IntervalStart(split_index_);

337 split_index_++;

338 if (split_index_ == split_size_) {

339 updater_.value_max_ = max_value_;

340 } else {

341 updater_.value_max_ = IntervalStart(split_index_) - 1;

342 }

343 return &updater_;

344 }

345

346 void set_update_impact_callback(std::function<void(int, int64_t)> callback) {

347 update_impact_callback_ = std::move(callback);

348 }

349

350 private:

351 IntVar* var_;

352 std::function<void(int, int64_t)> update_impact_callback_;

353 bool new_start_;

354 IntVarIterator* iterator_;

355 int var_index_;

356 int64_t min_value_;

357 int64_t max_value_;

358 const int split_size_;

359 int split_index_;

360 std::function<void()> update_impact_closure_;

361 AssignIntervalCallFail updater_;

362};

363

364

365

366

367

368

370 public:

371 static const int kLogCacheSize;

372 static const double kPerfectImpact;

373 static const double kFailureImpact;

374 static const double kInitFailureImpact;

375 static const int kUninitializedVarIndex;

376

377 ImpactRecorder(Solver* const solver, DomainWatcher* const domain_watcher,

378 const std::vector<IntVar*>& vars,

380 : SearchMonitor(solver),

381 domain_watcher_(domain_watcher),

382 vars_(vars),

383 size_(vars.size()),

384 current_log_space_(0.0),

385 impacts_(size_),

386 original_min_(size_, 0LL),

387 domain_iterators_(new IntVarIterator*[size_]),

388 display_level_(display_level),

389 current_var_(kUninitializedVarIndex),

390 current_value_(0),

391 init_done_(false) {

392 for (int i = 0; i < size_; ++i) {

393 domain_iterators_[i] = vars_[i]->MakeDomainIterator(true);

394 var_map_[vars_[i]] = i;

395 }

396 }

397

398

399 ImpactRecorder(const ImpactRecorder&) = delete;

400 ImpactRecorder& operator=(const ImpactRecorder&) = delete;

401

402 void ApplyDecision(Decision* const d) override {

403 if (!init_done_) {

404 return;

405 }

406 d->Accept(&find_var_);

407 if (find_var_.operation() == FindVar::ASSIGN &&

408 var_map_.contains(find_var_.var())) {

409 current_var_ = var_map_[find_var_.var()];

410 current_value_ = find_var_.value();

411 current_log_space_ = domain_watcher_->LogSearchSpaceSize();

412 } else {

413 current_var_ = kUninitializedVarIndex;

414 current_value_ = 0;

415 }

416 }

417

418 void AfterDecision(Decision* const d, bool apply) override {

419 if (init_done_ && current_var_ != kUninitializedVarIndex) {

420 if (current_log_space_ > 0.0) {

421 const double log_space = domain_watcher_->LogSearchSpaceSize();

422 if (apply) {

423 const double impact = kPerfectImpact - log_space / current_log_space_;

424 UpdateImpact(current_var_, current_value_, impact);

425 current_var_ = kUninitializedVarIndex;

426 current_value_ = 0;

427 }

428 current_log_space_ = log_space;

429 }

430 }

431 }

432

433 void BeginFail() override {

434 if (init_done_ && current_var_ != kUninitializedVarIndex) {

435 UpdateImpact(current_var_, current_value_, kFailureImpact);

436 current_var_ = kUninitializedVarIndex;

437 current_value_ = 0;

438 }

439 }

440

441 void ResetAllImpacts() {

442 for (int i = 0; i < size_; ++i) {

443 original_min_[i] = vars_[i]->Min();

444

445

446

447 impacts_[i].resize(vars_[i]->Max() - vars_[i]->Min() + 1,

448 kInitFailureImpact);

449 }

450

451 for (int i = 0; i < size_; ++i) {

452 for (int j = 0; j < impacts_[i].size(); ++j) {

453 impacts_[i][j] = kInitFailureImpact;

454 }

455 }

456 }

457

458 void UpdateImpact(int var_index, int64_t value, double impact) {

459 const int64_t value_index = value - original_min_[var_index];

460 const double current_impact = impacts_[var_index][value_index];

461 const double new_impact =

462 (current_impact * (absl::GetFlag(FLAGS_cp_impact_divider) - 1) +

463 impact) /

464 absl::GetFlag(FLAGS_cp_impact_divider);

465 impacts_[var_index][value_index] = new_impact;

466 }

467

468 void InitImpact(int var_index, int64_t value) {

469 const double log_space = domain_watcher_->LogSearchSpaceSize();

470 const double impact = kPerfectImpact - log_space / current_log_space_;

471 const int64_t value_index = value - original_min_[var_index];

472 DCHECK_LT(var_index, size_);

473 DCHECK_LT(value_index, impacts_[var_index].size());

474 impacts_[var_index][value_index] = impact;

475 init_count_++;

476 }

477

478 void FirstRun(int64_t splits) {

479 Solver* const s = solver();

480 current_log_space_ = domain_watcher_->LogSearchSpaceSize();

482 LOG(INFO) << " - initial log2(SearchSpace) = " << current_log_space_;

483 }

484 const int64_t init_time = s->wall_time();

485 ResetAllImpacts();

486 int64_t removed_counter = 0;

487 FirstRunVariableContainers* container =

488 s->RevAlloc(new FirstRunVariableContainers(this, splits));

489

490 for (int var_index = 0; var_index < size_; ++var_index) {

491 IntVar* const var = vars_[var_index];

492 if (var->Bound()) {

493 continue;

494 }

495 IntVarIterator* const iterator = domain_iterators_[var_index];

496 DecisionBuilder* init_decision_builder = nullptr;

497 const bool no_split = var->Size() < splits;

498 if (no_split) {

499

500 container->without_split()->set_update_impact_callback(

501 container->update_impact_callback());

502 container->without_split()->Init(var, iterator, var_index);

503 init_decision_builder = container->without_split();

504 } else {

505

506

507 container->with_splits()->set_update_impact_callback(

508 container->update_impact_callback());

509 container->with_splits()->Init(var, iterator, var_index);

510 init_decision_builder = container->with_splits();

511 }

512

513 init_count_ = 0;

514

515 s->Solve(init_decision_builder);

516

517

518

519

520 if (init_count_ != var->Size() && no_split) {

521 container->ClearRemovedValues();

522 for (const int64_t value : InitAndGetValues(iterator)) {

523 const int64_t value_index = value - original_min_[var_index];

524 if (impacts_[var_index][value_index] == kInitFailureImpact) {

525 container->PushBackRemovedValue(value);

526 }

527 }

528 CHECK(container->HasRemovedValues()) << var->DebugString();

529 removed_counter += container->NumRemovedValues();

530 const double old_log = domain_watcher_->Log2(var->Size());

531 var->RemoveValues(container->removed_values());

532 current_log_space_ += domain_watcher_->Log2(var->Size()) - old_log;

533 }

534 }

536 if (removed_counter) {

537 LOG(INFO) << " - init done, time = " << s->wall_time() - init_time

538 << " ms, " << removed_counter

539 << " values removed, log2(SearchSpace) = "

540 << current_log_space_;

541 } else {

542 LOG(INFO) << " - init done, time = " << s->wall_time() - init_time

543 << " ms";

544 }

545 }

546 s->SaveAndSetValue(&init_done_, true);

547 }

548

549

550

551

552 void ScanVarImpacts(int var_index, int64_t* const best_impact_value,

553 double* const var_impacts,

556 CHECK(best_impact_value != nullptr);

557 CHECK(var_impacts != nullptr);

558 double max_impact = -std::numeric_limits<double>::max();

559 double min_impact = std::numeric_limits<double>::max();

560 double sum_var_impact = 0.0;

561 int64_t min_impact_value = -1;

562 int64_t max_impact_value = -1;

563 for (const int64_t value : InitAndGetValues(domain_iterators_[var_index])) {

564 const int64_t value_index = value - original_min_[var_index];

565 DCHECK_LT(var_index, size_);

566 DCHECK_LT(value_index, impacts_[var_index].size());

567 const double current_impact = impacts_[var_index][value_index];

568 sum_var_impact += current_impact;

569 if (current_impact > max_impact) {

570 max_impact = current_impact;

571 max_impact_value = value;

572 }

573 if (current_impact < min_impact) {

574 min_impact = current_impact;

575 min_impact_value = value;

576 }

577 }

578

579 switch (var_select) {

581 *var_impacts = sum_var_impact / vars_[var_index]->Size();

582 break;

583 }

585 *var_impacts = max_impact;

586 break;

587 }

588 default: {

589 *var_impacts = sum_var_impact;

590 break;

591 }

592 }

593

594 switch (value_select) {

596 *best_impact_value = min_impact_value;

597 break;

598 }

600 *best_impact_value = max_impact_value;

601 break;

602 }

603 }

604 }

605

606 std::string DebugString() const override { return "ImpactRecorder"; }

607

608 private:

609

610

611 class FirstRunVariableContainers : public BaseObject {

612 public:

613 FirstRunVariableContainers(ImpactRecorder* impact_recorder, int64_t splits)

614 : update_impact_callback_(

615 [impact_recorder](int var_index, int64_t value) {

616 impact_recorder->InitImpact(var_index, value);

617 }),

618 removed_values_(),

619 without_splits_(),

620 with_splits_(splits) {}

621 std::function<void(int, int64_t)> update_impact_callback() const {

622 return update_impact_callback_;

623 }

624 void PushBackRemovedValue(int64_t value) {

625 removed_values_.push_back(value);

626 }

627 bool HasRemovedValues() const { return !removed_values_.empty(); }

628 void ClearRemovedValues() { removed_values_.clear(); }

629 size_t NumRemovedValues() const { return removed_values_.size(); }

630 const std::vector<int64_t>& removed_values() const {

631 return removed_values_;

632 }

633 InitVarImpacts* without_split() { return &without_splits_; }

634 InitVarImpactsWithSplits* with_splits() { return &with_splits_; }

635

636 std::string DebugString() const override {

637 return "FirstRunVariableContainers";

638 }

639

640 private:

641 const std::function<void(int, int64_t)> update_impact_callback_;

642 std::vector<int64_t> removed_values_;

643 InitVarImpacts without_splits_;

644 InitVarImpactsWithSplits with_splits_;

645 };

646

647 DomainWatcher* const domain_watcher_;

648 std::vector<IntVar*> vars_;

649 const int size_;

650 double current_log_space_;

651

652

653 std::vector<std::vector<double> > impacts_;

654 std::vector<int64_t> original_min_;

655 std::unique_ptr<IntVarIterator*[]> domain_iterators_;

656 int64_t init_count_;

658 int current_var_;

659 int64_t current_value_;

660 FindVar find_var_;

661 absl::flat_hash_map<const IntVar*, int> var_map_;

662 bool init_done_;

663};

664

665const int ImpactRecorder::kLogCacheSize = 1000;

666const double ImpactRecorder::kPerfectImpact = 1.0;

667const double ImpactRecorder::kFailureImpact = 1.0;

668const double ImpactRecorder::kInitFailureImpact = 2.0;

669const int ImpactRecorder::kUninitializedVarIndex = -1;

670

671

672class ChoiceInfo {

673 public:

674 ChoiceInfo() : value_(0), var_(nullptr), left_(false) {}

675

676 ChoiceInfo(IntVar* const var, int64_t value, bool left)

677 : value_(value), var_(var), left_(left) {}

678

679 std::string DebugString() const {

680 return absl::StrFormat("%s %s %d", var_->name(), (left_ ? "==" : "!="),

681 value_);

682 }

683

684 IntVar* var() const { return var_; }

685

686 bool left() const { return left_; }

687

688 int64_t value() const { return value_; }

689

690 void set_left(bool left) { left_ = left; }

691

692 private:

693 int64_t value_;

694 IntVar* var_;

695 bool left_;

696};

697

698

699

700class RunHeuristicsAsDives : public Decision {

701 public:

702 RunHeuristicsAsDives(Solver* const solver, const std::vector<IntVar*>& vars,

704 bool run_all_heuristics, int random_seed,

705 int heuristic_period, int heuristic_num_failures_limit)

706 : heuristic_limit_(nullptr),

707 display_level_(level),

708 run_all_heuristics_(run_all_heuristics),

709 random_(random_seed),

710 heuristic_period_(heuristic_period),

711 heuristic_branch_count_(0),

712 heuristic_runs_(0) {

713 Init(solver, vars, heuristic_num_failures_limit);

714 }

715

717

718 void Apply(Solver* const solver) override {

719 if (!RunAllHeuristics(solver)) {

720 solver->Fail();

721 }

722 }

723

724 void Refute(Solver* const solver) override {}

725

726 bool ShouldRun() {

727 if (heuristic_period_ <= 0) {

728 return false;

729 }

730 ++heuristic_branch_count_;

731 return heuristic_branch_count_ % heuristic_period_ == 0;

732 }

733

734 bool RunOneHeuristic(Solver* const solver, int index) {

735 HeuristicWrapper* const wrapper = heuristics_[index];

736 heuristic_runs_++;

737

738 const bool result =

739 solver->SolveAndCommit(wrapper->phase, heuristic_limit_);

741 LOG(INFO) << " --- solution found by heuristic " << wrapper->name

742 << " --- ";

743 }

744 return result;

745 }

746

747 bool RunAllHeuristics(Solver* const solver) {

748 if (run_all_heuristics_) {

749 for (int index = 0; index < heuristics_.size(); ++index) {

750 for (int run = 0; run < heuristics_[index]->runs; ++run) {

751 if (RunOneHeuristic(solver, index)) {

752 return true;

753 }

754 }

755 }

756 return false;

757 } else {

758 DCHECK_GT(heuristics_.size(), 0);

759 const int index = absl::Uniform<int>(random_, 0, heuristics_.size());

760 return RunOneHeuristic(solver, index);

761 }

762 }

763

764 int Rand32(int size) {

765 DCHECK_GT(size, 0);

766 return absl::Uniform<int>(random_, 0, size);

767 }

768

769 void Init(Solver* const solver, const std::vector<IntVar*>& vars,

770 int heuristic_num_failures_limit) {

771 const int kRunOnce = 1;

772 const int kRunMore = 2;

773 const int kRunALot = 3;

774

775 heuristics_.push_back(new HeuristicWrapper(

778

779 heuristics_.push_back(new HeuristicWrapper(

782

783 heuristics_.push_back(

786 "AssignCenterValueToMinDomainSize", kRunOnce));

787

788 heuristics_.push_back(new HeuristicWrapper(

790 "AssignRandomValueToFirstUnbound", kRunALot));

791

792 heuristics_.push_back(new HeuristicWrapper(

794 "AssignMinValueToRandomVariable", kRunMore));

795

796 heuristics_.push_back(new HeuristicWrapper(

798 "AssignMaxValueToRandomVariable", kRunMore));

799

800 heuristics_.push_back(new HeuristicWrapper(

802 "AssignRandomValueToRandomVariable", kRunMore));

803

804 heuristic_limit_ = solver->MakeFailuresLimit(heuristic_num_failures_limit);

805 }

806

807 int heuristic_runs() const { return heuristic_runs_; }

808

809 private:

810

811

812 struct HeuristicWrapper {

813 HeuristicWrapper(Solver* const solver, const std::vector<IntVar*>& vars,

816 const std::string& heuristic_name, int heuristic_runs)

817 : phase(solver->MakePhase(vars, var_strategy, value_strategy)),

818 name(heuristic_name),

819 runs(heuristic_runs) {}

820

821

822 DecisionBuilder* const phase;

823

824 const std::string name;

825

826

827

828 const int runs;

829 };

830

831 std::vector<HeuristicWrapper*> heuristics_;

832 SearchMonitor* heuristic_limit_;

834 bool run_all_heuristics_;

835 std::mt19937 random_;

836 const int heuristic_period_;

837 int heuristic_branch_count_;

838 int heuristic_runs_;

839};

840

841

842

843

845 public:

846 static const double kSmallSearchSpaceLimit;

847

848 DefaultIntegerSearch(Solver* const solver, const std::vector<IntVar*>& vars,

849 const DefaultPhaseParameters& parameters)

850 : vars_(vars),

851 parameters_(parameters),

852 domain_watcher_(vars, ImpactRecorder::kLogCacheSize),

853 impact_recorder_(solver, &domain_watcher_, vars,

854 parameters.display_level),

855 heuristics_(solver, vars_, parameters_.display_level,

856 parameters_.run_all_heuristics, parameters_.random_seed,

857 parameters_.heuristic_period,

858 parameters_.heuristic_num_failures_limit),

859 find_var_(),

860 last_int_var_(nullptr),

861 last_int_value_(0),

862 last_operation_(FindVar::NONE),

863 last_conflict_count_(0),

864 init_done_(false) {}

865

866 ~DefaultIntegerSearch() override {}

867

868 Decision* Next(Solver* const solver) override {

869 CheckInit(solver);

870

871 if (heuristics_.ShouldRun()) {

872 return &heuristics_;

873 }

874

875 Decision* const decision = parameters_.decision_builder != nullptr

876 ? parameters_.decision_builder->Next(solver)

877 : ImpactNext(solver);

878

879

880 if (decision == nullptr) {

881 ClearLastDecision();

882 return nullptr;

883 }

884

885

886

887

888 decision->Accept(&find_var_);

889 IntVar* const decision_var =

890 find_var_.operation() != FindVar::NONE ? find_var_.var() : nullptr;

891

892

893

894

895

896

897

898

899

900 if (parameters_.use_last_conflict && last_int_var_ != nullptr &&

901 !last_int_var_->Bound() &&

902 (decision_var == nullptr || decision_var != last_int_var_)) {

903 switch (last_operation_) {

904 case FindVar::ASSIGN: {

905 if (last_int_var_->Contains(last_int_value_)) {

906 Decision* const assign =

907 solver->MakeAssignVariableValue(last_int_var_, last_int_value_);

908 ClearLastDecision();

909 last_conflict_count_++;

911 }

912 break;

913 }

914 case FindVar::SPLIT_LOW: {

915 if (last_int_var_->Max() > last_int_value_ &&

916 last_int_var_->Min() <= last_int_value_) {

917 Decision* const split = solver->MakeVariableLessOrEqualValue(

918 last_int_var_, last_int_value_);

919 ClearLastDecision();

920 last_conflict_count_++;

921 return split;

922 }

923 break;

924 }

925 case FindVar::SPLIT_HIGH: {

926 if (last_int_var_->Min() < last_int_value_ &&

927 last_int_var_->Max() >= last_int_value_) {

928 Decision* const split = solver->MakeVariableGreaterOrEqualValue(

929 last_int_var_, last_int_value_);

930 ClearLastDecision();

931 last_conflict_count_++;

932 return split;

933 }

934 break;

935 }

936 default: {

937 break;

938 }

939 }

940 }

941

942 if (parameters_.use_last_conflict) {

943

944 decision->Accept(&find_var_);

945 if (find_var_.operation() != FindVar::NONE) {

946 last_int_var_ = find_var_.var();

947 last_int_value_ = find_var_.value();

948 last_operation_ = find_var_.operation();

949 }

950 }

951

952 return decision;

953 }

954

955 void ClearLastDecision() {

956 last_int_var_ = nullptr;

957 last_int_value_ = 0;

958 last_operation_ = FindVar::NONE;

959 }

960

961 void AppendMonitors(Solver* const solver,

962 std::vector<SearchMonitor*>* const extras) override {

963 CHECK(solver != nullptr);

964 CHECK(extras != nullptr);

965 if (parameters_.decision_builder == nullptr) {

966 extras->push_back(&impact_recorder_);

967 }

968 }

969

970 void Accept(ModelVisitor* const visitor) const override {

973 vars_);

975 }

976

977 std::string DebugString() const override {

978 std::string out = "DefaultIntegerSearch(";

979

980 if (parameters_.decision_builder == nullptr) {

981 out.append("Impact Based Search, ");

982 } else {

983 out.append(parameters_.decision_builder->DebugString());

984 out.append(", ");

985 }

987 out.append(")");

988 return out;

989 }

990

991 std::string StatString() const {

992 const int runs = heuristics_.heuristic_runs();

993 std::string result;

994 if (runs > 0) {

995 if (!result.empty()) {

996 result.append(", ");

997 }

998 if (runs == 1) {

999 result.append("1 heuristic run");

1000 } else {

1001 absl::StrAppendFormat(&result, "%d heuristic runs", runs);

1002 }

1003 }

1004 if (last_conflict_count_ > 0) {

1005 if (!result.empty()) {

1006 result.append(", ");

1007 }

1008 if (last_conflict_count_ == 1) {

1009 result.append("1 last conflict hint");

1010 } else {

1011 absl::StrAppendFormat(&result, "%d last conflict hints",

1012 last_conflict_count_);

1013 }

1014 }

1015 return result;

1016 }

1017

1018 private:

1019 void CheckInit(Solver* const solver) {

1020 if (init_done_) {

1021 return;

1022 }

1023 if (parameters_.decision_builder == nullptr) {

1024

1025 for (int i = 0; i < vars_.size(); ++i) {

1026 if (vars_[i]->Max() - vars_[i]->Min() > 0xFFFFFF) {

1028 LOG(INFO) << "Domains are too large, switching to simple "

1029 << "heuristics";

1030 }

1031 solver->SaveValue(

1032 reinterpret_cast<void**>(&parameters_.decision_builder));

1033 parameters_.decision_builder =

1036 solver->SaveAndSetValue(&init_done_, true);

1037 return;

1038 }

1039 }

1040

1041 if (domain_watcher_.LogSearchSpaceSize() < kSmallSearchSpaceLimit) {

1043 LOG(INFO) << "Search space is too small, switching to simple "

1044 << "heuristics";

1045 }

1046 solver->SaveValue(

1047 reinterpret_cast<void**>(&parameters_.decision_builder));

1048 parameters_.decision_builder = solver->MakePhase(

1050 solver->SaveAndSetValue(&init_done_, true);

1051 return;

1052 }

1053

1055 LOG(INFO) << "Init impact based search phase on " << vars_.size()

1056 << " variables, initialization splits = "

1057 << parameters_.initialization_splits

1058 << ", heuristic_period = " << parameters_.heuristic_period

1059 << ", run_all_heuristics = "

1060 << parameters_.run_all_heuristics;

1061 }

1062

1063 impact_recorder_.FirstRun(parameters_.initialization_splits);

1064 }

1065 if (parameters_.persistent_impact) {

1066 init_done_ = true;

1067 } else {

1068 solver->SaveAndSetValue(&init_done_, true);

1069 }

1070 }

1071

1072

1073

1074

1075

1076 Decision* ImpactNext(Solver* const solver) {

1077 IntVar* var = nullptr;

1078 int64_t value = 0;

1079 double best_var_impact = -std::numeric_limits<double>::max();

1080 for (int i = 0; i < vars_.size(); ++i) {

1081 if (!vars_[i]->Bound()) {

1082 int64_t current_value = 0;

1083 double current_var_impact = 0.0;

1084 impact_recorder_.ScanVarImpacts(i, &current_value, &current_var_impact,

1085 parameters_.var_selection_schema,

1086 parameters_.value_selection_schema);

1087 if (current_var_impact > best_var_impact) {

1088 var = vars_[i];

1089 value = current_value;

1090 best_var_impact = current_var_impact;

1091 }

1092 }

1093 }

1094 if (var == nullptr) {

1095 return nullptr;

1096 } else {

1097 return solver->MakeAssignVariableValue(var, value);

1098 }

1099 }

1100

1101

1102

1103 std::vector<IntVar*> vars_;

1104 DefaultPhaseParameters parameters_;

1105 DomainWatcher domain_watcher_;

1106 ImpactRecorder impact_recorder_;

1107 RunHeuristicsAsDives heuristics_;

1108 FindVar find_var_;

1109 IntVar* last_int_var_;

1110 int64_t last_int_value_;

1111 FindVar::Operation last_operation_;

1112 int last_conflict_count_;

1113 bool init_done_;

1114};

1115

1116const double DefaultIntegerSearch::kSmallSearchSpaceLimit = 10.0;

1117}

1118

1119

1120

1125

1130

1136}