Google OR-Tools: ortools/constraint_solver/constraint

Google OR-Tools: ortools/constraint_solver/constraint_solver.cc Source File

19#include <algorithm>

20#include <csetjmp>

21#include <cstdint>

22#include <deque>

23#include <iosfwd>

24#include <limits>

25#include <memory>

26#include <ostream>

27#include <string>

28#include <type_traits>

29#include <utility>

30#include <vector>

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

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

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

42#include "zlib.h"

45ABSL_FLAG(bool, cp_trace_propagation, false,

46 "Trace propagation events (constraint and demon executions,"

47 " variable modifications).");

48ABSL_FLAG(bool, cp_trace_search, false, "Trace search events");

49ABSL_FLAG(bool, cp_print_added_constraints, false,

50 "show all constraints added to the solver.");

52 "use PrintModelVisitor on model before solving.");

54 "use StatisticsModelVisitor on model before solving.");

56 "Force failure at the beginning of a search.");

57ABSL_FLAG(std::string, cp_profile_file, "",

58 "Export profiling overview to file.");

59ABSL_FLAG(bool, cp_print_local_search_profile, false,

60 "Print local search profiling data after solving.");

61ABSL_FLAG(bool, cp_name_variables, false, "Force all variables to have names.");

62ABSL_FLAG(bool, cp_name_cast_variables, false,

63 "Name variables casted from expressions");

65 "Use small compact table constraint when possible.");

66ABSL_FLAG(bool, cp_use_cumulative_edge_finder, true,

67 "Use the O(n log n) cumulative edge finding algorithm described "

68 "in 'Edge Finding Filtering Algorithm for Discrete Cumulative "

69 "Resources in O(kn log n)' by Petr Vilim, CP 2009.");

70ABSL_FLAG(bool, cp_use_cumulative_time_table, true,

71 "Use a O(n^2) cumulative time table propagation algorithm.");

72ABSL_FLAG(bool, cp_use_cumulative_time_table_sync, false,

73 "Use a synchronized O(n^2 log n) cumulative time table propagation "

74 "algorithm.");

75ABSL_FLAG(bool, cp_use_sequence_high_demand_tasks, true,

76 "Use a sequence constraints for cumulative tasks that have a "

77 "demand greater than half of the capacity of the resource.");

78ABSL_FLAG(bool, cp_use_all_possible_disjunctions, true,

79 "Post temporal disjunctions for all pairs of tasks sharing a "

80 "cumulative resource and that cannot overlap because the sum of "

81 "their demand exceeds the capacity.");

82ABSL_FLAG(int, cp_max_edge_finder_size, 50,

83 "Do not post the edge finder in the cumulative constraints if "

84 "it contains more than this number of tasks");

85ABSL_FLAG(bool, cp_diffn_use_cumulative, true,

86 "Diffn constraint adds redundant cumulative constraint");

88 "If true, rmq's will be used in element expressions.");

89ABSL_FLAG(int, cp_check_solution_period, 1,

90 "Number of solutions explored between two solution checks during "

91 "local search.");

93 "Random seed used in several (but not all) random number "

94 "generators used by the CP solver. Use -1 to auto-generate an"

95 "undeterministic random seed.");

99#if defined(_MSC_VER)

100#pragma warning(disable : 4351 4355)

101#endif

102

104

105namespace {

106

107

108template <typename T, typename MethodPointer, typename... Args>

109void ForAll(const std::vector<T*>& objects, MethodPointer method,

110 const Args&... args) {

111 for (T* const object : objects) {

112 DCHECK(object != nullptr);

113 (object->*method)(args...);

114 }

115}

116

117

118template <typename E>

119constexpr typename std::underlying_type<E>::type to_underlying(E e) {

120 return static_cast<typename std::underlying_type<E>::type>(e);

121}

122

123}

124

125

126

135 params.set_trace_search(absl::GetFlag(FLAGS_cp_trace_search));

137 params.set_profile_file(absl::GetFlag(FLAGS_cp_profile_file));

139 absl::GetFlag(FLAGS_cp_print_local_search_profile));

141 absl::GetFlag(FLAGS_cp_print_local_search_profile));

142 params.set_print_model(absl::GetFlag(FLAGS_cp_print_model));

147 absl::GetFlag(FLAGS_cp_print_added_constraints));

150 absl::GetFlag(FLAGS_cp_use_cumulative_edge_finder));

152 absl::GetFlag(FLAGS_cp_use_cumulative_time_table));

154 absl::GetFlag(FLAGS_cp_use_cumulative_time_table_sync));

156 absl::GetFlag(FLAGS_cp_use_sequence_high_demand_tasks));

158 absl::GetFlag(FLAGS_cp_use_all_possible_disjunctions));

163 absl::GetFlag(FLAGS_cp_check_solution_period));

164 return params;

165}

166

167

174

175

176

177

181

183 return parameters_.profile_propagation() ||

184 !parameters_.profile_file().empty();

185}

186

188 return parameters_.profile_local_search() ||

189 parameters_.print_local_search_profile();

190}

191

193 return parameters_.trace_propagation();

194}

195

197 return parameters_.name_all_variables();

198}

199

200

201

205

207

209 if (stamp_ < std::numeric_limits<uint64_t>::max()) {

210 s->SaveAndSetValue(&stamp_, std::numeric_limits<uint64_t>::max());

211 }

212}

213

215 if (stamp_ == std::numeric_limits<uint64_t>::max()) {

217 }

218}

219

220

221

223

225 public:

227

229 : solver_(s),

230 stamp_(1),

231 freeze_level_(0),

232 in_process_(false),

233 clean_action_(nullptr),

234 clean_variable_(nullptr),

235 in_add_(false),

236 instruments_demons_(s->InstrumentsDemons()) {}

237

239

241 freeze_level_++;

242 stamp_++;

243 }

244

246 if (--freeze_level_ == 0) {

248 }

249 }

250

252 demon->set_stamp(stamp_ - 1);

253 if (!instruments_demons_) {

255 solver_->TopPeriodicCheck();

256 }

257 demon->Run(solver_);

258 solver_->CheckFail();

259 } else {

260 solver_->GetPropagationMonitor()->BeginDemonRun(demon);

262 solver_->TopPeriodicCheck();

263 }

264 demon->Run(solver_);

265 solver_->CheckFail();

266 solver_->GetPropagationMonitor()->EndDemonRun(demon);

267 }

268 }

269

271 if (!in_process_) {

272 in_process_ = true;

273 while (!var_queue_.empty() || !delayed_queue_.empty()) {

274 if (!var_queue_.empty()) {

275 Demon* const demon = var_queue_.front();

276 var_queue_.pop_front();

278 } else {

279 DCHECK(!delayed_queue_.empty());

280 Demon* const demon = delayed_queue_.front();

281 delayed_queue_.pop_front();

283 }

284 }

285 in_process_ = false;

286 }

287 }

288

290 if (!instruments_demons_) {

292 Demon* const demon = *it;

293 if (demon->stamp() < stamp_) {

296 0) {

297 solver_->TopPeriodicCheck();

298 }

299 demon->Run(solver_);

300 solver_->CheckFail();

301 }

302 }

303 } else {

305 Demon* const demon = *it;

306 if (demon->stamp() < stamp_) {

308 solver_->GetPropagationMonitor()->BeginDemonRun(demon);

310 0) {

311 solver_->TopPeriodicCheck();

312 }

313 demon->Run(solver_);

314 solver_->CheckFail();

315 solver_->GetPropagationMonitor()->EndDemonRun(demon);

316 }

317 }

318 }

319 }

320

326

329 if (demon->stamp() < stamp_) {

330 demon->set_stamp(stamp_);

331 var_queue_.push_back(demon);

332 if (freeze_level_ == 0) {

334 }

335 }

336 }

337

340 if (demon->stamp() < stamp_) {

341 demon->set_stamp(stamp_);

342 delayed_queue_.push_back(demon);

343 }

344 }

345

347

348 var_queue_.clear();

349 delayed_queue_.clear();

350

351

352 if (clean_action_ != nullptr) {

353 clean_action_(solver_);

354 clean_action_ = nullptr;

355 } else if (clean_variable_ != nullptr) {

357 clean_variable_ = nullptr;

358 }

359

360 freeze_level_ = 0;

361 in_process_ = false;

362 in_add_ = false;

363 to_add_.clear();

364 }

365

367

368 uint64_t stamp() const { return stamp_; }

369

371 DCHECK(clean_variable_ == nullptr);

372 clean_action_ = std::move(a);

373 }

374

376 DCHECK(clean_action_ == nullptr);

377 clean_variable_ = var;

378 }

379

381 DCHECK(clean_variable_ == nullptr);

382 clean_action_ = nullptr;

383 }

384

386 to_add_.push_back(c);

388 }

389

391 if (!in_add_) {

392 in_add_ = true;

393

394

395

396 for (int counter = 0; counter < to_add_.size(); ++counter) {

397 Constraint* const constraint = to_add_[counter];

398

400 }

401 in_add_ = false;

402 to_add_.clear();

403 }

404 }

405

406 private:

407 Solver* const solver_;

408 std::deque<Demon*> var_queue_;

409 std::deque<Demon*> delayed_queue_;

410 uint64_t stamp_;

411

412

413 uint32_t freeze_level_;

414 bool in_process_;

416 IntVar* clean_variable_;

417 std::vector<Constraint*> to_add_;

418 bool in_add_;

419 const bool instruments_demons_;

420};

421

422

423

458

460 public:

464

465 private:

467 int rev_int_index_;

468 int rev_int64_index_;

469 int rev_uint64_index_;

470 int rev_double_index_;

471 int rev_ptr_index_;

472 int rev_boolvar_list_index_;

473 int rev_bools_index_;

474 int rev_int_memory_index_;

475 int rev_int64_memory_index_;

476 int rev_double_memory_index_;

477 int rev_object_memory_index_;

478 int rev_object_array_memory_index_;

479 int rev_memory_index_;

480 int rev_memory_array_index_;

482};

483

485 : type_(t),

486 rev_int_index_(0),

487 rev_int64_index_(0),

488 rev_uint64_index_(0),

489 rev_double_index_(0),

490 rev_ptr_index_(0),

491 rev_boolvar_list_index_(0),

492 rev_bools_index_(0),

493 rev_int_memory_index_(0),

494 rev_int64_memory_index_(0),

495 rev_double_memory_index_(0),

496 rev_object_memory_index_(0),

497 rev_object_array_memory_index_(0),

498 info_(info) {}

499

500

501

502namespace {

503

504

505

506

507template <class T>

508struct addrval {

509 public:

510 addrval() : address_(nullptr) {}

511 explicit addrval(T* adr) : address_(adr), old_value_(*adr) {}

512 void restore() const { (*address_) = old_value_; }

513

514 private:

515 T* address_;

516 T old_value_;

517};

518

519

520

521

522

523

524template <class T>

525class TrailPacker {

526 public:

527 explicit TrailPacker(int block_size) : block_size_(block_size) {}

528

529

530 TrailPacker(const TrailPacker&) = delete;

531 TrailPacker& operator=(const TrailPacker&) = delete;

532 virtual ~TrailPacker() {}

533 int input_size() const { return block_size_ * sizeof(addrval<T>); }

534 virtual void Pack(const addrval<T>* block, std::string* packed_block) = 0;

535 virtual void Unpack(const std::string& packed_block, addrval<T>* block) = 0;

536

537 private:

538 const int block_size_;

539};

540

541template <class T>

542class NoCompressionTrailPacker : public TrailPacker<T> {

543 public:

544 explicit NoCompressionTrailPacker(int block_size)

545 : TrailPacker<T>(block_size) {}

546

547

548 NoCompressionTrailPacker(const NoCompressionTrailPacker&) = delete;

549 NoCompressionTrailPacker& operator=(const NoCompressionTrailPacker&) = delete;

550 ~NoCompressionTrailPacker() override {}

551 void Pack(const addrval<T>* block, std::string* packed_block) override {

552 DCHECK(block != nullptr);

553 DCHECK(packed_block != nullptr);

554 absl::string_view block_str(reinterpret_cast<const char*>(block),

555 this->input_size());

556 packed_block->assign(block_str.data(), block_str.size());

557 }

558 void Unpack(const std::string& packed_block, addrval<T>* block) override {

559 DCHECK(block != nullptr);

560 memcpy(block, packed_block.c_str(), packed_block.size());

561 }

562};

563

564template <class T>

565class ZlibTrailPacker : public TrailPacker<T> {

566 public:

567 explicit ZlibTrailPacker(int block_size)

568 : TrailPacker<T>(block_size),

569 tmp_size_(compressBound(this->input_size())),

570 tmp_block_(new char[tmp_size_]) {}

571

572

573 ZlibTrailPacker(const ZlibTrailPacker&) = delete;

574 ZlibTrailPacker& operator=(const ZlibTrailPacker&) = delete;

575

576 ~ZlibTrailPacker() override {}

577

578 void Pack(const addrval<T>* block, std::string* packed_block) override {

579 DCHECK(block != nullptr);

580 DCHECK(packed_block != nullptr);

581 uLongf size = tmp_size_;

582 const int result =

583 compress(reinterpret_cast<Bytef*>(tmp_block_.get()), &size,

584 reinterpret_cast<const Bytef*>(block), this->input_size());

585 CHECK_EQ(Z_OK, result);

586 absl::string_view block_str;

587 block_str = absl::string_view(tmp_block_.get(), size);

588 packed_block->assign(block_str.data(), block_str.size());

589 }

590

591 void Unpack(const std::string& packed_block, addrval<T>* block) override {

592 DCHECK(block != nullptr);

593 uLongf size = this->input_size();

594 const int result =

595 uncompress(reinterpret_cast<Bytef*>(block), &size,

596 reinterpret_cast<const Bytef*>(packed_block.c_str()),

597 packed_block.size());

598 CHECK_EQ(Z_OK, result);

599 }

600

601 private:

602 const uint64_t tmp_size_;

603 std::unique_ptr<char[]> tmp_block_;

604};

605

606template <class T>

607class CompressedTrail {

608 public:

609 CompressedTrail(

610 int block_size,

611 ConstraintSolverParameters::TrailCompression compression_level)

612 : block_size_(block_size),

613 blocks_(nullptr),

614 free_blocks_(nullptr),

615 data_(new addrval<T>[block_size]),

616 buffer_(new addrval<T>[block_size]),

617 buffer_used_(false),

618 current_(0),

619 size_(0) {

620 switch (compression_level) {

621 case ConstraintSolverParameters::NO_COMPRESSION: {

622 packer_.reset(new NoCompressionTrailPacker<T>(block_size));

623 break;

624 }

625 case ConstraintSolverParameters::COMPRESS_WITH_ZLIB: {

626 packer_.reset(new ZlibTrailPacker<T>(block_size));

627 break;

628 }

629 default: {

630 LOG(ERROR) << "Should not be here";

631 }

632 }

633

634

635

636

637

638

639 memset(data_.get(), 0, sizeof(*data_.get()) * block_size);

640 memset(buffer_.get(), 0, sizeof(*buffer_.get()) * block_size);

641 }

642 ~CompressedTrail() {

643 FreeBlocks(blocks_);

644 FreeBlocks(free_blocks_);

645 }

646 const addrval<T>& Back() const {

647

648 DCHECK_GT(current_, 0);

649 return data_[current_ - 1];

650 }

651 void PopBack() {

652 if (size_ > 0) {

653 --current_;

654 if (current_ <= 0) {

655 if (buffer_used_) {

656 data_.swap(buffer_);

657 current_ = block_size_;

658 buffer_used_ = false;

659 } else if (blocks_ != nullptr) {

660 packer_->Unpack(blocks_->compressed, data_.get());

661 FreeTopBlock();

662 current_ = block_size_;

663 }

664 }

665 --size_;

666 }

667 }

668 void PushBack(const addrval<T>& addr_val) {

669 if (current_ >= block_size_) {

670 if (buffer_used_) {

671 NewTopBlock();

672 packer_->Pack(buffer_.get(), &blocks_->compressed);

673

674 data_.swap(buffer_);

675 } else {

676 data_.swap(buffer_);

677 buffer_used_ = true;

678 }

679 current_ = 0;

680 }

681 data_[current_] = addr_val;

682 ++current_;

683 ++size_;

684 }

685 int64_t size() const { return size_; }

686

687 private:

688 struct Block {

689 std::string compressed;

690 Block* next;

691 };

692

693 void FreeTopBlock() {

694 Block* block = blocks_;

695 blocks_ = block->next;

696 block->compressed.clear();

697 block->next = free_blocks_;

698 free_blocks_ = block;

699 }

700 void NewTopBlock() {

701 Block* block = nullptr;

702 if (free_blocks_ != nullptr) {

703 block = free_blocks_;

704 free_blocks_ = block->next;

705 } else {

706 block = new Block;

707 }

708 block->next = blocks_;

709 blocks_ = block;

710 }

711 void FreeBlocks(Block* blocks) {

712 while (nullptr != blocks) {

713 Block* next = blocks->next;

714 delete blocks;

715 blocks = next;

716 }

717 }

718

719 std::unique_ptr<TrailPacker<T>> packer_;

720 const int block_size_;

721 Block* blocks_;

722 Block* free_blocks_;

723 std::unique_ptr<addrval<T>[]> data_;

724 std::unique_ptr<addrval<T>[]> buffer_;

725 bool buffer_used_;

726 int current_;

727 int size_;

728};

729}

730

731

732

733

734

735

736

738

755

763

765 int target = m->rev_int_index_;

766 for (int curr = rev_ints_.size(); curr > target; --curr) {

767 const addrval<int>& cell = rev_ints_.Back();

768 cell.restore();

770 }

771 DCHECK_EQ(rev_ints_.size(), target);

772

773 target = m->rev_int64_index_;

774 for (int curr = rev_int64s_.size(); curr > target; --curr) {

775 const addrval<int64_t>& cell = rev_int64s_.Back();

776 cell.restore();

778 }

780

781 target = m->rev_uint64_index_;

782 for (int curr = rev_uint64s_.size(); curr > target; --curr) {

783 const addrval<uint64_t>& cell = rev_uint64s_.Back();

784 cell.restore();

786 }

788

789 target = m->rev_double_index_;

790 for (int curr = rev_doubles_.size(); curr > target; --curr) {

791 const addrval<double>& cell = rev_doubles_.Back();

792 cell.restore();

794 }

796

797 target = m->rev_ptr_index_;

798 for (int curr = rev_ptrs_.size(); curr > target; --curr) {

799 const addrval<void*>& cell = rev_ptrs_.Back();

800 cell.restore();

802 }

803 DCHECK_EQ(rev_ptrs_.size(), target);

804

805 target = m->rev_boolvar_list_index_;

806 for (int curr = rev_boolvar_list_.size() - 1; curr >= target; --curr) {

809 }

811

813 target = m->rev_bools_index_;

814 for (int curr = rev_bools_.size() - 1; curr >= target; --curr) {

816 }

819

820 target = m->rev_int_memory_index_;

821 for (int curr = rev_int_memory_.size() - 1; curr >= target; --curr) {

823 }

825

826 target = m->rev_int64_memory_index_;

827 for (int curr = rev_int64_memory_.size() - 1; curr >= target; --curr) {

829 }

831

832 target = m->rev_double_memory_index_;

833 for (int curr = rev_double_memory_.size() - 1; curr >= target; --curr) {

835 }

837

838 target = m->rev_object_memory_index_;

839 for (int curr = rev_object_memory_.size() - 1; curr >= target; --curr) {

841 }

843

844 target = m->rev_object_array_memory_index_;

846 --curr) {

848 }

850

851 target = m->rev_memory_index_;

852 for (int curr = rev_memory_.size() - 1; curr >= target; --curr) {

853

854 ::operator delete(reinterpret_cast<char*>(rev_memory_[curr]));

855

856

857

858

859

860 }

862

863 target = m->rev_memory_array_index_;

864 for (int curr = rev_memory_array_.size() - 1; curr >= target; --curr) {

866

867 }

869 }

870};

871

872void Solver::InternalSaveValue(int* valptr) {

873 trail_->rev_ints_.PushBack(addrval<int>(valptr));

874}

875

876void Solver::InternalSaveValue(int64_t* valptr) {

877 trail_->rev_int64s_.PushBack(addrval<int64_t>(valptr));

878}

879

880void Solver::InternalSaveValue(uint64_t* valptr) {

881 trail_->rev_uint64s_.PushBack(addrval<uint64_t>(valptr));

882}

883

884void Solver::InternalSaveValue(double* valptr) {

885 trail_->rev_doubles_.PushBack(addrval<double>(valptr));

886}

887

888void Solver::InternalSaveValue(void** valptr) {

889 trail_->rev_ptrs_.PushBack(addrval<void*>(valptr));

890}

891

892

893

894

895void Solver::InternalSaveValue(bool* valptr) {

896 trail_->rev_bools_.push_back(valptr);

897 trail_->rev_bool_value_.push_back(*valptr);

898}

899

901 check_alloc_state();

902 trail_->rev_object_memory_.push_back(ptr);

903 return ptr;

904}

905

906int* Solver::SafeRevAllocArray(int* ptr) {

907 check_alloc_state();

908 trail_->rev_int_memory_.push_back(ptr);

909 return ptr;

910}

911

912int64_t* Solver::SafeRevAllocArray(int64_t* ptr) {

913 check_alloc_state();

914 trail_->rev_int64_memory_.push_back(ptr);

915 return ptr;

916}

917

918double* Solver::SafeRevAllocArray(double* ptr) {

919 check_alloc_state();

920 trail_->rev_double_memory_.push_back(ptr);

921 return ptr;

922}

923

924uint64_t* Solver::SafeRevAllocArray(uint64_t* ptr) {

925 check_alloc_state();

926 trail_->rev_int64_memory_.push_back(reinterpret_cast<int64_t*>(ptr));

927 return ptr;

928}

929

931 check_alloc_state();

932 trail_->rev_object_array_memory_.push_back(ptr);

933 return ptr;

934}

935

936IntVar** Solver::SafeRevAllocArray(IntVar** ptr) {

937 BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));

938 return reinterpret_cast<IntVar**>(in);

939}

940

942 BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));

943 return reinterpret_cast<IntExpr**>(in);

944}

945

947 BaseObject** in = SafeRevAllocArray(reinterpret_cast<BaseObject**>(ptr));

948 return reinterpret_cast<Constraint**>(in);

949}

950

951void* Solver::UnsafeRevAllocAux(void* ptr) {

952 check_alloc_state();

953 trail_->rev_memory_.push_back(ptr);

954 return ptr;

955}

956

957void** Solver::UnsafeRevAllocArrayAux(void** ptr) {

958 check_alloc_state();

959 trail_->rev_memory_array_.push_back(ptr);

960 return ptr;

961}

962

964 solver->trail_->rev_boolvar_list_.push_back(var);

965}

966

967

968

970 public:

972 : solver_(s),

973 marker_stack_(),

974 monitor_event_listeners_(to_underlying(Solver::MonitorEvent::kLast)),

975 fail_buffer_(),

976 solution_counter_(0),

977 unchecked_solution_counter_(0),

978 decision_builder_(nullptr),

979 created_by_solve_(false),

980 search_depth_(0),

981 left_search_depth_(0),

982 should_restart_(false),

983 should_finish_(false),

984 sentinel_pushed_(0),

985 jmpbuf_filled_(false),

986 backtrack_at_the_end_of_the_search_(true) {}

987

988

989

990

992 : solver_(s),

993 marker_stack_(),

994 monitor_event_listeners_(to_underlying(Solver::MonitorEvent::kLast)),

995 fail_buffer_(),

996 solution_counter_(0),

997 unchecked_solution_counter_(0),

998 decision_builder_(nullptr),

999 created_by_solve_(false),

1000 search_depth_(-1),

1001 left_search_depth_(-1),

1002 should_restart_(false),

1003 should_finish_(false),

1004 sentinel_pushed_(0),

1005 jmpbuf_filled_(false),

1006 backtrack_at_the_end_of_the_search_(true) {}

1007

1009

1034 if (monitor != nullptr) {

1035 monitor_event_listeners_[to_underlying(event)].push_back(monitor);

1036 }

1037 }

1040 return monitor_event_listeners_[to_underlying(event)];

1041 }

1047 return unchecked_solution_counter_;

1048 }

1050 decision_builder_ = db;

1051 }

1058 search_depth_++;

1059 left_search_depth_++;

1060 }

1063 return backtrack_at_the_end_of_the_search_;

1064 }

1066 backtrack_at_the_end_of_the_search_ = restore;

1067 }

1077 if (should_finish_ || should_restart_) {

1078 solver_->Fail();

1079 }

1080 }

1086

1087 private:

1088

1089 void JumpBack();

1090 void ClearBuffer() {

1091 CHECK(jmpbuf_filled_) << "Internal error in backtracking";

1092 jmpbuf_filled_ = false;

1093 }

1094

1095 Solver* const solver_;

1096 std::vector<StateMarker*> marker_stack_;

1097 std::vector<std::vector<SearchMonitor*>> monitor_event_listeners_;

1098 jmp_buf fail_buffer_;

1099 int64_t solution_counter_;

1100 int64_t unchecked_solution_counter_;

1102 bool created_by_solve_;

1104 int search_depth_;

1105 int left_search_depth_;

1106 bool should_restart_;

1107 bool should_finish_;

1108 int sentinel_pushed_;

1109 bool jmpbuf_filled_;

1110 bool backtrack_at_the_end_of_the_search_;

1111 std::string search_context_;

1112};

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124#ifndef CP_USE_EXCEPTIONS_FOR_BACKTRACK

1125

1126

1127#define CP_TRY(search) \

1128 CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \

1129 search->jmpbuf_filled_ = true; \

1130 if (setjmp(search->fail_buffer_) == 0)

1131#define CP_ON_FAIL else

1132#define CP_DO_FAIL(search) longjmp(search->fail_buffer_, 1)

1133#else

1134class FailException {};

1135#define CP_TRY(search) \

1136 CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \

1137 search->jmpbuf_filled_ = true; \

1138 try

1139#define CP_ON_FAIL catch (FailException&)

1140#define CP_DO_FAIL(search) throw FailException()

1141#endif

1142

1143void Search::JumpBack() {

1144 if (jmpbuf_filled_) {

1145 jmpbuf_filled_ = false;

1147 } else {

1148 std::string explanation = "Failure outside of search";

1149 solver_->AddConstraint(solver_->MakeFalseConstraint(explanation));

1150 }

1151}

1152

1154

1155namespace {

1157 public:

1159 : selector_(std::move(bs)) {}

1160 ~ApplyBranchSelector() override {}

1161

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

1163 s->SetBranchSelector(selector_);

1164 return nullptr;

1165 }

1166

1167 std::string DebugString() const override { return "Apply(BranchSelector)"; }

1168

1169 private:

1171};

1172}

1173

1175 selector_ = std::move(bs);

1176}

1177

1179

1180

1181

1182 const int solve_depth = SolveDepth();

1184 [solve_depth](Solver* s) {

1185 if (s->SolveDepth() == solve_depth) {

1187 }

1188 },

1189 false);

1190 searches_.back()->SetBranchSelector(std::move(bs));

1191}

1192

1194 return RevAlloc(new ApplyBranchSelector(std::move(bs)));

1195}

1196

1198 return state_ == OUTSIDE_SEARCH ? 0 : searches_.size() - 1;

1199}

1200

1202

1204 return searches_.back()->left_search_depth();

1205}

1206

1208 if (selector_ != nullptr) {

1209 return selector_();

1210 }

1212}

1213

1215 for (auto& listeners : monitor_event_listeners_) listeners.clear();

1216 search_depth_ = 0;

1217 left_search_depth_ = 0;

1218 selector_ = nullptr;

1219 backtrack_at_the_end_of_the_search_ = true;

1220}

1221

1222#define CALL_EVENT_LISTENERS(Event) \

1223 do { \

1224 ForAll(GetEventListeners(Solver::MonitorEvent::k##Event), \

1225 &SearchMonitor::Event); \

1226 } while (false)

1227

1229

1230

1231

1232 solution_counter_ = 0;

1233 unchecked_solution_counter_ = 0;

1234

1236}

1237

1242

1244

1250

1256

1262

1268

1274

1276

1278

1282

1286

1288 bool valid = true;

1291 if (!monitor->AcceptSolution()) {

1292

1293

1294

1295 valid = false;

1296 }

1297 }

1298 return valid;

1299}

1300

1302 bool should_continue = false;

1305 if (monitor->AtSolution()) {

1306

1307

1308

1309 should_continue = true;

1310 }

1311 }

1312 return should_continue;

1313}

1314

1316

1318 bool continue_at_local_optimum = false;

1321 if (monitor->AtLocalOptimum()) {

1322 continue_at_local_optimum = true;

1323 }

1324 }

1325 return continue_at_local_optimum;

1326}

1327

1329 bool accept = true;

1332 if (!monitor->AcceptDelta(delta, deltadelta)) {

1333 accept = false;

1334 }

1335 }

1336 return accept;

1337}

1338

1340

1344

1348 if (monitor->IsUncheckedSolutionLimitReached()) {

1349 return true;

1350 }

1351 }

1352 return false;

1353}

1354

1356

1361 progress = std::max(progress, monitor->ProgressPercent());

1362 }

1363 return progress;

1364}

1365

1369 if (decision_builder_ != nullptr) {

1370 decision_builder_->Accept(visitor);

1371 }

1372}

1373

1374#undef CALL_EVENT_LISTENERS

1375

1379

1381 return search->AcceptDelta(delta, deltadelta);

1382}

1383

1385

1389

1390namespace {

1391

1392

1393

1394class FailDecision : public Decision {

1395 public:

1396 void Apply(Solver* const s) override { s->Fail(); }

1397 void Refute(Solver* const s) override { s->Fail(); }

1398};

1399

1400

1401

1402class BalancingDecision : public Decision {

1403 public:

1404 ~BalancingDecision() override {}

1405 void Apply(Solver* const ) override {}

1406 void Refute(Solver* const ) override {}

1407};

1408}

1409

1411

1412

1413

1414

1415

1416namespace {

1417enum SentinelMarker {

1418 INITIAL_SEARCH_SENTINEL = 10000000,

1419 ROOT_NODE_SENTINEL = 20000000,

1420 SOLVER_CTOR_SENTINEL = 40000000

1421};

1422}

1423

1427

1429

1430namespace {

1433 << "Were parameters built using Solver::DefaultSolverParameters() ?";

1434}

1435}

1436

1439 : name_(name),

1443 use_fast_local_search_(true),

1445 Init();

1446}

1447

1449 : name_(name),

1453 use_fast_local_search_(true),

1455 Init();

1456}

1457

1458void Solver::Init() {

1459 CheckSolverParameters(parameters_);

1460 queue_ = std::make_unique<Queue>(this);

1461 trail_ = std::make_unique<Trail>(parameters_.trail_block_size(),

1464 branches_ = 0;

1465 fails_ = 0;

1466 decisions_ = 0;

1467 neighbors_ = 0;

1468 filtered_neighbors_ = 0;

1469 accepted_neighbors_ = 0;

1470 optimization_direction_ = NOT_SET;

1471 timer_ = std::make_unique<ClockTimer>();

1472 searches_.assign(1, new Search(this, 0));

1473 fail_stamp_ = uint64_t{1};

1474 balancing_decision_ = std::make_unique<BalancingDecision>();

1475 fail_intercept_ = nullptr;

1476 true_constraint_ = nullptr;

1477 false_constraint_ = nullptr;

1478 fail_decision_ = std::make_unique<FailDecision>();

1479 constraint_index_ = 0;

1480 additional_constraint_index_ = 0;

1481 num_int_vars_ = 0;

1482 propagation_monitor_.reset(BuildTrace(this));

1484 print_trace_ = nullptr;

1485 anonymous_variable_index_ = 0;

1486 should_fail_ = false;

1487

1489 demon_runs_[i] = 0;

1490 }

1491 searches_.push_back(new Search(this));

1492 PushSentinel(SOLVER_CTOR_SENTINEL);

1493 InitCachedIntConstants();

1494 InitCachedConstraint();

1495 timer_->Restart();

1499 reinterpret_cast<LocalSearchMonitor*>(local_search_profiler_));

1500}

1501

1503

1504 CHECK_EQ(2, searches_.size());

1505 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

1506

1509

1510 DCHECK_EQ(finalType, SENTINEL);

1511

1512 DCHECK_EQ(info.int_info, SOLVER_CTOR_SENTINEL);

1516}

1517

1519 std::string out = "Solver(name = \"" + name_ + "\", state = ";

1520 switch (state_) {

1522 out += "OUTSIDE_SEARCH";

1523 break;

1525 out += "IN_ROOT_NODE";

1526 break;

1528 out += "IN_SEARCH";

1529 break;

1531 out += "AT_SOLUTION";

1532 break;

1534 out += "NO_MORE_SOLUTIONS";

1535 break;

1537 out += "PROBLEM_INFEASIBLE";

1538 break;

1539 }

1540 absl::StrAppendFormat(

1541 &out,

1542 ", branches = %d, fails = %d, decisions = %d, delayed demon runs = %d, "

1543 "var demon runs = %d, normal demon runs = %d, Run time = %d ms)",

1544 branches_, fails_, decisions_, demon_runs_[DELAYED_PRIORITY],

1546 return out;

1547}

1548

1550

1552 return absl::ToInt64Milliseconds(timer_->GetDuration());

1553}

1554

1556 return absl::FromUnixSeconds(0) + timer_->GetDuration();

1557}

1558

1560 return TopLevelSearch()->solution_counter();

1561}

1562

1564 return TopLevelSearch()->unchecked_solution_counter();

1565}

1566

1567void Solver::IncrementUncheckedSolutionCounter() {

1569}

1570

1571bool Solver::IsUncheckedSolutionLimitReached() {

1573}

1574

1576

1578

1588

1593

1599

1603 m->rev_int_index_ = trail_->rev_ints_.size();

1604 m->rev_int64_index_ = trail_->rev_int64s_.size();

1605 m->rev_uint64_index_ = trail_->rev_uint64s_.size();

1606 m->rev_double_index_ = trail_->rev_doubles_.size();

1607 m->rev_ptr_index_ = trail_->rev_ptrs_.size();

1608 m->rev_boolvar_list_index_ = trail_->rev_boolvar_list_.size();

1609 m->rev_bools_index_ = trail_->rev_bools_.size();

1610 m->rev_int_memory_index_ = trail_->rev_int_memory_.size();

1611 m->rev_int64_memory_index_ = trail_->rev_int64_memory_.size();

1612 m->rev_double_memory_index_ = trail_->rev_double_memory_.size();

1613 m->rev_object_memory_index_ = trail_->rev_object_memory_.size();

1614 m->rev_object_array_memory_index_ = trail_->rev_object_array_memory_.size();

1615 m->rev_memory_index_ = trail_->rev_memory_.size();

1616 m->rev_memory_array_index_ = trail_->rev_memory_array_.size();

1617 }

1618 searches_.back()->marker_stack_.push_back(m);

1619 queue_->increase_stamp();

1620}

1621

1623 StateInfo info(std::move(a), fast);

1625}

1626

1628 CHECK(!searches_.back()->marker_stack_.empty())

1629 << "PopState() on an empty stack";

1630 CHECK(info != nullptr);

1631 StateMarker* const m = searches_.back()->marker_stack_.back();

1633 trail_->BacktrackTo(m);

1634 }

1636 (*info) = m->info_;

1637 searches_.back()->marker_stack_.pop_back();

1638 delete m;

1639 queue_->increase_stamp();

1640 return t;

1641}

1642

1643void Solver::check_alloc_state() {

1644 switch (state_) {

1650 break;

1652 LOG(FATAL) << "allocating at a leaf node";

1653 default:

1654 LOG(FATAL) << "This switch was supposed to be exhaustive, but it is not!";

1655 }

1656}

1657

1658void Solver::FreezeQueue() { queue_->Freeze(); }

1659

1660void Solver::UnfreezeQueue() { queue_->Unfreeze(); }

1661

1662void Solver::EnqueueVar(Demon* const d) { queue_->EnqueueVar(d); }

1663

1664void Solver::EnqueueDelayedDemon(Demon* const d) {

1665 queue_->EnqueueDelayedDemon(d);

1666}

1667

1669 queue_->ExecuteAll(demons);

1670}

1671

1673 queue_->EnqueueAll(demons);

1674}

1675

1677

1679

1680void Solver::set_action_on_fail(Action a) {

1681 queue_->set_action_on_fail(std::move(a));

1682}

1683

1684void Solver::set_variable_to_clean_on_fail(IntVar* v) {

1685 queue_->set_variable_to_clean_on_fail(v);

1686}

1687

1688void Solver::reset_action_on_fail() { queue_->reset_action_on_fail(); }

1689

1691 DCHECK(c != nullptr);

1692 if (c == true_constraint_) {

1693 return;

1694 }

1696 queue_->AddConstraint(c);

1698 DCHECK_GE(constraint_index_, 0);

1699 DCHECK_LE(constraint_index_, constraints_list_.size());

1700 const int constraint_parent =

1701 constraint_index_ == constraints_list_.size()

1702 ? additional_constraints_parent_list_[additional_constraint_index_]

1703 : constraint_index_;

1704 additional_constraints_list_.push_back(c);

1705 additional_constraints_parent_list_.push_back(constraint_parent);

1706 } else {

1707 if (parameters_.print_added_constraints()) {

1708 LOG(INFO) << c->DebugString();

1709 }

1710 constraints_list_.push_back(c);

1711 }

1712}

1713

1715 IntVar* const target_var, IntExpr* const expr) {

1716 if (constraint != nullptr) {

1718 cast_constraints_.insert(constraint);

1719 cast_information_[target_var] =

1721 }

1723 }

1724}

1725

1731

1732void Solver::ProcessConstraints() {

1733

1734

1738 }

1742 }

1743

1744 if (parameters_.disable_solve()) {

1745 LOG(INFO) << "Forcing early failure";

1747 }

1748

1749

1750 const int constraints_size = constraints_list_.size();

1751 additional_constraints_list_.clear();

1752 additional_constraints_parent_list_.clear();

1753

1754 for (constraint_index_ = 0; constraint_index_ < constraints_size;

1755 ++constraint_index_) {

1756 Constraint* const constraint = constraints_list_[constraint_index_];

1757 propagation_monitor_->BeginConstraintInitialPropagation(constraint);

1758 constraint->PostAndPropagate();

1759 propagation_monitor_->EndConstraintInitialPropagation(constraint);

1760 }

1761 CHECK_EQ(constraints_list_.size(), constraints_size);

1762

1763

1764 for (int additional_constraint_index_ = 0;

1765 additional_constraint_index_ < additional_constraints_list_.size();

1766 ++additional_constraint_index_) {

1768 additional_constraints_list_[additional_constraint_index_];

1769 const int parent_index =

1770 additional_constraints_parent_list_[additional_constraint_index_];

1771 Constraint* const parent = constraints_list_[parent_index];

1772 propagation_monitor_->BeginNestedConstraintInitialPropagation(parent,

1773 nested);

1774 nested->PostAndPropagate();

1775 propagation_monitor_->EndNestedConstraintInitialPropagation(parent, nested);

1776 }

1777}

1778

1781 DCHECK(searches_.back() != nullptr);

1782 return searches_.back()->created_by_solve();

1783}

1784

1786 return Solve(db, std::vector<SearchMonitor*>{m1});

1787}

1788

1790

1793 return Solve(db, {m1, m2});

1794}

1795

1798 return Solve(db, {m1, m2, m3});

1799}

1800

1804 return Solve(db, {m1, m2, m3, m4});

1805}

1806

1808 const std::vector<SearchMonitor*>& monitors) {

1810 searches_.back()->set_created_by_solve(true);

1812 const bool solution_found = searches_.back()->solution_counter() > 0;

1814 return solution_found;

1815}

1816

1818 return NewSearch(db, std::vector<SearchMonitor*>{m1});

1819}

1820

1822

1827

1830 return NewSearch(db, {m1, m2, m3});

1831}

1832

1836 return NewSearch(db, {m1, m2, m3, m4});

1837}

1838

1840

1841

1843 const std::vector<SearchMonitor*>& monitors) {

1844

1845

1846 CHECK(db != nullptr);

1847 const bool nested = state_ == IN_SEARCH;

1848

1850 LOG(FATAL) << "Cannot start new searches here.";

1851 }

1852

1853 Search* const search = nested ? new Search(this) : searches_.back();

1855

1856

1857

1858 if (nested) {

1859

1860 DCHECK_GE(searches_.size(), 2);

1861 searches_.push_back(search);

1862 } else {

1863

1864

1865 DCHECK_EQ(2, searches_.size());

1866

1867 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

1869 }

1870

1871

1872

1873

1874 propagation_monitor_->Install();

1875 if (demon_profiler_ != nullptr) {

1877 }

1878 local_search_monitor_->Install();

1879 if (local_search_profiler_ != nullptr) {

1881 }

1882

1883

1885 if (monitor != nullptr) {

1886 monitor->Install();

1887 }

1888 }

1889 std::vector<SearchMonitor*> extras;

1892 if (monitor != nullptr) {

1893 monitor->Install();

1894 }

1895 }

1896

1897

1898 if (nested) {

1899 if (print_trace_ != nullptr) {

1900 print_trace_->Install();

1901 }

1902 } else {

1903 print_trace_ = nullptr;

1904 if (parameters_.trace_propagation()) {

1906 print_trace_->Install();

1907 } else if (parameters_.trace_search()) {

1908

1909

1910

1911

1914 }

1915 }

1916

1917

1918

1920

1921

1922 PushSentinel(INITIAL_SEARCH_SENTINEL);

1924}

1925

1926

1927

1928bool Solver::BacktrackOneLevel(Decision** const fail_decision) {

1929 bool no_more_solutions = false;

1930 bool end_loop = false;

1931 while (!end_loop) {

1934 switch (t) {

1936 CHECK_EQ(info.ptr_info, this) << "Wrong sentinel found";

1939 searches_.back()->sentinel_pushed_--;

1940 no_more_solutions = true;

1941 end_loop = true;

1942 break;

1944 LOG(ERROR) << "Simple markers should not be encountered during search";

1945 break;

1947 if (info.int_info == 0) {

1948 (*fail_decision) = reinterpret_cast<Decision*>(info.ptr_info);

1949 end_loop = true;

1950 searches_.back()->set_search_depth(info.depth);

1951 searches_.back()->set_search_left_depth(info.left_depth);

1952 }

1953 break;

1957 }

1958 break;

1959 }

1960 }

1961 }

1962 Search* const search = searches_.back();

1963 search->EndFail();

1964 fail_stamp_++;

1965 if (no_more_solutions) {

1966 search->NoMoreSolutions();

1967 }

1968 return no_more_solutions;

1969}

1970

1971void Solver::PushSentinel(int magic_code) {

1972 StateInfo info(this, magic_code);

1974

1975 if (magic_code != SOLVER_CTOR_SENTINEL) {

1976 searches_.back()->sentinel_pushed_++;

1977 }

1978 const int pushed = searches_.back()->sentinel_pushed_;

1979 DCHECK((magic_code == SOLVER_CTOR_SENTINEL) ||

1980 (magic_code == INITIAL_SEARCH_SENTINEL && pushed == 1) ||

1981 (magic_code == ROOT_NODE_SENTINEL && pushed == 2));

1982}

1983

1985 Search* const search = searches_.back();

1986 CHECK_NE(0, search->sentinel_pushed_);

1987 if (SolveDepth() == 1) {

1988 if (search->sentinel_pushed_ > 1) {

1989 BacktrackToSentinel(ROOT_NODE_SENTINEL);

1990 }

1991 CHECK_EQ(1, search->sentinel_pushed_);

1992 PushSentinel(ROOT_NODE_SENTINEL);

1994 } else {

1996 if (search->sentinel_pushed_ > 0) {

1997 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

1998 }

1999 CHECK_EQ(0, search->sentinel_pushed_);

2000 PushSentinel(INITIAL_SEARCH_SENTINEL);

2001 }

2002

2004}

2005

2006

2007

2008void Solver::BacktrackToSentinel(int magic_code) {

2009 Search* const search = searches_.back();

2010 bool end_loop = search->sentinel_pushed_ == 0;

2011 while (!end_loop) {

2014 switch (t) {

2016 CHECK_EQ(info.ptr_info, this) << "Wrong sentinel found";

2017 CHECK_GE(--search->sentinel_pushed_, 0);

2020

2021 if (info.int_info == magic_code) {

2022 end_loop = true;

2023 }

2024 break;

2025 }

2027 break;

2029 break;

2032 break;

2033 }

2034 }

2035 }

2036 fail_stamp_++;

2037}

2038

2039

2040void Solver::JumpToSentinelWhenNested() {

2041 CHECK_GT(SolveDepth(), 1) << "calling JumpToSentinel from top level";

2042 Search* c = searches_.back();

2043 Search* p = ParentSearch();

2044 bool found = false;

2045 while (!c->marker_stack_.empty()) {

2046 StateMarker* const m = c->marker_stack_.back();

2048 p->marker_stack_.push_back(m);

2049 } else {

2051 CHECK_EQ(c->marker_stack_.size(), 1) << "Sentinel found too early";

2052 found = true;

2053 }

2054 delete m;

2055 }

2056 c->marker_stack_.pop_back();

2057 }

2058 c->set_search_depth(0);

2059 c->set_search_left_depth(0);

2060 CHECK_EQ(found, true) << "Sentinel not found";

2061}

2062

2063namespace {

2064class ReverseDecision : public Decision {

2065 public:

2066 explicit ReverseDecision(Decision* const d) : decision_(d) {

2067 CHECK(d != nullptr);

2068 }

2069 ~ReverseDecision() override {}

2070

2071 void Apply(Solver* const s) override { decision_->Refute(s); }

2072

2073 void Refute(Solver* const s) override { decision_->Apply(s); }

2074

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

2076 decision_->Accept(visitor);

2077 }

2078

2079 std::string DebugString() const override {

2080 std::string str = "Reverse(";

2081 str += decision_->DebugString();

2082 str += ")";

2083 return str;

2084 }

2085

2086 private:

2087 Decision* const decision_;

2088};

2089}

2090

2091

2093 Search* const search = searches_.back();

2095 const int solve_depth = SolveDepth();

2096 const bool top_level = solve_depth <= 1;

2097

2099 LOG(WARNING) << "NextSolution() called without a NewSearch before";

2100 return false;

2101 }

2102

2103 if (top_level) {

2104 switch (state_) {

2106 return false;

2108 return false;

2110 if (BacktrackOneLevel(&fd)) {

2112 return false;

2113 }

2115 break;

2116 }

2121 ProcessConstraints();

2123 PushSentinel(ROOT_NODE_SENTINEL);

2125 search->ClearBuffer();

2126 }

2128 queue_->AfterFailure();

2129 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

2131 return false;

2132 }

2133 break;

2134 }

2135 case IN_SEARCH:

2136 break;

2138 LOG(FATAL) << "Should not happen";

2139 break;

2140 }

2141 }

2142

2143 volatile bool finish = false;

2144 volatile bool result = false;

2146

2147 while (!finish) {

2149 if (fd != nullptr) {

2154 branches_++;

2156

2157

2161 fd = nullptr;

2162 }

2164 for (;;) {

2166 d = db->Next(this);

2168 if (d == fail_decision_.get()) {

2169 Fail();

2170 }

2171 if (d != nullptr) {

2173 switch (modification) {

2175 d = RevAlloc(new ReverseDecision(d));

2176

2177 ABSL_FALLTHROUGH_INTENDED;

2178 }

2180 decisions_++;

2185 branches_++;

2190 break;

2191 }

2197 break;

2198 }

2204 break;

2205 }

2208 }

2209 }

2210 } else {

2211 break;

2212 }

2213 }

2217 result = true;

2218 finish = true;

2219 } else {

2221 }

2222 } else {

2224 }

2225 }

2227 queue_->AfterFailure();

2229 fd = nullptr;

2230 BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL

2231 : INITIAL_SEARCH_SENTINEL);

2232 result = false;

2233 finish = true;

2236

2238 fd = nullptr;

2239 BacktrackToSentinel(top_level ? ROOT_NODE_SENTINEL

2240 : INITIAL_SEARCH_SENTINEL);

2243 PushSentinel(top_level ? ROOT_NODE_SENTINEL : INITIAL_SEARCH_SENTINEL);

2245 } else {

2246 if (BacktrackOneLevel(&fd)) {

2247 result = false;

2248 finish = true;

2249 }

2250 }

2251 }

2252 }

2253 if (result) {

2254 search->ClearBuffer();

2255 }

2256 if (top_level) {

2258 }

2259 return result;

2260}

2261

2263 Search* const search = searches_.back();

2265 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

2266 } else {

2267 CHECK_GT(searches_.size(), 2);

2268 if (search->sentinel_pushed_ > 0) {

2269 JumpToSentinelWhenNested();

2270 }

2271 }

2273 search->Clear();

2274 if (2 == searches_.size()) {

2275

2277

2278 if (!parameters_.profile_file().empty()) {

2279 const std::string& file_name = parameters_.profile_file();

2280 LOG(INFO) << "Exporting profile to " << file_name;

2282 }

2283 if (parameters_.print_local_search_profile()) {

2285 if (!profile.empty()) LOG(INFO) << profile;

2286 }

2287 } else {

2288 delete search;

2289 searches_.pop_back();

2290 }

2291}

2292

2296 LOG(FATAL) << "CheckAssignment is only available at the top level.";

2297 }

2298

2299 Search* const search = searches_.back();

2301

2302 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

2304

2305

2307

2308

2310 DCHECK_EQ(2, searches_.size());

2311 PushSentinel(INITIAL_SEARCH_SENTINEL);

2316 restore->Next(this);

2317 ProcessConstraints();

2319 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

2320 search->ClearBuffer();

2322 return true;

2323 }

2325 const int index =

2326 constraint_index_ < constraints_list_.size()

2327 ? constraint_index_

2328 : additional_constraints_parent_list_[additional_constraint_index_];

2329 Constraint* const ct = constraints_list_[index];

2330 if (ct->name().empty()) {

2331 LOG(INFO) << "Failing constraint = " << ct->DebugString();

2332 } else {

2333 LOG(INFO) << "Failing constraint = " << ct->name() << ":"

2335 }

2336 queue_->AfterFailure();

2337 BacktrackToSentinel(INITIAL_SEARCH_SENTINEL);

2339 return false;

2340 }

2341}

2342

2343namespace {

2344class AddConstraintDecisionBuilder : public DecisionBuilder {

2345 public:

2346 explicit AddConstraintDecisionBuilder(Constraint* const ct)

2347 : constraint_(ct) {

2348 CHECK(ct != nullptr);

2349 }

2350

2351 ~AddConstraintDecisionBuilder() override {}

2352

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

2354 solver->AddConstraint(constraint_);

2355 return nullptr;

2356 }

2357

2358 std::string DebugString() const override {

2359 return absl::StrFormat("AddConstraintDecisionBuilder(%s)",

2360 constraint_->DebugString());

2361 }

2362

2363 private:

2364 Constraint* const constraint_;

2365};

2366}

2367

2369 return RevAlloc(new AddConstraintDecisionBuilder(ct));

2370}

2371

2375

2378 return SolveAndCommit(db, std::vector<SearchMonitor*>{m1});

2379}

2380

2384

2389

2394

2396 const std::vector<SearchMonitor*>& monitors) {

2398 searches_.back()->set_created_by_solve(true);

2399 searches_.back()->set_backtrack_at_the_end_of_the_search(false);

2401 const bool solution_found = searches_.back()->solution_counter() > 0;

2403 return solution_found;

2404}

2405

2407 if (fail_intercept_) {

2408 fail_intercept_();

2409 return;

2410 }

2412 fails_++;

2413 searches_.back()->BeginFail();

2414 searches_.back()->JumpBack();

2415}

2416

2418 searches_.back()->set_should_finish(true);

2419}

2420

2422 searches_.back()->set_should_restart(true);

2423}

2424

2425

2426

2430 if (cast_info != nullptr) {

2432 }

2433 return nullptr;

2434}

2435

2436

2437

2439 const std::string* name = gtl::FindOrNull(propagation_object_names_, object);

2440 if (name != nullptr) {

2441 return *name;

2442 }

2443 const IntegerCastInfo* const cast_info =

2445 if (cast_info != nullptr && cast_info->expression != nullptr) {

2446 if (cast_info->expression->HasName()) {

2447 return absl::StrFormat("Var<%s>", cast_info->expression->name());

2448 } else if (parameters_.name_cast_variables()) {

2449 return absl::StrFormat("Var<%s>", cast_info->expression->DebugString());

2450 } else {

2451 const std::string new_name =

2452 absl::StrFormat("CastVar<%d>", anonymous_variable_index_++);

2453 propagation_object_names_[object] = new_name;

2454 return new_name;

2455 }

2456 }

2457 const std::string base_name = object->BaseName();

2458 if (parameters_.name_all_variables() && !base_name.empty()) {

2459 const std::string new_name =

2460 absl::StrFormat("%s_%d", base_name, anonymous_variable_index_++);

2461 propagation_object_names_[object] = new_name;

2462 return new_name;

2463 }

2464 return empty_name_;

2465}

2466

2468 absl::string_view name) {

2469 if (parameters_.store_names() &&

2470 GetName(object) != name) {

2471 propagation_object_names_[object] = name;

2472 }

2473}

2474

2476 return propagation_object_names_.contains(

2478 (!object->BaseName().empty() && parameters_.name_all_variables());

2479}

2480

2481

2482

2487

2492

2493

2494

2496 return solver_->GetName(this);

2497}

2498

2500 solver_->SetName(this, name);

2501}

2502

2504

2506

2508 solver_->ExecuteAll(demons);

2509}

2510

2512 solver_->EnqueueAll(demons);

2513}

2514

2515

2516

2518

2520 return name_.empty() ? DebugString() : name_;

2521}

2522

2524 Solver* const , std::vector<SearchMonitor*>* const ) {}

2525

2527

2528

2529

2533

2535 [[maybe_unused]] int64_t value) {}

2537 [[maybe_unused]] IntVar* const var, [[maybe_unused]] int64_t value,

2538 [[maybe_unused]] bool start_with_lower_half) {}

2541 [[maybe_unused]] IntervalVar* const var, [[maybe_unused]] int64_t est) {}

2543 [[maybe_unused]] IntervalVar* const var, [[maybe_unused]] int64_t est) {}

2545 [[maybe_unused]] SequenceVar* const sequence, [[maybe_unused]] int index) {}

2546

2548 [[maybe_unused]] SequenceVar* const sequence, [[maybe_unused]] int index) {}

2549

2550

2551

2552

2553

2622 "ScalarProductGreaterOrEqual";

2638

2646

2650 "VariableUsageLessConstant";

2652 "WeightedSumOfAssignedEqualVariable";

2653

2715

2717

2727

2728

2729

2731

2733 [[maybe_unused]] const std::string& type_name) {}

2735 [[maybe_unused]] const std::string& type_name) {}

2736

2738 [[maybe_unused]] const std::string& type_name,

2739 [[maybe_unused]] const Constraint* const constraint) {}

2741 [[maybe_unused]] const std::string& type_name,

2742 [[maybe_unused]] const Constraint* const constraint) {}

2743

2745 [[maybe_unused]] const std::string& type) {}

2748

2750 [[maybe_unused]] const std::string& type_name,

2751 [[maybe_unused]] const IntExpr* const expr) {}

2753 [[maybe_unused]] const std::string& type_name,

2754 [[maybe_unused]] const IntExpr* const expr) {}

2755

2757 [[maybe_unused]] const IntVar* const variable, IntExpr* const delegate) {

2758 if (delegate != nullptr) {

2759 delegate->Accept(this);

2760 }

2761}

2762

2764 [[maybe_unused]] const IntVar* const variable,

2765 [[maybe_unused]] const std::string& operation,

2766 [[maybe_unused]] int64_t value, IntVar* const delegate) {

2767 if (delegate != nullptr) {

2768 delegate->Accept(this);

2769 }

2770}

2771

2773 [[maybe_unused]] const IntervalVar* const variable,

2774 [[maybe_unused]] const std::string& operation,

2775 [[maybe_unused]] int64_t value, IntervalVar* const delegate) {

2776 if (delegate != nullptr) {

2777 delegate->Accept(this);

2778 }

2779}

2780

2782 for (int i = 0; i < variable->size(); ++i) {

2784 }

2785}

2786

2788 [[maybe_unused]] const std::string& arg_name,

2789 [[maybe_unused]] int64_t value) {}

2790

2792 [[maybe_unused]] const std::string& arg_name,

2793 [[maybe_unused]] const std::vector<int64_t>& values) {}

2794

2796 [[maybe_unused]] const std::string& arg_name,

2797 [[maybe_unused]] const IntTupleSet& tuples) {}

2798

2800 [[maybe_unused]] const std::string& arg_name, IntExpr* const argument) {

2801 argument->Accept(this);

2802}

2803

2805 [[maybe_unused]] const std::string& arg_name,

2807

2809 [[maybe_unused]] const std::string& arg_name,

2810 const std::vector<IntVar*>& arguments) {

2812}

2813

2815 [[maybe_unused]] const std::string& arg_name, IntervalVar* const argument) {

2816 argument->Accept(this);

2817}

2818

2820 [[maybe_unused]] const std::string& arg_name,

2821 const std::vector<IntervalVar*>& arguments) {

2823}

2824

2826 [[maybe_unused]] const std::string& arg_name, SequenceVar* const argument) {

2827 argument->Accept(this);

2828}

2829

2831 [[maybe_unused]] const std::string& arg_name,

2832 const std::vector<SequenceVar*>& arguments) {

2834}

2835

2836

2837

2839 int64_t index_min,

2840 int64_t index_max) {

2841 if (filter != nullptr) {

2842 std::vector<int64_t> cached_results;

2843 for (int i = index_min; i <= index_max; ++i) {

2844 cached_results.push_back(filter(i));

2845 }

2851 }

2852}

2853

2856 CHECK(eval != nullptr);

2857 std::vector<int64_t> cached_results;

2858 for (int i = index_min; i <= index_max; ++i) {

2859 cached_results.push_back(eval(i));

2860 }

2866}

2867

2869 const std::string& arg_name,

2870 int64_t index_max) {

2871 CHECK(eval != nullptr);

2872 std::vector<int64_t> cached_results;

2873 for (int i = 0; i <= index_max; ++i) {

2874 cached_results.push_back(eval(i));

2875 }

2877}

2878

2879

2880

2889 [[maybe_unused]] bool apply) {}

2899 [[maybe_unused]] Assignment* deltadelta) {

2900 return true;

2901}

2907

2909 for (std::underlying_type<Solver::MonitorEvent>::type event = 0;

2912 }

2913}

2914

2916 solver()->searches_.back()->AddEventListener(event, this);

2917}

2918

2919

2922

2924

2925

2930

2931

2934

2936

2937

2938

2943

2944

2945

2947 public:

2949

2951

2953 Constraint* const constraint) override {

2955 constraint);

2956 }

2957

2962

2965 ForAll(monitors_,

2967 nested);

2968 }

2969

2972 ForAll(monitors_,

2974 nested);

2975 }

2976

2980

2984

2988

2992

2996

3000

3004

3005

3008 monitor->SetMin(expr, new_min);

3009 }

3010 }

3011

3014 monitor->SetMax(expr, new_max);

3015 }

3016 }

3017

3019 int64_t new_max) override {

3021 monitor->SetRange(expr, new_min, new_max);

3022 }

3023 }

3024

3025

3028 monitor->SetMin(var, new_min);

3029 }

3030 }

3031

3034 monitor->SetMax(var, new_max);

3035 }

3036 }

3037

3038 void SetRange(IntVar* const var, int64_t new_min, int64_t new_max) override {

3040 monitor->SetRange(var, new_min, new_max);

3041 }

3042 }

3043

3047

3051

3055

3057 const std::vector<int64_t>& values) override {

3059 }

3060

3062 const std::vector<int64_t>& values) override {

3064 }

3065

3066

3070

3074

3076 int64_t new_max) override {

3078 new_max);

3079 }

3080

3084

3088

3090 int64_t new_max) override {

3092 }

3093

3097

3101

3103 int64_t new_max) override {

3105 new_max);

3106 }

3107

3111

3115

3119

3123

3127

3129 const std::vector<int>& rank_last,

3130 const std::vector<int>& unperformed) override {

3132 rank_last, unperformed);

3133 }

3134

3135

3137 if (monitor != nullptr) {

3138 monitors_.push_back(monitor);

3139 }

3140 }

3141

3142

3143

3145

3146 std::string DebugString() const override { return "Trace"; }

3147

3148 private:

3149 std::vector<PropagationMonitor*> monitors_;

3150};

3151

3153

3155

3156 reinterpret_cast<class Trace*>(propagation_monitor_.get())->Add(monitor);

3157}

3158

3160 return propagation_monitor_.get();

3161}

3162

3163

3164

3166 public:

3169

3181 const Assignment* deltadelta) override {

3183 neighbor_found, delta, deltadelta);

3184 }

3189 bool neighbor_found) override {

3191 neighbor_found);

3192 }

3197 bool neighbor_found) override {

3199 neighbor_found);

3200 }

3207 bool IsActive() const override { return !monitors_.empty(); }

3208

3209

3211 if (monitor != nullptr) {

3212 monitors_.push_back(monitor);

3213 }

3214 }

3215

3216

3217

3219

3221 return "LocalSearchMonitorPrimary";

3222 }

3223

3224 private:

3225 std::vector<LocalSearchMonitor*> monitors_;

3226};

3227

3231

3234 local_search_monitor_.get())

3235 ->Add(monitor);

3236}

3237

3239 return local_search_monitor_.get();

3240}

3241

3243 absl::string_view search_context) {

3245}

3246

3250

3254

3258

3260 if (local_search_state_ == nullptr) {

3261 local_search_state_ = std::make_unique<Assignment>(this);

3262 }

3263 return local_search_state_.get();

3264}

3265

3266

3267

3269 : db_(db), name_(db_->GetName()), seconds_(0) {}

3270

3272 timer_.Start();

3274

3276 [this](Solver* solver) {

3277 if (timer_.IsRunning()) {

3278 timer_.Stop();

3279 seconds_ += timer_.Get();

3280 }

3282 },

3283 true);

3284 Decision* const decision = db_->Next(solver);

3285 timer_.Stop();

3286 seconds_ += timer_.Get();

3288 return decision;

3289}

3290

3292 return db_->DebugString();

3293}

3294

3296 Solver* const solver, std::vector<SearchMonitor*>* const extras) {

3297 db_->AppendMonitors(solver, extras);

3298}

3299

3301 db_->Accept(visitor);

3302}

3303

3304

3305

3307

3315

3318 VLOG(3) << "Unknown constraint " << DebugString();

3320}

3321

3323 return solver()->cast_constraints_.contains(this);

3324}

3325

3327

3328

3329

3332 VLOG(3) << "Unknown expression " << DebugString();

3334}

3335

3336#undef CP_TRY

3337#undef CP_ON_FAIL

3338#undef CP_DO_FAIL

3339

3340}

virtual std::string DebugString() const

::operations_research::ConstraintSolverParameters_TrailCompression compress_trail() const

void set_profile_file(Arg_ &&arg, Args_... args)

void set_disable_solve(bool value)

void set_print_model_stats(bool value)

void set_trail_block_size(::int32_t value)

::int32_t array_split_size() const

void set_print_local_search_profile(bool value)

void set_print_model(bool value)

void set_profile_propagation(bool value)

void set_use_sequence_high_demand_tasks(bool value)

void set_check_solution_period(::int32_t value)

void set_array_split_size(::int32_t value)

ConstraintSolverParameters_TrailCompression TrailCompression

void set_use_cumulative_time_table(bool value)

void set_profile_local_search(bool value)

bool print_model_stats() const

void set_diffn_use_cumulative(bool value)

static constexpr TrailCompression NO_COMPRESSION

void set_print_added_constraints(bool value)

void set_use_cumulative_edge_finder(bool value)

void set_store_names(bool value)

void set_trace_search(bool value)

void set_trace_propagation(bool value)

void set_max_edge_finder_size(::int32_t value)

::int32_t trail_block_size() const

void set_name_all_variables(bool value)

void set_use_element_rmq(bool value)

void set_compress_trail(::operations_research::ConstraintSolverParameters_TrailCompression value)

void set_use_small_table(bool value)

void set_use_cumulative_time_table_sync(bool value)

void set_use_all_possible_disjunctions(bool value)

void set_name_cast_variables(bool value)

void set_num_branches(::int64_t value)

void set_num_solutions(::int64_t value)

void set_num_failures(::int64_t value)

void set_duration_seconds(double value)

void set_bytes_used(::int64_t value)

std::string DebugString() const override

Definition constraint_solver.cc:3306

virtual void InitialPropagate()=0

bool IsCastConstraint() const

Is the constraint created by a cast from expression to integer variable?

Definition constraint_solver.cc:3322

void PostAndPropagate()

Definition constraint_solver.cc:3308

virtual void Accept(ModelVisitor *visitor) const

Accepts the given visitor.

Definition constraint_solver.cc:3316

virtual IntVar * Var()

Definition constraint_solver.cc:3326

virtual Decision * Next(Solver *s)=0

virtual void Accept(ModelVisitor *visitor) const

Definition constraint_solver.cc:2526

virtual void AppendMonitors(Solver *solver, std::vector< SearchMonitor * > *extras)

Definition constraint_solver.cc:2523

std::string GetName() const

Definition constraint_solver.cc:2519

std::string DebugString() const override

Definition constraint_solver.cc:2517

virtual void VisitRankFirstInterval(SequenceVar *sequence, int index)

Definition constraint_solver.cc:2544

virtual void VisitSetVariableValue(IntVar *var, int64_t value)

Definition constraint_solver.cc:2534

virtual void VisitScheduleOrPostpone(IntervalVar *var, int64_t est)

Definition constraint_solver.cc:2540

virtual void VisitRankLastInterval(SequenceVar *sequence, int index)

Definition constraint_solver.cc:2547

virtual void VisitUnknownDecision()

Definition constraint_solver.cc:2539

virtual void VisitScheduleOrExpedite(IntervalVar *var, int64_t est)

Definition constraint_solver.cc:2542

virtual void VisitSplitVariableDomain(IntVar *var, int64_t value, bool start_with_lower_half)

Definition constraint_solver.cc:2536

virtual void Refute(Solver *s)=0

Refute will be called after a backtrack.

virtual void Apply(Solver *s)=0

Apply will be called first when the decision is executed.

virtual void Accept(DecisionVisitor *visitor) const

Accepts the given visitor.

Definition constraint_solver.cc:2530

void inhibit(Solver *s)

Definition constraint_solver.cc:208

virtual void Run(Solver *s)=0

This is the main callback of the demon.

virtual Solver::DemonPriority priority() const

Definition constraint_solver.cc:202

std::string DebugString() const override

Definition constraint_solver.cc:206

void desinhibit(Solver *s)

This method un-inhibits the demon that was previously inhibited.

Definition constraint_solver.cc:214

virtual void Accept(ModelVisitor *visitor) const

Accepts the given visitor.

Definition constraint_solver.cc:3330

void Accept(ModelVisitor *visitor) const override

Accepts the given visitor.

virtual void Accept(ModelVisitor *visitor) const =0

Accepts the given visitor.

LocalSearchMonitorPrimary(Solver *solver)

Definition constraint_solver.cc:3167

std::string DebugString() const override

Definition constraint_solver.cc:3220

void EndOperatorStart() override

Definition constraint_solver.cc:3173

void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta) override

Definition constraint_solver.cc:3179

void BeginOperatorStart() override

Local search operator events.

Definition constraint_solver.cc:3170

void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found) override

Definition constraint_solver.cc:3196

void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found) override

Definition constraint_solver.cc:3188

void BeginMakeNextNeighbor(const LocalSearchOperator *op) override

Definition constraint_solver.cc:3176

void BeginAcceptNeighbor(const LocalSearchOperator *op) override

Definition constraint_solver.cc:3193

bool IsActive() const override

Definition constraint_solver.cc:3207

void Add(LocalSearchMonitor *monitor)

Definition constraint_solver.cc:3210

void Install() override

Install itself on the solver.

Definition constraint_solver.cc:3218

void BeginFilterNeighbor(const LocalSearchOperator *op) override

Definition constraint_solver.cc:3185

void EndFiltering(const LocalSearchFilter *filter, bool reject) override

Definition constraint_solver.cc:3204

void BeginFiltering(const LocalSearchFilter *filter) override

Definition constraint_solver.cc:3201

LocalSearchMonitor(Solver *solver)

Definition constraint_solver.cc:2932

virtual void EndAcceptNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0

virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0

virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0

virtual void BeginOperatorStart()=0

Local search operator events.

virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0

~LocalSearchMonitor() override

Definition constraint_solver.cc:2935

void Install() override

Install itself on the solver.

Definition constraint_solver.cc:2939

virtual void BeginFiltering(const LocalSearchFilter *filter)=0

virtual void EndFilterNeighbor(const LocalSearchOperator *op, bool neighbor_found)=0

virtual void EndOperatorStart()=0

virtual void EndMakeNextNeighbor(const LocalSearchOperator *op, bool neighbor_found, const Assignment *delta, const Assignment *deltadelta)=0

virtual void EndFiltering(const LocalSearchFilter *filter, bool reject)=0

The base class for all local search operators.

static const char kCumulsArgument[]

static const char kStartMaxArgument[]

static const char kVarValueWatcher[]

static const char kConvexPiecewise[]

static const char kScalProdGreaterOrEqual[]

static const char kStepArgument[]

static const char kLexLess[]

virtual void VisitSequenceVariable(const SequenceVar *variable)

Definition constraint_solver.cc:2781

static const char kGreaterOrEqual[]

static const char kSolutionLimitArgument[]

static const char kAbsEqual[]

static const char kNullIntersect[]

static const char kStartExpr[]

virtual void VisitIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &arguments)

Definition constraint_solver.cc:2819

virtual void VisitIntervalArgument(const std::string &arg_name, IntervalVar *argument)

Visit interval argument.

Definition constraint_solver.cc:2814

static const char kIndexOf[]

static const char kVariableUsageLessConstantExtension[]

static const char kDeviation[]

static const char kSequenceArgument[]

static const char kAssumePathsArgument[]

void VisitInt64ToBoolExtension(Solver::IndexFilter1 filter, int64_t index_min, int64_t index_max)

Definition constraint_solver.cc:2838

static const char kIntervalBinaryRelation[]

static const char kIntegerVariable[]

static const char kDifferenceOperation[]

static const char kInitialState[]

static const char kIsMember[]

static const char kTraceOperation[]

static const char kSearchLimitExtension[]

static const char kEndsArgument[]

static const char kRelaxedMinOperation[]

static const char kFalseConstraint[]

static const char kFixedChargeArgument[]

static const char kDurationMaxArgument[]

void VisitInt64ToInt64AsArray(const Solver::IndexEvaluator1 &eval, const std::string &arg_name, int64_t index_max)

Expands function as array when index min is 0.

Definition constraint_solver.cc:2868

static const char kSumOperation[]

static const char kIntervalVariable[]

static const char kFinalStatesArgument[]

static const char kNoCycle[]

static const char kElement[]

static const char kSequenceVariable[]

static const char kTuplesArgument[]

static const char kFailuresLimitArgument[]

static const char kMirrorOperation[]

Operations.

static const char kMinEqual[]

static const char kEarlyCostArgument[]

static const char kInt64ToInt64Extension[]

static const char kNotBetween[]

static const char kDistribute[]

static const char kOpposite[]

static const char kTransition[]

static const char kActiveArgument[]

argument names:

static const char kObjectiveExtension[]

static const char kIsGreater[]

virtual void BeginVisitModel(const std::string &type_name)

--— Virtual methods for visitors --—

Definition constraint_solver.cc:2732

static const char kDifference[]

static const char kDurationMinArgument[]

virtual void BeginVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)

Definition constraint_solver.cc:2749

static const char kNextsArgument[]

static const char kProduct[]

virtual void VisitIntegerArgument(const std::string &arg_name, int64_t value)

Visit integer arguments.

Definition constraint_solver.cc:2787

static const char kRangeArgument[]

static const char kCircuit[]

static const char kLateCostArgument[]

static const char kEndMinArgument[]

static const char kMinArgument[]

virtual void VisitIntegerVariable(const IntVar *variable, IntExpr *delegate)

Definition constraint_solver.cc:2756

virtual void VisitSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &arguments)

Definition constraint_solver.cc:2830

static const char kCoefficientsArgument[]

virtual void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &tuples)

Definition constraint_solver.cc:2795

static const char kExpressionArgument[]

static const char kTrace[]

virtual void VisitIntegerVariableEvaluatorArgument(const std::string &arg_name, const Solver::Int64ToIntVar &arguments)

Helpers.

Definition constraint_solver.cc:2804

static const char kTargetArgument[]

~ModelVisitor() override

Definition constraint_solver.cc:2730

static const char kMapDomain[]

static const char kStartsArgument[]

static const char kIntervalDisjunction[]

static const char kPositionXArgument[]

static const char kStartSyncOnStartOperation[]

static const char kRelationArgument[]

static const char kIsDifferent[]

static const char kSortingConstraint[]

static const char kSizeArgument[]

static const char kMember[]

static const char kModulo[]

static const char kSumGreaterOrEqual[]

static const char kIntervalUnaryRelation[]

static const char kMaxArgument[]

virtual void EndVisitModel(const std::string &type_name)

Definition constraint_solver.cc:2734

static const char kProductOperation[]

static const char kTransitsArgument[]

static const char kPerformedExpr[]

virtual void VisitIntegerExpressionArgument(const std::string &arg_name, IntExpr *argument)

Visit integer expression argument.

Definition constraint_solver.cc:2799

static const char kNotMember[]

static const char kValueArgument[]

static const char kEndExpr[]

static const char kLessOrEqual[]

static const char kMaxEqual[]

static const char kLateDateArgument[]

static const char kRightArgument[]

static const char kEarlyDateArgument[]

static const char kScalProdLessOrEqual[]

static const char kIsGreaterOrEqual[]

virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)

Definition constraint_solver.cc:2808

static const char kCapacityArgument[]

static const char kSumLessOrEqual[]

static const char kModuloArgument[]

static const char kVarBoundWatcher[]

static const char kIsEqual[]

static const char kCumulative[]

static const char kScalProdEqual[]

static const char kSizeYArgument[]

static const char kSequencesArgument[]

static const char kEndMaxArgument[]

static const char kDurationExpr[]

static const char kVariableGroupExtension[]

virtual void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64_t > &values)

Definition constraint_solver.cc:2791

static const char kAllDifferent[]

static const char kValuesArgument[]

static const char kIsLess[]

static const char kIndexArgument[]

static const char kPack[]

static const char kPathCumul[]

static const char kRelaxedMaxOperation[]

static const char kScalProd[]

static const char kAtMost[]

static const char kStartSyncOnEndOperation[]

static const char kUsageLessConstantExtension[]

static const char kMaximizeArgument[]

static const char kLightElementEqual[]

static const char kElementEqual[]

static const char kCumulativeArgument[]

static const char kSquare[]

static const char kIntervalArgument[]

static const char kPositionYArgument[]

static const char kIsBetween[]

static const char kVarsArgument[]

virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *constraint)

Definition constraint_solver.cc:2737

static const char kVariableArgument[]

static const char kLinkExprVar[]

static const char kBranchesLimitArgument[]

static const char kIndex2Argument[]

static const char kSumEqual[]

virtual void EndVisitExtension(const std::string &type)

Definition constraint_solver.cc:2746

static const char kUsageEqualVariableExtension[]

static const char kSemiContinuous[]

static const char kDemandsArgument[]

static const char kDisjunctive[]

static const char kNonEqual[]

static const char kCountEqual[]

static const char kSizeXArgument[]

static const char kGreater[]

static const char kEquality[]

static const char kLeftArgument[]

static const char kGlobalCardinality[]

static const char kInversePermutation[]

static const char kCountAssignedItemsExtension[]

Extension names:

virtual void VisitIntervalVariable(const IntervalVar *variable, const std::string &operation, int64_t value, IntervalVar *delegate)

Definition constraint_solver.cc:2772

static const char kCountUsedBinsExtension[]

static const char kStartMinArgument[]

static const char kOptionalArgument[]

static const char kCountArgument[]

static const char kConditionalExpr[]

void VisitInt64ToInt64Extension(const Solver::IndexEvaluator1 &eval, int64_t index_min, int64_t index_max)

Definition constraint_solver.cc:2854

static const char kTrueConstraint[]

static const char kPartialArgument[]

static const char kDelayedPathCumul[]

virtual void BeginVisitExtension(const std::string &type)

Definition constraint_solver.cc:2744

static const char kIndex3Argument[]

static const char kWeightedSumOfAssignedEqualVariableExtension[]

static const char kInt64ToBoolExtension[]

virtual void VisitSequenceArgument(const std::string &arg_name, SequenceVar *argument)

Visit sequence argument.

Definition constraint_solver.cc:2825

static const char kEvaluatorArgument[]

static const char kCover[]

virtual void EndVisitIntegerExpression(const std::string &type_name, const IntExpr *expr)

Definition constraint_solver.cc:2752

static const char kAbs[]

Constraint and Expression types.

static const char kSmartTimeCheckArgument[]

static const char kCardsArgument[]

static const char kBetween[]

static const char kDivide[]

static const char kAllowedAssignments[]

static const char kTimeLimitArgument[]

static const char kPower[]

static const char kIsLessOrEqual[]

static const char kLess[]

static const char kIntervalsArgument[]

virtual void EndVisitConstraint(const std::string &type_name, const Constraint *constraint)

Definition constraint_solver.cc:2740

ProfiledDecisionBuilder(DecisionBuilder *db)

Definition constraint_solver.cc:3268

std::string DebugString() const override

Definition constraint_solver.cc:3291

Decision * Next(Solver *solver) override

Definition constraint_solver.cc:3271

void Accept(ModelVisitor *visitor) const override

Definition constraint_solver.cc:3300

const std::string & name() const

void AppendMonitors(Solver *solver, std::vector< SearchMonitor * > *extras) override

Definition constraint_solver.cc:3295

void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)

Definition constraint_solver.cc:2507

virtual std::string name() const

Object naming.

Definition constraint_solver.cc:2495

void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)

Definition constraint_solver.cc:2511

virtual std::string BaseName() const

Returns a base name for automatic naming.

Definition constraint_solver.cc:2505

void set_name(absl::string_view name)

Definition constraint_solver.cc:2499

std::string DebugString() const override

bool HasName() const

Returns whether the object has been named or not.

Definition constraint_solver.cc:2503

virtual void SetValues(IntVar *var, const std::vector< int64_t > &values)=0

virtual void SetDurationMax(IntervalVar *var, int64_t new_max)=0

virtual void SetStartMax(IntervalVar *var, int64_t new_max)=0

virtual void SetStartMin(IntervalVar *var, int64_t new_min)=0

IntervalVar modifiers.

virtual void PopContext()=0

virtual void RankSequence(SequenceVar *var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed)=0

virtual void RankNotFirst(SequenceVar *var, int index)=0

virtual void BeginNestedConstraintInitialPropagation(Constraint *parent, Constraint *nested)=0

virtual void RankNotLast(SequenceVar *var, int index)=0

virtual void PushContext(const std::string &context)=0

virtual void SetPerformed(IntervalVar *var, bool value)=0

virtual void SetEndMax(IntervalVar *var, int64_t new_max)=0

virtual void RemoveValue(IntVar *var, int64_t value)=0

virtual void BeginConstraintInitialPropagation(Constraint *constraint)=0

Propagation events.

virtual void EndDemonRun(Demon *demon)=0

virtual void SetDurationMin(IntervalVar *var, int64_t new_min)=0

virtual void RegisterDemon(Demon *demon)=0

virtual void SetEndMin(IntervalVar *var, int64_t new_min)=0

virtual void RankFirst(SequenceVar *var, int index)=0

SequenceVar modifiers.

virtual void RankLast(SequenceVar *var, int index)=0

virtual void SetDurationRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0

virtual void EndNestedConstraintInitialPropagation(Constraint *parent, Constraint *nested)=0

PropagationMonitor(Solver *solver)

Definition constraint_solver.cc:2920

virtual void StartProcessingIntegerVariable(IntVar *var)=0

virtual void EndProcessingIntegerVariable(IntVar *var)=0

void Install() override

Install itself on the solver.

Definition constraint_solver.cc:2926

virtual void RemoveInterval(IntVar *var, int64_t imin, int64_t imax)=0

virtual void BeginDemonRun(Demon *demon)=0

~PropagationMonitor() override

Definition constraint_solver.cc:2923

virtual void RemoveValues(IntVar *var, const std::vector< int64_t > &values)=0

virtual void SetStartRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0

virtual void EndConstraintInitialPropagation(Constraint *constraint)=0

virtual void SetValue(IntVar *var, int64_t value)=0

virtual void SetEndRange(IntervalVar *var, int64_t new_min, int64_t new_max)=0

void ProcessConstraints()

Definition constraint_solver.cc:390

void Process()

Definition constraint_solver.cc:270

void increase_stamp()

Definition constraint_solver.cc:366

void ProcessOneDemon(Demon *const demon)

Definition constraint_solver.cc:251

uint64_t stamp() const

Definition constraint_solver.cc:368

void EnqueueDelayedDemon(Demon *const demon)

Definition constraint_solver.cc:338

void EnqueueVar(Demon *const demon)

Definition constraint_solver.cc:327

Queue(Solver *const s)

Definition constraint_solver.cc:228

void AddConstraint(Constraint *const c)

Definition constraint_solver.cc:385

~Queue()

Definition constraint_solver.cc:238

static constexpr int64_t kTestPeriod

Definition constraint_solver.cc:226

void Freeze()

Definition constraint_solver.cc:240

void set_action_on_fail(Solver::Action a)

Definition constraint_solver.cc:370

void reset_action_on_fail()

Definition constraint_solver.cc:380

void Unfreeze()

Definition constraint_solver.cc:245

void ExecuteAll(const SimpleRevFIFO< Demon * > &demons)

Definition constraint_solver.cc:289

void AfterFailure()

Definition constraint_solver.cc:346

void set_variable_to_clean_on_fail(IntVar *var)

Definition constraint_solver.cc:375

void EnqueueAll(const SimpleRevFIFO< Demon * > &demons)

Definition constraint_solver.cc:321

A search monitor is a simple set of callbacks to monitor all search events.

static constexpr int kNoProgress

virtual void Install()

Definition constraint_solver.cc:2908

virtual bool AtSolution()

Definition constraint_solver.cc:2895

virtual void BeginInitialPropagation()

Before the initial propagation.

Definition constraint_solver.cc:2892

virtual void EndFail()

After completing the backtrack.

Definition constraint_solver.cc:2891

virtual void RestartSearch()

Restart the search.

Definition constraint_solver.cc:2882

virtual void EndInitialPropagation()

After the initial propagation.

Definition constraint_solver.cc:2893

virtual bool AcceptDelta(Assignment *delta, Assignment *deltadelta)

Definition constraint_solver.cc:2898

virtual void BeginNextDecision(DecisionBuilder *b)

Before calling DecisionBuilder::Next.

Definition constraint_solver.cc:2884

virtual void RefuteDecision(Decision *d)

Before refuting the decision.

Definition constraint_solver.cc:2887

virtual void EndNextDecision(DecisionBuilder *b, Decision *d)

After calling DecisionBuilder::Next, along with the returned decision.

Definition constraint_solver.cc:2885

virtual void ApplyDecision(Decision *d)

Before applying the decision.

Definition constraint_solver.cc:2886

virtual void Accept(ModelVisitor *visitor) const

Accepts the given model visitor.

Definition constraint_solver.cc:2905

virtual bool AtLocalOptimum()

Definition constraint_solver.cc:2897

virtual void ExitSearch()

End of the search.

Definition constraint_solver.cc:2883

SearchMonitor(Solver *const s)

virtual void PeriodicCheck()

Periodic call to check limits in long running methods.

Definition constraint_solver.cc:2904

virtual void NoMoreSolutions()

When the search tree is finished.

Definition constraint_solver.cc:2896

void ListenToEvent(Solver::MonitorEvent event)

Definition constraint_solver.cc:2915

virtual void BeginFail()

Just when the failure occurs.

Definition constraint_solver.cc:2890

virtual bool AcceptSolution()

Definition constraint_solver.cc:2894

virtual void EnterSearch()

Beginning of the search.

Definition constraint_solver.cc:2881

virtual void AfterDecision(Decision *d, bool apply)

Definition constraint_solver.cc:2888

virtual void AcceptNeighbor()

After accepting a neighbor during local search.

Definition constraint_solver.cc:2902

virtual void AcceptUncheckedNeighbor()

After accepting an unchecked neighbor during local search.

Definition constraint_solver.cc:2903

void RightMove()

Definition constraint_solver.cc:1061

bool AtSolution()

Definition constraint_solver.cc:1301

void set_search_context(absl::string_view search_context)

Definition constraint_solver.cc:1081

friend class Solver

Definition constraint_solver.cc:1085

bool created_by_solve() const

Definition constraint_solver.cc:1054

void set_created_by_solve(bool c)

Definition constraint_solver.cc:1053

void set_search_depth(int d)

Definition constraint_solver.cc:1069

void BeginFail()

Definition constraint_solver.cc:1275

bool should_finish() const

Definition constraint_solver.cc:1075

void IncrementSolutionCounter()

Definition constraint_solver.cc:1043

void CheckFail()

Definition constraint_solver.cc:1076

int search_depth() const

Definition constraint_solver.cc:1068

void AddEventListener(Solver::MonitorEvent event, SearchMonitor *monitor)

Definition constraint_solver.cc:1033

Search(Solver *const s, int)

Definition constraint_solver.cc:991

bool AcceptDelta(Assignment *delta, Assignment *deltadelta)

Definition constraint_solver.cc:1328

void AcceptNeighbor()

Definition constraint_solver.cc:1339

~Search()

Definition constraint_solver.cc:1008

Search(Solver *const s)

Definition constraint_solver.cc:971

void set_decision_builder(DecisionBuilder *const db)

Definition constraint_solver.cc:1049

void set_search_left_depth(int d)

Definition constraint_solver.cc:1071

bool should_restart() const

Definition constraint_solver.cc:1073

int64_t unchecked_solution_counter() const

Definition constraint_solver.cc:1046

void ApplyDecision(Decision *d)

Definition constraint_solver.cc:1257

void IncrementUncheckedSolutionCounter()

Definition constraint_solver.cc:1045

void BeginNextDecision(DecisionBuilder *db)

Definition constraint_solver.cc:1245

void Clear()

Definition constraint_solver.cc:1214

void set_backtrack_at_the_end_of_the_search(bool restore)

Definition constraint_solver.cc:1065

void EndInitialPropagation()

Definition constraint_solver.cc:1283

void Accept(ModelVisitor *visitor) const

Definition constraint_solver.cc:1366

DecisionBuilder * decision_builder() const

Definition constraint_solver.cc:1052

bool backtrack_at_the_end_of_the_search() const

Definition constraint_solver.cc:1062

void PeriodicCheck()

Definition constraint_solver.cc:1355

void BeginInitialPropagation()

Definition constraint_solver.cc:1279

Solver::DecisionModification ModifyDecision()

Definition constraint_solver.cc:1207

bool ContinueAtLocalOptimum()

Definition constraint_solver.cc:1317

void AcceptUncheckedNeighbor()

Definition constraint_solver.cc:1341

void EnterSearch()

Definition constraint_solver.cc:1228

void LeftMove()

Definition constraint_solver.cc:1057

void ExitSearch()

Definition constraint_solver.cc:1238

int64_t solution_counter() const

Definition constraint_solver.cc:1044

bool AcceptSolution()

Definition constraint_solver.cc:1287

const std::vector< SearchMonitor * > & GetEventListeners(Solver::MonitorEvent event) const

Definition constraint_solver.cc:1038

void NoMoreSolutions()

Definition constraint_solver.cc:1315

std::string search_context() const

Definition constraint_solver.cc:1084

void RestartSearch()

Definition constraint_solver.cc:1243

void set_should_finish(bool s)

Definition constraint_solver.cc:1074

bool IsUncheckedSolutionLimitReached()

Definition constraint_solver.cc:1345

void set_should_restart(bool s)

Definition constraint_solver.cc:1072

void EndFail()

Definition constraint_solver.cc:1277

void RefuteDecision(Decision *d)

Definition constraint_solver.cc:1269

void EndNextDecision(DecisionBuilder *db, Decision *d)

Definition constraint_solver.cc:1251

int left_search_depth() const

Definition constraint_solver.cc:1070

int ProgressPercent()

Definition constraint_solver.cc:1357

void SetBranchSelector(Solver::BranchSelector bs)

Definition constraint_solver.cc:1174

void AfterDecision(Decision *d, bool apply)

Definition constraint_solver.cc:1263

virtual void Accept(ModelVisitor *visitor) const

Accepts the given visitor.

IntervalVar * Interval(int index) const

Returns the index_th interval of the sequence.

int64_t size() const

Returns the number of interval vars in the sequence.

This iterator is not stable with respect to deletion.

static ConstraintSolverParameters DefaultSolverParameters()

Create a ConstraintSolverParameters proto with all the default values.

Definition constraint_solver.cc:127

void SetBranchSelector(BranchSelector bs)

Sets the given branch selector on the current active search.

Definition constraint_solver.cc:1178

bool CurrentlyInSolve() const

Definition constraint_solver.cc:1779

Search * ActiveSearch() const

Returns the active search, nullptr outside search.

Definition constraint_solver.cc:1153

bool IsLocalSearchProfilingEnabled() const

Returns whether we are profiling local search.

Definition constraint_solver.cc:187

void ExportProfilingOverview(const std::string &filename)

bool NextSolution()

Definition constraint_solver.cc:2092

int TopProgressPercent()

Definition constraint_solver.cc:1577

void RestartSearch()

Definition constraint_solver.cc:1984

uint64_t fail_stamp() const

The fail_stamp() is incremented after each backtrack.

Definition constraint_solver.cc:1678

DecisionBuilder * MakeApplyBranchSelector(BranchSelector bs)

Creates a decision builder that will set the branch selector.

Definition constraint_solver.cc:1193

int SearchDepth() const

Definition constraint_solver.cc:1201

DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)

int64_t branches() const

The number of branches explored since the creation of the solver.

int64_t solutions() const

The number of solutions found since the start of the search.

Definition constraint_solver.cc:1559

bool NameAllVariables() const

Returns whether all variables should be named.

Definition constraint_solver.cc:196

void AddPropagationMonitor(PropagationMonitor *monitor)

Definition constraint_solver.cc:3154

static constexpr int kNumPriorities

Number of priorities for demons.

void Fail()

Abandon the current branch in the search tree. A backtrack will follow.

Definition constraint_solver.cc:2406

@ NORMAL_PRIORITY

NORMAL_PRIORITY is the highest priority: Demons will be processed first.

@ VAR_PRIORITY

VAR_PRIORITY is between DELAYED_PRIORITY and NORMAL_PRIORITY.

void NewSearch(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)

Definition constraint_solver.cc:1842

LocalSearchMonitor * GetLocalSearchMonitor() const

Returns the local search monitor.

Definition constraint_solver.cc:3238

absl::Time Now() const

Definition constraint_solver.cc:1555

int SearchLeftDepth() const

Definition constraint_solver.cc:1203

std::function< int64_t(int64_t)> IndexEvaluator1

Callback typedefs.

@ IN_SEARCH

Executing the search code.

@ IN_ROOT_NODE

Executing the root node.

@ PROBLEM_INFEASIBLE

After search, the model is infeasible.

@ NO_MORE_SOLUTIONS

After failed NextSolution and before EndSearch.

@ OUTSIDE_SEARCH

Before search, after search.

@ AT_SOLUTION

After successful NextSolution and before EndSearch.

void set_context(absl::string_view context)

Sets the current context of the search.

std::string LocalSearchProfile() const

Returns local search profiling information in a human readable format.

~Solver()

Definition constraint_solver.cc:1502

bool CheckAssignment(Assignment *solution)

Checks whether the given assignment satisfies all relevant constraints.

Definition constraint_solver.cc:2293

void AddBacktrackAction(Action a, bool fast)

Definition constraint_solver.cc:1622

void PopState()

Definition constraint_solver.cc:1594

void SaveAndSetValue(T *adr, T val)

All-in-one SaveAndSetValue.

std::string model_name() const

Returns the name of the model.

Definition constraint_solver.cc:1428

void PushState()

Definition constraint_solver.cc:1589

void TopPeriodicCheck()

Definition constraint_solver.cc:1575

std::function< DecisionModification()> BranchSelector

ConstraintSolverStatistics GetConstraintSolverStatistics() const

Returns detailed cp search statistics.

Definition constraint_solver.cc:1579

IntExpr * CastExpression(const IntVar *var) const

!defined(SWIG)

Definition constraint_solver.cc:2427

DecisionBuilder * MakeConstraintAdder(Constraint *ct)

Definition constraint_solver.cc:2368

std::function< void(Solver *)> Action

int64_t unchecked_solutions() const

The number of unchecked solutions found by local search.

Definition constraint_solver.cc:1563

uint64_t stamp() const

Definition constraint_solver.cc:1676

void FinishCurrentSearch()

Tells the solver to kill or restart the current search.

Definition constraint_solver.cc:2417

std::function< bool(int64_t)> IndexFilter1

void Accept(ModelVisitor *visitor) const

Accepts the given model visitor.

Definition constraint_solver.cc:1726

bool IsProfilingEnabled() const

Returns whether we are profiling the solver.

Definition constraint_solver.cc:182

MonitorEvent

Search monitor events.

@ kIsUncheckedSolutionLimitReached

friend class SearchMonitor

std::string SearchContext() const

Definition constraint_solver.cc:3247

void EndSearch()

Definition constraint_solver.cc:2262

SearchMonitor * MakeSearchTrace(const std::string &prefix)

int SolveDepth() const

Definition constraint_solver.cc:1197

std::function< IntVar *(int64_t)> Int64ToIntVar

int64_t wall_time() const

Definition constraint_solver.cc:1551

friend class PropagationBaseObject

bool HasName(const PropagationBaseObject *object) const

Returns whether the object has been named or not.

Definition constraint_solver.cc:2475

void SetSearchContext(Search *search, absl::string_view search_context)

Definition constraint_solver.cc:3242

void RestartCurrentSearch()

Definition constraint_solver.cc:2421

std::string DebugString() const

!defined(SWIG)

Definition constraint_solver.cc:1518

ConstraintSolverParameters parameters() const

Stored Parameters.

bool Solve(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)

Definition constraint_solver.cc:1807

ModelVisitor * MakePrintModelVisitor()

Prints the model.

Assignment * GetOrCreateLocalSearchState()

Returns (or creates) an assignment representing the state of local search.

Definition constraint_solver.cc:3259

int64_t failures() const

The number of failures encountered since the creation of the solver.

bool CheckConstraint(Constraint *ct)

Definition constraint_solver.cc:2372

bool InstrumentsDemons() const

Returns whether we are instrumenting demons.

Definition constraint_solver.cc:178

bool AcceptSolution(Search *search) const

Definition constraint_solver.cc:3255

PropagationMonitor * GetPropagationMonitor() const

Returns the propagation monitor.

Definition constraint_solver.cc:3159

Decision * MakeFailDecision()

Definition constraint_solver.cc:1410

Solver(const std::string &name)

Solver API.

Definition constraint_solver.cc:1448

bool InstrumentsVariables() const

Returns whether we are tracing variables.

Definition constraint_solver.cc:192

void AddLocalSearchMonitor(LocalSearchMonitor *monitor)

Definition constraint_solver.cc:3232

static int64_t MemoryUsage()

Current memory usage in bytes.

Definition constraint_solver.cc:1549

void AddConstraint(Constraint *c)

Adds the constraint 'c' to the model.

Definition constraint_solver.cc:1690

ModelVisitor * MakeStatisticsModelVisitor()

Displays some nice statistics on the model.

bool SolveAndCommit(DecisionBuilder *db, const std::vector< SearchMonitor * > &monitors)

Definition constraint_solver.cc:2395

void AddCastConstraint(CastConstraint *constraint, IntVar *target_var, IntExpr *expr)

Definition constraint_solver.cc:1714

void BeginDemonRun(Demon *const demon) override

Definition constraint_solver.cc:2981

void RegisterDemon(Demon *const demon) override

Definition constraint_solver.cc:2977

void RemoveInterval(IntVar *const var, int64_t imin, int64_t imax) override

Definition constraint_solver.cc:3052

void RemoveValues(IntVar *const var, const std::vector< int64_t > &values) override

Definition constraint_solver.cc:3061

void RankNotFirst(SequenceVar *const var, int index) override

Definition constraint_solver.cc:3116

void BeginNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override

Definition constraint_solver.cc:2963

void RankLast(SequenceVar *const var, int index) override

Definition constraint_solver.cc:3120

void SetMax(IntExpr *const expr, int64_t new_max) override

Definition constraint_solver.cc:3012

void SetEndMin(IntervalVar *const var, int64_t new_min) override

Definition constraint_solver.cc:3081

void SetMin(IntExpr *const expr, int64_t new_min) override

IntExpr modifiers.

Definition constraint_solver.cc:3006

void SetMax(IntVar *const var, int64_t new_max) override

Definition constraint_solver.cc:3032

void Add(PropagationMonitor *const monitor)

Definition constraint_solver.cc:3136

void BeginConstraintInitialPropagation(Constraint *const constraint) override

Propagation events.

Definition constraint_solver.cc:2952

void RankSequence(SequenceVar *const var, const std::vector< int > &rank_first, const std::vector< int > &rank_last, const std::vector< int > &unperformed) override

Definition constraint_solver.cc:3128

void SetMin(IntVar *const var, int64_t new_min) override

IntVar modifiers.

Definition constraint_solver.cc:3026

void SetRange(IntExpr *const expr, int64_t new_min, int64_t new_max) override

Definition constraint_solver.cc:3018

void Install() override

Install itself on the solver.

Definition constraint_solver.cc:3144

void SetStartRange(IntervalVar *const var, int64_t new_min, int64_t new_max) override

Definition constraint_solver.cc:3075

void SetValue(IntVar *const var, int64_t value) override

Definition constraint_solver.cc:3048

std::string DebugString() const override

Definition constraint_solver.cc:3146

void SetRange(IntVar *const var, int64_t new_min, int64_t new_max) override

Definition constraint_solver.cc:3038

void SetStartMin(IntervalVar *const var, int64_t new_min) override

IntervalVar modifiers.

Definition constraint_solver.cc:3067

void SetEndRange(IntervalVar *const var, int64_t new_min, int64_t new_max) override

Definition constraint_solver.cc:3089

void SetPerformed(IntervalVar *const var, bool value) override

Definition constraint_solver.cc:3108

void SetValues(IntVar *const var, const std::vector< int64_t > &values) override

Definition constraint_solver.cc:3056

void PushContext(const std::string &context) override

Definition constraint_solver.cc:2997

void RemoveValue(IntVar *const var, int64_t value) override

Definition constraint_solver.cc:3044

void EndConstraintInitialPropagation(Constraint *const constraint) override

Definition constraint_solver.cc:2958

void RankFirst(SequenceVar *const var, int index) override

SequenceVar modifiers.

Definition constraint_solver.cc:3112

void SetStartMax(IntervalVar *const var, int64_t new_max) override

Definition constraint_solver.cc:3071

void EndProcessingIntegerVariable(IntVar *const var) override

Definition constraint_solver.cc:2993

Trace(Solver *const s)

Definition constraint_solver.cc:2948

~Trace() override

Definition constraint_solver.cc:2950

void EndDemonRun(Demon *const demon) override

Definition constraint_solver.cc:2985

void SetDurationMax(IntervalVar *const var, int64_t new_max) override

Definition constraint_solver.cc:3098

void SetDurationRange(IntervalVar *const var, int64_t new_min, int64_t new_max) override

Definition constraint_solver.cc:3102

void EndNestedConstraintInitialPropagation(Constraint *const parent, Constraint *const nested) override

Definition constraint_solver.cc:2970

void SetDurationMin(IntervalVar *const var, int64_t new_min) override

Definition constraint_solver.cc:3094

void SetEndMax(IntervalVar *const var, int64_t new_max) override

Definition constraint_solver.cc:3085

void PopContext() override

Definition constraint_solver.cc:3001

void StartProcessingIntegerVariable(IntVar *const var) override

Definition constraint_solver.cc:2989

void RankNotLast(SequenceVar *const var, int index) override

Definition constraint_solver.cc:3124

#define CP_ON_FAIL

Definition constraint_solver.cc:1131

#define CP_TRY(search)

Definition constraint_solver.cc:1127

#define CP_DO_FAIL(search)

Definition constraint_solver.cc:1132

ABSL_FLAG(bool, cp_trace_propagation, false, "Trace propagation events (constraint and demon executions," " variable modifications).")

void ConstraintSolverFailsHere()

Definition constraint_solver.cc:97

#define CALL_EVENT_LISTENERS(Event)

Definition constraint_solver.cc:1222

void STLDeleteElements(T *container)

const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)

For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false

dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp

void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)

void InternalSaveBooleanVarValue(Solver *const solver, IntVar *const var)

Definition constraint_solver.cc:963

void DeleteDemonProfiler(DemonProfiler *monitor)

int64_t GetProcessMemoryUsage()

void RestoreBoolValue(IntVar *var)

ModelCache * BuildModelCache(Solver *solver)

PropagationMonitor * BuildTrace(Solver *s)

Definition constraint_solver.cc:3152

Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid

void AcceptNeighbor(Search *search)

Definition constraint_solver.cc:1384

void AcceptUncheckedNeighbor(Search *search)

Definition constraint_solver.cc:1386

DemonProfiler * BuildDemonProfiler(Solver *solver)

std::ostream & operator<<(std::ostream &out, const Assignment &assignment)

LocalSearchMonitor * BuildLocalSearchMonitorPrimary(Solver *s)

Definition constraint_solver.cc:3228

void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)

LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)

bool ContinueAtLocalOptimum(Search *search)

Definition constraint_solver.cc:1376