1

2

3

4

5

6

7

8

9

10

11

12

13

14#include <algorithm>

15#include <cstdint>

16#include <functional>

17#include <limits>

18#include <list>

19#include <memory>

20#include <queue>

21#include <random>

22#include <string>

23#include <tuple>

24#include <utility>

25#include <vector>

26

27#include "absl/container/flat_hash_map.h"

28#include "absl/flags/flag.h"

29#include "absl/log/check.h"

30#include "absl/log/log.h"

31#include "absl/log/vlog_is_on.h"

32#include "absl/random/distributions.h"

33#include "absl/strings/str_cat.h"

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

35#include "absl/strings/str_join.h"

36#include "absl/strings/string_view.h"

37#include "absl/time/time.h"

38#include "absl/types/span.h"

50

51ABSL_FLAG(bool, cp_use_sparse_gls_penalties, false,

52 "Use sparse implementation to store Guided Local Search penalties");

54 "Whether search related logging should be "

55 "vlog or info.");

56ABSL_FLAG(int64_t, cp_large_domain_no_splitting_limit, 0xFFFFF,

57 "Size limit to allow holes in variables from the strategy.");

59

60

61

83

85

87

102

115

219

221

223

244

252

257

287

294

296

305

313

314std::string SearchLog::MemoryUsage() {

315 static const int64_t kDisplayThreshold = 2;

316 static const int64_t kKiloByte = 1024;

317 static const int64_t kMegaByte = kKiloByte * kKiloByte;

318 static const int64_t kGigaByte = kMegaByte * kKiloByte;

320 if (memory_usage > kDisplayThreshold * kGigaByte) {

321 return absl::StrFormat("memory used = %.2lf GB",

322 memory_usage * 1.0 / kGigaByte);

323 } else if (memory_usage > kDisplayThreshold * kMegaByte) {

324 return absl::StrFormat("memory used = %.2lf MB",

325 memory_usage * 1.0 / kMegaByte);

326 } else if (memory_usage > kDisplayThreshold * kKiloByte) {

327 return absl::StrFormat("memory used = %2lf KB",

328 memory_usage * 1.0 / kKiloByte);

329 } else {

330 return absl::StrFormat("memory used = %d", memory_usage);

331 }

332}

333

337

341

347

354

362

366

378

394

395

396namespace {

398 public:

399 SearchTrace(Solver* const s, const std::string& prefix)

401 ~SearchTrace() override {}

402

403 void EnterSearch() override {

404 LOG(INFO) << prefix_ << " EnterSearch(" << solver()->SolveDepth() << ")";

405 }

406 void RestartSearch() override {

407 LOG(INFO) << prefix_ << " RestartSearch(" << solver()->SolveDepth() << ")";

408 }

409 void ExitSearch() override {

410 LOG(INFO) << prefix_ << " ExitSearch(" << solver()->SolveDepth() << ")";

411 }

412 void BeginNextDecision(DecisionBuilder* const b) override {

413 LOG(INFO) << prefix_ << " BeginNextDecision(" << b << ") ";

414 }

415 void EndNextDecision(DecisionBuilder* const b, Decision* const d) override {

416 if (d) {

417 LOG(INFO) << prefix_ << " EndNextDecision(" << b << ", " << d << ") ";

418 } else {

419 LOG(INFO) << prefix_ << " EndNextDecision(" << b << ") ";

420 }

421 }

422 void ApplyDecision(Decision* const d) override {

423 LOG(INFO) << prefix_ << " ApplyDecision(" << d << ") ";

424 }

425 void RefuteDecision(Decision* const d) override {

426 LOG(INFO) << prefix_ << " RefuteDecision(" << d << ") ";

427 }

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

429 LOG(INFO) << prefix_ << " AfterDecision(" << d << ", " << apply << ") ";

430 }

431 void BeginFail() override {

432 LOG(INFO) << prefix_ << " BeginFail(" << solver()->SearchDepth() << ")";

433 }

434 void EndFail() override {

435 LOG(INFO) << prefix_ << " EndFail(" << solver()->SearchDepth() << ")";

436 }

437 void BeginInitialPropagation() override {

438 LOG(INFO) << prefix_ << " BeginInitialPropagation()";

439 }

440 void EndInitialPropagation() override {

441 LOG(INFO) << prefix_ << " EndInitialPropagation()";

442 }

443 bool AtSolution() override {

444 LOG(INFO) << prefix_ << " AtSolution()";

445 return false;

446 }

447 bool AcceptSolution() override {

448 LOG(INFO) << prefix_ << " AcceptSolution()";

449 return true;

450 }

451 void NoMoreSolutions() override {

452 LOG(INFO) << prefix_ << " NoMoreSolutions()";

453 }

454

455 std::string DebugString() const override { return "SearchTrace"; }

456

457 private:

458 const std::string prefix_;

459};

460}

461

465

466

467namespace {

469 public:

470 AtSolutionCallback(Solver* const solver, std::function<void()> callback)

472 ~AtSolutionCallback() override {}

473 bool AtSolution() override;

474 void Install() override;

475

476 private:

477 const std::function<void()> callback_;

478};

479

480bool AtSolutionCallback::AtSolution() {

481 callback_();

482 return false;

483}

484

485void AtSolutionCallback::Install() {

486 ListenToEvent(Solver::MonitorEvent::kAtSolution);

487}

488

489}

490

494

495namespace {

496class EnterSearchCallback : public SearchMonitor {

497 public:

498 EnterSearchCallback(Solver* const solver, std::function<void()> callback)

500 ~EnterSearchCallback() override {}

501 void EnterSearch() override;

502 void Install() override;

503

504 private:

505 const std::function<void()> callback_;

506};

507

508void EnterSearchCallback::EnterSearch() { callback_(); }

509

510void EnterSearchCallback::Install() {

511 ListenToEvent(Solver::MonitorEvent::kEnterSearch);

512}

513

514}

515

519

520namespace {

522 public:

523 ExitSearchCallback(Solver* const solver, std::function<void()> callback)

525 ~ExitSearchCallback() override {}

526 void ExitSearch() override;

527 void Install() override;

528

529 private:

530 const std::function<void()> callback_;

531};

532

533void ExitSearchCallback::ExitSearch() { callback_(); }

534

535void ExitSearchCallback::Install() {

536 ListenToEvent(Solver::MonitorEvent::kExitSearch);

537}

538

539}

540

544

545

546

547namespace {

549 public:

550 CompositeDecisionBuilder();

551 explicit CompositeDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);

552 ~CompositeDecisionBuilder() override;

554 void AppendMonitors(Solver* solver,

555 std::vector<SearchMonitor*>* monitors) override;

556 void Accept(ModelVisitor* visitor) const override;

557

558 protected:

559 std::vector<DecisionBuilder*> builders_;

560};

561

562CompositeDecisionBuilder::CompositeDecisionBuilder() {}

563

564CompositeDecisionBuilder::CompositeDecisionBuilder(

565 const std::vector<DecisionBuilder*>& dbs) {

566 for (int i = 0; i < dbs.size(); ++i) {

567 Add(dbs[i]);

568 }

569}

570

571CompositeDecisionBuilder::~CompositeDecisionBuilder() {}

572

573void CompositeDecisionBuilder::Add(DecisionBuilder* const db) {

574 if (db != nullptr) {

575 builders_.push_back(db);

576 }

577}

578

579void CompositeDecisionBuilder::AppendMonitors(

580 Solver* const solver, std::vector<SearchMonitor*>* const monitors) {

581 for (DecisionBuilder* const db : builders_) {

582 db->AppendMonitors(solver, monitors);

583 }

584}

585

586void CompositeDecisionBuilder::Accept(ModelVisitor* const visitor) const {

587 for (DecisionBuilder* const db : builders_) {

588 db->Accept(visitor);

589 }

590}

591}

592

593

594

595namespace {

596class ComposeDecisionBuilder : public CompositeDecisionBuilder {

597 public:

598 ComposeDecisionBuilder();

599 explicit ComposeDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);

600 ~ComposeDecisionBuilder() override;

601 Decision* Next(Solver* s) override;

602 std::string DebugString() const override;

603

604 private:

605 int start_index_;

606};

607

608ComposeDecisionBuilder::ComposeDecisionBuilder() : start_index_(0) {}

609

610ComposeDecisionBuilder::ComposeDecisionBuilder(

611 const std::vector<DecisionBuilder*>& dbs)

612 : CompositeDecisionBuilder(dbs), start_index_(0) {}

613

614ComposeDecisionBuilder::~ComposeDecisionBuilder() {}

615

616Decision* ComposeDecisionBuilder::Next(Solver* const s) {

617 const int size = builders_.size();

618 for (int i = start_index_; i < size; ++i) {

619 Decision* d = builders_[i]->Next(s);

620 if (d != nullptr) {

621 s->SaveAndSetValue(&start_index_, i);

622 return d;

623 }

624 }

625 s->SaveAndSetValue(&start_index_, size);

626 return nullptr;

627}

628

629std::string ComposeDecisionBuilder::DebugString() const {

630 return absl::StrFormat("ComposeDecisionBuilder(%s)",

632}

633}

634

642

652

664

671

672

673

674namespace {

675class ClosureDecision : public Decision {

676 public:

678 : apply_(std::move(apply)), refute_(std::move(refute)) {}

679 ~ClosureDecision() override {}

680

681 void Apply(Solver* const s) override { apply_(s); }

682

683 void Refute(Solver* const s) override { refute_(s); }

684

685 std::string DebugString() const override { return "ClosureDecision"; }

686

687 private:

688 Solver::Action apply_;

689 Solver::Action refute_;

690};

691}

692

696

697

698

699namespace {

700

701class TryDecisionBuilder;

702

703class TryDecision : public Decision {

704 public:

705 explicit TryDecision(TryDecisionBuilder* try_builder);

706 ~TryDecision() override;

707 void Apply(Solver* solver) override;

708 void Refute(Solver* solver) override;

709 std::string DebugString() const override { return "TryDecision"; }

710

711 private:

712 TryDecisionBuilder* const try_builder_;

713};

714

715class TryDecisionBuilder : public CompositeDecisionBuilder {

716 public:

717 TryDecisionBuilder();

718 explicit TryDecisionBuilder(const std::vector<DecisionBuilder*>& dbs);

719 ~TryDecisionBuilder() override;

720 Decision* Next(Solver* solver) override;

721 std::string DebugString() const override;

722 void AdvanceToNextBuilder(Solver* solver);

723

724 private:

725 TryDecision try_decision_;

726 int current_builder_;

727 bool start_new_builder_;

728};

729

730TryDecision::TryDecision(TryDecisionBuilder* const try_builder)

731 : try_builder_(try_builder) {}

732

733TryDecision::~TryDecision() {}

734

735void TryDecision::Apply(Solver* const) {}

736

737void TryDecision::Refute(Solver* const solver) {

738 try_builder_->AdvanceToNextBuilder(solver);

739}

740

741TryDecisionBuilder::TryDecisionBuilder()

742 : CompositeDecisionBuilder(),

743 try_decision_(this),

744 current_builder_(-1),

745 start_new_builder_(true) {}

746

747TryDecisionBuilder::TryDecisionBuilder(const std::vector<DecisionBuilder*>& dbs)

748 : CompositeDecisionBuilder(dbs),

749 try_decision_(this),

750 current_builder_(-1),

751 start_new_builder_(true) {}

752

753TryDecisionBuilder::~TryDecisionBuilder() {}

754

755Decision* TryDecisionBuilder::Next(Solver* const solver) {

756 if (current_builder_ < 0) {

757 solver->SaveAndSetValue(&current_builder_, 0);

758 start_new_builder_ = true;

759 }

760 if (start_new_builder_) {

761 start_new_builder_ = false;

762 return &try_decision_;

763 } else {

764 return builders_[current_builder_]->Next(solver);

765 }

766}

767

768std::string TryDecisionBuilder::DebugString() const {

769 return absl::StrFormat("TryDecisionBuilder(%s)",

771}

772

773void TryDecisionBuilder::AdvanceToNextBuilder(Solver* const solver) {

774 ++current_builder_;

775 start_new_builder_ = true;

776 if (current_builder_ >= builders_.size()) {

777 solver->Fail();

778 }

779}

780

781}

782

790

800

812

816

817

818

819

820

821namespace {

822class BaseVariableAssignmentSelector : public BaseObject {

823 public:

824 BaseVariableAssignmentSelector(Solver* solver,

825 const std::vector<IntVar*>& vars)

826 : solver_(solver),

827 vars_(vars),

828 first_unbound_(0),

829 last_unbound_(vars.size() - 1) {}

830

831 ~BaseVariableAssignmentSelector() override {}

832

833 virtual int64_t SelectValue(const IntVar* v, int64_t id) = 0;

834

835

836 virtual int64_t ChooseVariable() = 0;

837

838 int64_t ChooseVariableWrapper() {

839 int64_t i;

840 for (i = first_unbound_.Value(); i <= last_unbound_.Value(); ++i) {

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

842 break;

843 }

844 }

845 first_unbound_.SetValue(solver_, i);

846 if (i > last_unbound_.Value()) {

847 return -1;

848 }

849 for (i = last_unbound_.Value(); i >= first_unbound_.Value(); --i) {

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

851 break;

852 }

853 }

854 last_unbound_.SetValue(solver_, i);

855 return ChooseVariable();

856 }

857

858 void Accept(ModelVisitor* const visitor) const {

859 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);

860 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

861 vars_);

862 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);

863 }

864

865 const std::vector<IntVar*>& vars() const { return vars_; }

866

867 protected:

868 Solver* const solver_;

869 std::vector<IntVar*> vars_;

870 Rev<int64_t> first_unbound_;

871 Rev<int64_t> last_unbound_;

872};

873

874

875

876int64_t ChooseFirstUnbound(Solver*, const std::vector<IntVar*>& vars,

877 int64_t first_unbound, int64_t last_unbound) {

878 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

879 if (!vars[i]->Bound()) {

880 return i;

881 }

882 }

883 return -1;

884}

885

886

887

888int64_t ChooseMinSizeLowestMin(Solver*, const std::vector<IntVar*>& vars,

889 int64_t first_unbound, int64_t last_unbound) {

890 uint64_t best_size = std::numeric_limits<uint64_t>::max();

891 int64_t best_min = std::numeric_limits<int64_t>::max();

892 int64_t best_index = -1;

893 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

894 IntVar* const var = vars[i];

895 if (!var->Bound()) {

896 if (var->Size() < best_size ||

897 (var->Size() == best_size && var->Min() < best_min)) {

898 best_size = var->Size();

899 best_min = var->Min();

900 best_index = i;

901 }

902 }

903 }

904 return best_index;

905}

906

907

908

909int64_t ChooseMinSizeHighestMin(Solver*, const std::vector<IntVar*>& vars,

910 int64_t first_unbound, int64_t last_unbound) {

911 uint64_t best_size = std::numeric_limits<uint64_t>::max();

912 int64_t best_min = std::numeric_limits<int64_t>::min();

913 int64_t best_index = -1;

914 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

915 IntVar* const var = vars[i];

916 if (!var->Bound()) {

917 if (var->Size() < best_size ||

918 (var->Size() == best_size && var->Min() > best_min)) {

919 best_size = var->Size();

920 best_min = var->Min();

921 best_index = i;

922 }

923 }

924 }

925 return best_index;

926}

927

928

929

930int64_t ChooseMinSizeLowestMax(Solver*, const std::vector<IntVar*>& vars,

931 int64_t first_unbound, int64_t last_unbound) {

932 uint64_t best_size = std::numeric_limits<uint64_t>::max();

933 int64_t best_max = std::numeric_limits<int64_t>::max();

934 int64_t best_index = -1;

935 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

936 IntVar* const var = vars[i];

937 if (!var->Bound()) {

938 if (var->Size() < best_size ||

939 (var->Size() == best_size && var->Max() < best_max)) {

940 best_size = var->Size();

941 best_max = var->Max();

942 best_index = i;

943 }

944 }

945 }

946 return best_index;

947}

948

949

950

951int64_t ChooseMinSizeHighestMax(Solver*, const std::vector<IntVar*>& vars,

952 int64_t first_unbound, int64_t last_unbound) {

953 uint64_t best_size = std::numeric_limits<uint64_t>::max();

954 int64_t best_max = std::numeric_limits<int64_t>::min();

955 int64_t best_index = -1;

956 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

957 IntVar* const var = vars[i];

958 if (!var->Bound()) {

959 if (var->Size() < best_size ||

960 (var->Size() == best_size && var->Max() > best_max)) {

961 best_size = var->Size();

962 best_max = var->Max();

963 best_index = i;

964 }

965 }

966 }

967 return best_index;

968}

969

970

971

972int64_t ChooseLowestMin(Solver*, const std::vector<IntVar*>& vars,

973 int64_t first_unbound, int64_t last_unbound) {

974 int64_t best_min = std::numeric_limits<int64_t>::max();

975 int64_t best_index = -1;

976 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

977 IntVar* const var = vars[i];

978 if (!var->Bound()) {

979 if (var->Min() < best_min) {

980 best_min = var->Min();

981 best_index = i;

982 }

983 }

984 }

985 return best_index;

986}

987

988

989

990int64_t ChooseHighestMax(Solver*, const std::vector<IntVar*>& vars,

991 int64_t first_unbound, int64_t last_unbound) {

992 int64_t best_max = std::numeric_limits<int64_t>::min();

993 int64_t best_index = -1;

994 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

995 IntVar* const var = vars[i];

996 if (!var->Bound()) {

997 if (var->Max() > best_max) {

998 best_max = var->Max();

999 best_index = i;

1000 }

1001 }

1002 }

1003 return best_index;

1004}

1005

1006

1007

1008int64_t ChooseMinSize(Solver*, const std::vector<IntVar*>& vars,

1009 int64_t first_unbound, int64_t last_unbound) {

1010 uint64_t best_size = std::numeric_limits<uint64_t>::max();

1011 int64_t best_index = -1;

1012 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

1013 IntVar* const var = vars[i];

1014 if (!var->Bound()) {

1015 if (var->Size() < best_size) {

1016 best_size = var->Size();

1017 best_index = i;

1018 }

1019 }

1020 }

1021 return best_index;

1022}

1023

1024

1025

1026int64_t ChooseMaxSize(Solver*, const std::vector<IntVar*>& vars,

1027 int64_t first_unbound, int64_t last_unbound) {

1028 uint64_t best_size = 0;

1029 int64_t best_index = -1;

1030 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

1031 IntVar* const var = vars[i];

1032 if (!var->Bound()) {

1033 if (var->Size() > best_size) {

1034 best_size = var->Size();

1035 best_index = i;

1036 }

1037 }

1038 }

1039 return best_index;

1040}

1041

1042

1043

1044class HighestRegretSelectorOnMin : public BaseObject {

1045 public:

1046 explicit HighestRegretSelectorOnMin(const std::vector<IntVar*>& vars)

1047 : iterators_(vars.size()) {

1048 for (int64_t i = 0; i < vars.size(); ++i) {

1049 iterators_[i] = vars[i]->MakeDomainIterator(true);

1050 }

1051 }

1052 ~HighestRegretSelectorOnMin() override {};

1053 int64_t Choose(Solver* s, const std::vector<IntVar*>& vars,

1054 int64_t first_unbound, int64_t last_unbound);

1055 std::string DebugString() const override { return "MaxRegretSelector"; }

1056

1057 int64_t ComputeRegret(IntVar* var, int64_t index) const {

1058 DCHECK(!var->Bound());

1059 const int64_t vmin = var->Min();

1060 IntVarIterator* const iterator = iterators_[index];

1061 iterator->Init();

1062 iterator->Next();

1063 return iterator->Value() - vmin;

1064 }

1065

1066 private:

1067 std::vector<IntVarIterator*> iterators_;

1068};

1069

1070int64_t HighestRegretSelectorOnMin::Choose(Solver* const,

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

1072 int64_t first_unbound,

1073 int64_t last_unbound) {

1074 int64_t best_regret = 0;

1075 int64_t index = -1;

1076 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

1077 IntVar* const var = vars[i];

1078 if (!var->Bound()) {

1079 const int64_t regret = ComputeRegret(var, i);

1080 if (regret > best_regret) {

1081 best_regret = regret;

1082 index = i;

1083 }

1084 }

1085 }

1086 return index;

1087}

1088

1089

1090

1091int64_t ChooseRandom(Solver* solver, const std::vector<IntVar*>& vars,

1092 int64_t first_unbound, int64_t last_unbound) {

1093 const int64_t span = last_unbound - first_unbound + 1;

1094 const int64_t shift = solver->Rand32(span);

1095 for (int64_t i = 0; i < span; ++i) {

1096 const int64_t index = (i + shift) % span + first_unbound;

1097 if (!vars[index]->Bound()) {

1098 return index;

1099 }

1100 }

1101 return -1;

1102}

1103

1104

1105

1106class CheapestVarSelector : public BaseObject {

1107 public:

1108 explicit CheapestVarSelector(std::function<int64_t(int64_t)> var_evaluator)

1109 : var_evaluator_(std::move(var_evaluator)) {}

1110 ~CheapestVarSelector() override {};

1111 int64_t Choose(Solver* s, const std::vector<IntVar*>& vars,

1112 int64_t first_unbound, int64_t last_unbound);

1113 std::string DebugString() const override { return "CheapestVarSelector"; }

1114

1115 private:

1116 std::function<int64_t(int64_t)> var_evaluator_;

1117};

1118

1119int64_t CheapestVarSelector::Choose(Solver* const,

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

1121 int64_t first_unbound,

1122 int64_t last_unbound) {

1123 int64_t best_eval = std::numeric_limits<int64_t>::max();

1124 int64_t index = -1;

1125 for (int64_t i = first_unbound; i <= last_unbound; ++i) {

1126 if (!vars[i]->Bound()) {

1127 const int64_t eval = var_evaluator_(i);

1128 if (eval < best_eval) {

1129 best_eval = eval;

1130 index = i;

1131 }

1132 }

1133 }

1134 return index;

1135}

1136

1137

1138

1139

1140class PathSelector : public BaseObject {

1141 public:

1142 PathSelector() : first_(std::numeric_limits<int64_t>::max()) {}

1143 ~PathSelector() override {};

1144 int64_t Choose(Solver* s, const std::vector<IntVar*>& vars);

1145 std::string DebugString() const override { return "ChooseNextOnPath"; }

1146

1147 private:

1148 bool UpdateIndex(const std::vector<IntVar*>& vars, int64_t* index) const;

1149 bool FindPathStart(const std::vector<IntVar*>& vars, int64_t* index) const;

1150

1151 Rev<int64_t> first_;

1152};

1153

1154int64_t PathSelector::Choose(Solver* const s,

1155 const std::vector<IntVar*>& vars) {

1156 int64_t index = first_.Value();

1157 if (!UpdateIndex(vars, &index)) {

1158 return -1;

1159 }

1160 int64_t count = 0;

1161 while (vars[index]->Bound()) {

1162 index = vars[index]->Value();

1163 if (!UpdateIndex(vars, &index)) {

1164 return -1;

1165 }

1166 ++count;

1167 if (count >= vars.size() &&

1168 !FindPathStart(vars, &index)) {

1169 return -1;

1170 }

1171 }

1172 first_.SetValue(s, index);

1173 return index;

1174}

1175

1176bool PathSelector::UpdateIndex(const std::vector<IntVar*>& vars,

1177 int64_t* index) const {

1178 if (*index >= vars.size()) {

1179 if (!FindPathStart(vars, index)) {

1180 return false;

1181 }

1182 }

1183 return true;

1184}

1185

1186

1187

1188

1189

1190

1191

1192bool PathSelector::FindPathStart(const std::vector<IntVar*>& vars,

1193 int64_t* index) const {

1194

1195 for (int64_t i = vars.size() - 1; i >= 0; --i) {

1196 if (vars[i]->Bound()) {

1197 const int64_t next = vars[i]->Value();

1198 if (next < vars.size() && !vars[next]->Bound()) {

1199 *index = next;

1200 return true;

1201 }

1202 }

1203 }

1204

1205 for (int64_t i = vars.size() - 1; i >= 0; --i) {

1206 if (!vars[i]->Bound()) {

1207 bool has_possible_prev = false;

1208 for (int64_t j = 0; j < vars.size(); ++j) {

1209 if (vars[j]->Contains(i)) {

1210 has_possible_prev = true;

1211 break;

1212 }

1213 }

1214 if (!has_possible_prev) {

1215 *index = i;

1216 return true;

1217 }

1218 }

1219 }

1220

1221 for (int64_t i = 0; i < vars.size(); ++i) {

1222 if (!vars[i]->Bound()) {

1223 *index = i;

1224 return true;

1225 }

1226 }

1227 return false;

1228}

1229

1230

1231

1232int64_t SelectMinValue(const IntVar* v, int64_t) { return v->Min(); }

1233

1234

1235

1236int64_t SelectMaxValue(const IntVar* v, int64_t) { return v->Max(); }

1237

1238

1239

1240int64_t SelectRandomValue(const IntVar* v, int64_t) {

1241 const uint64_t span = v->Max() - v->Min() + 1;

1242 if (span > absl::GetFlag(FLAGS_cp_large_domain_no_splitting_limit)) {

1243

1244 return v->Min();

1245 }

1246 const uint64_t size = v->Size();

1247 Solver* const s = v->solver();

1248 if (size > span / 4) {

1249

1250 for (;;) {

1251 const int64_t value = v->Min() + s->Rand64(span);

1252 if (v->Contains(value)) {

1253 return value;

1254 }

1255 }

1256 } else {

1257 int64_t index = s->Rand64(size);

1258 if (index <= size / 2) {

1259 for (int64_t i = v->Min(); i <= v->Max(); ++i) {

1260 if (v->Contains(i)) {

1261 if (--index == 0) {

1262 return i;

1263 }

1264 }

1265 }

1266 CHECK_LE(index, 0);

1267 } else {

1268 for (int64_t i = v->Max(); i > v->Min(); --i) {

1269 if (v->Contains(i)) {

1270 if (--index == 0) {

1271 return i;

1272 }

1273 }

1274 }

1275 CHECK_LE(index, 0);

1276 }

1277 }

1278 return 0;

1279}

1280

1281

1282

1283int64_t SelectCenterValue(const IntVar* v, int64_t) {

1284 const int64_t vmin = v->Min();

1285 const int64_t vmax = v->Max();

1286 if (vmax - vmin > absl::GetFlag(FLAGS_cp_large_domain_no_splitting_limit)) {

1287

1288 return vmin;

1289 }

1290 const int64_t mid = (vmin + vmax) / 2;

1291 if (v->Contains(mid)) {

1292 return mid;

1293 }

1294 const int64_t diameter = vmax - mid;

1295 for (int64_t i = 1; i <= diameter; ++i) {

1296 if (v->Contains(mid - i)) {

1297 return mid - i;

1298 }

1299 if (v->Contains(mid + i)) {

1300 return mid + i;

1301 }

1302 }

1303 return 0;

1304}

1305

1306

1307

1308int64_t SelectSplitValue(const IntVar* v, int64_t) {

1309 const int64_t vmin = v->Min();

1310 const int64_t vmax = v->Max();

1311 const uint64_t delta = vmax - vmin;

1312 const int64_t mid = vmin + delta / 2;

1313 return mid;

1314}

1315

1316

1317

1318class CheapestValueSelector : public BaseObject {

1319 public:

1320 CheapestValueSelector(std::function<int64_t(int64_t, int64_t)> eval,

1321 std::function<int64_t(int64_t)> tie_breaker)

1322 : eval_(std::move(eval)), tie_breaker_(std::move(tie_breaker)) {}

1323 ~CheapestValueSelector() override {}

1324 int64_t Select(const IntVar* v, int64_t id);

1325 std::string DebugString() const override { return "CheapestValue"; }

1326

1327 private:

1328 std::function<int64_t(int64_t, int64_t)> eval_;

1329 std::function<int64_t(int64_t)> tie_breaker_;

1330 std::vector<int64_t> cache_;

1331};

1332

1333int64_t CheapestValueSelector::Select(const IntVar* v, int64_t id) {

1334 cache_.clear();

1335 int64_t best = std::numeric_limits<int64_t>::max();

1336 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(false));

1337 for (const int64_t i : InitAndGetValues(it.get())) {

1338 int64_t eval = eval_(id, i);

1339 if (eval < best) {

1340 best = eval;

1341 cache_.clear();

1342 cache_.push_back(i);

1343 } else if (eval == best) {

1344 cache_.push_back(i);

1345 }

1346 }

1347 DCHECK_GT(cache_.size(), 0);

1348 if (tie_breaker_ == nullptr || cache_.size() == 1) {

1349 return cache_.back();

1350 } else {

1351 return cache_[tie_breaker_(cache_.size())];

1352 }

1353}

1354

1355

1356

1357

1358

1359

1360

1361

1362

1363class BestValueByComparisonSelector : public BaseObject {

1364 public:

1365 explicit BestValueByComparisonSelector(

1366 Solver::VariableValueComparator comparator)

1367 : comparator_(std::move(comparator)) {}

1368 ~BestValueByComparisonSelector() override {}

1369 int64_t Select(const IntVar* v, int64_t id);

1370 std::string DebugString() const override {

1371 return "BestValueByComparisonSelector";

1372 }

1373

1374 private:

1375 Solver::VariableValueComparator comparator_;

1376};

1377

1378int64_t BestValueByComparisonSelector::Select(const IntVar* v, int64_t id) {

1379 std::unique_ptr<IntVarIterator> it(v->MakeDomainIterator(false));

1380 it->Init();

1381 DCHECK(it->Ok());

1382 int64_t best_value = it->Value();

1383 for (it->Next(); it->Ok(); it->Next()) {

1384 const int64_t candidate_value = it->Value();

1385 if (comparator_(id, candidate_value, best_value)) {

1386 best_value = candidate_value;

1387 }

1388 }

1389 return best_value;

1390}

1391

1392

1393

1394class VariableAssignmentSelector : public BaseVariableAssignmentSelector {

1395 public:

1396 VariableAssignmentSelector(Solver* solver, const std::vector<IntVar*>& vars,

1397 Solver::VariableIndexSelector var_selector,

1398 Solver::VariableValueSelector value_selector,

1399 const std::string& name)

1400 : BaseVariableAssignmentSelector(solver, vars),

1401 var_selector_(std::move(var_selector)),

1402 value_selector_(std::move(value_selector)),

1403 name_(name) {}

1404 ~VariableAssignmentSelector() override {}

1405 int64_t SelectValue(const IntVar* var, int64_t id) override {

1406 return value_selector_(var, id);

1407 }

1408 int64_t ChooseVariable() override {

1409 return var_selector_(solver_, vars_, first_unbound_.Value(),

1410 last_unbound_.Value());

1411 }

1412 std::string DebugString() const override;

1413

1414 private:

1415 Solver::VariableIndexSelector var_selector_;

1416 Solver::VariableValueSelector value_selector_;

1417 const std::string name_;

1418};

1419

1420std::string VariableAssignmentSelector::DebugString() const {

1421 return absl::StrFormat("%s(%s)", name_, JoinDebugStringPtr(vars_, ", "));

1422}

1423

1424

1425

1426class BaseEvaluatorSelector : public BaseVariableAssignmentSelector {

1427 public:

1428 BaseEvaluatorSelector(Solver* solver, const std::vector<IntVar*>& vars,

1429 std::function<int64_t(int64_t, int64_t)> evaluator);

1430 ~BaseEvaluatorSelector() override {}

1431

1432 protected:

1433 struct Element {

1434 Element() : var(0), value(0) {}

1435 Element(int64_t i, int64_t j) : var(i), value(j) {}

1436 int64_t var;

1437 int64_t value;

1438 };

1439

1440 std::string DebugStringInternal(absl::string_view name) const {

1441 return absl::StrFormat("%s(%s)", name, JoinDebugStringPtr(vars_, ", "));

1442 }

1443

1444 std::function<int64_t(int64_t, int64_t)> evaluator_;

1445};

1446

1447BaseEvaluatorSelector::BaseEvaluatorSelector(

1448 Solver* solver, const std::vector<IntVar*>& vars,

1449 std::function<int64_t(int64_t, int64_t)> evaluator)

1450 : BaseVariableAssignmentSelector(solver, vars),

1451 evaluator_(std::move(evaluator)) {}

1452

1453

1454

1455class DynamicEvaluatorSelector : public BaseEvaluatorSelector {

1456 public:

1457 DynamicEvaluatorSelector(Solver* solver, const std::vector<IntVar*>& vars,

1458 std::function<int64_t(int64_t, int64_t)> evaluator,

1459 std::function<int64_t(int64_t)> tie_breaker);

1460 ~DynamicEvaluatorSelector() override {}

1461 int64_t SelectValue(const IntVar* var, int64_t id) override;

1462 int64_t ChooseVariable() override;

1463 std::string DebugString() const override;

1464

1465 private:

1466 int64_t first_;

1467 std::function<int64_t(int64_t)> tie_breaker_;

1468 std::vector<Element> cache_;

1469};

1470

1471DynamicEvaluatorSelector::DynamicEvaluatorSelector(

1472 Solver* solver, const std::vector<IntVar*>& vars,

1473 std::function<int64_t(int64_t, int64_t)> evaluator,

1474 std::function<int64_t(int64_t)> tie_breaker)

1475 : BaseEvaluatorSelector(solver, vars, std::move(evaluator)),

1476 first_(-1),

1477 tie_breaker_(std::move(tie_breaker)) {}

1478

1479int64_t DynamicEvaluatorSelector::SelectValue(const IntVar*, int64_t) {

1480 return cache_[first_].value;

1481}

1482

1483int64_t DynamicEvaluatorSelector::ChooseVariable() {

1484 int64_t best_evaluation = std::numeric_limits<int64_t>::max();

1485 cache_.clear();

1486 for (int64_t i = 0; i < vars_.size(); ++i) {

1487 const IntVar* const var = vars_[i];

1488 if (!var->Bound()) {

1489 std::unique_ptr<IntVarIterator> it(var->MakeDomainIterator(false));

1490 for (const int64_t j : InitAndGetValues(it.get())) {

1491 const int64_t value = evaluator_(i, j);

1492 if (value < best_evaluation) {

1493 best_evaluation = value;

1494 cache_.clear();

1495 cache_.push_back(Element(i, j));

1496 } else if (value == best_evaluation && tie_breaker_) {

1497 cache_.push_back(Element(i, j));

1498 }

1499 }

1500 }

1501 }

1502

1503 if (cache_.empty()) {

1504 return -1;

1505 }

1506

1507 if (tie_breaker_ == nullptr || cache_.size() == 1) {

1508 first_ = 0;

1509 return cache_.front().var;

1510 } else {

1511 first_ = tie_breaker_(cache_.size());

1512 return cache_[first_].var;

1513 }

1514}

1515

1516std::string DynamicEvaluatorSelector::DebugString() const {

1517 return DebugStringInternal("AssignVariablesOnDynamicEvaluator");

1518}

1519

1520

1521

1522class StaticEvaluatorSelector : public BaseEvaluatorSelector {

1523 public:

1524 StaticEvaluatorSelector(

1525 Solver* solver, const std::vector<IntVar*>& vars,

1526 const std::function<int64_t(int64_t, int64_t)>& evaluator);

1527 ~StaticEvaluatorSelector() override {}

1528 int64_t SelectValue(const IntVar* var, int64_t id) override;

1529 int64_t ChooseVariable() override;

1530 std::string DebugString() const override;

1531

1532 private:

1533 class Compare {

1534 public:

1535 explicit Compare(std::function<int64_t(int64_t, int64_t)> evaluator)

1536 : evaluator_(std::move(evaluator)) {}

1537 bool operator()(const Element& lhs, const Element& rhs) const {

1538 const int64_t value_lhs = Value(lhs);

1539 const int64_t value_rhs = Value(rhs);

1540 return value_lhs < value_rhs ||

1541 (value_lhs == value_rhs &&

1542 (lhs.var < rhs.var ||

1543 (lhs.var == rhs.var && lhs.value < rhs.value)));

1544 }

1545 int64_t Value(const Element& element) const {

1546 return evaluator_(element.var, element.value);

1547 }

1548

1549 private:

1550 std::function<int64_t(int64_t, int64_t)> evaluator_;

1551 };

1552

1553 Compare comp_;

1554 std::vector<Element> elements_;

1555 int64_t first_;

1556};

1557

1558StaticEvaluatorSelector::StaticEvaluatorSelector(

1559 Solver* solver, const std::vector<IntVar*>& vars,

1560 const std::function<int64_t(int64_t, int64_t)>& evaluator)

1561 : BaseEvaluatorSelector(solver, vars, evaluator),

1562 comp_(evaluator),

1563 first_(-1) {}

1564

1565int64_t StaticEvaluatorSelector::SelectValue(const IntVar*, int64_t) {

1566 return elements_[first_].value;

1567}

1568

1569int64_t StaticEvaluatorSelector::ChooseVariable() {

1570 if (first_ == -1) {

1571

1572 int64_t element_size = 0;

1573 for (int64_t i = 0; i < vars_.size(); ++i) {

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

1575 element_size += vars_[i]->Size();

1576 }

1577 }

1578 elements_.resize(element_size);

1579 int count = 0;

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

1581 const IntVar* const var = vars_[i];

1582 if (!var->Bound()) {

1583 std::unique_ptr<IntVarIterator> it(var->MakeDomainIterator(false));

1584 for (const int64_t value : InitAndGetValues(it.get())) {

1585 elements_[count++] = Element(i, value);

1586 }

1587 }

1588 }

1589

1590 std::sort(elements_.begin(), elements_.end(), comp_);

1591 solver_->SaveAndSetValue<int64_t>(&first_, 0);

1592 }

1593 for (int64_t i = first_; i < elements_.size(); ++i) {

1594 const Element& element = elements_[i];

1595 IntVar* const var = vars_[element.var];

1596 if (!var->Bound() && var->Contains(element.value)) {

1597 solver_->SaveAndSetValue(&first_, i);

1598 return element.var;

1599 }

1600 }

1601 solver_->SaveAndSetValue(&first_, static_cast<int64_t>(elements_.size()));

1602 return -1;

1603}

1604

1605std::string StaticEvaluatorSelector::DebugString() const {

1606 return DebugStringInternal("AssignVariablesOnStaticEvaluator");

1607}

1608

1609

1610

1611class AssignOneVariableValue : public Decision {

1612 public:

1613 AssignOneVariableValue(IntVar* v, int64_t val);

1614 ~AssignOneVariableValue() override {}

1615 void Apply(Solver* s) override;

1616 void Refute(Solver* s) override;

1617 std::string DebugString() const override;

1618 void Accept(DecisionVisitor* const visitor) const override {

1619 visitor->VisitSetVariableValue(var_, value_);

1620 }

1621

1622 private:

1623 IntVar* const var_;

1624 int64_t value_;

1625};

1626

1627AssignOneVariableValue::AssignOneVariableValue(IntVar* const v, int64_t val)

1628 : var_(v), value_(val) {}

1629

1630std::string AssignOneVariableValue::DebugString() const {

1631 return absl::StrFormat("[%s == %d] or [%s != %d]", var_->DebugString(),

1633}

1634

1635void AssignOneVariableValue::Apply(Solver* const) { var_->SetValue(value_); }

1636

1637void AssignOneVariableValue::Refute(Solver* const) {

1639}

1640}

1641

1645

1646

1647

1648namespace {

1649class AssignOneVariableValueOrFail : public Decision {

1650 public:

1651 AssignOneVariableValueOrFail(IntVar* v, int64_t value);

1652 ~AssignOneVariableValueOrFail() override {}

1653 void Apply(Solver* s) override;

1654 void Refute(Solver* s) override;

1655 std::string DebugString() const override;

1656 void Accept(DecisionVisitor* const visitor) const override {

1657 visitor->VisitSetVariableValue(var_, value_);

1658 }

1659

1660 private:

1661 IntVar* const var_;

1662 const int64_t value_;

1663};

1664

1665AssignOneVariableValueOrFail::AssignOneVariableValueOrFail(IntVar* const v,

1666 int64_t value)

1667 : var_(v), value_(value) {}

1668

1669std::string AssignOneVariableValueOrFail::DebugString() const {

1670 return absl::StrFormat("[%s == %d] or fail", var_->DebugString(), value_);

1671}

1672

1673void AssignOneVariableValueOrFail::Apply(Solver* const) {

1675}

1676

1677void AssignOneVariableValueOrFail::Refute(Solver* const s) { s->Fail(); }

1678}

1679

1684

1685

1686

1687namespace {

1688class AssignOneVariableValueDoNothing : public Decision {

1689 public:

1690 AssignOneVariableValueDoNothing(IntVar* const v, int64_t value)

1691 : var_(v), value_(value) {}

1692 ~AssignOneVariableValueDoNothing() override {}

1693 void Apply(Solver* const) override { var_->SetValue(value_); }

1694 void Refute(Solver* const) override {}

1695 std::string DebugString() const override {

1696 return absl::StrFormat("[%s == %d] or []", var_->DebugString(), value_);

1697 }

1698 void Accept(DecisionVisitor* const visitor) const override {

1699 visitor->VisitSetVariableValue(var_, value_);

1700 }

1701

1702 private:

1703 IntVar* const var_;

1704 const int64_t value_;

1705};

1706

1707}

1708

1713

1714

1715

1716namespace {

1717class SplitOneVariable : public Decision {

1718 public:

1719 SplitOneVariable(IntVar* v, int64_t val, bool start_with_lower_half);

1720 ~SplitOneVariable() override {}

1721 void Apply(Solver* s) override;

1722 void Refute(Solver* s) override;

1723 std::string DebugString() const override;

1724 void Accept(DecisionVisitor* const visitor) const override {

1725 visitor->VisitSplitVariableDomain(var_, value_, start_with_lower_half_);

1726 }

1727

1728 private:

1729 IntVar* const var_;

1730 const int64_t value_;

1731 const bool start_with_lower_half_;

1732};

1733

1734SplitOneVariable::SplitOneVariable(IntVar* const v, int64_t val,

1735 bool start_with_lower_half)

1736 : var_(v), value_(val), start_with_lower_half_(start_with_lower_half) {}

1737

1738std::string SplitOneVariable::DebugString() const {

1739 if (start_with_lower_half_) {

1740 return absl::StrFormat("[%s <= %d]", var_->DebugString(), value_);

1741 } else {

1742 return absl::StrFormat("[%s >= %d]", var_->DebugString(), value_);

1743 }

1744}

1745

1746void SplitOneVariable::Apply(Solver* const) {

1747 if (start_with_lower_half_) {

1748 var_->SetMax(value_);

1749 } else {

1750 var_->SetMin(value_ + 1);

1751 }

1752}

1753

1754void SplitOneVariable::Refute(Solver* const) {

1755 if (start_with_lower_half_) {

1756 var_->SetMin(value_ + 1);

1757 } else {

1758 var_->SetMax(value_);

1759 }

1760}

1761}

1762

1767

1772

1777

1778

1779

1780namespace {

1781class AssignVariablesValues : public Decision {

1782 public:

1783

1784

1785

1786

1787 enum class RefutationBehavior { kForbidAssignment, kDoNothing, kFail };

1788 AssignVariablesValues(

1789 const std::vector<IntVar*>& vars, const std::vector<int64_t>& values,

1790 RefutationBehavior refutation = RefutationBehavior::kForbidAssignment);

1791 ~AssignVariablesValues() override {}

1792 void Apply(Solver* s) override;

1793 void Refute(Solver* s) override;

1794 std::string DebugString() const override;

1795 void Accept(DecisionVisitor* const visitor) const override {

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

1797 visitor->VisitSetVariableValue(vars_[i], values_[i]);

1798 }

1799 }

1800

1801 virtual void Accept(ModelVisitor* const visitor) const {

1802 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);

1803 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

1804 vars_);

1805 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);

1806 }

1807

1808 private:

1809 const std::vector<IntVar*> vars_;

1810 const std::vector<int64_t> values_;

1811 const RefutationBehavior refutation_;

1812};

1813

1814AssignVariablesValues::AssignVariablesValues(const std::vector<IntVar*>& vars,

1815 const std::vector<int64_t>& values,

1816 RefutationBehavior refutation)

1817 : vars_(vars), values_(values), refutation_(refutation) {}

1818

1819std::string AssignVariablesValues::DebugString() const {

1820 std::string out;

1821 if (vars_.empty()) out += "do nothing";

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

1823 absl::StrAppendFormat(&out, "[%s == %d]", vars_[i]->DebugString(),

1824 values_[i]);

1825 }

1826 switch (refutation_) {

1827 case RefutationBehavior::kForbidAssignment:

1828 out += " or forbid assignment";

1829 break;

1830 case RefutationBehavior::kDoNothing:

1831 out += " or do nothing";

1832 break;

1833 case RefutationBehavior::kFail:

1834 out += " or fail";

1835 break;

1836 }

1837 return out;

1838}

1839

1840void AssignVariablesValues::Apply(Solver* const) {

1841 if (vars_.empty()) return;

1842 vars_[0]->FreezeQueue();

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

1844 vars_[i]->SetValue(values_[i]);

1845 }

1846 vars_[0]->UnfreezeQueue();

1847}

1848

1849void AssignVariablesValues::Refute(Solver* const s) {

1850 switch (refutation_) {

1851 case RefutationBehavior::kForbidAssignment: {

1852 std::vector<IntVar*> terms;

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

1854 IntVar* term = s->MakeBoolVar();

1855 s->AddConstraint(s->MakeIsDifferentCstCt(vars_[i], values_[i], term));

1856 terms.push_back(term);

1857 }

1858 s->AddConstraint(s->MakeSumGreaterOrEqual(terms, 1));

1859 break;

1860 }

1861 case RefutationBehavior::kDoNothing: {

1862 break;

1863 }

1864 case RefutationBehavior::kFail: {

1865 s->Fail();

1866 break;

1867 }

1868 }

1869}

1870}

1871

1879

1886

1893

1894

1895

1896namespace {

1898 public:

1899 enum Mode {

1900 ASSIGN,

1901 SPLIT_LOWER,

1902 SPLIT_UPPER,

1903 };

1904

1905 BaseAssignVariables(BaseVariableAssignmentSelector* const selector, Mode mode)

1906 : selector_(selector), mode_(mode) {}

1907

1908 ~BaseAssignVariables() override;

1909 Decision* Next(Solver* s) override;

1910 std::string DebugString() const override;

1911 static BaseAssignVariables* MakePhase(

1912 Solver* s, const std::vector<IntVar*>& vars,

1913 Solver::VariableIndexSelector var_selector,

1914 Solver::VariableValueSelector value_selector,

1915 const std::string& value_selector_name, BaseAssignVariables::Mode mode);

1916

1917 static Solver::VariableIndexSelector MakeVariableSelector(

1918 Solver* const s, const std::vector<IntVar*>& vars,

1919 Solver::IntVarStrategy str) {

1920 switch (str) {

1921 case Solver::INT_VAR_DEFAULT:

1922 case Solver::INT_VAR_SIMPLE:

1923 case Solver::CHOOSE_FIRST_UNBOUND:

1924 return ChooseFirstUnbound;

1925 case Solver::CHOOSE_RANDOM:

1926 return ChooseRandom;

1927 case Solver::CHOOSE_MIN_SIZE_LOWEST_MIN:

1928 return ChooseMinSizeLowestMin;

1929 case Solver::CHOOSE_MIN_SIZE_HIGHEST_MIN:

1930 return ChooseMinSizeHighestMin;

1931 case Solver::CHOOSE_MIN_SIZE_LOWEST_MAX:

1932 return ChooseMinSizeLowestMax;

1933 case Solver::CHOOSE_MIN_SIZE_HIGHEST_MAX:

1934 return ChooseMinSizeHighestMax;

1935 case Solver::CHOOSE_LOWEST_MIN:

1936 return ChooseLowestMin;

1937 case Solver::CHOOSE_HIGHEST_MAX:

1938 return ChooseHighestMax;

1939 case Solver::CHOOSE_MIN_SIZE:

1940 return ChooseMinSize;

1941 case Solver::CHOOSE_MAX_SIZE:

1942 return ChooseMaxSize;

1943 case Solver::CHOOSE_MAX_REGRET_ON_MIN: {

1944 HighestRegretSelectorOnMin* const selector =

1945 s->RevAlloc(new HighestRegretSelectorOnMin(vars));

1946 return [selector](Solver* solver, const std::vector<IntVar*>& vars,

1947 int first_unbound, int last_unbound) {

1948 return selector->Choose(solver, vars, first_unbound, last_unbound);

1949 };

1950 }

1951 case Solver::CHOOSE_PATH: {

1952 PathSelector* const selector = s->RevAlloc(new PathSelector());

1953 return [selector](Solver* solver, const std::vector<IntVar*>& vars, int,

1954 int) { return selector->Choose(solver, vars); };

1955 }

1956 default:

1957 LOG(FATAL) << "Unknown int var strategy " << str;

1958 return nullptr;

1959 }

1960 }

1961

1962 static Solver::VariableValueSelector MakeValueSelector(

1963 Solver* const, Solver::IntValueStrategy val_str) {

1964 switch (val_str) {

1965 case Solver::INT_VALUE_DEFAULT:

1966 case Solver::INT_VALUE_SIMPLE:

1967 case Solver::ASSIGN_MIN_VALUE:

1968 return SelectMinValue;

1969 case Solver::ASSIGN_MAX_VALUE:

1970 return SelectMaxValue;

1971 case Solver::ASSIGN_RANDOM_VALUE:

1972 return SelectRandomValue;

1973 case Solver::ASSIGN_CENTER_VALUE:

1974 return SelectCenterValue;

1975 case Solver::SPLIT_LOWER_HALF:

1976 return SelectSplitValue;

1977 case Solver::SPLIT_UPPER_HALF:

1978 return SelectSplitValue;

1979 default:

1980 LOG(FATAL) << "Unknown int value strategy " << val_str;

1981 return nullptr;

1982 }

1983 }

1984

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

1986 selector_->Accept(visitor);

1987 }

1988

1989 protected:

1990 BaseVariableAssignmentSelector* const selector_;

1991 const Mode mode_;

1992};

1993

1994BaseAssignVariables::~BaseAssignVariables() {}

1995

1996Decision* BaseAssignVariables::Next(Solver* const s) {

1997 const std::vector<IntVar*>& vars = selector_->vars();

1998 int id = selector_->ChooseVariableWrapper();

1999 if (id >= 0 && id < vars.size()) {

2000 IntVar* const var = vars[id];

2001 const int64_t value = selector_->SelectValue(var, id);

2002 switch (mode_) {

2003 case ASSIGN:

2004 return s->RevAlloc(new AssignOneVariableValue(var, value));

2005 case SPLIT_LOWER:

2006 return s->RevAlloc(new SplitOneVariable(var, value, true));

2007 case SPLIT_UPPER:

2008 return s->RevAlloc(new SplitOneVariable(var, value, false));

2009 }

2010 }

2011 return nullptr;

2012}

2013

2014std::string BaseAssignVariables::DebugString() const {

2015 return selector_->DebugString();

2016}

2017

2018BaseAssignVariables* BaseAssignVariables::MakePhase(

2019 Solver* const s, const std::vector<IntVar*>& vars,

2022 const std::string& value_selector_name, BaseAssignVariables::Mode mode) {

2023 BaseVariableAssignmentSelector* const selector =

2024 s->RevAlloc(new VariableAssignmentSelector(

2025 s, vars, std::move(var_selector), std::move(value_selector),

2026 value_selector_name));

2027 return s->RevAlloc(new BaseAssignVariables(selector, mode));

2028}

2029

2031 switch (var_str) {

2035 return "ChooseFirstUnbound";

2037 return "ChooseRandom";

2039 return "ChooseMinSizeLowestMin";

2041 return "ChooseMinSizeHighestMin";

2043 return "ChooseMinSizeLowestMax";

2045 return "ChooseMinSizeHighestMax";

2047 return "ChooseLowestMin";

2049 return "ChooseHighestMax";

2051 return "ChooseMinSize";

2053 return "ChooseMaxSize;";

2055 return "HighestRegretSelectorOnMin";

2057 return "PathSelector";

2058 default:

2059 LOG(FATAL) << "Unknown int var strategy " << var_str;

2060 return "";

2061 }

2062}

2063

2065 switch (val_str) {

2069 return "SelectMinValue";

2071 return "SelectMaxValue";

2073 return "SelectRandomValue";

2075 return "SelectCenterValue";

2077 return "SelectSplitValue";

2079 return "SelectSplitValue";

2080 default:

2081 LOG(FATAL) << "Unknown int value strategy " << val_str;

2082 return "";

2083 }

2084}

2085

2088 return ChooseVariableName(var_str) + "_" + SelectValueName(val_str);

2089}

2090}

2091

2099

2108

2119

2131

2141

2152

2171

2189

2204

2224

2240

2261

2267

2289

2290

2291

2292namespace {

2293class AssignVariablesFromAssignment : public DecisionBuilder {

2294 public:

2295 AssignVariablesFromAssignment(const Assignment* const assignment,

2297 const std::vector<IntVar*>& vars)

2298 : assignment_(assignment), db_(db), vars_(vars), iter_(0) {}

2299

2300 ~AssignVariablesFromAssignment() override {}

2301

2302 Decision* Next(Solver* const s) override {

2303 if (iter_ < vars_.size()) {

2304 IntVar* const var = vars_[iter_++];

2305 return s->RevAlloc(

2306 new AssignOneVariableValue(var, assignment_->Value(var)));

2307 } else {

2308 return db_->Next(s);

2309 }

2310 }

2311

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

2313 visitor->BeginVisitExtension(ModelVisitor::kVariableGroupExtension);

2314 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,

2315 vars_);

2316 visitor->EndVisitExtension(ModelVisitor::kVariableGroupExtension);

2317 }

2318

2319 private:

2320 const Assignment* const assignment_;

2321 DecisionBuilder* const db_;

2322 const std::vector<IntVar*> vars_;

2323 int iter_;

2324};

2325}

2326

2332

2333

2334

2335

2336

2342

2345

2347

2351

2356

2374

2378

2384

2390

2396

2402

2408

2414

2420

2426

2431

2435

2442

2464

2470

2475

2480

2484

2486

2488

2493

2498

2503

2508

2513

2517

2521

2525

2529

2533

2538

2543

2548

2549namespace {

2550

2551

2552

2554 public:

2556 explicit FirstSolutionCollector(Solver* s);

2557 ~FirstSolutionCollector() override;

2558 void EnterSearch() override;

2559 bool AtSolution() override;

2560 void Install() override;

2561 std::string DebugString() const override;

2562

2563 private:

2564 bool done_;

2565};

2566

2567FirstSolutionCollector::FirstSolutionCollector(Solver* const s,

2568 const Assignment* const a)

2570

2571FirstSolutionCollector::FirstSolutionCollector(Solver* const s)

2573

2574FirstSolutionCollector::~FirstSolutionCollector() {}

2575

2576void FirstSolutionCollector::EnterSearch() {

2577 SolutionCollector::EnterSearch();

2578 done_ = false;

2579}

2580

2581bool FirstSolutionCollector::AtSolution() {

2582 if (!done_) {

2583 PushSolution();

2584 done_ = true;

2585 }

2586 return false;

2587}

2588

2589void FirstSolutionCollector::Install() {

2590 SolutionCollector::Install();

2591 ListenToEvent(Solver::MonitorEvent::kAtSolution);

2592}

2593

2594std::string FirstSolutionCollector::DebugString() const {

2595 if (prototype_ == nullptr) {

2596 return "FirstSolutionCollector()";

2597 } else {

2598 return "FirstSolutionCollector(" + prototype_->DebugString() + ")";

2599 }

2600}

2601}

2602

2607

2611

2612

2613

2614

2615namespace {

2617 public:

2619 explicit LastSolutionCollector(Solver* s);

2620 ~LastSolutionCollector() override;

2621 bool AtSolution() override;

2622 void Install() override;

2623 std::string DebugString() const override;

2624};

2625

2626LastSolutionCollector::LastSolutionCollector(Solver* const s,

2627 const Assignment* const a)

2628 : SolutionCollector(s, a) {}

2629

2630LastSolutionCollector::LastSolutionCollector(Solver* const s)

2632

2633LastSolutionCollector::~LastSolutionCollector() {}

2634

2635bool LastSolutionCollector::AtSolution() {

2636 PopSolution();

2637 PushSolution();

2638 return true;

2639}

2640

2641void LastSolutionCollector::Install() {

2642 SolutionCollector::Install();

2643 ListenToEvent(Solver::MonitorEvent::kAtSolution);

2644}

2645

2646std::string LastSolutionCollector::DebugString() const {

2647 if (prototype_ == nullptr) {

2648 return "LastSolutionCollector()";

2649 } else {

2650 return "LastSolutionCollector(" + prototype_->DebugString() + ")";

2651 }

2652}

2653}

2654

2659

2663

2664

2665

2666namespace {

2668 public:

2669 BestValueSolutionCollector(Solver* solver, const Assignment* assignment,

2670 std::vector<bool> maximize);

2671 BestValueSolutionCollector(Solver* solver, std::vector<bool> maximize);

2672 ~BestValueSolutionCollector() override {}

2673 void EnterSearch() override;

2674 bool AtSolution() override;

2675 void Install() override;

2676 std::string DebugString() const override;

2677

2678 private:

2679 void ResetBestObjective() {

2680 for (int i = 0; i < maximize_.size(); ++i) {

2681 best_[i] = maximize_[i] ? std::numeric_limits<int64_t>::min()

2682 : std::numeric_limits<int64_t>::max();

2683 }

2684 }

2685

2686 const std::vector<bool> maximize_;

2687 std::vector<int64_t> best_;

2688};

2689

2690BestValueSolutionCollector::BestValueSolutionCollector(

2691 Solver* solver, const Assignment* assignment, std::vector<bool> maximize)

2692 : SolutionCollector(solver, assignment),

2693 maximize_(std::move(maximize)),

2694 best_(maximize_.size()) {

2695 ResetBestObjective();

2696}

2697

2698BestValueSolutionCollector::BestValueSolutionCollector(

2699 Solver* solver, std::vector<bool> maximize)

2701 maximize_(std::move(maximize)),

2702 best_(maximize_.size()) {

2703 ResetBestObjective();

2704}

2705

2706void BestValueSolutionCollector::EnterSearch() {

2707 SolutionCollector::EnterSearch();

2708 ResetBestObjective();

2709}

2710

2711bool BestValueSolutionCollector::AtSolution() {

2712 if (prototype_ != nullptr && prototype_->HasObjective()) {

2713 const int size = std::min(prototype_->NumObjectives(),

2714 static_cast<int>(maximize_.size()));

2715

2716

2717 bool is_improvement = false;

2718 for (int i = 0; i < size; ++i) {

2719 const IntVar* objective = prototype_->ObjectiveFromIndex(i);

2720 const int64_t objective_value =

2721 maximize_[i] ? CapOpp(objective->Max()) : objective->Min();

2722 if (objective_value < best_[i]) {

2723 is_improvement = true;

2724 break;

2725 } else if (objective_value > best_[i]) {

2726 break;

2727 }

2728 }

2729 if (solution_count() == 0 || is_improvement) {

2730 PopSolution();

2731 PushSolution();

2732 for (int i = 0; i < size; ++i) {

2733 best_[i] = maximize_[i]

2734 ? CapOpp(prototype_->ObjectiveFromIndex(i)->Max())

2735 : prototype_->ObjectiveFromIndex(i)->Min();

2736 }

2737 }

2738 }

2739 return true;

2740}

2741

2742void BestValueSolutionCollector::Install() {

2743 SolutionCollector::Install();

2744 ListenToEvent(Solver::MonitorEvent::kAtSolution);

2745}

2746

2747std::string BestValueSolutionCollector::DebugString() const {

2748 if (prototype_ == nullptr) {

2749 return "BestValueSolutionCollector()";

2750 } else {

2751 return "BestValueSolutionCollector(" + prototype_->DebugString() + ")";

2752 }

2753}

2754}

2755

2760

2766

2770

2775

2776

2777

2778namespace {

2780 public:

2781 NBestValueSolutionCollector(Solver* solver, const Assignment* assignment,

2782 int solution_count, std::vector<bool> maximize);

2783 NBestValueSolutionCollector(Solver* solver, int solution_count,

2784 std::vector<bool> maximize);

2785 ~NBestValueSolutionCollector() override { Clear(); }

2786 void EnterSearch() override;

2787 void ExitSearch() override;

2788 bool AtSolution() override;

2789 void Install() override;

2790 std::string DebugString() const override;

2791

2792 private:

2793 void Clear();

2794

2795 const std::vector<bool> maximize_;

2796 std::priority_queue<std::pair<std::vector<int64_t>, SolutionData>>

2797 solutions_pq_;

2798 const int solution_count_;

2799};

2800

2801NBestValueSolutionCollector::NBestValueSolutionCollector(

2802 Solver* solver, const Assignment* assignment, int solution_count,

2803 std::vector<bool> maximize)

2804 : SolutionCollector(solver, assignment),

2805 maximize_(std::move(maximize)),

2806 solution_count_(solution_count) {}

2807

2808NBestValueSolutionCollector::NBestValueSolutionCollector(

2809 Solver* solver, int solution_count, std::vector<bool> maximize)

2811 maximize_(std::move(maximize)),

2812 solution_count_(solution_count) {}

2813

2814void NBestValueSolutionCollector::EnterSearch() {

2815 SolutionCollector::EnterSearch();

2816

2817

2818 if (solution_count_ > 1) {

2819 solver()->SetUseFastLocalSearch(false);

2820 }

2821 Clear();

2822}

2823

2824void NBestValueSolutionCollector::ExitSearch() {

2825 while (!solutions_pq_.empty()) {

2826 Push(solutions_pq_.top().second);

2827 solutions_pq_.pop();

2828 }

2829}

2830

2831bool NBestValueSolutionCollector::AtSolution() {

2832 if (prototype_ != nullptr && prototype_->HasObjective()) {

2833 const int size = std::min(prototype_->NumObjectives(),

2834 static_cast<int>(maximize_.size()));

2835 std::vector<int64_t> objective_values(size);

2836 for (int i = 0; i < size; ++i) {

2837 objective_values[i] =

2838 maximize_[i] ? CapOpp(prototype_->ObjectiveFromIndex(i)->Max())

2839 : prototype_->ObjectiveFromIndex(i)->Min();

2840 }

2841 if (solutions_pq_.size() < solution_count_) {

2842 solutions_pq_.push(

2843 {std::move(objective_values), BuildSolutionDataForCurrentState()});

2844 } else if (!solutions_pq_.empty()) {

2845 const auto& [top_obj_value, top_sol_data] = solutions_pq_.top();

2846 if (std::lexicographical_compare(

2847 objective_values.begin(), objective_values.end(),

2848 top_obj_value.begin(), top_obj_value.end())) {

2849 FreeSolution(top_sol_data.solution);

2850 solutions_pq_.pop();

2851 solutions_pq_.push(

2852 {std::move(objective_values), BuildSolutionDataForCurrentState()});

2853 }

2854 }

2855 }

2856 return true;

2857}

2858

2859void NBestValueSolutionCollector::Install() {

2860 SolutionCollector::Install();

2861 ListenToEvent(Solver::MonitorEvent::kExitSearch);

2862 ListenToEvent(Solver::MonitorEvent::kAtSolution);

2863}

2864

2865std::string NBestValueSolutionCollector::DebugString() const {

2866 if (prototype_ == nullptr) {

2867 return "NBestValueSolutionCollector()";

2868 } else {

2869 return "NBestValueSolutionCollector(" + prototype_->DebugString() + ")";

2870 }

2871}

2872

2873void NBestValueSolutionCollector::Clear() {

2874 while (!solutions_pq_.empty()) {

2875 delete solutions_pq_.top().second.solution;

2876 solutions_pq_.pop();

2877 }

2878}

2879

2880}

2881

2890

2899

2910

2919

2920

2921

2922namespace {

2924 public:

2926 explicit AllSolutionCollector(Solver* s);

2927 ~AllSolutionCollector() override;

2928 bool AtSolution() override;

2929 void Install() override;

2930 std::string DebugString() const override;

2931};

2932

2933AllSolutionCollector::AllSolutionCollector(Solver* const s,

2934 const Assignment* const a)

2935 : SolutionCollector(s, a) {}

2936

2937AllSolutionCollector::AllSolutionCollector(Solver* const s)

2939

2940AllSolutionCollector::~AllSolutionCollector() {}

2941

2942bool AllSolutionCollector::AtSolution() {

2943 PushSolution();

2944 return true;

2945}

2946

2947void AllSolutionCollector::Install() {

2948 SolutionCollector::Install();

2949 ListenToEvent(Solver::MonitorEvent::kAtSolution);

2950}

2951

2952std::string AllSolutionCollector::DebugString() const {

2953 if (prototype_ == nullptr) {

2954 return "AllSolutionCollector()";

2955 } else {

2956 return "AllSolutionCollector(" + prototype_->DebugString() + ")";

2957 }

2958}

2959}

2960

2965

2969

2970

2971

3069

3076

3110

3117

3134

3174

3184

3197

3202

3206

3212

3219

3220namespace {

3221class ApplyBoundDecisionBuilder : public DecisionBuilder {

3222 public:

3223 explicit ApplyBoundDecisionBuilder(OptimizeVar* optimize_var)

3224 : optimize_var_(optimize_var) {}

3225 ~ApplyBoundDecisionBuilder() override = default;

3226 Decision* Next(Solver*) override {

3227 optimize_var_->ApplyBound();

3228 return nullptr;

3229 }

3230

3231 private:

3232 OptimizeVar* optimize_var_;

3233};

3234}

3235

3249

3269

3274

3276

3287

3291

3295

3300

3307

3308namespace {

3309class WeightedOptimizeVar : public OptimizeVar {

3310 public:

3311 WeightedOptimizeVar(Solver* solver, bool maximize,

3312 const std::vector<IntVar*>& sub_objectives,

3313 const std::vector<int64_t>& weights, int64_t step)

3315 solver->MakeScalProd(sub_objectives, weights)->Var(), step),

3316 sub_objectives_(sub_objectives),

3317 weights_(weights) {

3318 CHECK_EQ(sub_objectives.size(), weights.size());

3319 }

3320

3321 ~WeightedOptimizeVar() override {}

3322 std::string Name() const override;

3323

3324 private:

3325 const std::vector<IntVar*> sub_objectives_;

3326 const std::vector<int64_t> weights_;

3327};

3328

3329std::string WeightedOptimizeVar::Name() const { return "weighted objective"; }

3330}

3331

3338

3345

3352

3359

3365

3371

3372

3373

3374namespace {

3376 public:

3377 Metaheuristic(Solver* solver, const std::vector<bool>& maximize,

3378 std::vector<IntVar*> objectives, std::vector<int64_t> steps);

3379 ~Metaheuristic() override {}

3380

3381 void EnterSearch() override;

3382 void RefuteDecision(Decision* d) override;

3383};

3384

3385Metaheuristic::Metaheuristic(Solver* solver, const std::vector<bool>& maximize,

3386 std::vector<IntVar*> objectives,

3387 std::vector<int64_t> steps)

3388 : ObjectiveMonitor(solver, maximize, std::move(objectives),

3389 std::move(steps)) {}

3390

3391void Metaheuristic::EnterSearch() {

3392 ObjectiveMonitor::EnterSearch();

3393

3394

3395 solver()->SetUseFastLocalSearch(false);

3396}

3397

3398void Metaheuristic::RefuteDecision(Decision*) {

3399 for (int i = 0; i < Size(); ++i) {

3400 const int64_t objective_value = MinimizationVar(i)->Min();

3401 if (objective_value > BestInternalValue(i)) break;

3402 if (objective_value <= CapSub(BestInternalValue(i), Step(i))) return;

3403 }

3404 solver()->Fail();

3405}

3406

3407

3408

3409class TabuSearch : public Metaheuristic {

3410 public:

3411 TabuSearch(Solver* solver, const std::vector<bool>& maximize,

3412 std::vector<IntVar*> objectives, std::vector<int64_t> steps,

3413 const std::vector<IntVar*>& vars, int64_t keep_tenure,

3414 int64_t forbid_tenure, double tabu_factor);

3415 ~TabuSearch() override {}

3416 void EnterSearch() override;

3417 void ApplyDecision(Decision* d) override;

3418 bool AtSolution() override;

3419 bool AcceptSolution() override;

3420 bool AtLocalOptimum() override;

3421 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;

3423 void BeginNextDecision(DecisionBuilder* const) override {

3424 if (stop_search_) solver()->Fail();

3425 }

3426 void RefuteDecision(Decision* const d) override {

3427 Metaheuristic::RefuteDecision(d);

3428 if (stop_search_) solver()->Fail();

3429 }

3430 std::string DebugString() const override { return "Tabu Search"; }

3431

3432 protected:

3433 struct VarValue {

3434 int var_index;

3435 int64_t value;

3436 int64_t stamp;

3437 };

3438 typedef std::list<VarValue> TabuList;

3439

3440 virtual std::vector<IntVar*> CreateTabuVars();

3441 const TabuList& forbid_tabu_list() { return forbid_tabu_list_; }

3442 IntVar* vars(int index) const { return vars_[index]; }

3443

3444 private:

3445 void AgeList(int64_t tenure, TabuList* list);

3446 void AgeLists();

3447 int64_t TabuLimit() const {

3448 return (synced_keep_tabu_list_.size() + synced_forbid_tabu_list_.size()) *

3449 tabu_factor_;

3450 }

3451

3452 const std::vector<IntVar*> vars_;

3453 Assignment::IntContainer assignment_container_;

3454 bool has_stored_assignment_ = false;

3455 std::vector<int64_t> last_values_;

3456 TabuList keep_tabu_list_;

3457 TabuList synced_keep_tabu_list_;

3458 int64_t keep_tenure_;

3459 TabuList forbid_tabu_list_;

3460 TabuList synced_forbid_tabu_list_;

3461 int64_t forbid_tenure_;

3462 double tabu_factor_;

3463 int64_t stamp_;

3464 int64_t solution_count_ = 0;

3465 bool stop_search_ = false;

3466 std::vector<int64_t> delta_values_;

3467 SparseBitset<> delta_vars_;

3468 std::vector<int> var_index_to_index_;

3469};

3470

3471TabuSearch::TabuSearch(Solver* solver, const std::vector<bool>& maximize,

3472 std::vector<IntVar*> objectives,

3473 std::vector<int64_t> steps,

3474 const std::vector<IntVar*>& vars, int64_t keep_tenure,

3475 int64_t forbid_tenure, double tabu_factor)

3476 : Metaheuristic(solver, maximize, std::move(objectives), std::move(steps)),

3477 vars_(vars),

3478 last_values_(Size(), std::numeric_limits<int64_t>::max()),

3479 keep_tenure_(keep_tenure),

3480 forbid_tenure_(forbid_tenure),

3481 tabu_factor_(tabu_factor),

3482 stamp_(0),

3483 delta_values_(vars.size(), 0),

3484 delta_vars_(vars.size()) {

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

3486 assignment_container_.FastAdd(vars_[index]);

3487 DCHECK_EQ(vars_[index], assignment_container_.Element(index).Var());

3488 const int var_index = vars_[index]->index();

3489 if (var_index >= var_index_to_index_.size()) {

3490 var_index_to_index_.resize(var_index + 1, -1);

3491 }

3492 var_index_to_index_[var_index] = index;

3493 }

3494}

3495

3496void TabuSearch::EnterSearch() {

3497 Metaheuristic::EnterSearch();

3498 solver()->SetUseFastLocalSearch(true);

3499 stamp_ = 0;

3500 has_stored_assignment_ = false;

3501 solution_count_ = 0;

3502 stop_search_ = false;

3503}

3504

3505void TabuSearch::ApplyDecision(Decision* const d) {

3506 Solver* const s = solver();

3507 if (d == s->balancing_decision()) {

3508 return;

3509 }

3510

3511 synced_keep_tabu_list_ = keep_tabu_list_;

3512 synced_forbid_tabu_list_ = forbid_tabu_list_;

3513 Constraint* tabu_ct = nullptr;

3514 {

3515

3516

3517 const std::vector<IntVar*> tabu_vars = CreateTabuVars();

3518 if (!tabu_vars.empty()) {

3519 IntVar* tabu_var = s->MakeIsGreaterOrEqualCstVar(

3520 s->MakeSum(tabu_vars)->Var(), TabuLimit());

3521

3522

3523 IntVar* aspiration = MakeMinimizationVarsLessOrEqualWithStepsStatus(

3524 [this](int i) { return BestInternalValue(i); });

3525 tabu_ct = s->MakeSumGreaterOrEqual({aspiration, tabu_var}, int64_t{1});

3526 }

3527 }

3528 if (tabu_ct != nullptr) s->AddConstraint(tabu_ct);

3529

3530

3531 if (CurrentInternalValuesAreConstraining()) {

3532 MakeMinimizationVarsLessOrEqualWithSteps(

3533 [this](int i) { return CurrentInternalValue(i); });

3534 }

3535}

3536

3537bool TabuSearch::AcceptSolution() {

3538

3539 if (found_initial_solution_) {

3540 for (int i = 0; i < Size(); ++i) {

3541 if (last_values_[i] != MinimizationVar(i)->Min()) {

3542 return true;

3543 }

3544 }

3545 return false;

3546 }

3547 return true;

3548}

3549

3550std::vector<IntVar*> TabuSearch::CreateTabuVars() {

3551 Solver* const s = solver();

3552

3553

3554

3555

3556

3557

3558

3559 std::vector<IntVar*> tabu_vars;

3560 for (const auto [var_index, value, unused_stamp] : keep_tabu_list_) {

3561 tabu_vars.push_back(s->MakeIsEqualCstVar(vars(var_index), value));

3562 }

3563 for (const auto [var_index, value, unused_stamp] : forbid_tabu_list_) {

3564 tabu_vars.push_back(s->MakeIsDifferentCstVar(vars(var_index), value));

3565 }

3566 return tabu_vars;

3567}

3568

3569bool TabuSearch::AtSolution() {

3570 ++solution_count_;

3571 if (!ObjectiveMonitor::AtSolution()) {

3572 return false;

3573 }

3574 for (int i = 0; i < Size(); ++i) {

3575 last_values_[i] = CurrentInternalValue(i);

3576 }

3577

3578

3579

3580 if (0 != stamp_ && has_stored_assignment_) {

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

3582 IntVar* var = vars(index);

3583 const int64_t old_value = assignment_container_.Element(index).Value();

3584 const int64_t new_value = var->Value();

3585 if (old_value != new_value) {

3586 if (keep_tenure_ > 0) {

3587 keep_tabu_list_.push_front({index, new_value, stamp_});

3588 }

3589 if (forbid_tenure_ > 0) {

3590 forbid_tabu_list_.push_front({index, old_value, stamp_});

3591 }

3592 }

3593 }

3594 }

3595 assignment_container_.Store();

3596 has_stored_assignment_ = true;

3597

3598 return true;

3599}

3600

3601bool TabuSearch::AtLocalOptimum() {

3602 solver()->SetUseFastLocalSearch(false);

3603

3604

3605 if (stamp_ > 0 && solution_count_ == 0 && keep_tabu_list_.empty() &&

3606 forbid_tabu_list_.empty()) {

3607 stop_search_ = true;

3608 }

3609 solution_count_ = 0;

3610 AgeLists();

3611 for (int i = 0; i < Size(); ++i) {

3612 SetCurrentInternalValue(i, std::numeric_limits<int64_t>::max());

3613 }

3614 return found_initial_solution_;

3615}

3616

3617bool TabuSearch::AcceptDelta(Assignment* delta, Assignment* deltadelta) {

3618 if (delta == nullptr) return true;

3619 if (!Metaheuristic::AcceptDelta(delta, deltadelta)) return false;

3620 if (synced_keep_tabu_list_.empty() && synced_forbid_tabu_list_.empty()) {

3621 return true;

3622 }

3623 const Assignment::IntContainer& delta_container = delta->IntVarContainer();

3624

3625 for (const IntVarElement& element : delta_container.elements()) {

3626 if (!element.Bound()) return true;

3627 }

3629 for (const IntVarElement& element : delta_container.elements()) {

3630 const int var_index = element.Var()->index();

3631 if (var_index >= var_index_to_index_.size()) continue;

3632 const int index = var_index_to_index_[var_index];

3633 if (index == -1) continue;

3634 delta_values_[index] = element.Value();

3635 delta_vars_.Set(index);

3636 }

3637 int num_respected = 0;

3638 auto get_value = [this](int var_index) {

3639 return delta_vars_[var_index]

3640 ? delta_values_[var_index]

3641 : assignment_container_.Element(var_index).Value();

3642 };

3643 const int64_t tabu_limit = TabuLimit();

3644 for (const auto [var_index, value, unused_stamp] : synced_keep_tabu_list_) {

3645 if (get_value(var_index) == value) {

3646 if (++num_respected >= tabu_limit) return true;

3647 }

3648 }

3649 for (const auto [var_index, value, unused_stamp] : synced_forbid_tabu_list_) {

3650 if (get_value(var_index) != value) {

3651 if (++num_respected >= tabu_limit) return true;

3652 }

3653 }

3654 if (num_respected >= tabu_limit) return true;

3655

3656

3657 if (Size() == 1) {

3658 if (Maximize(0)) {

3659 delta->SetObjectiveMinFromIndex(0, CapAdd(BestInternalValue(0), Step(0)));

3660 } else {

3661 delta->SetObjectiveMaxFromIndex(0, CapSub(BestInternalValue(0), Step(0)));

3662 }

3663 } else {

3664 for (int i = 0; i < Size(); ++i) {

3665 if (Maximize(i)) {

3666 delta->SetObjectiveMinFromIndex(i, BestInternalValue(i));

3667 } else {

3668 delta->SetObjectiveMaxFromIndex(i, BestInternalValue(i));

3669 }

3670 }

3671 }

3672

3673 return true;

3674}

3675

3676void TabuSearch::AcceptNeighbor() {

3677 if (0 != stamp_) {

3678 AgeLists();

3679 }

3680}

3681

3682void TabuSearch::AgeList(int64_t tenure, TabuList* list) {

3683 while (!list->empty() && list->back().stamp < stamp_ - tenure) {

3684 list->pop_back();

3685 }

3686}

3687

3688void TabuSearch::AgeLists() {

3689 AgeList(keep_tenure_, &keep_tabu_list_);

3690 AgeList(forbid_tenure_, &forbid_tabu_list_);

3691 ++stamp_;

3692}

3693

3694class GenericTabuSearch : public TabuSearch {

3695 public:

3696 GenericTabuSearch(Solver* solver, bool maximize, IntVar* objective,

3697 int64_t step, const std::vector<IntVar*>& vars,

3698 int64_t forbid_tenure)

3699 : TabuSearch(solver, {maximize}, {objective}, {step}, vars, 0,

3700 forbid_tenure, 1) {}

3701 std::string DebugString() const override { return "Generic Tabu Search"; }

3702

3703 protected:

3704 std::vector<IntVar*> CreateTabuVars() override;

3705};

3706

3707std::vector<IntVar*> GenericTabuSearch::CreateTabuVars() {

3708 Solver* const s = solver();

3709

3710

3711

3712 std::vector<IntVar*> forbid_values;

3713 for (const auto [var_index, value, unused_stamp] : forbid_tabu_list()) {

3714 forbid_values.push_back(s->MakeIsDifferentCstVar(vars(var_index), value));

3715 }

3716 std::vector<IntVar*> tabu_vars;

3717 if (!forbid_values.empty()) {

3718 tabu_vars.push_back(s->MakeIsGreaterCstVar(s->MakeSum(forbid_values), 0));

3719 }

3720 return tabu_vars;

3721}

3722

3723}

3724

3734

3743

3750

3751

3752

3753namespace {

3754class SimulatedAnnealing : public Metaheuristic {

3755 public:

3756 SimulatedAnnealing(Solver* solver, const std::vector<bool>& maximize,

3757 std::vector<IntVar*> objectives,

3758 std::vector<int64_t> steps,

3759 std::vector<int64_t> initial_temperatures);

3760 ~SimulatedAnnealing() override {}

3761 void ApplyDecision(Decision* d) override;

3762 bool AtLocalOptimum() override;

3763 void AcceptNeighbor() override;

3764 std::string DebugString() const override { return "Simulated Annealing"; }

3765

3766 private:

3767 double Temperature(int index) const {

3768 return iteration_ > 0

3769 ? (1.0 * temperature0_[index]) / iteration_

3770 : 0;

3771 }

3772

3773 const std::vector<int64_t> temperature0_;

3774 int64_t iteration_;

3775 std::mt19937 rand_;

3776};

3777

3778SimulatedAnnealing::SimulatedAnnealing(

3779 Solver* solver, const std::vector<bool>& maximize,

3780 std::vector<IntVar*> objectives, std::vector<int64_t> steps,

3781 std::vector<int64_t> initial_temperatures)

3782 : Metaheuristic(solver, maximize, std::move(objectives), std::move(steps)),

3783 temperature0_(std::move(initial_temperatures)),

3784 iteration_(0),

3786

3787

3788

3789

3790

3791

3792

3793

3794

3795

3796

3797

3798

3799

3800void SimulatedAnnealing::ApplyDecision(Decision* const d) {

3801 Solver* const s = solver();

3802 if (d == s->balancing_decision()) {

3803 return;

3804 }

3805 if (CurrentInternalValuesAreConstraining()) {

3806 MakeMinimizationVarsLessOrEqualWithSteps([this](int i) {

3807 const double rand_double = absl::Uniform<double>(rand_, 0.0, 1.0);

3808#if defined(_MSC_VER) || defined(__ANDROID__)

3809 const double rand_log2_double = log(rand_double) / log(2.0L);

3810#else

3811 const double rand_log2_double = log2(rand_double);

3812#endif

3813 const int64_t energy_bound = Temperature(i) * rand_log2_double;

3814

3815

3816 return CapSub(CurrentInternalValue(i), energy_bound);

3817 });

3818 }

3819}

3820

3821bool SimulatedAnnealing::AtLocalOptimum() {

3822 for (int i = 0; i < Size(); ++i) {

3823 SetCurrentInternalValue(i, std::numeric_limits<int64_t>::max());

3824 }

3825 ++iteration_;

3826 if (!found_initial_solution_) return false;

3827 for (int i = 0; i < Size(); ++i) {

3828 if (Temperature(i) <= 0) return false;

3829 }

3830 return true;

3831}

3832

3833void SimulatedAnnealing::AcceptNeighbor() {

3834 if (iteration_ > 0) {

3835 ++iteration_;

3836 }

3837}

3838}

3839

3846

3854

3855

3856

3857namespace {

3858

3859

3860

3861

3862class GuidedLocalSearchPenaltiesTable {

3863 public:

3864 struct VarValue {

3865 int64_t var;

3866 int64_t value;

3867 };

3868 explicit GuidedLocalSearchPenaltiesTable(int num_vars);

3869 bool HasPenalties() const { return has_values_; }

3870 void IncrementPenalty(const VarValue& var_value);

3871 int64_t GetPenalty(const VarValue& var_value) const;

3872 void Reset();

3873

3874 private:

3875 std::vector<std::vector<int64_t>> penalties_;

3876 bool has_values_;

3877};

3878

3879GuidedLocalSearchPenaltiesTable::GuidedLocalSearchPenaltiesTable(int num_vars)

3880 : penalties_(num_vars), has_values_(false) {}

3881

3882void GuidedLocalSearchPenaltiesTable::IncrementPenalty(

3883 const VarValue& var_value) {

3884 std::vector<int64_t>& var_penalties = penalties_[var_value.var];

3885 const int64_t value = var_value.value;

3886 if (value >= var_penalties.size()) {

3887 var_penalties.resize(value + 1, 0);

3888 }

3889 ++var_penalties[value];

3890 has_values_ = true;

3891}

3892

3893void GuidedLocalSearchPenaltiesTable::Reset() {

3894 has_values_ = false;

3895 for (int i = 0; i < penalties_.size(); ++i) {

3896 penalties_[i].clear();

3897 }

3898}

3899

3900int64_t GuidedLocalSearchPenaltiesTable::GetPenalty(

3901 const VarValue& var_value) const {

3902 const std::vector<int64_t>& var_penalties = penalties_[var_value.var];

3903 const int64_t value = var_value.value;

3904 return (value >= var_penalties.size()) ? 0 : var_penalties[value];

3905}

3906

3907

3908class GuidedLocalSearchPenaltiesMap {

3909 public:

3910 struct VarValue {

3911 int64_t var;

3912 int64_t value;

3913

3914 friend bool operator==(const VarValue& lhs, const VarValue& rhs) {

3915 return lhs.var == rhs.var && lhs.value == rhs.value;

3916 }

3917 template <typename H>

3918 friend H AbslHashValue(H h, const VarValue& var_value) {

3919 return H::combine(std::move(h), var_value.var, var_value.value);

3920 }

3921 };

3922 explicit GuidedLocalSearchPenaltiesMap(int num_vars);

3923 bool HasPenalties() const { return (!penalties_.empty()); }

3924 void IncrementPenalty(const VarValue& var_value);

3925 int64_t GetPenalty(const VarValue& var_value) const;

3926 void Reset();

3927

3928 private:

3929 Bitmap penalized_;

3930 absl::flat_hash_map<VarValue, int64_t> penalties_;

3931};

3932

3933GuidedLocalSearchPenaltiesMap::GuidedLocalSearchPenaltiesMap(int num_vars)

3934 : penalized_(num_vars, false) {}

3935

3936void GuidedLocalSearchPenaltiesMap::IncrementPenalty(

3937 const VarValue& var_value) {

3938 ++penalties_[var_value];

3939 penalized_.Set(var_value.var, true);

3940}

3941

3942void GuidedLocalSearchPenaltiesMap::Reset() {

3943 penalties_.clear();

3944 penalized_.Clear();

3945}

3946

3947int64_t GuidedLocalSearchPenaltiesMap::GetPenalty(

3948 const VarValue& var_value) const {

3949 return (penalized_.Get(var_value.var))

3951 : 0;

3952}

3953

3954template <typename P>

3955class GuidedLocalSearch : public Metaheuristic {

3956 public:

3957 GuidedLocalSearch(

3958 Solver* solver, IntVar* objective, bool maximize, int64_t step,

3959 const std::vector<IntVar*>& vars, double penalty_factor,

3960 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

3961 get_equivalent_pairs,

3962 bool reset_penalties_on_new_best_solution);

3963 ~GuidedLocalSearch() override {}

3964 bool AcceptDelta(Assignment* delta, Assignment* deltadelta) override;

3965 void ApplyDecision(Decision* d) override;

3966 bool AtSolution() override;

3967 void EnterSearch() override;

3968 bool AtLocalOptimum() override;

3969 virtual int64_t AssignmentElementPenalty(int index) const = 0;

3970 virtual int64_t AssignmentPenalty(int64_t var, int64_t value) const = 0;

3971 virtual int64_t Evaluate(const Assignment* delta, int64_t current_penalty,

3972 bool incremental) = 0;

3973 virtual IntExpr* MakeElementPenalty(int index) = 0;

3974 std::string DebugString() const override { return "Guided Local Search"; }

3975

3976 protected:

3977

3978

3979

3980 template <typename T, typename IndexType = int64_t>

3981 class DirtyArray {

3982 public:

3983 explicit DirtyArray(IndexType size)

3984 : base_data_(size), modified_data_(size), touched_(size) {}

3985

3986

3987 void Set(IndexType i, const T& value) {

3988 modified_data_[i] = value;

3989 touched_.Set(i);

3990 }

3991

3992 void SetAll(const T& value) {

3993 for (IndexType i = 0; i < modified_data_.size(); ++i) {

3994 Set(i, value);

3995 }

3996 }

3997

3998 T Get(IndexType i) const { return modified_data_[i]; }

3999

4000

4001 void Commit() {

4002 for (const IndexType index : touched_.PositionsSetAtLeastOnce()) {

4003 base_data_[index] = modified_data_[index];

4004 }

4005 touched_.ResetAllToFalse();

4006 }

4007

4008 void Revert() {

4009 for (const IndexType index : touched_.PositionsSetAtLeastOnce()) {

4010 modified_data_[index] = base_data_[index];

4011 }

4012 touched_.ResetAllToFalse();

4013 }

4014

4015

4016 int NumSetValues() const {

4017 return touched_.NumberOfSetCallsWithDifferentArguments();

4018 }

4019

4020 private:

4021 std::vector<T> base_data_;

4022 std::vector<T> modified_data_;

4023 SparseBitset<IndexType> touched_;

4024 };

4025

4026 int64_t GetValue(int64_t index) const {

4028 }

4029 IntVar* GetVar(int64_t index) const {

4030 return assignment_.Element(index).Var();

4031 }

4032 void AddVars(const std::vector<IntVar*>& vars);

4033 int NumPrimaryVars() const { return num_vars_; }

4034 int GetLocalIndexFromVar(IntVar* var) const {

4035 const int var_index = var->index();

4036 return (var_index < var_index_to_local_index_.size())

4037 ? var_index_to_local_index_[var_index]

4038 : -1;

4039 }

4040 void ResetPenalties();

4041

4042 IntVar* penalized_objective_;

4043 Assignment::IntContainer assignment_;

4044 int64_t assignment_penalized_value_;

4045 int64_t old_penalized_value_;

4046 const int num_vars_;

4047 std::vector<int> var_index_to_local_index_;

4048 const double penalty_factor_;

4049 P penalties_;

4050 DirtyArray<int64_t> penalized_values_;

4051 bool incremental_;

4052 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4053 get_equivalent_pairs_;

4054 const bool reset_penalties_on_new_best_solution_;

4055};

4056

4057template <typename P>

4058GuidedLocalSearch<P>::GuidedLocalSearch(

4059 Solver* solver, IntVar* objective, bool maximize, int64_t step,

4060 const std::vector<IntVar*>& vars, double penalty_factor,

4061 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4062 get_equivalent_pairs,

4063 bool reset_penalties_on_new_best_solution)

4064 : Metaheuristic(solver, {maximize}, {objective}, {step}),

4065 penalized_objective_(nullptr),

4066 assignment_penalized_value_(0),

4067 old_penalized_value_(0),

4068 num_vars_(vars.size()),

4069 penalty_factor_(penalty_factor),

4070 penalties_(vars.size()),

4071 penalized_values_(vars.size()),

4072 incremental_(false),

4073 get_equivalent_pairs_(std::move(get_equivalent_pairs)),

4074 reset_penalties_on_new_best_solution_(

4075 reset_penalties_on_new_best_solution) {

4076 AddVars(vars);

4077}

4078

4079template <typename P>

4080void GuidedLocalSearch<P>::AddVars(const std::vector<IntVar*>& vars) {

4081 const int offset = assignment_.Size();

4082 if (vars.empty()) return;

4083 assignment_.Resize(offset + vars.size());

4084 for (int i = 0; i < vars.size(); ++i) {

4085 assignment_.AddAtPosition(vars[i], offset + i);

4086 }

4087 const int max_var_index =

4088 (*std::max_element(vars.begin(), vars.end(), [](IntVar* a, IntVar* b) {

4089 return a->index() < b->index();

4090 }))->index();

4091 if (max_var_index >= var_index_to_local_index_.size()) {

4092 var_index_to_local_index_.resize(max_var_index + 1, -1);

4093 }

4094 for (int i = 0; i < vars.size(); ++i) {

4095 var_index_to_local_index_[vars[i]->index()] = offset + i;

4096 }

4097}

4098

4099

4100

4101

4102

4103

4104

4105

4106template <typename P>

4107void GuidedLocalSearch<P>::ApplyDecision(Decision* const d) {

4108 if (d == solver()->balancing_decision()) {

4109 return;

4110 }

4111 assignment_penalized_value_ = 0;

4112 if (penalties_.HasPenalties()) {

4113

4114

4115 {

4116 std::vector<IntVar*> elements;

4117 for (int i = 0; i < num_vars_; ++i) {

4118 elements.push_back(MakeElementPenalty(i)->Var());

4119 const int64_t penalty = AssignmentElementPenalty(i);

4120 penalized_values_.Set(i, penalty);

4121 assignment_penalized_value_ =

4122 CapAdd(assignment_penalized_value_, penalty);

4123 }

4124 solver()->SaveAndSetValue(

4125 reinterpret_cast<void**>(&penalized_objective_),

4126 reinterpret_cast<void*>(solver()->MakeSum(elements)->Var()));

4127 }

4128 penalized_values_.Commit();

4129 old_penalized_value_ = assignment_penalized_value_;

4130 incremental_ = false;

4131 IntExpr* max_pen_exp = solver()->MakeDifference(

4132 CapSub(CurrentInternalValue(0), Step(0)), penalized_objective_);

4134 solver()

4135 ->MakeMax(max_pen_exp, CapSub(BestInternalValue(0), Step(0)))

4136 ->Var();

4137 solver()->AddConstraint(

4138 solver()->MakeLessOrEqual(MinimizationVar(0), max_exp));

4139 } else {

4140 penalized_objective_ = nullptr;

4141 const int64_t bound =

4142 (CurrentInternalValue(0) < std::numeric_limits<int64_t>::max())

4143 ? CapSub(CurrentInternalValue(0), Step(0))

4144 : CurrentInternalValue(0);

4145 MinimizationVar(0)->SetMax(bound);

4146 }

4147}

4148

4149template <typename P>

4150void GuidedLocalSearch<P>::ResetPenalties() {

4151 assignment_penalized_value_ = 0;

4152 old_penalized_value_ = 0;

4153 penalized_values_.SetAll(0);

4154 penalized_values_.Commit();

4155 penalties_.Reset();

4156}

4157

4158template <typename P>

4159bool GuidedLocalSearch<P>::AtSolution() {

4160 const int64_t old_best = BestInternalValue(0);

4162 return false;

4163 }

4164 if (penalized_objective_ != nullptr && penalized_objective_->Bound()) {

4165

4166

4167

4168

4169 if (reset_penalties_on_new_best_solution_ &&

4170 old_best != BestInternalValue(0)) {

4171 ResetPenalties();

4172 DCHECK_EQ(CurrentInternalValue(0), BestInternalValue(0));

4173 } else {

4174

4175 SetCurrentInternalValue(

4176 0, CapAdd(CurrentInternalValue(0), penalized_objective_->Value()));

4177 }

4178 }

4179 assignment_.Store();

4180 return true;

4181}

4182

4183template <typename P>

4184void GuidedLocalSearch<P>::EnterSearch() {

4185 Metaheuristic::EnterSearch();

4186 solver()->SetUseFastLocalSearch(true);

4187 penalized_objective_ = nullptr;

4188 ResetPenalties();

4189}

4190

4191

4192

4193template <typename P>

4194bool GuidedLocalSearch<P>::AcceptDelta(Assignment* delta,

4196 if (delta == nullptr && deltadelta == nullptr) return true;

4197 if (!penalties_.HasPenalties()) {

4198 return Metaheuristic::AcceptDelta(delta, deltadelta);

4199 }

4200 int64_t penalty = 0;

4201 if (!deltadelta->Empty()) {

4202 if (!incremental_) {

4203 DCHECK_EQ(penalized_values_.NumSetValues(), 0);

4204 penalty = Evaluate(delta, assignment_penalized_value_, true);

4205 } else {

4206 penalty = Evaluate(deltadelta, old_penalized_value_, true);

4207 }

4208 incremental_ = true;

4209 } else {

4210 if (incremental_) {

4211 penalized_values_.Revert();

4212 }

4213 incremental_ = false;

4214 DCHECK_EQ(penalized_values_.NumSetValues(), 0);

4215 penalty = Evaluate(delta, assignment_penalized_value_, false);

4216 }

4217 old_penalized_value_ = penalty;

4218 if (!delta->HasObjective()) {

4219 delta->AddObjective(ObjectiveVar(0));

4220 }

4221 if (delta->Objective() == ObjectiveVar(0)) {

4222 const int64_t bound =

4223 std::max(CapSub(CapSub(CurrentInternalValue(0), Step(0)), penalty),

4224 CapSub(BestInternalValue(0), Step(0)));

4225 if (Maximize(0)) {

4226 delta->SetObjectiveMin(std::max(CapOpp(bound), delta->ObjectiveMin()));

4227 } else {

4228 delta->SetObjectiveMax(std::min(bound, delta->ObjectiveMax()));

4229 }

4230 }

4231 return true;

4232}

4233

4234

4235

4236template <typename P>

4237bool GuidedLocalSearch<P>::AtLocalOptimum() {

4238 solver()->SetUseFastLocalSearch(false);

4239 std::vector<double> utilities(num_vars_);

4240 double max_utility = -std::numeric_limits<double>::infinity();

4241 for (int var = 0; var < num_vars_; ++var) {

4242 const IntVarElement& element = assignment_.Element(var);

4243 if (!element.Bound()) {

4244

4245 return false;

4246 }

4247 const int64_t value = element.Value();

4248

4249

4250 const int64_t cost = (value != var) ? AssignmentPenalty(var, value) : 0;

4251 const double utility = cost / (penalties_.GetPenalty({var, value}) + 1.0);

4252 utilities[var] = utility;

4253 if (utility > max_utility) max_utility = utility;

4254 }

4255 for (int var = 0; var < num_vars_; ++var) {

4256 if (utilities[var] == max_utility) {

4257 const IntVarElement& element = assignment_.Element(var);

4258 DCHECK(element.Bound());

4259 const int64_t value = element.Value();

4260 if (get_equivalent_pairs_ == nullptr) {

4261 penalties_.IncrementPenalty({var, value});

4262 } else {

4263 for (const auto [other_var, other_value] :

4264 get_equivalent_pairs_(var, value)) {

4265 penalties_.IncrementPenalty({other_var, other_value});

4266 }

4267 }

4268 }

4269 }

4270 SetCurrentInternalValue(0, std::numeric_limits<int64_t>::max());

4271 return true;

4272}

4273

4274template <typename P>

4275class BinaryGuidedLocalSearch : public GuidedLocalSearch<P> {

4276 public:

4277 BinaryGuidedLocalSearch(

4278 Solver* solver, IntVar* objective,

4279 std::function<int64_t(int64_t, int64_t)> objective_function,

4280 bool maximize, int64_t step, const std::vector<IntVar*>& vars,

4281 double penalty_factor,

4282 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4283 get_equivalent_pairs,

4284 bool reset_penalties_on_new_best_solution);

4285 ~BinaryGuidedLocalSearch() override {}

4286 IntExpr* MakeElementPenalty(int index) override;

4287 int64_t AssignmentElementPenalty(int index) const override;

4288 int64_t AssignmentPenalty(int64_t var, int64_t value) const override;

4289 int64_t Evaluate(const Assignment* delta, int64_t current_penalty,

4290 bool incremental) override;

4291

4292 private:

4293 int64_t PenalizedValue(int64_t i, int64_t j) const;

4294 std::function<int64_t(int64_t, int64_t)> objective_function_;

4295};

4296

4297template <typename P>

4298BinaryGuidedLocalSearch<P>::BinaryGuidedLocalSearch(

4299 Solver* const solver, IntVar* const objective,

4300 std::function<int64_t(int64_t, int64_t)> objective_function, bool maximize,

4301 int64_t step, const std::vector<IntVar*>& vars, double penalty_factor,

4302 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4303 get_equivalent_pairs,

4304 bool reset_penalties_on_new_best_solution)

4305 : GuidedLocalSearch<P>(solver, objective, maximize, step, vars,

4306 penalty_factor, std::move(get_equivalent_pairs),

4307 reset_penalties_on_new_best_solution),

4308 objective_function_(std::move(objective_function)) {

4309 solver->SetGuidedLocalSearchPenaltyCallback(

4310 [this](int64_t i, int64_t j, int64_t) { return PenalizedValue(i, j); });

4311}

4312

4313template <typename P>

4314IntExpr* BinaryGuidedLocalSearch<P>::MakeElementPenalty(int index) {

4315 return this->solver()->MakeElement(

4316 [this, index](int64_t i) { return PenalizedValue(index, i); },

4317 this->GetVar(index));

4318}

4319

4320template <typename P>

4321int64_t BinaryGuidedLocalSearch<P>::AssignmentElementPenalty(int index) const {

4322 return PenalizedValue(index, this->GetValue(index));

4323}

4324

4325template <typename P>

4326int64_t BinaryGuidedLocalSearch<P>::AssignmentPenalty(int64_t var,

4327 int64_t value) const {

4328 return objective_function_(var, value);

4329}

4330

4331template <typename P>

4332int64_t BinaryGuidedLocalSearch<P>::Evaluate(const Assignment* delta,

4333 int64_t current_penalty,

4334 bool incremental) {

4335 int64_t penalty = current_penalty;

4337 for (const IntVarElement& new_element : container.elements()) {

4338 const int index = this->GetLocalIndexFromVar(new_element.Var());

4339 if (index == -1) continue;

4340 penalty = CapSub(penalty, this->penalized_values_.Get(index));

4341 if (new_element.Activated()) {

4342 const int64_t new_penalty = PenalizedValue(index, new_element.Value());

4343 penalty = CapAdd(penalty, new_penalty);

4344 if (incremental) {

4345 this->penalized_values_.Set(index, new_penalty);

4346 }

4347 }

4348 }

4349 return penalty;

4350}

4351

4352

4353template <typename P>

4354int64_t BinaryGuidedLocalSearch<P>::PenalizedValue(int64_t i, int64_t j) const {

4355 const int64_t penalty = this->penalties_.GetPenalty({i, j});

4356

4357 if (penalty == 0) return 0;

4358 const double penalized_value_fp =

4359 this->penalty_factor_ * penalty * objective_function_(i, j);

4360 const int64_t penalized_value =

4361 (penalized_value_fp <= std::numeric_limits<int64_t>::max())

4362 ? static_cast<int64_t>(penalized_value_fp)

4363 : std::numeric_limits<int64_t>::max();

4364 return penalized_value;

4365}

4366

4367template <typename P>

4368class TernaryGuidedLocalSearch : public GuidedLocalSearch<P> {

4369 public:

4370 TernaryGuidedLocalSearch(

4371 Solver* solver, IntVar* objective,

4372 std::function<int64_t(int64_t, int64_t, int64_t)> objective_function,

4373 bool maximize, int64_t step, const std::vector<IntVar*>& vars,

4374 const std::vector<IntVar*>& secondary_vars, double penalty_factor,

4375 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4376 get_equivalent_pairs,

4377 bool reset_penalties_on_new_best_solution);

4378 ~TernaryGuidedLocalSearch() override {}

4379 IntExpr* MakeElementPenalty(int index) override;

4380 int64_t AssignmentElementPenalty(int index) const override;

4381 int64_t AssignmentPenalty(int64_t var, int64_t value) const override;

4382 int64_t Evaluate(const Assignment* delta, int64_t current_penalty,

4383 bool incremental) override;

4384

4385 private:

4386 int64_t PenalizedValue(int64_t i, int64_t j, int64_t k) const;

4387

4388 std::function<int64_t(int64_t, int64_t, int64_t)> objective_function_;

4389 std::vector<int> secondary_values_;

4390};

4391

4392template <typename P>

4393TernaryGuidedLocalSearch<P>::TernaryGuidedLocalSearch(

4394 Solver* const solver, IntVar* const objective,

4395 std::function<int64_t(int64_t, int64_t, int64_t)> objective_function,

4396 bool maximize, int64_t step, const std::vector<IntVar*>& vars,

4397 const std::vector<IntVar*>& secondary_vars, double penalty_factor,

4398 std::function<std::vector<std::pair<int64_t, int64_t>>(int64_t, int64_t)>

4399 get_equivalent_pairs,

4400 bool reset_penalties_on_new_best_solution)

4401 : GuidedLocalSearch<P>(solver, objective, maximize, step, vars,

4402 penalty_factor, std::move(get_equivalent_pairs),

4403 reset_penalties_on_new_best_solution),

4404 objective_function_(std::move(objective_function)),

4405 secondary_values_(this->NumPrimaryVars(), -1) {

4406 this->AddVars(secondary_vars);

4407 solver->SetGuidedLocalSearchPenaltyCallback(

4408 [this](int64_t i, int64_t j, int64_t k) {

4409 return PenalizedValue(i, j, k);

4410 });

4411}

4412

4413template <typename P>

4414IntExpr* TernaryGuidedLocalSearch<P>::MakeElementPenalty(int index) {

4415 Solver* const solver = this->solver();

4417 solver->AddConstraint(solver->MakeLightElement(

4418 [this, index](int64_t j, int64_t k) {

4419 return PenalizedValue(index, j, k);

4420 },

4421 var, this->GetVar(index), this->GetVar(this->NumPrimaryVars() + index)));

4422 return var;

4423}

4424

4425template <typename P>

4426int64_t TernaryGuidedLocalSearch<P>::AssignmentElementPenalty(int index) const {

4427 return PenalizedValue(index, this->GetValue(index),

4428 this->GetValue(this->NumPrimaryVars() + index));

4429}

4430

4431template <typename P>

4432int64_t TernaryGuidedLocalSearch<P>::AssignmentPenalty(int64_t var,

4433 int64_t value) const {

4434 return objective_function_(var, value,

4435 this->GetValue(this->NumPrimaryVars() + var));

4436}

4437

4438template <typename P>

4439int64_t TernaryGuidedLocalSearch<P>::Evaluate(const Assignment* delta,

4440 int64_t current_penalty,

4441 bool incremental) {

4442 int64_t penalty = current_penalty;

4444

4445

4446

4447 for (const IntVarElement& new_element : container.elements()) {

4448 const int index = this->GetLocalIndexFromVar(new_element.Var());

4449 if (index != -1 && index < this->NumPrimaryVars()) {

4450 secondary_values_[index] = -1;

4451 }

4452 }

4453 for (const IntVarElement& new_element : container.elements()) {

4454 const int index = this->GetLocalIndexFromVar(new_element.Var());

4455 if (!new_element.Activated()) continue;

4456 if (index != -1 && index >= this->NumPrimaryVars()) {

4457 secondary_values_[index - this->NumPrimaryVars()] = new_element.Value();

4458 }

4459 }

4460 for (const IntVarElement& new_element : container.elements()) {

4461 const int index = this->GetLocalIndexFromVar(new_element.Var());

4462

4463 if (index == -1 || index >= this->NumPrimaryVars()) {

4464 continue;

4465 }

4466 penalty = CapSub(penalty, this->penalized_values_.Get(index));

4467

4468 if (new_element.Activated() && secondary_values_[index] != -1) {

4469 const int64_t new_penalty =

4470 PenalizedValue(index, new_element.Value(), secondary_values_[index]);

4471 penalty = CapAdd(penalty, new_penalty);

4472 if (incremental) {

4473 this->penalized_values_.Set(index, new_penalty);

4474 }

4475 }

4476 }

4477 return penalty;

4478}

4479

4480

4481template <typename P>

4482int64_t TernaryGuidedLocalSearch<P>::PenalizedValue(int64_t i, int64_t j,

4483 int64_t k) const {

4484 const int64_t penalty = this->penalties_.GetPenalty({i, j});

4485

4486 if (penalty == 0) return 0;

4487 const double penalized_value_fp =

4488 this->penalty_factor_ * penalty * objective_function_(i, j, k);

4489 const int64_t penalized_value =

4490 (penalized_value_fp < std::numeric_limits<int64_t>::max())

4491 ? static_cast<int64_t>(penalized_value_fp)

4492 : std::numeric_limits<int64_t>::max();

4493 return penalized_value;

4494}

4495}

4496

4517

4540

4541

4542

4543

4544

4546

4553

4558

4563

4568

4575

4576void SearchLimit::TopPeriodicCheck() {

4577 if (solver()->TopLevelSearch() != solver()->ActiveSearch()) {

4579 }

4580}

4581

4582

4583

4602

4604

4612

4623

4625

4631

4639

4652

4663

4674

4683

4689

4697

4712

4713bool RegularLimit::CheckTime(absl::Duration offset) {

4715}

4716

4717absl::Duration RegularLimit::TimeElapsed() {

4718 const int64_t kMaxSkip = 100;

4719 const int64_t kCheckWarmupIterations = 100;

4720 ++check_count_;

4722 next_check_ <= check_count_) {

4723 Solver* const s = solver();

4724 absl::Duration elapsed = s->Now() - solver_time_at_limit_start_;

4725 if (smart_time_check_ && check_count_ > kCheckWarmupIterations &&

4726 elapsed > absl::ZeroDuration()) {

4728 check_count_ * absl::FDivDuration(duration_limit_, elapsed));

4729 next_check_ =

4730 std::min(check_count_ + kMaxSkip, estimated_check_count_at_limit);

4731 }

4732 last_time_elapsed_ = elapsed;

4733 }

4734 return last_time_elapsed_;

4735}

4736

4743

4750

4757

4764

4771

4778

4786

4797

4798

4799

4811

4830

4832

4837

4847

4864

4871

4905

4956

4965

4976

4977

4978namespace {

4980 public:

4982 : SearchLimit(limit_1->solver()), limit_1_(limit_1), limit_2_(limit_2) {

4983 CHECK(limit_1 != nullptr);

4984 CHECK(limit_2 != nullptr);

4985 CHECK_EQ(limit_1->solver(), limit_2->solver())

4986 << "Illegal arguments: cannot combines limits that belong to different "

4987 << "solvers, because the reversible allocations could delete one and "

4988 << "not the other.";

4989 }

4990

4991 bool CheckWithOffset(absl::Duration offset) override {

4992

4993

4994 const bool check_1 = limit_1_->CheckWithOffset(offset);

4995 const bool check_2 = limit_2_->CheckWithOffset(offset);

4996 return check_1 || check_2;

4997 }

4998

4999 void Init() override {

5000 limit_1_->Init();

5001 limit_2_->Init();

5002 }

5003

5004 void Copy(const SearchLimit* const) override {

5005 LOG(FATAL) << "Not implemented.";

5006 }

5007

5008 SearchLimit* MakeClone() const override {

5009

5010 return solver()->MakeLimit(limit_1_->MakeClone(), limit_2_->MakeClone());

5011 }

5012

5013 void EnterSearch() override {

5014 limit_1_->EnterSearch();

5015 limit_2_->EnterSearch();

5016 }

5017 void BeginNextDecision(DecisionBuilder* const b) override {

5018 limit_1_->BeginNextDecision(b);

5019 limit_2_->BeginNextDecision(b);

5020 }

5021 void PeriodicCheck() override {

5022 limit_1_->PeriodicCheck();

5023 limit_2_->PeriodicCheck();

5024 }

5025 void RefuteDecision(Decision* const d) override {

5026 limit_1_->RefuteDecision(d);

5027 limit_2_->RefuteDecision(d);

5028 }

5029 std::string DebugString() const override {

5030 return absl::StrCat("OR limit (", limit_1_->DebugString(), " OR ",

5031 limit_2_->DebugString(), ")");

5032 }

5033

5034 private:

5035 SearchLimit* const limit_1_;

5036 SearchLimit* const limit_2_;

5037};

5038}

5039

5044

5045namespace {

5047 public:

5048 CustomLimit(Solver* s, std::function<bool()> limiter);

5049 bool CheckWithOffset(absl::Duration offset) override;

5050 void Init() override;

5051 void Copy(const SearchLimit* limit) override;

5052 SearchLimit* MakeClone() const override;

5053

5054 private:

5055 std::function<bool()> limiter_;

5056};

5057

5058CustomLimit::CustomLimit(Solver* const s, std::function<bool()> limiter)

5059 : SearchLimit(s), limiter_(std::move(limiter)) {}

5060

5061bool CustomLimit::CheckWithOffset(absl::Duration) {

5062

5063 if (limiter_) return limiter_();

5064 return false;

5065}

5066

5067void CustomLimit::Init() {}

5068

5069void CustomLimit::Copy(const SearchLimit* const limit) {

5070 const CustomLimit* const custom =

5071 reinterpret_cast<const CustomLimit* const>(limit);

5072 limiter_ = custom->limiter_;

5073}

5074

5075SearchLimit* CustomLimit::MakeClone() const {

5076 return solver()->RevAlloc(new CustomLimit(solver(), limiter_));

5077}

5078}

5079

5083

5084

5085

5086namespace {

5088 public:

5089 explicit SolveOnce(DecisionBuilder* const db) : db_(db) {

5090 CHECK(db != nullptr);

5091 }

5092

5093 SolveOnce(DecisionBuilder* const db,

5094 const std::vector<SearchMonitor*>& monitors)

5095 : db_(db), monitors_(monitors) {

5096 CHECK(db != nullptr);

5097 }

5098

5099 ~SolveOnce() override {}

5100

5101 Decision* Next(Solver* s) override {

5102 bool res = s->SolveAndCommit(db_, monitors_);

5103 if (!res) {

5104 s->Fail();

5105 }

5106 return nullptr;

5107 }

5108

5109 std::string DebugString() const override {

5110 return absl::StrFormat("SolveOnce(%s)", db_->DebugString());

5111 }

5112

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

5114 db_->Accept(visitor);

5115 }

5116

5117 private:

5118 DecisionBuilder* const db_;

5119 std::vector<SearchMonitor*> monitors_;

5120};

5121}

5122

5126

5133

5142

5153

5166

5171

5172

5173

5174namespace {

5176 public:

5178 bool maximize, int64_t step)

5179 : db_(db),

5181 maximize_(maximize),

5182 step_(step),

5183 collector_(nullptr) {

5184 CHECK(db != nullptr);

5186 CHECK(solution->HasObjective());

5187 AddMonitors();

5188 }

5189

5190 NestedOptimize(DecisionBuilder* const db, Assignment* const solution,

5191 bool maximize, int64_t step,

5192 const std::vector<SearchMonitor*>& monitors)

5193 : db_(db),

5194 solution_(solution),

5195 maximize_(maximize),

5196 step_(step),

5197 monitors_(monitors),

5198 collector_(nullptr) {

5199 CHECK(db != nullptr);

5200 CHECK(solution != nullptr);

5201 CHECK(solution->HasObjective());

5202 AddMonitors();

5203 }

5204

5205 void AddMonitors() {

5206 Solver* const solver = solution_->solver();

5207 collector_ = solver->MakeLastSolutionCollector(solution_);

5208 monitors_.push_back(collector_);

5209 OptimizeVar* const optimize =

5210 solver->MakeOptimize(maximize_, solution_->Objective(), step_);

5211 monitors_.push_back(optimize);

5212 }

5213

5214 Decision* Next(Solver* solver) override {

5215 solver->Solve(db_, monitors_);

5217 solver->Fail();

5218 }

5220 return nullptr;

5221 }

5222

5223 std::string DebugString() const override {

5224 return absl::StrFormat("NestedOptimize(db = %s, maximize = %d, step = %d)",

5226 }

5227

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

5229 db_->Accept(visitor);

5230 }

5231

5232 private:

5233 DecisionBuilder* const db_;

5234 Assignment* const solution_;

5235 const bool maximize_;

5236 const int64_t step_;

5237 std::vector<SearchMonitor*> monitors_;

5238 SolutionCollector* collector_;

5239};

5240}

5241

5247

5256

5267

5280

5292

5298

5299

5300

5301namespace {

5302

5303int64_t NextLuby(int i) {

5304 DCHECK_GT(i, 0);

5305 DCHECK_LT(i, std::numeric_limits<int32_t>::max());

5306 int64_t power;

5307

5308

5309 power = 2;

5310

5311 while (power < (i + 1)) {

5312 power <<= 1;

5313 }

5314 if (power == i + 1) {

5315 return (power / 2);

5316 }

5317 return NextLuby(i - (power / 2) + 1);

5318}

5319

5320class LubyRestart : public SearchMonitor {

5321 public:

5322 LubyRestart(Solver* const s, int scale_factor)

5323 : SearchMonitor(s),

5324 scale_factor_(scale_factor),

5325 iteration_(1),

5326 current_fails_(0),

5327 next_step_(scale_factor) {

5328 CHECK_GE(scale_factor, 1);

5329 }

5330

5331 ~LubyRestart() override {}

5332

5333 void BeginFail() override {

5334 if (++current_fails_ >= next_step_) {

5335 current_fails_ = 0;

5336 next_step_ = NextLuby(++iteration_) * scale_factor_;

5337 solver()->RestartCurrentSearch();

5338 }

5339 }

5340

5341 void Install() override { ListenToEvent(Solver::MonitorEvent::kBeginFail); }

5342

5343 std::string DebugString() const override {

5344 return absl::StrFormat("LubyRestart(%i)", scale_factor_);

5345 }

5346

5347 private:

5348 const int scale_factor_;

5349 int iteration_;

5350 int64_t current_fails_;

5351 int64_t next_step_;

5352};

5353}

5354

5358

5359

5360

5361namespace {

5363 public:

5364 ConstantRestart(Solver* const s, int frequency)

5365 : SearchMonitor(s), frequency_(frequency), current_fails_(0) {

5366 CHECK_GE(frequency, 1);

5367 }

5368

5369 ~ConstantRestart() override {}

5370

5371 void BeginFail() override {

5372 if (++current_fails_ >= frequency_) {

5373 current_fails_ = 0;

5374 solver()->RestartCurrentSearch();

5375 }

5376 }

5377

5378 void Install() override { ListenToEvent(Solver::MonitorEvent::kBeginFail); }

5379

5380 std::string DebugString() const override {

5381 return absl::StrFormat("ConstantRestart(%i)", frequency_);

5382 }

5383

5384 private:

5385 const int frequency_;

5386 int64_t current_fails_;

5387};

5388}

5389

5393

5394

5395

5396

5397

5398

5399

5400

5401

5402

5403

5404

5405

5406

5407

5408

5409

5410

5500

5501

5502

5510

5518

5526

5527

5528

5533

5539

5547

5557

5569}