Google OR-Tools: ortools/constraint_solver/constraint

Google OR-Tools: ortools/constraint_solver/constraint_solveri.h Source File

51#ifndef ORTOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_

52#define ORTOOLS_CONSTRAINT_SOLVER_CONSTRAINT_SOLVERI_H_

54#include <stdint.h>

55#include <string.h>

57#include <algorithm>

58#include <functional>

59#include <memory>

60#include <string>

61#include <tuple>

62#include <utility>

63#include <vector>

65#include "absl/algorithm/container.h"

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

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

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

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

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

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

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

111

113 public:

141

146#ifndef SWIG

147template <class T>

149 private:

150 enum { CHUNK_SIZE = 16 };

151 struct Chunk {

152 T data[CHUNK_SIZE];

153 const Chunk* const next;

154 explicit Chunk(const Chunk* next) : next(next) {}

155 };

156

157 public:

159 class Iterator {

160 public:

162 : chunk_(l->chunks_), value_(l->Last()) {}

163 bool ok() const { return (value_ != nullptr); }

164 T operator*() const { return *value_; }

167 if (value_ == chunk_->data + CHUNK_SIZE) {

168 chunk_ = chunk_->next;

169 value_ = chunk_ ? chunk_->data : nullptr;

170 }

171 }

172

173 private:

174 const Chunk* chunk_;

175 const T* value_;

176 };

177

179

180 void Push(Solver* const s, T val) {

181 if (pos_.Value() == 0) {

182 Chunk* const chunk = s->UnsafeRevAlloc(new Chunk(chunks_));

183 s->SaveAndSetValue(reinterpret_cast<void**>(&chunks_),

184 reinterpret_cast<void*>(chunk));

185 pos_.SetValue(s, CHUNK_SIZE - 1);

186 } else {

187 pos_.Decr(s);

188 }

189 chunks_->data[pos_.Value()] = val;

190 }

191

194 if (chunks_ == nullptr || LastValue() != val) {

195 Push(s, val);

196 }

198

200 const T* Last() const {

201 return chunks_ ? &chunks_->data[pos_.Value()] : nullptr;

202 }

203

204 T* MutableLast() { return chunks_ ? &chunks_->data[pos_.Value()] : nullptr; }

205

208 DCHECK(chunks_);

209 return chunks_->data[pos_.Value()];

210 }

215 chunks_->data[pos_.Value()] = v;

216 }

218 private:

219 Chunk* chunks_;

221};

222

224

225inline uint64_t Hash1(uint64_t value) {

226 value = (~value) + (value << 21);

227 value ^= value >> 24;

228 value += (value << 3) + (value << 8);

229 value ^= value >> 14;

230 value += (value << 2) + (value << 4);

231 value ^= value >> 28;

232 value += (value << 31);

233 return value;

234}

235

236inline uint64_t Hash1(uint32_t value) {

237 uint64_t a = value;

238 a = (a + 0x7ed55d16) + (a << 12);

239 a = (a ^ 0xc761c23c) ^ (a >> 19);

240 a = (a + 0x165667b1) + (a << 5);

241 a = (a + 0xd3a2646c) ^ (a << 9);

242 a = (a + 0xfd7046c5) + (a << 3);

243 a = (a ^ 0xb55a4f09) ^ (a >> 16);

244 return a;

245}

246

247inline uint64_t Hash1(int64_t value) {

248 return Hash1(static_cast<uint64_t>(value));

249}

250

251inline uint64_t Hash1(int value) { return Hash1(static_cast<uint32_t>(value)); }

252

253inline uint64_t Hash1(void* const ptr) {

254#if defined(__x86_64__) || defined(_M_X64) || defined(__powerpc64__) || \

255 defined(__aarch64__) || (defined(_MIPS_SZPTR) && (_MIPS_SZPTR == 64))

256 return Hash1(reinterpret_cast<uint64_t>(ptr));

258 return Hash1(reinterpret_cast<uint32_t>(ptr));

259#endif

260}

261

262template <class T>

263uint64_t Hash1(const std::vector<T*>& ptrs) {

264 if (ptrs.empty()) return 0;

265 if (ptrs.size() == 1) return Hash1(ptrs[0]);

266 uint64_t hash = Hash1(ptrs[0]);

267 for (int i = 1; i < ptrs.size(); ++i) {

268 hash = hash * i + Hash1(ptrs[i]);

269 }

270 return hash;

271}

272

273inline uint64_t Hash1(const std::vector<int64_t>& ptrs) {

274 if (ptrs.empty()) return 0;

275 if (ptrs.size() == 1) return Hash1(ptrs[0]);

276 uint64_t hash = Hash1(ptrs[0]);

277 for (int i = 1; i < ptrs.size(); ++i) {

278 hash = hash * i + Hash1(ptrs[i]);

279 }

280 return hash;

281}

282

285template <class K, class V>

287 public:

289 : solver_(solver),

290 array_(solver->UnsafeRevAllocArray(new Cell*[initial_size])),

291 size_(initial_size),

292 num_items_(0) {

293 memset(array_, 0, sizeof(*array_) * size_.Value());

294 }

295

297

299

302 uint64_t code = Hash1(key) % size_.Value();

303 Cell* tmp = array_[code];

304 while (tmp) {

305 if (tmp->key() == key) {

306 return true;

307 }

308 tmp = tmp->next();

309 }

310 return false;

311 }

312

316 const V& FindWithDefault(const K& key, const V& default_value) const {

317 uint64_t code = Hash1(key) % size_.Value();

318 Cell* tmp = array_[code];

319 while (tmp) {

320 if (tmp->key() == key) {

321 return tmp->value();

322 }

323 tmp = tmp->next();

324 }

325 return default_value;

326 }

327

329 void Insert(const K& key, const V& value) {

330 const int position = Hash1(key) % size_.Value();

331 Cell* const cell =

332 solver_->UnsafeRevAlloc(new Cell(key, value, array_[position]));

333 solver_->SaveAndSetValue(reinterpret_cast<void**>(&array_[position]),

334 reinterpret_cast<void*>(cell));

335 num_items_.Incr(solver_);

336 if (num_items_.Value() > 2 * size_.Value()) {

337 Double();

338 }

339 }

340

341 private:

342 class Cell {

343 public:

344 Cell(const K& key, const V& value, Cell* const next)

345 : key_(key), value_(value), next_(next) {}

346

347 void SetRevNext(Solver* const solver, Cell* const next) {

348 solver->SaveAndSetValue(reinterpret_cast<void**>(&next_),

349 reinterpret_cast<void*>(next));

350 }

351

352 Cell* next() const { return next_; }

353

354 const K& key() const { return key_; }

355

356 const V& value() const { return value_; }

357

358 private:

359 const K key_;

360 const V value_;

361 Cell* next_;

362 };

363

364 void Double() {

365 Cell** const old_cell_array = array_;

366 const int old_size = size_.Value();

367 size_.SetValue(solver_, size_.Value() * 2);

368 solver_->SaveAndSetValue(

369 reinterpret_cast<void**>(&array_),

370 reinterpret_cast<void*>(

371 solver_->UnsafeRevAllocArray(new Cell*[size_.Value()])));

372 memset(array_, 0, size_.Value() * sizeof(*array_));

373 for (int i = 0; i < old_size; ++i) {

374 Cell* tmp = old_cell_array[i];

375 while (tmp != nullptr) {

376 Cell* const to_reinsert = tmp;

377 tmp = tmp->next();

378 const uint64_t new_position = Hash1(to_reinsert->key()) % size_.Value();

379 to_reinsert->SetRevNext(solver_, array_[new_position]);

380 solver_->SaveAndSetValue(

381 reinterpret_cast<void**>(&array_[new_position]),

382 reinterpret_cast<void*>(to_reinsert));

383 }

384 }

385 }

386

387 Solver* const solver_;

388 Cell** array_;

389 NumericalRev<int> size_;

390 NumericalRev<int> num_items_;

391};

392

395 public:

397

399

401

403 bool value_;

405

409 public:

418 bool IsCardinalityZero() const { return bits_.Value() == uint64_t{0}; }

421 return (bits_.Value() != 0) && !(bits_.Value() & (bits_.Value() - 1));

427 private:

429};

430

434 public:

435 explicit RevBitSet(int64_t size);

436

437

442 bool IsSet(int64_t index) const;

454

456

457 private:

459 void Save(Solver* solver, int offset);

460 const int64_t size_;

461 const int64_t length_;

462 std::unique_ptr<uint64_t[]> bits_;

463 std::unique_ptr<uint64_t[]> stamps_;

464};

465

468 public:

473 void SetToOne(Solver* solver, int64_t row, int64_t column);

475 void SetToZero(Solver* solver, int64_t row, int64_t column);

477 bool IsSet(int64_t row, int64_t column) const {

478 DCHECK_GE(row, 0);

479 DCHECK_LT(row, rows_);

480 DCHECK_GE(column, 0);

481 DCHECK_LT(column, columns_);

483 }

488

492 int64_t GetFirstBit(int row, int start) const;

495

496 private:

497 const int64_t rows_;

498 const int64_t columns_;

499};

500

504

506

508template <class T>

509class CallMethod0 : public Demon {

510 public:

511 CallMethod0(T* const ct, void (T::*method)(), const std::string& name)

512 : constraint_(ct), method_(method), name_(name) {}

516 void Run(Solver* const) override { (constraint_->*method_)(); }

517

519 return "CallMethod_" + name_ + "(" + constraint_->DebugString() + ")";

521

523 T* const constraint_;

524 void (T::* const method_)();

525 const std::string name_;

526};

527

528template <class T>

530 const std::string& name) {

532}

534template <class P>

536 return absl::StrCat(param);

537}

538

539

540template <class P>

542 return param->DebugString();

543}

544

545

546template <class T, class P>

548 public:

549 CallMethod1(T* const ct, void (T::*method)(P), const std::string& name,

550 P param1)

551 : constraint_(ct), method_(method), name_(name), param1_(param1) {}

552

554

555 void Run(Solver* const) override { (constraint_->*method_)(param1_); }

556

558 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),

560 }

562 private:

563 T* const constraint_;

564 void (T::* const method_)(P);

565 const std::string name_;

566 P param1_;

567};

568

569template <class T, class P>

571 const std::string& name, P param1) {

573}

576template <class T, class P, class Q>

578 public:

579 CallMethod2(T* const ct, void (T::*method)(P, Q), const std::string& name,

580 P param1, Q param2)

581 : constraint_(ct),

582 method_(method),

583 name_(name),

584 param1_(param1),

585 param2_(param2) {}

586

588

589 void Run(Solver* const) override {

590 (constraint_->*method_)(param1_, param2_);

592

594 return absl::StrCat("CallMethod_", name_, "(", constraint_->DebugString(),

598

599 private:

600 T* const constraint_;

601 void (T::* const method_)(P, Q);

602 const std::string name_;

603 P param1_;

604 Q param2_;

605};

606

607template <class T, class P, class Q>

609 void (T::*method)(P, Q), const std::string& name,

610 P param1, Q param2) {

611 return s->RevAlloc(

613}

615template <class T, class P, class Q, class R>

616class CallMethod3 : public Demon {

617 public:

618 CallMethod3(T* const ct, void (T::*method)(P, Q, R), const std::string& name,

619 P param1, Q param2, R param3)

620 : constraint_(ct),

621 method_(method),

622 name_(name),

623 param1_(param1),

624 param2_(param2),

625 param3_(param3) {}

626

628

629 void Run(Solver* const) override {

630 (constraint_->*method_)(param1_, param2_, param3_);

632

634 return absl::StrCat(absl::StrCat("CallMethod_", name_),

635 absl::StrCat("(", constraint_->DebugString()),

639 }

640

641 private:

642 T* const constraint_;

643 void (T::* const method_)(P, Q, R);

644 const std::string name_;

645 P param1_;

646 Q param2_;

647 R param3_;

648};

649

650template <class T, class P, class Q, class R>

652 void (T::*method)(P, Q, R), const std::string& name,

653 P param1, Q param2, R param3) {

654 return s->RevAlloc(

661

663

665template <class T>

666class DelayedCallMethod0 : public Demon {

667 public:

668 DelayedCallMethod0(T* const ct, void (T::*method)(), const std::string& name)

669 : constraint_(ct), method_(method), name_(name) {}

673 void Run(Solver* const) override { (constraint_->*method_)(); }

674

678

680 return "DelayedCallMethod_" + name_ + "(" + constraint_->DebugString() +

681 ")";

682 }

684 private:

685 T* const constraint_;

686 void (T::* const method_)();

687 const std::string name_;

688};

689

690template <class T>

692 void (T::*method)(),

693 const std::string& name) {

696

698template <class T, class P>

699class DelayedCallMethod1 : public Demon {

700 public:

701 DelayedCallMethod1(T* const ct, void (T::*method)(P), const std::string& name,

702 P param1)

703 : constraint_(ct), method_(method), name_(name), param1_(param1) {}

704

706

707 void Run(Solver* const) override { (constraint_->*method_)(param1_); }

708

712

714 return absl::StrCat("DelayedCallMethod_", name_, "(",

715 constraint_->DebugString(), ", ",

718

719 private:

720 T* const constraint_;

721 void (T::* const method_)(P);

722 const std::string name_;

723 P param1_;

724};

725

726template <class T, class P>

728 void (T::*method)(P),

729 const std::string& name, P param1) {

730 return s->RevAlloc(new DelayedCallMethod1<T, P>(ct, method, name, param1));

732

734template <class T, class P, class Q>

735class DelayedCallMethod2 : public Demon {

736 public:

738 const std::string& name, P param1, Q param2)

739 : constraint_(ct),

740 method_(method),

741 name_(name),

742 param1_(param1),

743 param2_(param2) {}

744

746

747 void Run(Solver* const) override {

748 (constraint_->*method_)(param1_, param2_);

750

754

756 return absl::StrCat(absl::StrCat("DelayedCallMethod_", name_),

757 absl::StrCat("(", constraint_->DebugString()),

760 }

761

762 private:

763 T* const constraint_;

764 void (T::* const method_)(P, Q);

765 const std::string name_;

766 P param1_;

767 Q param2_;

768};

769

770template <class T, class P, class Q>

772 void (T::*method)(P, Q),

773 const std::string& name, P param1,

774 Q param2) {

775 return s->RevAlloc(

777}

779

780#endif

781

782

783

784template <typename F>

785class LightIntFunctionElementCt : public Constraint {

786 public:

788 IntVar* const index, F values,

789 std::function<bool()> deep_serialize)

791 var_(var),

792 index_(index),

793 values_(std::move(values)),

794 deep_serialize_(std::move(deep_serialize)) {}

796

797 void Post() override {

799 solver(), this, &LightIntFunctionElementCt::IndexBound, "IndexBound");

800 index_->WhenBound(demon);

802

804 if (index_->Bound()) {

805 IndexBound();

806 }

808

809 std::string DebugString() const override {

810 return absl::StrFormat("LightIntFunctionElementCt(%s, %s)",

812 }

817 var_);

819 index_);

820

821 if (deep_serialize_ == nullptr || deep_serialize_()) {

823 index_->Max());

824 }

826 }

827

828 private:

829 void IndexBound() { var_->SetValue(values_(index_->Min())); }

830

831 IntVar* const var_;

832 IntVar* const index_;

833 F values_;

834 std::function<bool()> deep_serialize_;

835};

836

837

838

839template <typename F>

841 public:

843 IntVar* const index1, IntVar* const index2,

844 F values, std::function<bool()> deep_serialize)

846 var_(var),

847 index1_(index1),

848 index2_(index2),

849 values_(std::move(values)),

850 deep_serialize_(std::move(deep_serialize)) {}

852 void Post() override {

854 solver(), this, &LightIntIntFunctionElementCt::IndexBound,

855 "IndexBound");

856 index1_->WhenBound(demon);

857 index2_->WhenBound(demon);

858 }

860

861 std::string DebugString() const override {

862 return "LightIntIntFunctionElementCt";

864

868 var_);

870 index1_);

872 index2_);

873

874 const int64_t index1_min = index1_->Min();

875 const int64_t index1_max = index1_->Max();

878 if (deep_serialize_ == nullptr || deep_serialize_()) {

879 for (int i = index1_min; i <= index1_max; ++i) {

881 [this, i](int64_t j) { return values_(i, j); }, index2_->Min(),

882 index2_->Max());

883 }

884 }

886 }

887

888 private:

889 void IndexBound() {

890 if (index1_->Bound() && index2_->Bound()) {

891 var_->SetValue(values_(index1_->Min(), index2_->Min()));

892 }

893 }

894

895 IntVar* const var_;

896 IntVar* const index1_;

897 IntVar* const index2_;

898 F values_;

899 std::function<bool()> deep_serialize_;

900};

901

902

903

904template <typename F>

906 public:

908 IntVar* const index1, IntVar* const index2,

911 var_(var),

912 index1_(index1),

913 index2_(index2),

914 index3_(index3),

915 values_(std::move(values)) {}

917 void Post() override {

919 solver(), this, &LightIntIntIntFunctionElementCt::IndexBound,

920 "IndexBound");

921 index1_->WhenBound(demon);

922 index2_->WhenBound(demon);

923 index3_->WhenBound(demon);

924 }

926

927 std::string DebugString() const override {

928 return "LightIntIntFunctionElementCt";

930

934 var_);

936 index1_);

938 index2_);

940 index3_);

942 }

943

944 private:

945 void IndexBound() {

946 if (index1_->Bound() && index2_->Bound() && index3_->Bound()) {

947 var_->SetValue(values_(index1_->Min(), index2_->Min(), index3_->Min()));

948 }

949 }

950

951 IntVar* const var_;

952 IntVar* const index1_;

953 IntVar* const index2_;

954 IntVar* const index3_;

955 F values_;

956};

957

961

975

976

978 public:

981 virtual bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) = 0;

983 virtual void Start(const Assignment* assignment) = 0;

984 virtual void Reset() {}

985#ifndef SWIG

987#endif

989 virtual bool HoldsDelta() const { return false; }

993 public:

995

997 max_inversible_index_ = candidate_values_.size();

998 candidate_value_to_index_.resize(max_value + 1, -1);

999 committed_value_to_index_.resize(max_value + 1, -1);

1001

1005 DCHECK_LT(index, candidate_values_.size());

1006 return candidate_values_[index];

1007 }

1009 return committed_values_[index];

1010 }

1012 return checkpoint_values_[index];

1013 }

1015 candidate_values_[index] = value;

1016 if (index < max_inversible_index_) {

1017 candidate_value_to_index_[value] = index;

1018 }

1019 MarkChange(index);

1020 }

1021

1023 return candidate_is_active_[index];

1024 }

1026 if (active) {

1027 candidate_is_active_.Set(index);

1028 } else {

1029 candidate_is_active_.Clear(index);

1031 MarkChange(index);

1032 }

1035 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {

1036 const int64_t value = candidate_values_[index];

1037 committed_values_[index] = value;

1038 if (index < max_inversible_index_) {

1039 committed_value_to_index_[value] = index;

1040 }

1041 committed_is_active_.CopyBucket(candidate_is_active_, index);

1045 }

1046

1047 void CheckPoint() { checkpoint_values_ = committed_values_; }

1048

1049 void Revert(bool only_incremental) {

1050 incremental_changes_.ResetAllToFalse();

1051 if (only_incremental) return;

1052

1053 for (const int64_t index : changes_.PositionsSetAtLeastOnce()) {

1054 const int64_t committed_value = committed_values_[index];

1055 candidate_values_[index] = committed_value;

1056 if (index < max_inversible_index_) {

1057 candidate_value_to_index_[committed_value] = index;

1058 }

1059 candidate_is_active_.CopyBucket(committed_is_active_, index);

1060 }

1062 }

1063

1065 return changes_.PositionsSetAtLeastOnce();

1066 }

1068 return incremental_changes_.PositionsSetAtLeastOnce();

1069 }

1070

1071 void Resize(int size) {

1072 candidate_values_.resize(size);

1073 committed_values_.resize(size);

1074 checkpoint_values_.resize(size);

1075 candidate_is_active_.Resize(size);

1076 committed_is_active_.Resize(size);

1077 changes_.ClearAndResize(size);

1078 incremental_changes_.ClearAndResize(size);

1080

1082 return candidate_value_to_index_[value];

1083 }

1085 return committed_value_to_index_[value];

1086 }

1087

1088 private:

1089 void MarkChange(int64_t index) {

1090 incremental_changes_.Set(index);

1091 changes_.Set(index);

1093

1094 std::vector<int64_t> candidate_values_;

1095 std::vector<int64_t> committed_values_;

1096 std::vector<int64_t> checkpoint_values_;

1097

1100

1103

1104 int64_t max_inversible_index_ = -1;

1105 std::vector<int64_t> candidate_value_to_index_;

1106 std::vector<int64_t> committed_value_to_index_;

1107};

1108

1114class IntVarLocalSearchOperator : public LocalSearchOperator {

1115 public:

1116

1117

1118

1120 bool keep_inverse_values = false) {

1122 if (keep_inverse_values) {

1123 int64_t max_value = -1;

1124 for (const IntVar* const var : vars) {

1125 max_value = std::max(max_value, var->Max());

1126 }

1127 state_.SetCurrentDomainInjectiveAndKeepInverseValues(max_value);

1128 }

1129 }

1131

1132 bool HoldsDelta() const override { return true; }

1135 void Start(const Assignment* assignment) override {

1136 state_.CheckPoint();

1139 CHECK_LE(size, assignment->Size())

1140 << "Assignment contains fewer variables than operator";

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

1144 if (element->Var() != vars_[i]) {

1145 CHECK(container.Contains(vars_[i]))

1146 << "Assignment does not contain operator variable " << vars_[i];

1147 element = &(container.Element(vars_[i]));

1148 }

1151 }

1154 }

1155 virtual bool IsIncremental() const { return false; }

1156

1157 int Size() const { return vars_.size(); }

1160 int64_t Value(int64_t index) const {

1161 DCHECK_LT(index, vars_.size());

1162 return state_.CandidateValue(index);

1165 IntVar* Var(int64_t index) const { return vars_[index]; }

1166 virtual bool SkipUnchanged(int) const { return false; }

1169 return state_.CheckPointValue(index);

1170 }

1171 void SetValue(int64_t index, int64_t value) {

1175 return state_.CandidateIsActive(index);

1182 for (const int64_t index : state_.IncrementalIndicesChanged()) {

1184 const int64_t value = Value(index);

1187 AddToAssignment(var, value, activated, &assignment_indices_, index,

1189 }

1190 } else {

1193 const int64_t value = Value(index);

1194 const bool activated = Activated(index);

1197 index, delta);

1198 }

1199 }

1200 }

1201 return true;

1202 }

1203

1204 void RevertChanges(bool change_was_incremental) {

1205 candidate_has_changes_ = change_was_incremental && IsIncremental();

1206

1207 if (!candidate_has_changes_) {

1208 for (const int64_t index : state_.CandidateIndicesChanged()) {

1209 assignment_indices_[index] = -1;

1210 }

1211 }

1212 state_.Revert(candidate_has_changes_);

1213 }

1214

1215 void AddVars(const std::vector<IntVar*>& vars) {

1216 if (!vars.empty()) {

1217 vars_.insert(vars_.end(), vars.begin(), vars.end());

1218 const int64_t size = Size();

1219 assignment_indices_.resize(size, -1);

1220 state_.Resize(size);

1221 }

1222 }

1227 virtual void OnStart() {}

1228

1231

1239

1240 protected:

1243

1246

1248 return state_.CandidateInverseValue(index);

1249 }

1252 }

1253

1254 void AddToAssignment(IntVar* var, int64_t value, bool active,

1255 std::vector<int>* assignment_indices, int64_t index,

1260 if (assignment_indices != nullptr) {

1261 if ((*assignment_indices)[index] == -1) {

1262 (*assignment_indices)[index] = container->Size();

1263 element = assignment->FastAdd(var);

1264 } else {

1265 element = container->MutableElement((*assignment_indices)[index]);

1266 }

1267 } else {

1268 element = assignment->FastAdd(var);

1269 }

1270 if (active) {

1273 } else {

1275 }

1276 }

1277

1278 private:

1279 std::vector<IntVar*> vars_;

1280 mutable std::vector<int> assignment_indices_;

1281 bool candidate_has_changes_ = false;

1282

1283 LocalSearchOperatorState state_;

1284};

1285

1293

1314 public:

1315 explicit BaseLns(const std::vector<IntVar*>& vars);

1321 bool HasFragments() const override { return true; }

1322

1323 protected:

1324

1326

1327 private:

1330 std::vector<int> fragment_;

1331};

1338 public:

1339 explicit ChangeValue(const std::vector<IntVar*>& vars);

1341 virtual int64_t ModifyValue(int64_t index, int64_t value) = 0;

1342

1343 protected:

1346

1347 private:

1349

1350 int index_;

1351};

1353

1354

1356 public:

1358 : use_sibling_(use_sibling) {}

1360 template <class PathOperator>

1361 void Reset(const PathOperator& path_operator, int base_index_reference) {

1362 index_ = 0;

1364 const int64_t base_node = path_operator.BaseNode(base_index_reference);

1365 const int alternative_index =

1368 alternative_set_ =

1369 alternative_index >= 0

1370 ? absl::Span<const int64_t>(

1371 path_operator.alternative_sets_[alternative_index])

1372 : absl::Span<const int64_t>();

1373 }

1374 bool Next() { return ++index_ < alternative_set_.size(); }

1376 return (index_ >= alternative_set_.size()) ? -1 : alternative_set_[index_];

1377 }

1378

1379 private:

1380 const bool use_sibling_;

1381 int index_ = 0;

1382 absl::Span<const int64_t> alternative_set_;

1383};

1384

1389 template <class PathOperator>

1390 void Reset(const PathOperator& path_operator, int base_index_reference) {

1391 using Span = absl::Span<const int>;

1392 index_ = 0;

1393 const int64_t base_node = path_operator.BaseNode(base_index_reference);

1394 const int64_t start_node = path_operator.StartNode(base_index_reference);

1395 const auto& get_incoming_neighbors =

1396 path_operator.iteration_parameters_.get_incoming_neighbors;

1397 incoming_neighbors_ =

1398 path_operator.IsPathStart(base_node) || !get_incoming_neighbors

1400 : Span(get_incoming_neighbors(base_node, start_node));

1401 const auto& get_outgoing_neighbors =

1402 path_operator.iteration_parameters_.get_outgoing_neighbors;

1403 outgoing_neighbors_ =

1404 path_operator.IsPathEnd(base_node) || !get_outgoing_neighbors

1405 ? Span()

1406 : Span(get_outgoing_neighbors(base_node, start_node));

1407 }

1408 bool Next() {

1409 return ++index_ < incoming_neighbors_.size() + outgoing_neighbors_.size();

1410 }

1412 if (index_ < incoming_neighbors_.size()) {

1413 return incoming_neighbors_[index_];

1414 }

1415 const int index = index_ - incoming_neighbors_.size();

1416 return (index >= outgoing_neighbors_.size()) ? -1

1417 : outgoing_neighbors_[index];

1418 }

1420 return index_ < incoming_neighbors_.size();

1421 }

1423 return index_ >= incoming_neighbors_.size();

1424 }

1425

1426 private:

1427 int index_ = 0;

1428 absl::Span<const int> incoming_neighbors_;

1429 absl::Span<const int> outgoing_neighbors_;

1431

1432template <class PathOperator>

1436 : path_operator_(*path_operator),

1437 base_index_reference_(base_index_reference) {}

1439 DCHECK(!alternatives_.empty());

1440 DCHECK(!finished_);

1441 return alternatives_[0].get();

1442 }

1444 DCHECK(!alternatives_.empty());

1445 DCHECK(!finished_);

1446 return alternatives_[1].get();

1447 }

1449 DCHECK(neighbors_);

1450 DCHECK(!finished_);

1451 return neighbors_.get();

1452 }

1454 if (path_operator_.ConsiderAlternatives(base_index_reference_)) {

1455 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(

1456 true));

1457 alternatives_.push_back(std::make_unique<AlternativeNodeIterator>(

1458 false));

1461 neighbors_ = std::make_unique<NodeNeighborIterator>();

1462 }

1463 }

1464 void Reset(bool update_end_nodes = false) {

1465 finished_ = false;

1466 for (auto& alternative_iterator : alternatives_) {

1467 alternative_iterator->Reset(path_operator_, base_index_reference_);

1468 }

1469 if (neighbors_) {

1470 neighbors_->Reset(path_operator_, base_index_reference_);

1471 if (update_end_nodes) neighbor_end_node_ = neighbors_->GetValue();

1472 }

1473 }

1475 DCHECK(!finished_);

1476 for (auto& alternative_iterator : alternatives_) {

1477 if (alternative_iterator->Next()) return true;

1478 alternative_iterator->Reset(path_operator_, base_index_reference_);

1479 }

1480 if (neighbors_) {

1481 if (neighbors_->Next()) return true;

1482 neighbors_->Reset(path_operator_, base_index_reference_);

1483 }

1484 finished_ = true;

1485 return false;

1486 }

1488

1489 if (!neighbors_) return true;

1490 return neighbor_end_node_ == neighbors_->GetValue();

1491 }

1492

1493 private:

1494 const PathOperator& path_operator_;

1495 int base_index_reference_ = -1;

1496#ifndef SWIG

1497 std::vector<std::unique_ptr<AlternativeNodeIterator>> alternatives_;

1498#endif

1499 std::unique_ptr<NodeNeighborIterator> neighbors_;

1500 int neighbor_end_node_ = -1;

1501 bool finished_ = false;

1502};

1503

1514

1517template <bool ignore_path_vars>

1519 public:

1521 struct IterationParameters {

1529

1530

1531

1532

1533

1534

1535

1536

1537

1538

1542 std::function<const std::vector<int>&(

1543 int, int)>

1545 std::function<const std::vector<int>&(

1546 int, int)>

1548 };

1551 const std::vector<IntVar*>& path_vars,

1555 base_nodes_(

1557 end_nodes_(

1559 base_paths_(

1563 just_started_(false),

1564 first_start_(true),

1565 next_base_to_increment_(iteration_parameters.number_of_base_nodes),

1566 iteration_parameters_(std::move(iteration_parameters)),

1567 optimal_paths_enabled_(false),

1569 alternative_index_(next_vars.size(), -1) {

1570 DCHECK_GT(iteration_parameters_.number_of_base_nodes, 0);

1571 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {

1573 }

1574 if constexpr (!ignore_path_vars) {

1576 }

1577 path_basis_.push_back(0);

1578 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {

1580 }

1581 if ((path_basis_.size() > 2) ||

1582 (!next_vars.empty() && !next_vars.back()

1583 ->solver()

1584 ->parameters()

1585 .skip_locally_optimal_paths())) {

1586 iteration_parameters_.skip_locally_optimal_paths = false;

1587 }

1588 }

1590 const std::vector<IntVar*>& next_vars,

1591 const std::vector<IntVar*>& path_vars, int number_of_base_nodes,

1592 bool skip_locally_optimal_paths, bool accept_path_end_base,

1593 std::function<int(int64_t)> start_empty_path_class,

1594 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,

1595 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors)

1597 {number_of_base_nodes, skip_locally_optimal_paths,

1598 accept_path_end_base, std::move(start_empty_path_class),

1599 std::move(get_incoming_neighbors),

1600 std::move(get_outgoing_neighbors)}) {}

1604 first_start_ = true;

1606 }

1607 void Reset() override {

1608 active_paths_.Clear();

1610 }

1611

1612

1614 if constexpr (ignore_path_vars) return true;

1617 return Value(path_index) == OldValue(path_index);

1622

1624 int64_t Next(int64_t node) const {

1626 return Value(node);

1627 }

1628

1630 int64_t Prev(int64_t node) const {

1634 }

1638 int64_t Path(int64_t node) const {

1639 if constexpr (ignore_path_vars) return 0LL;

1646 protected:

1649 while (IncrementPosition()) {

1650

1651

1654 return true;

1656 }

1657 return false;

1658 }

1670

1671 int64_t BaseNode(int i) const { return base_nodes_[i]; }

1674 return GetNodeWithDefault(base_node_iterators_[i].GetAlternativeIterator(),

1676 }

1679 return GetNodeWithDefault(

1680 base_node_iterators_[i].GetSiblingAlternativeIterator(), BaseNode(i));

1681 }

1683 int64_t StartNode(int i) const { return path_starts_[base_paths_[i]]; }

1684

1685 int64_t EndNode(int i) const { return path_ends_[base_paths_[i]]; }

1687 const std::vector<int64_t>& path_starts() const { return path_starts_; }

1688

1693 : start_node;

1695

1706

1707

1708

1718 }

1722 next_base_to_increment_ = base_index;

1723 }

1728 int64_t OldNext(int64_t node) const {

1731 }

1733 int64_t PrevNext(int64_t node) const {

1736 }

1738 int64_t OldPrev(int64_t node) const {

1743 int64_t OldPath(int64_t node) const {

1744 if constexpr (ignore_path_vars) return 0LL;

1746 }

1747

1749 return node_path_starts_[node];

1750 }

1751

1752 int CurrentNodePathEnd(int64_t node) const { return node_path_ends_[node]; }

1753

1754

1755

1756 bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination) {

1757 if (destination == before_chain || destination == chain_end) return false;

1760 const int64_t destination_path = Path(destination);

1761 const int64_t after_chain = Next(chain_end);

1762 SetNext(chain_end, Next(destination), destination_path);

1763 if constexpr (!ignore_path_vars) {

1764 int current = destination;

1765 int next = Next(before_chain);

1766 while (current != chain_end) {

1767 SetNext(current, next, destination_path);

1768 current = next;

1769 next = Next(next);

1770 }

1771 } else {

1772 SetNext(destination, Next(before_chain), destination_path);

1773 }

1774 SetNext(before_chain, after_chain, Path(before_chain));

1775 return true;

1776 }

1777

1780 bool ReverseChain(int64_t before_chain, int64_t after_chain,

1781 int64_t* chain_last) {

1783 int64_t path = Path(before_chain);

1784 int64_t current = Next(before_chain);

1785 if (current == after_chain) {

1786 return false;

1787 }

1788 int64_t current_next = Next(current);

1789 SetNext(current, after_chain, path);

1790 while (current_next != after_chain) {

1791 const int64_t next = Next(current_next);

1792 SetNext(current_next, current, path);

1793 current = current_next;

1794 current_next = next;

1795 }

1796 SetNext(before_chain, current, path);

1797 *chain_last = current;

1798 return true;

1799 }

1800 return false;

1801 }

1802

1804 bool SwapNodes(int64_t node1, int64_t node2) {

1807 return false;

1808 }

1809 if (node1 == node2) return false;

1810 const int64_t prev_node1 = Prev(node1);

1811 const bool ok = MoveChain(prev_node1, node1, Prev(node2));

1812 return MoveChain(Prev(node2), node2, prev_node1) || ok;

1813 }

1814

1815

1816 bool MakeActive(int64_t node, int64_t destination) {

1817 if (IsPathEnd(destination)) return false;

1818 const int64_t destination_path = Path(destination);

1819 SetNext(node, Next(destination), destination_path);

1820 SetNext(destination, node, destination_path);

1821 return true;

1822 }

1825 bool MakeChainInactive(int64_t before_chain, int64_t chain_end) {

1826 const int64_t kNoPath = -1;

1829 const int64_t after_chain = Next(chain_end);

1830 int64_t current = Next(before_chain);

1831 while (current != after_chain) {

1832 const int64_t next = Next(current);

1833 SetNext(current, current, kNoPath);

1834 current = next;

1835 }

1837 return true;

1838 }

1839 return false;

1840 }

1841

1844 if (active == inactive) return false;

1845 const int64_t prev = Prev(active);

1847 }

1851 absl::Span<const int64_t> inactive_chain) {

1852 if (active_chain.empty()) return false;

1853 if (active_chain == inactive_chain) return false;

1854 const int before_active_chain = Prev(active_chain.front());

1855 if (!MakeChainInactive(before_active_chain, active_chain.back())) {

1856 return false;

1857 }

1858 for (auto it = inactive_chain.crbegin(); it != inactive_chain.crend();

1859 ++it) {

1860 if (!MakeActive(*it, before_active_chain)) return false;

1862 return true;

1863 }

1864

1866 void SetNext(int64_t from, int64_t to, int64_t path) {

1869 if constexpr (!ignore_path_vars) {

1872 }

1873 }

1874

1875

1878

1881

1883 bool IsInactive(int64_t node) const {

1884 return !IsPathEnd(node) && inactives_[node];

1885 }

1886

1889 virtual bool InitPosition() const { return false; }

1897

1898 int AddAlternativeSet(const std::vector<int64_t>& alternative_set) {

1899 const int alternative = alternative_sets_.size();

1900 for (int64_t node : alternative_set) {

1901 DCHECK_EQ(-1, alternative_index_[node]);

1902 alternative_index_[node] = alternative;

1903 }

1904 alternative_sets_.push_back(alternative_set);

1905 sibling_alternative_.push_back(-1);

1906 return alternative;

1907 }

1908#ifndef SWIG

1909

1910

1911 template <typename PairType>

1913 const std::vector<PairType>& pair_alternative_sets) {

1914 for (const auto& [alternative_set, sibling_alternative_set] :

1915 pair_alternative_sets) {

1916 sibling_alternative_.back() = AddAlternativeSet(alternative_set) + 1;

1918 }

1919 }

1920#endif

1922 int64_t GetActiveInAlternativeSet(int alternative_index) const {

1923 return alternative_index >= 0

1924 ? active_in_alternative_set_[alternative_index]

1925 : -1;

1926 }

1928 int64_t GetActiveAlternativeNode(int node) const {

1929 return GetActiveInAlternativeSet(alternative_index_[node]);

1930 }

1931

1932 int GetSiblingAlternativeIndex(int node) const {

1934 return alternative >= 0 ? sibling_alternative_[alternative] : -1;

1935 }

1937 int GetAlternativeIndex(int node) const {

1938 return (node >= alternative_index_.size()) ? -1 : alternative_index_[node];

1942 int64_t GetActiveAlternativeSibling(int node) const {

1947

1951 int64_t exclude) const {

1952 if (before_chain == chain_end || before_chain == exclude) return false;

1953 int64_t current = before_chain;

1954 int chain_size = 0;

1955 while (current != chain_end) {

1957 if (IsPathEnd(current)) return false;

1958 current = Next(current);

1959 ++chain_size;

1960 if (current == exclude) return false;

1962 return true;

1963 }

1964

1965 bool HasNeighbors() const {

1966 return iteration_parameters_.get_incoming_neighbors != nullptr ||

1967 iteration_parameters_.get_outgoing_neighbors != nullptr;

1968 }

1969

1970 struct Neighbor {

1971

1972 int neighbor;

1973

1974

1975 bool outgoing;

1977 Neighbor GetNeighborForBaseNode(int64_t base_index) const {

1978 auto* iterator = base_node_iterators_[base_index].GetNeighborIterator();

1979 return {.neighbor = iterator->GetValue(),

1980 .outgoing = iterator->IsOutgoingNeighbor()};

1982

1984

1985 private:

1986 template <class NodeIterator>

1987 static int GetNodeWithDefault(const NodeIterator* node_iterator,

1988 int default_value) {

1989 const int node = node_iterator->GetValue();

1990 return node >= 0 ? node : default_value;

1991 }

1992

1993 void OnStart() override {

1994 optimal_paths_enabled_ = false;

1995 if (!iterators_initialized_) {

1996 iterators_initialized_ = true;

1997 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {

1998 base_node_iterators_[i].Initialize();

1999 }

2000 }

2001 InitializeBaseNodes();

2002 InitializeAlternatives();

2003 OnNodeInitialization();

2004 }

2005

2007 bool OnSamePath(int64_t node1, int64_t node2) const {

2008 if (IsInactive(node1) != IsInactive(node2)) {

2009 return false;

2010 }

2011 for (int node = node1; !IsPathEnd(node); node = OldNext(node)) {

2012 if (node == node2) {

2013 return true;

2014 }

2015 }

2016 for (int node = node2; !IsPathEnd(node); node = OldNext(node)) {

2017 if (node == node1) {

2018 return true;

2019 }

2020 }

2021 return false;

2022 }

2023

2024 bool CheckEnds() const {

2025 for (int i = iteration_parameters_.number_of_base_nodes - 1; i >= 0; --i) {

2026 if (base_nodes_[i] != end_nodes_[i] ||

2027 !base_node_iterators_[i].HasReachedEnd()) {

2028 return true;

2029 }

2030 }

2031 return false;

2032 }

2033 bool IncrementPosition() {

2034 const int base_node_size = iteration_parameters_.number_of_base_nodes;

2035

2036 if (just_started_) {

2037 just_started_ = false;

2038 return true;

2039 }

2040 const int number_of_paths = path_starts_.size();

2041

2042

2043

2044

2045

2046 int last_restarted = base_node_size;

2047 for (int i = base_node_size - 1; i >= 0; --i) {

2048 if (base_nodes_[i] < number_of_nexts_ && i <= next_base_to_increment_) {

2049 if (base_node_iterators_[i].Increment()) break;

2050 base_nodes_[i] = OldNext(base_nodes_[i]);

2051 base_node_iterators_[i].Reset();

2052 if (iteration_parameters_.accept_path_end_base ||

2053 !IsPathEnd(base_nodes_[i])) {

2054 break;

2055 }

2056 }

2057 base_nodes_[i] = StartNode(i);

2058 base_node_iterators_[i].Reset();

2059 last_restarted = i;

2060 }

2061 next_base_to_increment_ = base_node_size;

2062

2063

2064

2065

2066

2067

2068

2069

2070

2071 for (int i = last_restarted; i < base_node_size; ++i) {

2072 base_nodes_[i] = GetBaseNodeRestartPosition(i);

2073 base_node_iterators_[i].Reset();

2074 }

2075 if (last_restarted > 0) {

2076 return CheckEnds();

2077 }

2078

2079

2080

2081 if (optimal_paths_enabled_ &&

2082 iteration_parameters_.skip_locally_optimal_paths) {

2083 if (path_basis_.size() > 1) {

2084 for (int i = 1; i < path_basis_.size(); ++i) {

2085 active_paths_.DeactivatePathPair(StartNode(path_basis_[i - 1]),

2086 StartNode(path_basis_[i]));

2087 }

2088 } else {

2089 active_paths_.DeactivatePathPair(StartNode(path_basis_[0]),

2090 StartNode(path_basis_[0]));

2091 }

2092 }

2093 std::vector<int> current_starts(base_node_size);

2094 for (int i = 0; i < base_node_size; ++i) {

2095 current_starts[i] = StartNode(i);

2096 }

2097

2098

2099 optimal_paths_enabled_ = true;

2100 while (true) {

2101 for (int i = base_node_size - 1; i >= 0; --i) {

2102 const int next_path_index = base_paths_[i] + 1;

2103 if (next_path_index < number_of_paths) {

2104 base_paths_[i] = next_path_index;

2105 base_nodes_[i] = path_starts_[next_path_index];

2106 base_node_iterators_[i].Reset();

2107 if (i == 0 || !OnSamePathAsPreviousBase(i)) {

2108 break;

2109 }

2110 } else {

2111 base_paths_[i] = 0;

2112 base_nodes_[i] = path_starts_[0];

2113 base_node_iterators_[i].Reset();

2114 }

2115 }

2116 if (!iteration_parameters_.skip_locally_optimal_paths) return CheckEnds();

2117

2118

2119 if (path_basis_.size() > 1) {

2120 for (int j = 1; j < path_basis_.size(); ++j) {

2121 if (active_paths_.IsPathPairActive(StartNode(path_basis_[j - 1]),

2122 StartNode(path_basis_[j]))) {

2123 return CheckEnds();

2124 }

2125 }

2126 } else {

2127 if (active_paths_.IsPathPairActive(StartNode(path_basis_[0]),

2128 StartNode(path_basis_[0]))) {

2129 return CheckEnds();

2130 }

2131 }

2132

2133

2134 if (!CheckEnds()) return false;

2135 bool stop = true;

2136 for (int i = 0; i < base_node_size; ++i) {

2137 if (StartNode(i) != current_starts[i]) {

2138 stop = false;

2139 break;

2140 }

2141 }

2142 if (stop) return false;

2143 }

2144 return CheckEnds();

2145 }

2146

2147 void InitializePathStarts() {

2148

2149

2150 int max_next = -1;

2151 std::vector<bool> has_prevs(number_of_nexts_, false);

2152 for (int i = 0; i < number_of_nexts_; ++i) {

2153 const int next = OldNext(i);

2154 if (next < number_of_nexts_) {

2155 has_prevs[next] = true;

2156 }

2157 max_next = std::max(max_next, next);

2158 }

2159

2160 if (iteration_parameters_.skip_locally_optimal_paths) {

2161 active_paths_.Initialize(

2162 [&has_prevs](int node) { return !has_prevs[node]; });

2163 for (int i = 0; i < number_of_nexts_; ++i) {

2164 if (!has_prevs[i]) {

2165 int current = i;

2166 while (!IsPathEnd(current)) {

2167 if ((OldNext(current) != PrevNext(current))) {

2168 active_paths_.ActivatePath(i);

2169 break;

2170 }

2171 current = OldNext(current);

2172 }

2173 }

2174 }

2175 }

2176

2177

2178 std::vector<bool> empty_found(number_of_nexts_, false);

2179 std::vector<int64_t> new_path_starts;

2180 for (int i = 0; i < number_of_nexts_; ++i) {

2181 if (!has_prevs[i]) {

2182 if (IsPathEnd(OldNext(i))) {

2183 if (iteration_parameters_.start_empty_path_class != nullptr) {

2184 if (empty_found[iteration_parameters_.start_empty_path_class(i)])

2185 continue;

2186 empty_found[iteration_parameters_.start_empty_path_class(i)] = true;

2187 }

2188 }

2189 new_path_starts.push_back(i);

2190 }

2191 }

2192 if (!first_start_) {

2193

2194

2195

2196

2197 std::vector<int> node_paths(max_next + 1, -1);

2198 for (int i = 0; i < path_starts_.size(); ++i) {

2199 int node = path_starts_[i];

2200 while (!IsPathEnd(node)) {

2201 node_paths[node] = i;

2202 node = OldNext(node);

2203 }

2204 node_paths[node] = i;

2205 }

2206 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {

2207 if (IsInactive(base_nodes_[j]) || node_paths[base_nodes_[j]] == -1) {

2208

2209

2210 base_nodes_[j] = GetBaseNodeRestartPosition(j);

2211 base_paths_[j] = node_paths[base_nodes_[j]];

2212 } else {

2213 base_paths_[j] = node_paths[base_nodes_[j]];

2214 }

2215

2216 base_node_iterators_[j].Reset();

2217 }

2218

2219

2220

2221 int new_index = 0;

2222 absl::flat_hash_set<int> found_bases;

2223 for (int i = 0; i < path_starts_.size(); ++i) {

2224 int index = new_index;

2225

2226 while (index < new_path_starts.size() &&

2227 new_path_starts[index] < path_starts_[i]) {

2228 ++index;

2229 }

2230 const bool found = (index < new_path_starts.size() &&

2231 new_path_starts[index] == path_starts_[i]);

2232 if (found) {

2233 new_index = index;

2234 }

2235 for (int j = 0; j < iteration_parameters_.number_of_base_nodes; ++j) {

2236 if (base_paths_[j] == i && !found_bases.contains(j)) {

2237 found_bases.insert(j);

2238 base_paths_[j] = new_index;

2239

2240

2241 if (!found) {

2242 base_nodes_[j] = new_path_starts[new_index];

2243 }

2244 }

2245 }

2246 }

2247 }

2248 path_starts_.swap(new_path_starts);

2249

2250

2251 path_ends_.clear();

2252 path_ends_.reserve(path_starts_.size());

2253 int64_t max_node_index = number_of_nexts_ - 1;

2254 for (const int start_node : path_starts_) {

2255 int64_t node = start_node;

2256 while (!IsPathEnd(node)) node = OldNext(node);

2257 path_ends_.push_back(node);

2258 max_node_index = std::max(max_node_index, node);

2259 }

2260 node_path_starts_.assign(max_node_index + 1, -1);

2261 node_path_ends_.assign(max_node_index + 1, -1);

2262 for (int i = 0; i < path_starts_.size(); ++i) {

2263 const int64_t start_node = path_starts_[i];

2264 const int64_t end_node = path_ends_[i];

2265 int64_t node = start_node;

2266 while (!IsPathEnd(node)) {

2267 node_path_starts_[node] = start_node;

2268 node_path_ends_[node] = end_node;

2269 node = OldNext(node);

2270 }

2271 node_path_starts_[node] = start_node;

2272 node_path_ends_[node] = end_node;

2273 }

2274 }

2275 void InitializeInactives() {

2276 inactives_.clear();

2277 for (int i = 0; i < number_of_nexts_; ++i) {

2278 inactives_.push_back(OldNext(i) == i);

2279 }

2280 }

2281 void InitializeBaseNodes() {

2282

2283 InitializeInactives();

2284 InitializePathStarts();

2285 if (first_start_ || InitPosition()) {

2286

2287

2288 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {

2289 base_paths_[i] = 0;

2290 base_nodes_[i] = path_starts_[0];

2291 }

2292 first_start_ = false;

2293 }

2294 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {

2295

2296 int64_t base_node = base_nodes_[i];

2297 if (RestartAtPathStartOnSynchronize() || IsInactive(base_node)) {

2298 base_node = path_starts_[base_paths_[i]];

2299 base_nodes_[i] = base_node;

2300 }

2301 end_nodes_[i] = base_node;

2302 }

2303

2304

2305 for (int i = 1; i < iteration_parameters_.number_of_base_nodes; ++i) {

2306 if (OnSamePathAsPreviousBase(i) &&

2307 !OnSamePath(base_nodes_[i - 1], base_nodes_[i])) {

2308 const int64_t base_node = base_nodes_[i - 1];

2309 base_nodes_[i] = base_node;

2310 end_nodes_[i] = base_node;

2311 base_paths_[i] = base_paths_[i - 1];

2312 }

2313 }

2314 for (int i = 0; i < iteration_parameters_.number_of_base_nodes; ++i) {

2315 base_node_iterators_[i].Reset(true);

2316 }

2317 just_started_ = true;

2318 }

2319 void InitializeAlternatives() {

2320 active_in_alternative_set_.resize(alternative_sets_.size(), -1);

2321 for (int i = 0; i < alternative_sets_.size(); ++i) {

2322 const int64_t current_active = active_in_alternative_set_[i];

2323 if (current_active >= 0 && !IsInactive(current_active)) continue;

2324 for (int64_t index : alternative_sets_[i]) {

2325 if (!IsInactive(index)) {

2326 active_in_alternative_set_[i] = index;

2327 break;

2328 }

2329 }

2330 }

2331 }

2332

2333 class ActivePaths {

2334 public:

2335 explicit ActivePaths(int num_nodes) : start_to_path_(num_nodes, -1) {}

2336 void Clear() { to_reset_ = true; }

2337 template <typename T>

2338 void Initialize(T is_start) {

2339 if (is_path_pair_active_.empty()) {

2340 num_paths_ = 0;

2341 absl::c_fill(start_to_path_, -1);

2342 for (int i = 0; i < start_to_path_.size(); ++i) {

2343 if (is_start(i)) {

2344 start_to_path_[i] = num_paths_;

2345 ++num_paths_;

2346 }

2347 }

2348 }

2349 }

2350 void DeactivatePathPair(int start1, int start2) {

2351 if (to_reset_) Reset();

2352 is_path_pair_active_[start_to_path_[start1] * num_paths_ +

2353 start_to_path_[start2]] = false;

2354 }

2355 void ActivatePath(int start) {

2356 if (to_reset_) Reset();

2357 const int p1 = start_to_path_[start];

2358 const int p1_block = num_paths_ * p1;

2359 for (int p2 = 0; p2 < num_paths_; ++p2) {

2360 is_path_pair_active_[p1_block + p2] = true;

2361 }

2362 for (int p2_block = 0; p2_block < is_path_pair_active_.size();

2363 p2_block += num_paths_) {

2364 is_path_pair_active_[p2_block + p1] = true;

2365 }

2366 }

2367 bool IsPathPairActive(int start1, int start2) const {

2368 if (to_reset_) return true;

2369 return is_path_pair_active_[start_to_path_[start1] * num_paths_ +

2370 start_to_path_[start2]];

2371 }

2372

2373 private:

2374 void Reset() {

2375 if (!to_reset_) return;

2376 is_path_pair_active_.assign(num_paths_ * num_paths_, true);

2377 to_reset_ = false;

2378 }

2379

2380 bool to_reset_ = true;

2381 int num_paths_ = 0;

2382 std::vector<int64_t> start_to_path_;

2383 std::vector<bool> is_path_pair_active_;

2384 };

2385

2386 std::unique_ptr<int[]> base_nodes_;

2387 std::unique_ptr<int[]> end_nodes_;

2388 std::unique_ptr<int[]> base_paths_;

2389 std::vector<int> node_path_starts_;

2390 std::vector<int> node_path_ends_;

2391 bool iterators_initialized_ = false;

2392#ifndef SWIG

2393 std::vector<BaseNodeIterators<PathOperator>> base_node_iterators_;

2394#endif

2395 std::vector<int64_t> path_starts_;

2396 std::vector<int64_t> path_ends_;

2397 std::vector<bool> inactives_;

2398 bool just_started_;

2399 bool first_start_;

2400 int next_base_to_increment_;

2401 IterationParameters iteration_parameters_;

2402 bool optimal_paths_enabled_;

2403 std::vector<int> path_basis_;

2404 ActivePaths active_paths_;

2406#ifndef SWIG

2407 std::vector<std::vector<int64_t>> alternative_sets_;

2408#endif

2409 std::vector<int> alternative_index_;

2410 std::vector<int64_t> active_in_alternative_set_;

2411 std::vector<int> sibling_alternative_;

2412

2416};

2417

2418#ifndef SWIG

2420

2428

2429

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

2432 const std::vector<IntVar*>& secondary_vars,

2433 std::function<int(int64_t)> start_empty_path_class,

2434 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =

2435 nullptr,

2436 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =

2437 nullptr);

2438

2440

2453

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

2456 const std::vector<IntVar*>& secondary_vars,

2457 std::function<int(int64_t)> start_empty_path_class,

2458 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =

2459 nullptr,

2460 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =

2461 nullptr,

2462 int64_t chain_length = 1LL, bool single_path = false,

2463 const std::string& name = "Relocate");

2464

2466

2474

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

2477 const std::vector<IntVar*>& secondary_vars,

2478 std::function<int(int64_t)> start_empty_path_class,

2479 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =

2480 nullptr,

2481 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =

2482 nullptr);

2483

2485

2495

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

2498 const std::vector<IntVar*>& secondary_vars,

2499 std::function<int(int64_t)> start_empty_path_class,

2500 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =

2501 nullptr,

2502 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =

2503 nullptr);

2504

2506

2513

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

2516 const std::vector<IntVar*>& secondary_vars,

2517 std::function<int(int64_t)> start_empty_path_class,

2518 std::function<const std::vector<int>&(int, int)> get_incoming_neighbors =

2519 nullptr,

2520 std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors =

2521 nullptr);

2522

2524

2531

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

2534 const std::vector<IntVar*>& secondary_vars,

2535 std::function<int(int64_t)> start_empty_path_class);

2536

2537

2538

2539

2540

2541

2542

2543

2544

2545

2546

2547

2548

2549

2550

2551

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

2554 const std::vector<IntVar*>& secondary_vars,

2555 std::function<int(int64_t)> start_empty_path_class);

2556

2557

2558

2559

2560

2561

2562

2563

2564

2565

2566

2567

2568

2569

2570

2571

2572

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

2575 const std::vector<IntVar*>& secondary_vars,

2576 std::function<int(int64_t)> start_empty_path_class);

2577

2579

2583

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

2586 const std::vector<IntVar*>& secondary_vars,

2587 std::function<int(int64_t)> start_empty_path_class);

2588

2590

2596

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

2599 const std::vector<IntVar*>& secondary_vars,

2600 std::function<int(int64_t)> start_empty_path_class);

2601

2603

2609

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

2612 const std::vector<IntVar*>& secondary_vars,

2613 std::function<int(int64_t)> start_empty_path_class);

2614

2616

2623

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

2626 const std::vector<IntVar*>& secondary_vars,

2627 std::function<int(int64_t)> start_empty_path_class);

2628

2630

2636

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

2639 const std::vector<IntVar*>& secondary_vars,

2640 std::function<int(int64_t)> start_empty_path_class);

2641

2643

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

2646 const std::vector<IntVar*>& secondary_vars,

2647 std::function<int(int64_t)> start_empty_path_class, int max_chain_size);

2648

2650

2661

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

2664 const std::vector<IntVar*>& secondary_vars,

2665 std::function<int(int64_t)> start_empty_path_class);

2666

2668

2675

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

2678 const std::vector<IntVar*>& secondary_vars,

2680 int chain_length);

2681

2689

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

2692 const std::vector<IntVar*>& secondary_vars,

2694 int tsp_size);

2695

2697

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

2700 const std::vector<IntVar*>& secondary_vars,

2702

2704

2708

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

2711 const std::vector<IntVar*>& secondary_vars,

2712 int number_of_chunks, int chunk_size,

2713 bool unactive_fragments);

2714#endif

2715

2716#if !defined(SWIG)

2717

2718

2719

2720

2721

2722

2723

2724

2725

2726

2727

2728

2729

2730

2731

2732

2734 public:

2738

2739

2740

2742 DCHECK(!graph_was_built_);

2743 num_nodes_ = std::max(num_nodes_, std::max(tail.value(), head.value()) + 1);

2744 const ArcId arc_id(arcs_.size());

2745 arcs_.push_back({.tail = tail, .head = head, .arc_id = arc_id});

2746 return arc_id;

2748

2749

2751

2752

2754

2755 private:

2756

2757

2758 bool HasDirectedCycle() const;

2759

2760 struct Arc {

2764 bool operator<(const Arc& other) const {

2765 return std::tie(tail, arc_id) < std::tie(other.tail, other.arc_id);

2766 }

2767 };

2768 int num_nodes_ = 0;

2769 std::vector<Arc> arcs_;

2770

2771

2772

2774

2775 bool graph_was_built_ = false;

2776

2778

2779 std::vector<NodeId> nodes_to_visit_;

2780

2781 std::vector<ArcId> sorted_arcs_;

2782};

2783

2784

2785

2786

2787

2788

2789

2790

2791

2792

2793

2794

2795class LocalSearchState {

2796 public:

2797 class Variable;

2800

2801 VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max);

2802

2803 bool RelaxVariableDomain(VariableDomainId domain_id);

2804 bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value);

2805 bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value);

2806 int64_t VariableDomainMin(VariableDomainId domain_id) const;

2809 int64_t max);

2811

2814

2815

2816

2818

2819

2821

2826 return state_domains_are_all_nonempty_ && num_committed_empty_domains_ == 0;

2827 }

2828

2829 void AddWeightedSumConstraint(

2830 const std::vector<VariableDomainId>& input_domain_ids,

2831 const std::vector<int64_t>& input_weights, int64_t input_offset,

2833

2834

2835 void CompileConstraints();

2836

2840

2841 struct VariableDomain {

2842 int64_t min;

2843 int64_t max;

2844 };

2845 bool IntersectionIsEmpty(const VariableDomain& d1,

2846 const VariableDomain& d2) const {

2847 return d1.max < d2.min || d2.max < d1.min;

2848 }

2851 struct TrailedVariableDomain {

2852 VariableDomain committed_domain;

2853 VariableDomainId domain_id;

2854 };

2855 std::vector<TrailedVariableDomain> trailed_domains_;

2856 util_intops::StrongVector<VariableDomainId, bool> domain_is_trailed_;

2857

2858 bool state_domains_are_all_nonempty_ = true;

2859 bool state_has_relaxed_domains_ = false;

2860

2861

2862 int num_committed_empty_domains_ = 0;

2863 int trailed_num_committed_empty_domains_ = 0;

2864

2865

2866

2867 class Constraint;

2868 void TrailConstraint(Constraint* constraint) {

2869 trailed_constraints_.push_back(constraint);

2870 }

2871 std::vector<Constraint*> trailed_constraints_;

2872

2873

2874

2875 class DependencyGraph {

2876 public:

2877 DependencyGraph() {}

2878

2879

2880

2881

2882

2883 struct Dependency {

2885 int input_index;

2886 ConstraintId constraint_id;

2887 };

2888

2889 void AddDomainsConstraintDependencies(

2890 const std::vector<VariableDomainId>& domain_ids,

2891 ConstraintId constraint_id);

2892

2893 void AddConstraintDomainDependency(ConstraintId constraint_id,

2894 VariableDomainId domain_id);

2900

2901 const std::vector<Dependency>& ComputeSortedDependencies(

2903

2904 private:

2905 using ArcId = SubDagComputer::ArcId;

2906 using NodeId = SubDagComputer::NodeId;

2907

2908

2910

2911

2912

2913 NodeId GetOrCreateNodeOfConstraintId(ConstraintId constraint_id);

2914

2916

2918

2920

2922

2923

2924 int num_dag_nodes_ = 1;

2925

2926 std::vector<Dependency> sorted_dependencies_;

2927 };

2928 DependencyGraph dependency_graph_;

2929

2930

2931

2932

2933 struct Trigger {

2934 Constraint* constraint;

2935 int input_index;

2936 };

2937

2938

2939

2940 std::vector<Trigger> triggers_;

2942

2943

2944

2945

2946 class Constraint {

2947 public:

2948 virtual ~Constraint() = default;

2949 virtual LocalSearchState::VariableDomain Propagate(int input_index) = 0;

2951 virtual void Commit() = 0;

2952 virtual void Revert() = 0;

2953 };

2954

2955

2956 class WeightedSum final : public Constraint {

2957 public:

2959 const std::vector<VariableDomainId>& input_domain_ids,

2960 const std::vector<int64_t>& input_weights, int64_t input_offset,

2962 ~WeightedSum() override = default;

2963 LocalSearchState::VariableDomain Propagate(int input_index) override;

2964 void Commit() override;

2965 void Revert() override;

2966 VariableDomainId Output() const override { return output_; }

2967

2968 private:

2969

2970

2971 struct WeightedVariable {

2972 int64_t min;

2973 int64_t max;

2974 int64_t committed_min;

2975 int64_t committed_max;

2976 int64_t weight;

2977 VariableDomainId domain;

2978 bool is_trailed;

2979 void Commit() {

2980 committed_min = min;

2981 committed_max = max;

2982 is_trailed = false;

2983 }

2984 void Revert() {

2985 min = committed_min;

2986 max = committed_max;

2987 is_trailed = false;

2988 }

2989 };

2990 std::vector<WeightedVariable> inputs_;

2991 std::vector<WeightedVariable*> trailed_inputs_;

2992

2993 struct Invariants {

2994

2995 int64_t num_neg_inf;

2996

2997 int64_t wsum_mins;

2998

2999 int64_t num_pos_inf;

3000

3001 int64_t wsum_maxs;

3002 };

3003 Invariants invariants_;

3004 Invariants committed_invariants_;

3005

3007 LocalSearchState* const state_;

3008 bool constraint_is_trailed_ = false;

3009 };

3010

3011 util_intops::StrongVector<ConstraintId, std::unique_ptr<Constraint>>

3012 constraints_;

3013};

3014

3015

3016

3017

3018

3019

3020class LocalSearchState::Variable {

3021 public:

3022 Variable() : state_(nullptr), domain_id_(VariableDomainId(-1)) {}

3023 int64_t Min() const {

3025 return state_->VariableDomainMin(domain_id_);

3026 }

3027 int64_t Max() const {

3029 return state_->VariableDomainMax(domain_id_);

3030 }

3031

3032

3033 bool SetMin(int64_t new_min) const {

3035 return state_->TightenVariableDomainMin(domain_id_, new_min) &&

3036 state_->PropagateTighten(domain_id_);

3037 }

3038

3039

3040 bool SetMax(int64_t new_max) const {

3041 if (!Exists()) return true;

3042 return state_->TightenVariableDomainMax(domain_id_, new_max) &&

3043 state_->PropagateTighten(domain_id_);

3044 }

3046 if (state_ == nullptr) return;

3047 if (state_->RelaxVariableDomain(domain_id_)) {

3048 state_->PropagateRelax(domain_id_);

3049 }

3050 }

3051 bool Exists() const { return state_ != nullptr; }

3058 : state_(state), domain_id_(domain_id) {}

3059

3062};

3063#endif

3064

3075

3082 public:

3088

3093

3094

3095

3096

3097

3099 int64_t objective_min, int64_t objective_max) = 0;

3100 virtual bool IsIncremental() const { return false; }

3101

3107 virtual void Synchronize(const Assignment* assignment,

3111

3113 virtual void Reset() {}

3114

3116 virtual int64_t GetSynchronizedObjectiveValue() const { return 0LL; }

3118

3120};

3121

3126 public:

3127

3128

3129 enum FilterEventType { kAccept, kRelax };

3130 struct FilterEvent {

3132 FilterEventType event_type;

3133 int priority;

3134 };

3135

3136 std::string DebugString() const override {

3137 return "LocalSearchFilterManager";

3138 }

3139

3140

3141

3147

3151

3153 const Assignment* deltadelta, int64_t objective_min,

3154 int64_t objective_max);

3158 int64_t GetAcceptedObjectiveValue() const { return accepted_value_; }

3159

3160 private:

3161

3162

3163 void FindIncrementalEventEnd();

3164

3165 std::vector<FilterEvent> events_;

3166 int last_event_called_ = -1;

3167

3168

3169

3170

3171 int incremental_events_end_ = 0;

3172 int64_t synchronized_value_;

3173 int64_t accepted_value_;

3174};

3175

3177 public:

3184

3185 bool FindIndex(IntVar* const var, int64_t* index) const {

3186 DCHECK(index != nullptr);

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

3188 *index = (var_index < var_index_to_index_.size())

3189 ? var_index_to_index_[var_index]

3190 : kUnassigned;

3191 return *index != kUnassigned;

3192 }

3193

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

3196 int Size() const { return vars_.size(); }

3197 IntVar* Var(int index) const { return vars_[index]; }

3198 int64_t Value(int index) const {

3199 DCHECK(IsVarSynced(index));

3200 return values_[index];

3201 }

3202 bool IsVarSynced(int index) const { return var_synced_[index]; }

3203

3204 protected:

3205 virtual void OnSynchronize(const Assignment*) {}

3206 void SynchronizeOnAssignment(const Assignment* assignment);

3207

3209 std::vector<IntVar*> vars_;

3210 std::vector<int64_t> values_;

3211 std::vector<bool> var_synced_;

3212 std::vector<int> var_index_to_index_;

3213 static const int kUnassigned;

3215

3220 std::string DebugString() const override { return "PropagationMonitor"; }

3221

3223 virtual void BeginConstraintInitialPropagation(Constraint* constraint) = 0;

3224 virtual void EndConstraintInitialPropagation(Constraint* constraint) = 0;

3225 virtual void BeginNestedConstraintInitialPropagation(Constraint* parent,

3227 virtual void EndNestedConstraintInitialPropagation(Constraint* parent,

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

3238 virtual void SetMax(IntExpr* expr, int64_t new_max) = 0;

3239 virtual void SetRange(IntExpr* expr, int64_t new_min, int64_t new_max) = 0;

3243 virtual void SetRange(IntVar* var, int64_t new_min, int64_t new_max) = 0;

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

3249 const std::vector<int64_t>& values) = 0;

3254 int64_t new_max) = 0;

3258 int64_t new_max) = 0;

3262 int64_t new_max) = 0;

3270 const std::vector<int>& rank_first,

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

3272 const std::vector<int>& unperformed) = 0;

3274 void Install() override;

3276

3278

3282 std::string DebugString() const override { return "LocalSearchMonitor"; }

3283

3285 virtual void BeginOperatorStart() = 0;

3286 virtual void EndOperatorStart() = 0;

3293 bool neighbor_found) = 0;

3296 bool neighbor_found) = 0;

3301

3305

3308 static const int kUnboundBooleanVarValue;

3311 : IntVar(s, name), value_(kUnboundBooleanVarValue) {}

3314

3315 int64_t Min() const override { return (value_ == 1); }

3316 void SetMin(int64_t m) override;

3317 int64_t Max() const override { return (value_ != 0); }

3319 void SetRange(int64_t mi, int64_t ma) override;

3321 int64_t Value() const override {

3324 }

3330 uint64_t Size() const override;

3331 bool Contains(int64_t v) const override;

3337 IntVar* IsEqual(int64_t constant) override;

3338 IntVar* IsDifferent(int64_t constant) override;

3339 IntVar* IsGreaterOrEqual(int64_t constant) override;

3343 std::string BaseName() const override { return "BooleanVar"; }

3344

3345 int RawValue() const { return value_; }

3346

3351};

3352

3359 public:

3361 : symmetry_manager_(nullptr), index_in_symmetry_manager_(-1) {}

3363

3364 void AddIntegerVariableEqualValueClause(IntVar* var, int64_t value);

3365 void AddIntegerVariableGreaterOrEqualValueClause(IntVar* var, int64_t value);

3366 void AddIntegerVariableLessOrEqualValueClause(IntVar* var, int64_t value);

3367

3368 private:

3370 void set_symmetry_manager_and_index(SymmetryManager* manager, int index) {

3371 CHECK(symmetry_manager_ == nullptr);

3372 CHECK_EQ(-1, index_in_symmetry_manager_);

3373 symmetry_manager_ = manager;

3374 index_in_symmetry_manager_ = index;

3375 }

3376 SymmetryManager* symmetry_manager() const { return symmetry_manager_; }

3377 int index_in_symmetry_manager() const { return index_in_symmetry_manager_; }

3378

3379 SymmetryManager* symmetry_manager_;

3381 int index_in_symmetry_manager_;

3382};

3383

3387 public:

3388 SearchLog(Solver* solver, std::vector<IntVar*> vars, std::string vars_name,

3389 std::vector<double> scaling_factors, std::vector<double> offsets,

3390 std::function<std::string()> display_callback,

3391 bool display_on_new_solutions_only, int period);

3393 void EnterSearch() override;

3394 void ExitSearch() override;

3395 bool AtSolution() override;

3396 void BeginFail() override;

3397 void NoMoreSolutions() override;

3405 std::string DebugString() const override;

3406

3407 protected:

3408

3409 virtual void OutputLine(const std::string& line);

3410

3411 private:

3413

3414 const int period_;

3415 std::unique_ptr<WallTimer> timer_;

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

3417 const std::string vars_name_;

3418 const std::vector<double> scaling_factors_;

3419 const std::vector<double> offsets_;

3420 std::function<std::string()> display_callback_;

3421 const bool display_on_new_solutions_only_;

3422 int nsol_;

3423 absl::Duration tick_;

3424 std::vector<int64_t> objective_min_;

3425 std::vector<int64_t> objective_max_;

3426 std::vector<int64_t> last_objective_value_;

3427 absl::Duration last_objective_timestamp_;

3428 int min_right_depth_;

3429 int max_depth_;

3430 int sliding_min_depth_;

3431 int sliding_max_depth_;

3432 int neighbors_offset_ = 0;

3433};

3434

3440 public:

3441 enum VoidConstraintType {

3442 VOID_FALSE_CONSTRAINT = 0,

3443 VOID_TRUE_CONSTRAINT,

3444 VOID_CONSTRAINT_MAX,

3445 };

3446

3447 enum VarConstantConstraintType {

3448 VAR_CONSTANT_EQUALITY = 0,

3449 VAR_CONSTANT_GREATER_OR_EQUAL,

3450 VAR_CONSTANT_LESS_OR_EQUAL,

3458 };

3530

3535

3542

3547

3553 int64_t value,

3559 IntVar* var, int64_t value1, int64_t value2,

3563 Constraint* ct, IntVar* var, int64_t value1, int64_t value2,

3565

3567

3576

3579

3582

3584

3587

3591

3593

3596

3602

3610

3612

3614 IntVar* var, int64_t value1, int64_t value2,

3616

3618 IntExpr* expression, IntVar* var, int64_t value1, int64_t value2,

3620

3622

3624 IntVar* var, const std::vector<int64_t>& values,

3626

3628 IntExpr* expression, IntVar* var, const std::vector<int64_t>& values,

3630

3632

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

3641

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

3647 IntExpr* expression, const std::vector<IntVar*>& var,

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

3650

3652

3654 const std::vector<IntVar*>& vars, int64_t value,

3656

3658 IntExpr* expression, const std::vector<IntVar*>& var, int64_t value,

3660

3662

3663 private:

3664 Solver* const solver_;

3666

3668#if !defined(SWIG)

3670 public:

3672 const std::string& TypeName() const;

3673 void SetTypeName(const std::string& type_name);

3674

3676 void SetIntegerArgument(const std::string& arg_name, int64_t value);

3677 void SetIntegerArrayArgument(const std::string& arg_name,

3678 const std::vector<int64_t>& values);

3679 void SetIntegerMatrixArgument(const std::string& arg_name,

3683 const std::vector<IntVar*>& vars);

3686 const std::vector<IntervalVar*>& vars);

3689 const std::vector<SequenceVar*>& vars);

3690

3694

3697 int64_t def) const;

3700 const std::string& arg_name) const;

3702 const std::string& arg_name) const;

3703

3705 const std::string& arg_name) const;

3707 const std::string& arg_name) const;

3708

3709 private:

3710 std::string type_name_;

3711 absl::flat_hash_map<std::string, int64_t> integer_argument_;

3712 absl::flat_hash_map<std::string, std::vector<int64_t>>

3713 integer_array_argument_;

3714 absl::flat_hash_map<std::string, IntTupleSet> matrix_argument_;

3715 absl::flat_hash_map<std::string, IntExpr*> integer_expression_argument_;

3716 absl::flat_hash_map<std::string, IntervalVar*> interval_argument_;

3717 absl::flat_hash_map<std::string, SequenceVar*> sequence_argument_;

3718 absl::flat_hash_map<std::string, std::vector<IntVar*>>

3719 integer_variable_array_argument_;

3720 absl::flat_hash_map<std::string, std::vector<IntervalVar*>>

3721 interval_array_argument_;

3722 absl::flat_hash_map<std::string, std::vector<SequenceVar*>>

3723 sequence_array_argument_;

3724};

3725

3728 public:

3730

3732

3734 void BeginVisitModel(const std::string& solver_name) override;

3735 void EndVisitModel(const std::string& solver_name) override;

3736 void BeginVisitConstraint(const std::string& type_name,

3737 const Constraint* constraint) override;

3738 void EndVisitConstraint(const std::string& type_name,

3741 const IntExpr* expr) override;

3743 const IntExpr* expr) override;

3746 const std::string& operation, int64_t value,

3747 IntVar* delegate) override;

3749 const std::string& operation, int64_t value,

3754 int64_t value) override;

3756 const std::vector<int64_t>& values) override;

3761 IntExpr* argument) override;

3763 const std::string& arg_name,

3764 const std::vector<IntVar*>& arguments) override;

3769 const std::string& arg_name,

3770 const std::vector<IntervalVar*>& arguments) override;

3775 const std::string& arg_name,

3776 const std::vector<SequenceVar*>& arguments) override;

3777

3778 protected:

3782

3783 private:

3784 std::vector<ArgumentHolder*> holders_;

3785};

3786

3787template <class T>

3789 public:

3791 : index_min_(index_min),

3792 index_max_(index_max),

3793 values_(new T[index_max - index_min + 1]) {

3794 DCHECK_LE(index_min, index_max);

3795 }

3796

3797 ~ArrayWithOffset() override {}

3798

3799 virtual T Evaluate(int64_t index) const {

3800 DCHECK_GE(index, index_min_);

3801 DCHECK_LE(index, index_max_);

3802 return values_[index - index_min_];

3803 }

3804

3805 void SetValue(int64_t index, T value) {

3806 DCHECK_GE(index, index_min_);

3807 DCHECK_LE(index, index_max_);

3808 values_[index - index_min_] = value;

3810

3811 std::string DebugString() const override { return "ArrayWithOffset"; }

3812

3813 private:

3814 const int64_t index_min_;

3815 const int64_t index_max_;

3816 std::unique_ptr<T[]> values_;

3822

3824template <class T, class C>

3826 public:

3828 : block_size_(block_size), block_offset_(0) {

3829 CHECK_GT(block_size, 0);

3830 }

3831

3833 for (int i = 0; i < elements_.size(); ++i) {

3834 delete[] elements_[i];

3835 }

3836 }

3838 T At(int64_t index) const {

3839 const int64_t block_index = ComputeBlockIndex(index);

3840 const int64_t relative_index = block_index - block_offset_;

3841 if (relative_index < 0 || relative_index >= elements_.size()) {

3842 return T();

3843 }

3844 const T* block = elements_[relative_index];

3845 return block != nullptr ? block[index - block_index * block_size_] : T();

3846 }

3847

3848 void RevInsert(Solver* const solver, int64_t index, T value) {

3849 const int64_t block_index = ComputeBlockIndex(index);

3850 T* const block = GetOrCreateBlock(block_index);

3851 const int64_t residual = index - block_index * block_size_;

3852 solver->SaveAndSetValue(reinterpret_cast<C*>(&block[residual]),

3853 reinterpret_cast<C>(value));

3854 }

3855

3856 private:

3857 T* NewBlock() const {

3858 T* const result = new T[block_size_];

3859 for (int i = 0; i < block_size_; ++i) {

3860 result[i] = T();

3861 }

3862 return result;

3863 }

3864

3865 T* GetOrCreateBlock(int block_index) {

3866 if (elements_.size() == 0) {

3867 block_offset_ = block_index;

3868 GrowUp(block_index);

3869 } else if (block_index < block_offset_) {

3870 GrowDown(block_index);

3871 } else if (block_index - block_offset_ >= elements_.size()) {

3872 GrowUp(block_index);

3873 }

3874 T* block = elements_[block_index - block_offset_];

3875 if (block == nullptr) {

3876 block = NewBlock();

3877 elements_[block_index - block_offset_] = block;

3878 }

3879 return block;

3880 }

3881

3882 int64_t ComputeBlockIndex(int64_t value) const {

3883 return value >= 0 ? value / block_size_

3884 : (value - block_size_ + 1) / block_size_;

3885 }

3886

3887 void GrowUp(int64_t block_index) {

3888 elements_.resize(block_index - block_offset_ + 1);

3889 }

3890

3891 void GrowDown(int64_t block_index) {

3892 const int64_t delta = block_offset_ - block_index;

3893 block_offset_ = block_index;

3894 DCHECK_GT(delta, 0);

3895 elements_.insert(elements_.begin(), delta, nullptr);

3896 }

3897

3898 const int64_t block_size_;

3899 std::vector<T*> elements_;

3900 int block_offset_;

3901};

3902

3907template <class T>

3908class RevIntSet {

3909 public:

3910 static constexpr int kNoInserted = -1;

3911

3913 explicit RevIntSet(int capacity)

3914 : elements_(new T[capacity]),

3915 num_elements_(0),

3916 capacity_(capacity),

3917 position_(new int[capacity]),

3918 delete_position_(true) {

3919 for (int i = 0; i < capacity; ++i) {

3921 }

3923

3925 RevIntSet(int capacity, int* shared_positions, int shared_positions_size)

3926 : elements_(new T[capacity]),

3927 num_elements_(0),

3928 capacity_(capacity),

3929 position_(shared_positions),

3930 delete_position_(false) {

3931 for (int i = 0; i < shared_positions_size; ++i) {

3933 }

3934 }

3935

3937 if (delete_position_) {

3938 delete[] position_;

3939 }

3940 }

3941

3942 int Size() const { return num_elements_.Value(); }

3943

3944 int Capacity() const { return capacity_; }

3945

3946 T Element(int i) const {

3947 DCHECK_GE(i, 0);

3948 DCHECK_LT(i, num_elements_.Value());

3949 return elements_[i];

3950 }

3951

3952 T RemovedElement(int i) const {

3953 DCHECK_GE(i, 0);

3954 DCHECK_LT(i + num_elements_.Value(), capacity_);

3955 return elements_[i + num_elements_.Value()];

3957

3959 const int position = num_elements_.Value();

3960 DCHECK_LT(position, capacity_);

3961 DCHECK(NotAlreadyInserted(elt));

3962 elements_[position] = elt;

3963 position_[elt] = position;

3964 num_elements_.Incr(solver);

3965 }

3966

3967 void Remove(Solver* const solver, const T& value_index) {

3968 num_elements_.Decr(solver);

3969 SwapTo(value_index, num_elements_.Value());

3971

3972 void Restore(Solver* const solver, const T& value_index) {

3973 SwapTo(value_index, num_elements_.Value());

3974 num_elements_.Incr(solver);

3975 }

3976

3977 void Clear(Solver* const solver) { num_elements_.SetValue(solver, 0); }

3978

3979

3982 const_iterator end() const { return elements_.get() + num_elements_.Value(); }

3983

3986 bool NotAlreadyInserted(const T& elt) {

3987 for (int i = 0; i < num_elements_.Value(); ++i) {

3988 if (elt == elements_[i]) {

3989 return false;

3990 }

3991 }

3992 return true;

3995 void SwapTo(T value_index, int next_position) {

3996 const int current_position = position_[value_index];

3997 if (current_position != next_position) {

3998 const T next_value_index = elements_[next_position];

3999 elements_[current_position] = next_value_index;

4000 elements_[next_position] = value_index;

4001 position_[value_index] = next_position;

4002 position_[next_value_index] = current_position;

4003 }

4004 }

4005

4007 std::unique_ptr<T[]> elements_;

4011 const int capacity_;

4013 int* position_;

4015 const bool delete_position_;

4016};

4017

4019

4020class RevPartialSequence {

4021 public:

4022 explicit RevPartialSequence(const std::vector<int>& items)

4023 : elements_(items),

4024 first_ranked_(0),

4025 last_ranked_(items.size() - 1),

4026 size_(items.size()),

4027 position_(new int[size_]) {

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

4029 elements_[i] = items[i];

4030 position_[i] = i;

4031 }

4033

4035 : elements_(size),

4036 first_ranked_(0),

4037 last_ranked_(size - 1),

4038 size_(size),

4039 position_(new int[size_]) {

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

4041 elements_[i] = i;

4042 position_[i] = i;

4043 }

4044 }

4045

4047

4048 int NumFirstRanked() const { return first_ranked_.Value(); }

4049

4050 int NumLastRanked() const { return size_ - 1 - last_ranked_.Value(); }

4051

4052 int Size() const { return size_; }

4053

4054#if !defined(SWIG)

4055 const int& operator[](int index) const {

4056 DCHECK_GE(index, 0);

4057 DCHECK_LT(index, size_);

4058 return elements_[index];

4059 }

4061

4063 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());

4064 SwapTo(elt, first_ranked_.Value());

4065 first_ranked_.Incr(solver);

4066 }

4069 DCHECK_LE(first_ranked_.Value(), last_ranked_.Value());

4070 SwapTo(elt, last_ranked_.Value());

4071 last_ranked_.Decr(solver);

4072 }

4073

4075 const int position = position_[elt];

4076 return (position < first_ranked_.Value() ||

4077 position > last_ranked_.Value());

4078 }

4079

4081 std::string result = "[";

4082 for (int i = 0; i < first_ranked_.Value(); ++i) {

4083 absl::StrAppend(&result, elements_[i]);

4084 if (i != first_ranked_.Value() - 1) {

4085 result.append("-");

4087 }

4088 result.append("|");

4089 for (int i = first_ranked_.Value(); i <= last_ranked_.Value(); ++i) {

4090 absl::StrAppend(&result, elements_[i]);

4091 if (i != last_ranked_.Value()) {

4092 result.append("-");

4093 }

4094 }

4095 result.append("|");

4096 for (int i = last_ranked_.Value() + 1; i < size_; ++i) {

4097 absl::StrAppend(&result, elements_[i]);

4098 if (i != size_ - 1) {

4099 result.append("-");

4100 }

4101 }

4102 result.append("]");

4103 return result;

4104 }

4105

4106 private:

4107 void SwapTo(int elt, int next_position) {

4108 const int current_position = position_[elt];

4109 if (current_position != next_position) {

4110 const int next_elt = elements_[next_position];

4111 elements_[current_position] = next_elt;

4112 elements_[next_position] = elt;

4113 position_[elt] = next_position;

4114 position_[next_elt] = current_position;

4115 }

4116 }

4117

4119 std::vector<int> elements_;

4121 NumericalRev<int> first_ranked_;

4123 NumericalRev<int> last_ranked_;

4125 const int size_;

4127 std::unique_ptr<int[]> position_;

4128};

4129

4134class UnsortedNullableRevBitset {

4135 public:

4137 explicit UnsortedNullableRevBitset(int bit_size);

4138

4139 ~UnsortedNullableRevBitset() {}

4140

4141

4143 void Init(Solver* solver, const std::vector<uint64_t>& mask);

4144

4146

4147 bool RevSubtract(Solver* solver, const std::vector<uint64_t>& mask);

4148

4151 bool RevAnd(Solver* solver, const std::vector<uint64_t>& mask);

4152

4155 int ActiveWordSize() const { return active_words_.Size(); }

4156

4158 bool Empty() const { return active_words_.Size() == 0; }

4159

4167 bool Intersects(const std::vector<uint64_t>& mask, int* support_index);

4168

4170 int64_t bit_size() const { return bit_size_; }

4172 int64_t word_size() const { return word_size_; }

4174 const RevIntSet<int>& active_words() const { return active_words_; }

4175

4176 private:

4177 void CleanUpActives(Solver* solver);

4178

4179 const int64_t bit_size_;

4180 const int64_t word_size_;

4181 RevArray<uint64_t> bits_;

4183 std::vector<int> to_remove_;

4185

4186template <class T>

4187bool IsArrayConstant(const std::vector<T>& values, const T& value) {

4188 for (int i = 0; i < values.size(); ++i) {

4189 if (values[i] != value) {

4190 return false;

4191 }

4192 }

4193 return true;

4194}

4195

4196template <class T>

4198 for (int i = 0; i < values.size(); ++i) {

4199 if (values[i] != 0 && values[i] != 1) {

4200 return false;

4201 }

4202 }

4203 return true;

4204}

4205

4206template <class T>

4207bool AreAllOnes(const std::vector<T>& values) {

4210

4211template <class T>

4212bool AreAllNull(const std::vector<T>& values) {

4213 return IsArrayConstant(values, T(0));

4214}

4215

4216template <class T>

4218 for (const T& current_value : values) {

4219 if (current_value < value) {

4220 return false;

4221 }

4222 }

4223 return true;

4225

4226template <class T>

4227bool AreAllLessOrEqual(const std::vector<T>& values, const T& value) {

4228 for (const T& current_value : values) {

4229 if (current_value > value) {

4230 return false;

4231 }

4232 }

4233 return true;

4234}

4235

4236template <class T>

4240

4241template <class T>

4242bool AreAllNegative(const std::vector<T>& values) {

4243 return AreAllLessOrEqual(values, T(0));

4244}

4245

4246template <class T>

4250

4251template <class T>

4252bool AreAllStrictlyNegative(const std::vector<T>& values) {

4253 return AreAllLessOrEqual(values, T(-1));

4255

4256template <class T>

4257bool IsIncreasingContiguous(const std::vector<T>& values) {

4258 for (int i = 0; i < values.size() - 1; ++i) {

4259 if (values[i + 1] != values[i] + 1) {

4260 return false;

4261 }

4262 }

4263 return true;

4265

4266template <class T>

4267bool IsIncreasing(const std::vector<T>& values) {

4268 for (int i = 0; i < values.size() - 1; ++i) {

4269 if (values[i + 1] < values[i]) {

4270 return false;

4271 }

4272 }

4273 return true;

4274}

4275

4276template <class T>

4277bool IsArrayInRange(const std::vector<IntVar*>& vars, T range_min,

4278 T range_max) {

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

4280 if (vars[i]->Min() < range_min || vars[i]->Max() > range_max) {

4281 return false;

4282 }

4283 }

4284 return true;

4285}

4286

4287inline bool AreAllBound(const std::vector<IntVar*>& vars) {

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

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

4290 return false;

4291 }

4292 }

4293 return true;

4294}

4295

4296inline bool AreAllBooleans(const std::vector<IntVar*>& vars) {

4298}

4302template <class T>

4304 const std::vector<T>& values) {

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

4306 if (values[i] != 0 && !vars[i]->Bound()) {

4307 return false;

4311}

4312

4314inline bool AreAllBoundTo(const std::vector<IntVar*>& vars, int64_t value) {

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

4316 if (!vars[i]->Bound() || vars[i]->Min() != value) {

4317 return false;

4318 }

4319 }

4320 return true;

4321}

4322

4323inline int64_t MaxVarArray(const std::vector<IntVar*>& vars) {

4324 DCHECK(!vars.empty());

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

4328 result = std::max<int64_t>(result, vars[i]->Max());

4329 }

4330 return result;

4331}

4332

4333inline int64_t MinVarArray(const std::vector<IntVar*>& vars) {

4334 DCHECK(!vars.empty());

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

4338 result = std::min<int64_t>(result, vars[i]->Min());

4339 }

4340 return result;

4341}

4342

4343inline void FillValues(const std::vector<IntVar*>& vars,

4344 std::vector<int64_t>* const values) {

4345 values->clear();

4346 values->resize(vars.size());

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

4348 (*values)[i] = vars[i]->Value();

4349 }

4350}

4351

4352inline int64_t PosIntDivUp(int64_t e, int64_t v) {

4353 DCHECK_GT(v, 0);

4354 return (e < 0 || e % v == 0) ? e / v : e / v + 1;

4356

4357inline int64_t PosIntDivDown(int64_t e, int64_t v) {

4358 DCHECK_GT(v, 0);

4359 return (e >= 0 || e % v == 0) ? e / v : e / v - 1;

4360}

4361

4363

int64_t MemoryUsage(int unused)

AlternativeNodeIterator(bool use_sibling)

Definition constraint_solveri.h:1368

bool Next()

Definition constraint_solveri.h:1385

void Reset(const PathOperator &path_operator, int base_index_reference)

Definition constraint_solveri.h:1372

~AlternativeNodeIterator()

Definition constraint_solveri.h:1370

int GetValue() const

Definition constraint_solveri.h:1386

Argument Holder: useful when visiting a model.

Definition constraint_solveri.h:3681

const IntTupleSet & FindIntegerMatrixArgumentOrDie(const std::string &arg_name) const

void SetIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &vars)

void SetIntervalArgument(const std::string &arg_name, IntervalVar *var)

void SetIntervalArrayArgument(const std::string &arg_name, const std::vector< IntervalVar * > &vars)

IntExpr * FindIntegerExpressionArgumentOrDie(const std::string &arg_name) const

bool HasIntegerExpressionArgument(const std::string &arg_name) const

Checks if arguments exist.

const std::vector< IntVar * > & FindIntegerVariableArrayArgumentOrDie(const std::string &arg_name) const

void SetSequenceArgument(const std::string &arg_name, SequenceVar *var)

bool HasIntegerVariableArrayArgument(const std::string &arg_name) const

const std::vector< int64_t > & FindIntegerArrayArgumentOrDie(const std::string &arg_name) const

int64_t FindIntegerArgumentOrDie(const std::string &arg_name) const

void SetIntegerExpressionArgument(const std::string &arg_name, IntExpr *expr)

void SetSequenceArrayArgument(const std::string &arg_name, const std::vector< SequenceVar * > &vars)

int64_t FindIntegerArgumentWithDefault(const std::string &arg_name, int64_t def) const

Getters.

std::string DebugString() const override

Definition constraint_solveri.h:3823

const E & Element(const V *const var) const

E * MutableElement(const V *const var)

bool Contains(const V *const var) const

IntContainer * MutableIntVarContainer()

IntVarElement * FastAdd(IntVar *var)

Adds without checking if variable has been previously added.

AssignmentContainer< IntVar, IntVarElement > IntContainer

virtual IntVar * CastToVar()

~BaseIntExpr() override

Definition constraint_solveri.h:119

IntVar * Var() override

Creates a variable from the expression.

BaseIntExpr(Solver *const s)

Definition constraint_solveri.h:118

Here's a sample relaxing one variable at a time:

Definition constraint_solveri.h:1324

void AppendToFragment(int index)

bool HasFragments() const override

Definition constraint_solveri.h:1332

virtual void InitFragments()

BaseLns(const std::vector< IntVar * > &vars)

bool MakeOneNeighbor() override

This method should not be overridden. Override NextFragment() instead.

virtual bool NextFragment()=0

BaseNodeIterators(const PathOperator *path_operator, int base_index_reference)

Definition constraint_solveri.h:1446

AlternativeNodeIterator * GetAlternativeIterator() const

Definition constraint_solveri.h:1454

bool Increment()

Definition constraint_solveri.h:1485

NodeNeighborIterator * GetNeighborIterator() const

Definition constraint_solveri.h:1459

void Reset(bool update_end_nodes=false)

Definition constraint_solveri.h:1475

AlternativeNodeIterator * GetSiblingAlternativeIterator() const

Definition constraint_solveri.h:1449

void Initialize()

Definition constraint_solveri.h:1464

bool HasReachedEnd() const

Definition constraint_solveri.h:1498

virtual std::string DebugString() const

void CopyBucket(const Bitset64< IndexType > &other, IndexType i)

IntVarIterator * MakeDomainIterator(bool reversible) const override

IntVarIterator * MakeHoleIterator(bool reversible) const override

void RemoveValue(int64_t v) override

This method removes the value 'v' from the domain of the variable.

SimpleRevFIFO< Demon * > delayed_bound_demons_

Definition constraint_solveri.h:3362

void SetMax(int64_t m) override

void SetRange(int64_t mi, int64_t ma) override

This method sets both the min and the max of the expression.

void RemoveInterval(int64_t l, int64_t u) override

virtual void RestoreValue()=0

void WhenDomain(Demon *d) override

Definition constraint_solveri.h:3341

SimpleRevFIFO< Demon * > bound_demons_

Definition constraint_solveri.h:3361

static const int kUnboundBooleanVarValue

Definition constraint_solveri.h:3320

void WhenBound(Demon *d) override

bool Bound() const override

Returns true if the min and the max of the expression are equal.

Definition constraint_solveri.h:3332

int VarType() const override

Definition constraint_solveri.h:3347

int value_

Definition constraint_solveri.h:3360

IntVar * IsLessOrEqual(int64_t constant) override

std::string BaseName() const override

Returns a base name for automatic naming.

Definition constraint_solveri.h:3355

void WhenRange(Demon *d) override

Attach a demon that will watch the min or the max of the expression.

Definition constraint_solveri.h:3340

Demon proxy to a method on the constraint with no arguments.

Definition constraint_solveri.h:513

~CallMethod0() override

Definition constraint_solveri.h:518

std::string DebugString() const override

Definition constraint_solveri.h:522

CallMethod0(T *const ct, void(T::*method)(), const std::string &name)

Definition constraint_solveri.h:515

Demon proxy to a method on the constraint with one argument.

Definition constraint_solveri.h:551

~CallMethod1() override

Definition constraint_solveri.h:557

CallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)

Definition constraint_solveri.h:553

std::string DebugString() const override

Definition constraint_solveri.h:561

Demon proxy to a method on the constraint with two arguments.

Definition constraint_solveri.h:581

std::string DebugString() const override

Definition constraint_solveri.h:597

~CallMethod2() override

Definition constraint_solveri.h:591

CallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)

Definition constraint_solveri.h:583

Demon proxy to a method on the constraint with three arguments.

Definition constraint_solveri.h:620

~CallMethod3() override

Definition constraint_solveri.h:631

CallMethod3(T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)

Definition constraint_solveri.h:622

std::string DebugString() const override

Definition constraint_solveri.h:637

virtual int64_t ModifyValue(int64_t index, int64_t value)=0

bool MakeOneNeighbor() override

This method should not be overridden. Override ModifyValue() instead.

ChangeValue(const std::vector< IntVar * > &vars)

Constraint(Solver *const solver)

Low-priority demon proxy to a method on the constraint with no arguments.

Definition constraint_solveri.h:670

~DelayedCallMethod0() override

Definition constraint_solveri.h:675

DelayedCallMethod0(T *const ct, void(T::*method)(), const std::string &name)

Definition constraint_solveri.h:672

std::string DebugString() const override

Definition constraint_solveri.h:683

Solver::DemonPriority priority() const override

Definition constraint_solveri.h:679

~DelayedCallMethod1() override

Definition constraint_solveri.h:709

DelayedCallMethod1(T *const ct, void(T::*method)(P), const std::string &name, P param1)

Definition constraint_solveri.h:705

Solver::DemonPriority priority() const override

Definition constraint_solveri.h:713

std::string DebugString() const override

Definition constraint_solveri.h:717

Low-priority demon proxy to a method on the constraint with two arguments.

Definition constraint_solveri.h:739

std::string DebugString() const override

Definition constraint_solveri.h:759

Solver::DemonPriority priority() const override

Definition constraint_solveri.h:755

DelayedCallMethod2(T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)

Definition constraint_solveri.h:741

~DelayedCallMethod2() override

Definition constraint_solveri.h:749

virtual void SetValue(int64_t v)

This method sets the value of the expression.

virtual bool Bound() const

Returns true if the min and the max of the expression are equal.

virtual int64_t Min() const =0

IntVar * Var(int index) const

Definition constraint_solveri.h:3209

int64_t OldInverseValue(int64_t index) const

Definition constraint_solveri.h:1258

void AddToAssignment(IntVar *var, int64_t value, bool active, std::vector< int > *assignment_indices, int64_t index, Assignment *assignment) const

Definition constraint_solveri.h:1262

virtual bool SkipUnchanged(int) const

Definition constraint_solveri.h:1174

virtual bool IsIncremental() const

Definition constraint_solveri.h:1163

int Size() const

Definition constraint_solveri.h:1165

virtual void OnStart()

Definition constraint_solveri.h:1235

bool Activated(int64_t index) const

Definition constraint_solveri.h:1182

void SetValue(int64_t index, int64_t value)

Definition constraint_solveri.h:1179

void Start(const Assignment *assignment) override

Definition constraint_solveri.h:1143

void RevertChanges(bool change_was_incremental)

Definition constraint_solveri.h:1212

bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override

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

Definition constraint_solveri.h:1223

void Deactivate(int64_t index)

Definition constraint_solveri.h:1186

IntVar * Var(int64_t index) const

Returns the variable of given index.

Definition constraint_solveri.h:1173

int64_t Value(int64_t index) const

Definition constraint_solveri.h:1168

int64_t InverseValue(int64_t index) const

Definition constraint_solveri.h:1255

bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const

Definition constraint_solveri.h:1188

int64_t PrevValue(int64_t index) const

Definition constraint_solveri.h:1176

bool HoldsDelta() const override

Definition constraint_solveri.h:1140

IntVarLocalSearchOperator(const std::vector< IntVar * > &vars, bool keep_inverse_values=false)

Definition constraint_solveri.h:1127

void Activate(int64_t index)

Definition constraint_solveri.h:1185

int64_t OldValue(int64_t index) const

Definition constraint_solveri.h:1175

virtual bool MakeOneNeighbor()

MakeNextNeighbor() in a subclass of IntVarLocalSearchOperator.

~IntVarLocalSearchOperator() override

Definition constraint_solveri.h:1138

int index() const

Returns the index of the variable.

LightIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index, F values, std::function< bool()> deep_serialize)

Definition constraint_solveri.h:791

~LightIntFunctionElementCt() override

Definition constraint_solveri.h:799

void InitialPropagate() override

Definition constraint_solveri.h:807

void Accept(ModelVisitor *const visitor) const override

Accepts the given visitor.

Definition constraint_solveri.h:818

std::string DebugString() const override

Definition constraint_solveri.h:813

void Post() override

Definition constraint_solveri.h:801

~LightIntIntFunctionElementCt() override

Definition constraint_solveri.h:855

void Accept(ModelVisitor *const visitor) const override

Accepts the given visitor.

Definition constraint_solveri.h:869

void InitialPropagate() override

Definition constraint_solveri.h:863

void Post() override

Definition constraint_solveri.h:856

LightIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, F values, std::function< bool()> deep_serialize)

Definition constraint_solveri.h:846

std::string DebugString() const override

Definition constraint_solveri.h:865

void Post() override

Definition constraint_solveri.h:921

LightIntIntIntFunctionElementCt(Solver *const solver, IntVar *const var, IntVar *const index1, IntVar *const index2, IntVar *const index3, F values)

Definition constraint_solveri.h:911

std::string DebugString() const override

Definition constraint_solveri.h:931

void Accept(ModelVisitor *const visitor) const override

Accepts the given visitor.

Definition constraint_solveri.h:935

~LightIntIntIntFunctionElementCt() override

Definition constraint_solveri.h:920

void InitialPropagate() override

Definition constraint_solveri.h:929

LocalSearchFilterManager(std::vector< FilterEvent > filter_events)

int64_t GetSynchronizedObjectiveValue() const

Definition constraint_solveri.h:3169

void Synchronize(const Assignment *assignment, const Assignment *delta)

Synchronizes all filters to assignment.

bool Accept(LocalSearchMonitor *monitor, const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)

virtual bool IsIncremental() const

Definition constraint_solveri.h:3112

virtual void Reset()

Sets the filter to empty solution.

Definition constraint_solveri.h:3125

virtual void Revert()

Cancels the changes made by the last Relax()/Accept() calls.

Definition constraint_solveri.h:3122

virtual bool Accept(const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)=0

virtual int64_t GetAcceptedObjectiveValue() const

Objective value from the last time Accept() was called and returned true.

Definition constraint_solveri.h:3131

virtual void Synchronize(const Assignment *assignment, const Assignment *delta)=0

virtual bool IsActive() const =0

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

virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0

virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0

void Install() override

Install itself on the solver.

virtual void BeginFiltering(const LocalSearchFilter *filter)=0

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

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

int64_t CheckPointValue(int64_t index) const

Definition constraint_solveri.h:1019

void SetCandidateActive(int64_t index, bool active)

Definition constraint_solveri.h:1033

void SetCurrentDomainInjectiveAndKeepInverseValues(int max_value)

Definition constraint_solveri.h:1004

void Resize(int size)

Definition constraint_solveri.h:1079

void Revert(bool only_incremental)

Definition constraint_solveri.h:1057

int64_t CandidateValue(int64_t index) const

Definition constraint_solveri.h:1012

LocalSearchOperatorState()

Definition constraint_solveri.h:1002

void CheckPoint()

Definition constraint_solveri.h:1055

void SetCandidateValue(int64_t index, int64_t value)

Definition constraint_solveri.h:1022

const std::vector< int64_t > & IncrementalIndicesChanged() const

Definition constraint_solveri.h:1075

const std::vector< int64_t > & CandidateIndicesChanged() const

Definition constraint_solveri.h:1072

int64_t CommittedInverseValue(int64_t value) const

Definition constraint_solveri.h:1092

int64_t CommittedValue(int64_t index) const

Definition constraint_solveri.h:1016

bool CandidateIsActive(int64_t index) const

Definition constraint_solveri.h:1030

int64_t CandidateInverseValue(int64_t value) const

Definition constraint_solveri.h:1089

void Commit()

Definition constraint_solveri.h:1042

The base class for all local search operators.

Definition constraint_solveri.h:985

virtual void Reset()

Definition constraint_solveri.h:992

virtual bool HoldsDelta() const

Definition constraint_solveri.h:997

virtual bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta)=0

virtual const LocalSearchOperator * Self() const

Definition constraint_solveri.h:994

virtual void EnterSearch()

Definition constraint_solveri.h:990

virtual bool HasFragments() const

Definition constraint_solveri.h:996

~LocalSearchOperator() override

Definition constraint_solveri.h:988

virtual void Start(const Assignment *assignment)=0

LocalSearchOperator()

Definition constraint_solveri.h:987

Variable()

Definition constraint_solveri.h:3034

bool Exists() const

Definition constraint_solveri.h:3063

bool SetMin(int64_t new_min) const

Definition constraint_solveri.h:3045

bool SetMax(int64_t new_max) const

Definition constraint_solveri.h:3052

void Relax() const

Definition constraint_solveri.h:3057

friend class LocalSearchState

Definition constraint_solveri.h:3067

bool StateIsFeasible() const

Definition constraint_solveri.h:2837

void ChangeRelaxedVariableDomain(VariableDomainId domain_id, int64_t min, int64_t max)

void PropagateRelax(VariableDomainId domain_id)

static Variable DummyVariable()

Variable MakeVariable(VariableDomainId domain_id)

Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max)

int64_t VariableDomainMax(VariableDomainId domain_id) const

bool PropagateTighten(VariableDomainId domain_id)

virtual void InsertVarArrayConstantArrayExpression(IntExpr *expression, const std::vector< IntVar * > &var, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type)=0

VoidConstraintType

Definition constraint_solveri.h:3453

VarArrayConstantExpressionType

Definition constraint_solveri.h:3543

@ VAR_ARRAY_CONSTANT_INDEX

Definition constraint_solveri.h:3544

@ VAR_ARRAY_CONSTANT_EXPRESSION_MAX

Definition constraint_solveri.h:3545

VarArrayConstantArrayExpressionType

Definition constraint_solveri.h:3531

@ VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX

Definition constraint_solveri.h:3533

@ VAR_ARRAY_CONSTANT_ARRAY_SCAL_PROD

Definition constraint_solveri.h:3532

virtual void InsertVarConstantConstraint(Constraint *ct, IntVar *var, int64_t value, VarConstantConstraintType type)=0

ExprExpressionType

Definition constraint_solveri.h:3482

@ EXPR_SQUARE

Definition constraint_solveri.h:3485

@ EXPR_EXPRESSION_MAX

Definition constraint_solveri.h:3486

@ EXPR_ABS

Definition constraint_solveri.h:3484

@ EXPR_OPPOSITE

Definition constraint_solveri.h:3483

virtual IntExpr * FindExprExprExpression(IntExpr *var1, IntExpr *var2, ExprExprExpressionType type) const =0

Expr Expr Expressions.

virtual Constraint * FindExprExprConstraint(IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type) const =0

Expr Expr Constraints.

virtual Constraint * FindVoidConstraint(VoidConstraintType type) const =0

Void constraints.

virtual IntExpr * FindVarArrayConstantArrayExpression(const std::vector< IntVar * > &vars, const std::vector< int64_t > &values, VarArrayConstantArrayExpressionType type) const =0

Var Array Constant Array Expressions.

virtual IntExpr * FindVarArrayExpression(const std::vector< IntVar * > &vars, VarArrayExpressionType type) const =0

Var Array Expressions.

virtual IntExpr * FindExprExpression(IntExpr *expr, ExprExpressionType type) const =0

Expr Expressions.

VarConstantConstraintType

Definition constraint_solveri.h:3459

@ VAR_CONSTANT_NON_EQUALITY

Definition constraint_solveri.h:3463

@ VAR_CONSTANT_CONSTRAINT_MAX

Definition constraint_solveri.h:3464

virtual void InsertExprExprConstraint(Constraint *ct, IntExpr *expr1, IntExpr *expr2, ExprExprConstraintType type)=0

ExprConstantExpressionType

Definition constraint_solveri.h:3508

@ EXPR_CONSTANT_SUM

Definition constraint_solveri.h:3514

@ EXPR_CONSTANT_DIVIDE

Definition constraint_solveri.h:3510

@ EXPR_CONSTANT_IS_NOT_EQUAL

Definition constraint_solveri.h:3516

@ EXPR_CONSTANT_MIN

Definition constraint_solveri.h:3513

@ EXPR_CONSTANT_IS_GREATER_OR_EQUAL

Definition constraint_solveri.h:3517

@ EXPR_CONSTANT_IS_EQUAL

Definition constraint_solveri.h:3515

@ EXPR_CONSTANT_MAX

Definition constraint_solveri.h:3512

@ EXPR_CONSTANT_IS_LESS_OR_EQUAL

Definition constraint_solveri.h:3518

@ EXPR_CONSTANT_DIFFERENCE

Definition constraint_solveri.h:3509

@ EXPR_CONSTANT_EXPRESSION_MAX

Definition constraint_solveri.h:3519

@ EXPR_CONSTANT_PROD

Definition constraint_solveri.h:3511

virtual void InsertExprExpression(IntExpr *expression, IntExpr *expr, ExprExpressionType type)=0

VarConstantArrayExpressionType

Definition constraint_solveri.h:3526

@ VAR_CONSTANT_ARRAY_EXPRESSION_MAX

Definition constraint_solveri.h:3528

@ VAR_CONSTANT_ARRAY_ELEMENT

Definition constraint_solveri.h:3527

virtual void InsertVoidConstraint(Constraint *ct, VoidConstraintType type)=0

virtual void InsertExprExprExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, ExprExprExpressionType type)=0

virtual void InsertVarConstantArrayExpression(IntExpr *expression, IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type)=0

ExprExprExpressionType

Definition constraint_solveri.h:3489

@ EXPR_EXPR_MIN

Definition constraint_solveri.h:3494

@ EXPR_EXPR_IS_EQUAL

Definition constraint_solveri.h:3498

@ EXPR_EXPR_EXPRESSION_MAX

Definition constraint_solveri.h:3500

@ EXPR_EXPR_PROD

Definition constraint_solveri.h:3491

@ EXPR_EXPR_IS_NOT_EQUAL

Definition constraint_solveri.h:3499

@ EXPR_EXPR_MAX

Definition constraint_solveri.h:3493

@ EXPR_EXPR_DIFFERENCE

Definition constraint_solveri.h:3490

@ EXPR_EXPR_IS_LESS_OR_EQUAL

Definition constraint_solveri.h:3497

@ EXPR_EXPR_IS_LESS

Definition constraint_solveri.h:3496

@ EXPR_EXPR_SUM

Definition constraint_solveri.h:3495

@ EXPR_EXPR_DIV

Definition constraint_solveri.h:3492

virtual IntExpr * FindVarArrayConstantExpression(const std::vector< IntVar * > &vars, int64_t value, VarArrayConstantExpressionType type) const =0

Var Array Constant Expressions.

virtual void InsertExprConstantExpression(IntExpr *expression, IntExpr *var, int64_t value, ExprConstantExpressionType type)=0

VarConstantConstantExpressionType

Definition constraint_solveri.h:3521

@ VAR_CONSTANT_CONSTANT_EXPRESSION_MAX

Definition constraint_solveri.h:3523

@ VAR_CONSTANT_CONSTANT_SEMI_CONTINUOUS

Definition constraint_solveri.h:3522

virtual void InsertVarConstantConstantConstraint(Constraint *ct, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type)=0

virtual void InsertVarArrayConstantExpression(IntExpr *expression, const std::vector< IntVar * > &var, int64_t value, VarArrayConstantExpressionType type)=0

virtual void InsertVarConstantConstantExpression(IntExpr *expression, IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type)=0

ExprExprConstantExpressionType

Definition constraint_solveri.h:3503

@ EXPR_EXPR_CONSTANT_CONDITIONAL

Definition constraint_solveri.h:3504

@ EXPR_EXPR_CONSTANT_EXPRESSION_MAX

Definition constraint_solveri.h:3505

virtual Constraint * FindVarConstantConstraint(IntVar *var, int64_t value, VarConstantConstraintType type) const =0

Var Constant Constraints.

virtual IntExpr * FindVarConstantArrayExpression(IntVar *var, const std::vector< int64_t > &values, VarConstantArrayExpressionType type) const =0

Var Constant Array Expressions.

VarArrayExpressionType

Definition constraint_solveri.h:3536

@ VAR_ARRAY_MIN

Definition constraint_solveri.h:3538

@ VAR_ARRAY_SUM

Definition constraint_solveri.h:3539

@ VAR_ARRAY_MAX

Definition constraint_solveri.h:3537

@ VAR_ARRAY_EXPRESSION_MAX

Definition constraint_solveri.h:3540

ExprExprConstraintType

Definition constraint_solveri.h:3472

@ EXPR_EXPR_EQUALITY

Definition constraint_solveri.h:3473

@ EXPR_EXPR_GREATER_OR_EQUAL

Definition constraint_solveri.h:3475

@ EXPR_EXPR_NON_EQUALITY

Definition constraint_solveri.h:3478

@ EXPR_EXPR_LESS_OR_EQUAL

Definition constraint_solveri.h:3477

@ EXPR_EXPR_CONSTRAINT_MAX

Definition constraint_solveri.h:3479

@ EXPR_EXPR_LESS

Definition constraint_solveri.h:3476

@ EXPR_EXPR_GREATER

Definition constraint_solveri.h:3474

ModelCache(Solver *solver)

virtual IntExpr * FindExprConstantExpression(IntExpr *expr, int64_t value, ExprConstantExpressionType type) const =0

Expr Constant Expressions.

virtual void InsertExprExprConstantExpression(IntExpr *expression, IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type)=0

virtual IntExpr * FindExprExprConstantExpression(IntExpr *var1, IntExpr *var2, int64_t constant, ExprExprConstantExpressionType type) const =0

Expr Expr Constant Expressions.

virtual IntExpr * FindVarConstantConstantExpression(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantExpressionType type) const =0

Var Constant Constant Expressions.

virtual Constraint * FindVarConstantConstantConstraint(IntVar *var, int64_t value1, int64_t value2, VarConstantConstantConstraintType type) const =0

Var Constant Constant Constraints.

virtual void InsertVarArrayExpression(IntExpr *expression, const std::vector< IntVar * > &vars, VarArrayExpressionType type)=0

VarConstantConstantConstraintType

Definition constraint_solveri.h:3467

@ VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX

Definition constraint_solveri.h:3469

@ VAR_CONSTANT_CONSTANT_BETWEEN

Definition constraint_solveri.h:3468

Model Parser.

Definition constraint_solveri.h:3739

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

Visit interval argument.

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

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

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

Integer arguments.

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

void VisitSequenceVariable(const SequenceVar *variable) override

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

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

Visit sequence argument.

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

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

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

void PushArgumentHolder()

ArgumentHolder * Top() const

void VisitIntegerMatrixArgument(const std::string &arg_name, const IntTupleSet &values) override

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

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

Variables.

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

Visit integer arguments.

static const char kMinArgument[]

static const char kTargetArgument[]

static const char kMaxArgument[]

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

Visit integer expression argument.

static const char kIndexArgument[]

static const char kLightElementEqual[]

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

static const char kIndex2Argument[]

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

static const char kIndex3Argument[]

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

NodeNeighborIterator()

Definition constraint_solveri.h:1398

bool Next()

Definition constraint_solveri.h:1419

~NodeNeighborIterator()

Definition constraint_solveri.h:1399

bool IsIncomingNeighbor() const

Definition constraint_solveri.h:1430

int GetValue() const

Definition constraint_solveri.h:1422

bool IsOutgoingNeighbor() const

Definition constraint_solveri.h:1433

void Reset(const PathOperator &path_operator, int base_index_reference)

Definition constraint_solveri.h:1401

Subclass of Rev<T> which adds numerical operations.

void Decr(Solver *const s)

bool HasNeighbors() const

Definition constraint_solveri.h:1976

int number_of_nexts() const

Number of next variables.

Definition constraint_solveri.h:1655

bool SkipUnchanged(int index) const override

Definition constraint_solveri.h:1624

bool MakeChainInactive(int64_t before_chain, int64_t chain_end)

Definition constraint_solveri.h:1836

int64_t Prev(int64_t node) const

Returns the node before node in the current delta.

Definition constraint_solveri.h:1641

bool SwapActiveAndInactive(int64_t active, int64_t inactive)

Replaces active by inactive in the current path, making active inactive.

Definition constraint_solveri.h:1854

int PathClassFromStartNode(int64_t start_node) const

Definition constraint_solveri.h:1701

int64_t Path(int64_t node) const

Definition constraint_solveri.h:1649

void AddPairAlternativeSets(const std::vector< PairType > &pair_alternative_sets)

Definition constraint_solveri.h:1923

bool MakeActive(int64_t node, int64_t destination)

Insert the inactive node after destination.

Definition constraint_solveri.h:1827

int64_t OldNext(int64_t node) const

Definition constraint_solveri.h:1739

virtual void ResetIncrementalism()

Definition constraint_solveri.h:1679

virtual bool ConsiderAlternatives(int64_t) const

Definition constraint_solveri.h:1737

bool SwapNodes(int64_t node1, int64_t node2)

Swaps the nodes node1 and node2.

Definition constraint_solveri.h:1815

int64_t BaseSiblingAlternativeNode(int i) const

Returns the alternative node for the sibling of the ith base node.

Definition constraint_solveri.h:1689

void SetNext(int64_t from, int64_t to, int64_t path)

Sets 'to' to be the node after 'from' on the given path.

Definition constraint_solveri.h:1877

const int number_of_nexts_

Definition constraint_solveri.h:1994

virtual bool OnSamePathAsPreviousBase(int64_t)

it's currently way more complicated to implement.

Definition constraint_solveri.h:1721

virtual int64_t GetBaseNodeRestartPosition(int base_index)

Definition constraint_solveri.h:1727

int CurrentNodePathStart(int64_t node) const

Definition constraint_solveri.h:1759

int GetSiblingAlternativeIndex(int node) const

Returns the index of the alternative set of the sibling of node.

Definition constraint_solveri.h:1943

int64_t OldPath(int64_t node) const

Definition constraint_solveri.h:1754

int GetAlternativeIndex(int node) const

Returns the index of the alternative set of the node.

Definition constraint_solveri.h:1948

int64_t PrevNext(int64_t node) const

Definition constraint_solveri.h:1744

virtual bool InitPosition() const

Definition constraint_solveri.h:1900

int64_t OldPrev(int64_t node) const

Definition constraint_solveri.h:1749

virtual void OnNodeInitialization()

Definition constraint_solveri.h:1674

int AddAlternativeSet(const std::vector< int64_t > &alternative_set)

Definition constraint_solveri.h:1909

bool IsPathStart(int64_t node) const

Returns true if node is the first node on the path.

Definition constraint_solveri.h:1891

~PathOperator() override

Definition constraint_solveri.h:1612

bool MoveChain(int64_t before_chain, int64_t chain_end, int64_t destination)

Definition constraint_solveri.h:1767

bool IsPathEnd(int64_t node) const

Definition constraint_solveri.h:1888

bool SwapActiveAndInactiveChains(absl::Span< const int64_t > active_chain, absl::Span< const int64_t > inactive_chain)

Definition constraint_solveri.h:1861

virtual bool MakeNeighbor()=0

int64_t EndNode(int i) const

Returns the end node of the ith base node.

Definition constraint_solveri.h:1696

int64_t GetActiveInAlternativeSet(int alternative_index) const

Returns the active node in the given alternative set.

Definition constraint_solveri.h:1933

PathOperator(const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)

Builds an instance of PathOperator from next and path variables.

Definition constraint_solveri.h:1561

void Reset() override

Definition constraint_solveri.h:1618

virtual bool RestartAtPathStartOnSynchronize()

Definition constraint_solveri.h:1714

bool IsInactive(int64_t node) const

Returns true if node is inactive.

Definition constraint_solveri.h:1894

const std::vector< int64_t > & path_starts() const

Returns the vector of path start nodes.

Definition constraint_solveri.h:1698

bool CheckChainValidity(int64_t before_chain, int64_t chain_end, int64_t exclude) const

Definition constraint_solveri.h:1961

void ResetPosition()

Definition constraint_solveri.h:1904

bool ReverseChain(int64_t before_chain, int64_t after_chain, int64_t *chain_last)

Definition constraint_solveri.h:1791

int PathClass(int i) const

Returns the class of the path of the ith base node.

Definition constraint_solveri.h:1700

void EnterSearch() override

Definition constraint_solveri.h:1614

virtual void SetNextBaseToIncrement(int64_t base_index)

Definition constraint_solveri.h:1732

int64_t BaseAlternativeNode(int i) const

Returns the alternative node for the ith base node.

Definition constraint_solveri.h:1684

bool MakeOneNeighbor() override

This method should not be overridden. Override MakeNeighbor() instead.

Definition constraint_solveri.h:1659

int64_t StartNode(int i) const

Returns the start node of the ith base node.

Definition constraint_solveri.h:1694

int64_t BaseNode(int i) const

Returns the ith base node of the operator.

Definition constraint_solveri.h:1682

int CurrentNodePathEnd(int64_t node) const

Definition constraint_solveri.h:1763

std::string DebugString() const override

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

std::string DebugString() const override

Definition constraint_solveri.h:3232

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 EndDemonRun(Demon *demon)=0

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

virtual void RegisterDemon(Demon *demon)=0

virtual void SetMin(IntExpr *expr, int64_t new_min)=0

IntExpr modifiers.

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

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

SequenceVar modifiers.

virtual void SetMax(IntExpr *expr, int64_t new_max)=0

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

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

virtual void StartProcessingIntegerVariable(IntVar *var)=0

virtual void EndProcessingIntegerVariable(IntVar *var)=0

void Install() override

Install itself on the solver.

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

virtual void SetRange(IntExpr *expr, int64_t new_min, int64_t new_max)=0

virtual void BeginDemonRun(Demon *demon)=0

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 SetValue(IntVar *var, int64_t value)=0

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

Matrix version of the RevBitSet class.

Definition constraint_solveri.h:471

bool IsSet(int64_t row, int64_t column) const

Returns whether the 'column' bit in the 'row' row is set.

Definition constraint_solveri.h:481

void ClearAll(Solver *solver)

Cleans all bits.

int64_t GetFirstBit(int row, int start) const

void SetToZero(Solver *solver, int64_t row, int64_t column)

Erases the 'column' bit in the 'row' row.

void SetToOne(Solver *solver, int64_t row, int64_t column)

Sets the 'column' bit in the 'row' row.

int64_t Cardinality() const

Returns the number of bits set to one.

void ClearAll(Solver *solver)

Cleans all bits.

void SetToZero(Solver *solver, int64_t index)

Erases the 'index' bit.

bool IsCardinalityOne() const

Does it contains only one bit set?

void SetToOne(Solver *solver, int64_t index)

Sets the 'index' bit.

friend class RevBitMatrix

Definition constraint_solveri.h:459

bool IsSet(int64_t index) const

Returns whether the 'index' bit is set.

int64_t GetFirstBit(int start) const

bool IsCardinalityZero() const

Is bitset null?

T At(int64_t index) const

Definition constraint_solveri.h:3850

void Insert(const K &key, const V &value)

Inserts (key, value) in the multi-map.

Definition constraint_solveri.h:333

bool ContainsKey(const K &key) const

Returns true if the multi-map contains at least one instance of 'key'.

Definition constraint_solveri.h:305

int num_items() const

Definition constraint_solveri.h:302

~RevImmutableMultiMap()

Definition constraint_solveri.h:300

RevImmutableMultiMap(Solver *const solver, int initial_size)

Definition constraint_solveri.h:292

const V & FindWithDefault(const K &key, const V &default_value) const

Definition constraint_solveri.h:320

RevIntSet(int capacity)

Capacity is the fixed size of the set (it cannot grow).

Definition constraint_solveri.h:3925

const T * const_iterator

Iterators on the indices.

Definition constraint_solveri.h:3992

void Insert(Solver *const solver, const T &elt)

Definition constraint_solveri.h:3970

static constexpr int kNoInserted

Definition constraint_solveri.h:3922

const_iterator begin() const

Definition constraint_solveri.h:3993

bool IsRanked(int elt) const

Definition constraint_solveri.h:4086

void RankLast(Solver *const solver, int elt)

Definition constraint_solveri.h:4080

std::string DebugString() const

Definition constraint_solveri.h:4092

RevPartialSequence(const std::vector< int > &items)

Definition constraint_solveri.h:4034

void RankFirst(Solver *const solver, int elt)

Definition constraint_solveri.h:4074

A reversible switch that can switch once from false to true.

Definition constraint_solveri.h:398

bool Switched() const

Definition constraint_solveri.h:402

RevSwitch()

Definition constraint_solveri.h:400

void Switch(Solver *const solver)

Definition constraint_solveri.h:404

virtual void OutputLine(const std::string &line)

void AcceptUncheckedNeighbor() override

After accepting an unchecked neighbor during local search.

void EndInitialPropagation() override

After the initial propagation.

void BeginInitialPropagation() override

Before the initial propagation.

void RefuteDecision(Decision *decision) override

Before refuting the decision.

std::string DebugString() const override

void ApplyDecision(Decision *decision) override

Before applying the decision.

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

SearchMonitor(Solver *const s)

void operator++()

Definition constraint_solveri.h:169

Iterator(const SimpleRevFIFO< T > *l)

Definition constraint_solveri.h:165

bool ok() const

Definition constraint_solveri.h:167

T operator*() const

Definition constraint_solveri.h:168

void SetLastValue(const T &v)

Sets the last value in the FIFO.

Definition constraint_solveri.h:217

const T * Last() const

Returns the last item of the FIFO.

Definition constraint_solveri.h:204

T * MutableLast()

Definition constraint_solveri.h:208

void Push(Solver *const s, T val)

Definition constraint_solveri.h:184

void PushIfNotTop(Solver *const s, T val)

Pushes the var on top if is not a duplicate of the current top object.

Definition constraint_solveri.h:197

const T & LastValue() const

Returns the last value in the FIFO.

Definition constraint_solveri.h:211

SimpleRevFIFO()

Definition constraint_solveri.h:182

void SetToZero(Solver *solver, int64_t pos)

Erases the 'pos' bit.

SmallRevBitSet(int64_t size)

void SetToOne(Solver *solver, int64_t pos)

Sets the 'pos' bit.

bool IsCardinalityZero() const

Is bitset null?

Definition constraint_solveri.h:422

int64_t Cardinality() const

Returns the number of bits set to one.

int64_t GetFirstOne() const

bool IsCardinalityOne() const

Does it contains only one bit set?

Definition constraint_solveri.h:424

std::function< int64_t(int64_t, int64_t, int64_t)> IndexEvaluator3

void SaveAndSetValue(T *adr, T val)

All-in-one SaveAndSetValue.

const std::vector< ArcId > & ComputeSortedSubDagArcs(NodeId node)

void BuildGraph(int num_nodes)

friend class SymmetryManager

Definition constraint_solveri.h:3381

bool Intersects(const std::vector< uint64_t > &mask, int *support_index)

bool RevSubtract(Solver *solver, const std::vector< uint64_t > &mask)

int64_t bit_size() const

Returns the number of bits given in the constructor of the bitset.

Definition constraint_solveri.h:4182

int ActiveWordSize() const

Definition constraint_solveri.h:4167

bool RevAnd(Solver *solver, const std::vector< uint64_t > &mask)

absl::Status Exists(absl::string_view path, Options options)

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

LocalSearchOperator * MakeExtendedSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— ExtendedSwapActive --—

std::string ParameterDebugString(P param)

Definition constraint_solveri.h:539

bool IsArrayConstant(const std::vector< T > &values, const T &value)

Definition constraint_solveri.h:4199

LocalSearchOperator * RelocateAndMakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— RelocateAndMakeInactive --—

LocalSearchOperator * MakeTSPOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int chain_length)

--— TSP-based operators --—

LocalSearchOperator * MakeCross(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)

--— Cross --—

SubDagComputer::ArcId ArcId

Demon * MakeConstraintDemon3(Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)

Definition constraint_solveri.h:655

LocalSearchOperator * MakeSwapActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— SwapActive --—

LocalSearchOperator * ExchangeAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

bool AreAllGreaterOrEqual(const std::vector< T > &values, const T &value)

Definition constraint_solveri.h:4229

bool AreAllStrictlyPositive(const std::vector< T > &values)

Definition constraint_solveri.h:4259

bool IsArrayBoolean(const std::vector< T > &values)

Definition constraint_solveri.h:4209

LocalSearchOperator * MakeExchange(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)

--— Exchange --—

LocalSearchOperator * MakeActiveAndRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— MakeActiveAndRelocate --—

bool AreAllBoundOrNull(const std::vector< IntVar * > &vars, const std::vector< T > &values)

Definition constraint_solveri.h:4315

int64_t MaxVarArray(const std::vector< IntVar * > &vars)

Definition constraint_solveri.h:4335

LocalSearchOperator * MakeTSPLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)

Demon * MakeConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)

Definition constraint_solveri.h:612

Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)

Definition constraint_solveri.h:695

Demon * MakeDelayedConstraintDemon2(Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)

Definition constraint_solveri.h:775

ClosedInterval::Iterator end(ClosedInterval interval)

LocalSearchOperator * MakeRelocate(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr, int64_t chain_length=1LL, bool single_path=false, const std::string &name="Relocate")

--— Relocate --—

VarTypes

Definition constraint_solveri.h:130

@ DOMAIN_INT_VAR

Definition constraint_solveri.h:132

@ VAR_ADD_CST

Definition constraint_solveri.h:135

@ BOOLEAN_VAR

Definition constraint_solveri.h:133

@ CST_SUB_VAR

Definition constraint_solveri.h:137

@ TRACE_VAR

Definition constraint_solveri.h:139

@ OPP_VAR

Definition constraint_solveri.h:138

@ VAR_TIMES_CST

Definition constraint_solveri.h:136

@ UNSPECIFIED

Definition constraint_solveri.h:131

@ CONST_VAR

Definition constraint_solveri.h:134

bool AreAllBoundTo(const std::vector< IntVar * > &vars, int64_t value)

Returns true if all variables are assigned to 'value'.

Definition constraint_solveri.h:4326

LocalSearchOperator * RelocateAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

-— RelocateAndMakeActive --—

void FillValues(const std::vector< IntVar * > &vars, std::vector< int64_t > *const values)

Definition constraint_solveri.h:4355

bool AreAllBooleans(const std::vector< IntVar * > &vars)

Definition constraint_solveri.h:4308

LocalSearchOperator * MakePathLns(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)

--— Path-based Large Neighborhood Search --—

int64_t MinVarArray(const std::vector< IntVar * > &vars)

Definition constraint_solveri.h:4345

LocalSearchOperator * MakeInactive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

--— MakeInactive --—

LocalSearchOperator * MakeTwoOpt(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)

--— 2Opt --—

Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)

Definition constraint_solveri.h:533

std::vector< int64_t > ToInt64Vector(const std::vector< int > &input)

bool AreAllPositive(const std::vector< T > &values)

Definition constraint_solveri.h:4249

LocalSearchOperator * ExchangePathStartEndsAndMakeActive(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)

Definition constraint_solveri.h:731

LocalSearchOperator * MakeSwapActiveChain(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)

--— SwapActiveChain --—

LocalSearchOperator * MakeLinKernighan(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)

--— Lin-Kernighan --—

LocalSearchState::VariableDomainId VariableDomainId

bool IsArrayInRange(const std::vector< IntVar * > &vars, T range_min, T range_max)

Definition constraint_solveri.h:4289

Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)

Definition constraint_solveri.h:574

bool AreAllOnes(const std::vector< T > &values)

Definition constraint_solveri.h:4219

bool AreAllBound(const std::vector< IntVar * > &vars)

Definition constraint_solveri.h:4299

uint64_t Hash1(uint64_t value)

Hash functions.