Google OR-Tools: ortools/constraint_solver/local

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

14#include <algorithm>

15#include <cmath>

16#include <cstddef>

17#include <cstdint>

18#include <functional>

19#include <limits>

20#include <memory>

21#include <optional>

22#include <random>

23#include <string>

24#include <utility>

25#include <vector>

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

28#include "absl/base/nullability.h"

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

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

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

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

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

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

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

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

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

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

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

53ABSL_FLAG(int, cp_local_search_sync_frequency, 16,

54 "Frequency of checks for better solutions in the solution pool.");

56ABSL_FLAG(int, cp_local_search_tsp_opt_size, 13,

57 "Size of TSPs solved in the TSPOpt operator.");

59ABSL_FLAG(int, cp_local_search_tsp_lns_size, 10,

60 "Size of TSPs solved in the TSPLns operator.");

72bool AcceptDelta(Search* search, Assignment* delta, Assignment* deltadelta);

82 CHECK(delta != nullptr);

83 VLOG(2) << DebugString() << "::MakeNextNeighbor(delta=("

84 << delta->DebugString() << "), deltadelta=("

85 << (deltadelta ? deltadelta->DebugString() : std::string("nullptr"))

86 << "))";

87 while (true) {

91 return false;

92 }

96 return true;

97 }

98 }

99 return false;

100}

101

103

104

105

108

110

112 fragment_.clear();

114 for (int candidate : fragment_) {

116 }

117 return true;

118 }

119 return false;

120}

121

123

125

127 if (index >= 0 && index < Size()) {

128 fragment_.push_back(index);

129 }

130}

131

133

134

135

136

137

138namespace {

139class SimpleLns : public BaseLns {

140 public:

141 SimpleLns(const std::vector<IntVar*>& vars, int number_of_variables)

142 : BaseLns(vars), index_(0), number_of_variables_(number_of_variables) {

143 CHECK_GT(number_of_variables_, 0);

144 }

145 ~SimpleLns() override {}

146 void InitFragments() override { index_ = 0; }

147 bool NextFragment() override;

148 std::string DebugString() const override { return "SimpleLns"; }

149

150 private:

151 int index_;

152 const int number_of_variables_;

153};

154

155bool SimpleLns::NextFragment() {

156 const int size = Size();

157 if (index_ < size) {

158 for (int i = index_; i < index_ + number_of_variables_; ++i) {

159 AppendToFragment(i % size);

160 }

161 ++index_;

162 return true;

163 }

164 return false;

165}

166

167

168

169

170

171class RandomLns : public BaseLns {

172 public:

173 RandomLns(const std::vector<IntVar*>& vars, int number_of_variables,

174 int32_t seed)

175 : BaseLns(vars), rand_(seed), number_of_variables_(number_of_variables) {

176 CHECK_GT(number_of_variables_, 0);

177 CHECK_LE(number_of_variables_, Size());

178 }

179 ~RandomLns() override {}

180 bool NextFragment() override;

181

182 std::string DebugString() const override { return "RandomLns"; }

183

184 private:

185 std::mt19937 rand_;

186 const int number_of_variables_;

187};

188

189bool RandomLns::NextFragment() {

190 DCHECK_GT(Size(), 0);

191 for (int i = 0; i < number_of_variables_; ++i) {

192 AppendToFragment(absl::Uniform<int>(rand_, 0, Size()));

193 }

194 return true;

195}

196}

197

199 const std::vector<IntVar*>& vars, int number_of_variables) {

201}

202

204 const std::vector<IntVar*>& vars, int number_of_variables, int32_t seed) {

205 return RevAlloc(new RandomLns(vars, number_of_variables, seed));

206}

207

208

209

210

211

212

213namespace {

215 public:

216 MoveTowardTargetLS(const std::vector<IntVar*>& variables,

217 const std::vector<int64_t>& target_values)

219 target_(target_values),

220

221

222

223 variable_index_(Size() - 1) {

224 CHECK_EQ(target_values.size(), variables.size()) << "Illegal arguments.";

225 }

226

227 ~MoveTowardTargetLS() override {}

228

229 std::string DebugString() const override { return "MoveTowardTargetLS"; }

230

231 protected:

232

233 bool MakeOneNeighbor() override {

234 while (num_var_since_last_start_ < Size()) {

235 ++num_var_since_last_start_;

236 variable_index_ = (variable_index_ + 1) % Size();

237 const int64_t target_value = target_.at(variable_index_);

238 const int64_t current_value = OldValue(variable_index_);

239 if (current_value != target_value) {

240 SetValue(variable_index_, target_value);

241 return true;

242 }

243 }

244 return false;

245 }

246

247 private:

248 void OnStart() override {

249

250

251

252

253

254

255

256

257

258

259

260 CHECK_GE(variable_index_, 0);

261 CHECK_LT(variable_index_, Size());

262 num_var_since_last_start_ = 0;

263 }

264

265

266 const std::vector<int64_t> target_;

267

268

269 int64_t variable_index_;

270

271

272 int64_t num_var_since_last_start_;

273};

274}

275

278 typedef std::vector<IntVarElement> Elements;

280

281 std::vector<IntVar*> vars;

282 std::vector<int64_t> values;

285 for (const auto& it : elements) {

286 vars.push_back(it.Var());

287 values.push_back(it.Value());

288 }

290}

291

293 const std::vector<IntVar*>& variables,

294 const std::vector<int64_t>& target_values) {

295 return RevAlloc(new MoveTowardTargetLS(variables, target_values));

296}

297

298

299

302

304

306 const int size = Size();

307 while (index_ < size) {

310 ++index_;

311 return true;

312 }

313 return false;

314}

315

317

318

319

320namespace {

321class IncrementValue : public ChangeValue {

322 public:

323 explicit IncrementValue(const std::vector<IntVar*>& vars)

324 : ChangeValue(vars) {}

325 ~IncrementValue() override {}

326 int64_t ModifyValue(int64_t, int64_t value) override { return value + 1; }

327

328 std::string DebugString() const override { return "IncrementValue"; }

329};

330

331

332

333class DecrementValue : public ChangeValue {

334 public:

335 explicit DecrementValue(const std::vector<IntVar*>& vars)

336 : ChangeValue(vars) {}

337 ~DecrementValue() override {}

338 int64_t ModifyValue(int64_t, int64_t value) override { return value - 1; }

339

340 std::string DebugString() const override { return "DecrementValue"; }

341};

342}

343

344

345

347 std::function<const std::vector<int>&(int, int)>;

348

349

350

351template <bool ignore_path_vars>

353 public:

354 TwoOpt(const std::vector<IntVar*>& vars,

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

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

359 : PathOperator<ignore_path_vars>(vars, secondary_vars,

360 (get_incoming_neighbors == nullptr &&

361 get_outgoing_neighbors == nullptr)

362 ? 2

363 : 1,

364 true,

365 true,

366 std::move(start_empty_path_class),

367 std::move(get_incoming_neighbors),

368 std::move(get_outgoing_neighbors)),

369 last_base_(-1),

370 last_(-1) {}

374

375 std::string DebugString() const override { return "TwoOpt"; }

376

377 protected:

380

381 return true;

382 }

386

387 private:

389

390 int64_t last_base_;

391 int64_t last_;

392};

393

394template <bool ignore_path_vars>

396 const int64_t node0 = this->BaseNode(0);

397 int64_t before_chain = node0;

398 int64_t after_chain = -1;

401 if (neighbor < 0 || this->IsInactive(neighbor)) return false;

404 return false;

405 }

406 if (outgoing) {

407 if (this->IsPathEnd(neighbor)) return false;

408

409 after_chain = this->Next(neighbor);

410 } else {

411 if (this->IsPathStart(neighbor)) return false;

412

413 before_chain = this->Prev(neighbor);

414 after_chain = node0;

415 }

416 } else {

418 after_chain = this->BaseNode(1);

419 }

420

421 if (last_base_ != node0 || last_ == -1 || this->HasNeighbors()) {

424 last_ = -1;

425 return false;

426 }

427 last_base_ = node0;

428 last_ = this->Next(before_chain);

429 int64_t chain_last;

430 if (this->ReverseChain(before_chain, after_chain, &chain_last)

431

432

433 && last_ != chain_last) {

434 return true;

435 }

436 last_ = -1;

437 return false;

438 }

439 DCHECK_EQ(before_chain, node0);

440 const int64_t to_move = this->Next(last_);

441 DCHECK_EQ(this->Next(to_move), after_chain);

442 return this->MoveChain(last_, to_move, before_chain);

443}

444

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

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

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

451 if (secondary_vars.empty()) {

453 vars, secondary_vars, std::move(start_empty_path_class),

454 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

455 }

457 vars, secondary_vars, std::move(start_empty_path_class),

458 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

459}

460

461

462

463template <bool ignore_path_vars>

465 public:

466 Relocate(const std::vector<IntVar*>& vars,

467 const std::vector<IntVar*>& secondary_vars, absl::string_view name,

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

470 NeighborAccessor get_outgoing_neighbors, int64_t chain_length = 1LL,

471 bool single_path = false)

473 vars, secondary_vars,

474 (get_incoming_neighbors == nullptr &&

475 get_outgoing_neighbors == nullptr)

476 ? 2

477 : 1,

478 true,

479 false, std::move(start_empty_path_class),

480 chain_length == 1 ? std::move(get_incoming_neighbors) : nullptr,

481 std::move(get_outgoing_neighbors)),

482 chain_length_(chain_length),

483 single_path_(single_path),

484 name_(absl::StrCat(name, "<", chain_length, ">")) {

485 CHECK_GT(chain_length_, 0);

486 }

489

490 std::string DebugString() const override { return name_; }

491

492 protected:

494

495

496 return single_path_;

497 }

498

499 private:

500 const int64_t chain_length_;

501 const bool single_path_;

502 const std::string name_;

503};

504

505template <bool ignore_path_vars>

507 const auto do_move = [this](int64_t before_chain, int64_t destination) {

508 DCHECK(!this->IsPathEnd(destination));

509 int64_t chain_end = before_chain;

510 for (int i = 0; i < chain_length_; ++i) {

511 if (this->IsPathEnd(chain_end) || chain_end == destination) return false;

512 chain_end = this->Next(chain_end);

513 }

514 return !this->IsPathEnd(chain_end) &&

515 this->MoveChain(before_chain, chain_end, destination);

516 };

517 const int64_t node0 = this->BaseNode(0);

520 if (neighbor < 0 || this->IsInactive(neighbor)) return false;

521 if (outgoing) {

522 return do_move(this->Prev(neighbor),

523 node0);

524 }

525 DCHECK_EQ(chain_length_, 1);

526

527

528

530 << "Path starts have no incoming neighbors.";

531 return do_move(this->Prev(neighbor),

532 this->Prev(node0));

533 }

535 return do_move(node0, this->BaseNode(1));

536}

537

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

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

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

543 NeighborAccessor get_outgoing_neighbors, int64_t chain_length,

544 bool single_path, const std::string& name) {

545 if (secondary_vars.empty()) {

547 vars, secondary_vars, name, std::move(start_empty_path_class),

548 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors),

549 chain_length, single_path));

550 }

552 vars, secondary_vars, name, std::move(start_empty_path_class),

553 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors),

554 chain_length, single_path));

555}

556

557

558

559template <bool ignore_path_vars>

561 public:

562 Exchange(const std::vector<IntVar*>& vars,

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

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

567 : PathOperator<ignore_path_vars>(vars, secondary_vars,

568 (get_incoming_neighbors == nullptr &&

569 get_outgoing_neighbors == nullptr)

570 ? 2

571 : 1,

572 true,

573 false,

574 std::move(start_empty_path_class),

575 std::move(get_incoming_neighbors),

576 std::move(get_outgoing_neighbors)) {}

579

580 std::string DebugString() const override { return "Exchange"; }

581};

582

583template <bool ignore_path_vars>

585 const int64_t node0 = this->BaseNode(0);

588 if (neighbor < 0 || this->IsInactive(neighbor)) return false;

589 if (outgoing) {

590

591 return this->SwapNodes(this->Next(node0), neighbor);

592 }

594 << "Path starts have no incoming neighbors.";

595

596 return this->SwapNodes(this->Prev(node0), neighbor);

597 }

599}

600

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

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

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

607 if (secondary_vars.empty()) {

609 vars, secondary_vars, std::move(start_empty_path_class),

610 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

611 }

613 vars, secondary_vars, std::move(start_empty_path_class),

614 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

615}

616

617

618

619template <bool ignore_path_vars>

621 public:

622 Cross(const std::vector<IntVar*>& vars,

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

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

627 : PathOperator<ignore_path_vars>(vars, secondary_vars,

628 (get_incoming_neighbors == nullptr &&

629 get_outgoing_neighbors == nullptr)

630 ? 2

631 : 1,

632 true,

633 true,

634 std::move(start_empty_path_class),

635 std::move(get_incoming_neighbors),

636 std::move(get_outgoing_neighbors)) {}

639

640 std::string DebugString() const override { return "Cross"; }

641};

642

643template <bool ignore_path_vars>

645 const int64_t start0 = this->StartNode(0);

646 int64_t start1 = -1;

647 const int64_t node0 = this->BaseNode(0);

648 int64_t node1 = -1;

649 if (node0 == start0) return false;

650 bool cross_path_starts = false;

653 if (neighbor < 0) return false;

654 cross_path_starts = outgoing;

656 if (this->IsInactive(neighbor)) return false;

658

659

660

661

662

663

664

665 node1 = cross_path_starts ? this->Prev(neighbor) : this->Next(neighbor);

666 } else {

669 cross_path_starts = start0 < start1;

670 }

671 if (start1 == start0 || node1 == start1) return false;

672

673 bool moved = false;

674 if (cross_path_starts) {

675

676

681 return false;

682 }

683 const int first1 = this->Next(start1);

685 moved |= this->MoveChain(start0, node0, start1);

687 moved |= this->MoveChain(this->Prev(first1), node1, start0);

688 } else {

689

690

691

695 return false;

696 }

697

698

701 return false;

702 }

703

707 prev_end_node1);

708 }

710 moved |= this->MoveChain(this->Prev(node1), prev_end_node1,

712 }

713 }

714 return moved;

715}

716

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

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

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

723 if (secondary_vars.empty()) {

725 vars, secondary_vars, std::move(start_empty_path_class),

726 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

727 }

729 vars, secondary_vars, std::move(start_empty_path_class),

730 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

731}

732

733

734

735

736template <bool ignore_path_vars>

738 public:

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

741 const std::vector<IntVar*>& secondary_vars, int number_of_base_nodes,

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

745 : PathOperator<ignore_path_vars>(vars, secondary_vars,

746 number_of_base_nodes, false, false,

747 std::move(start_empty_path_class),

748 std::move(get_incoming_neighbors),

749 std::move(get_outgoing_neighbors)),

750 inactive_node_(0) {

751

752 }

754

755 protected:

758

759 private:

761

762 int inactive_node_;

763};

764

765template <bool ignore_path_vars>

767 for (int i = 0; i < this->Size(); ++i) {

768 if (this->IsInactive(i)) {

769 inactive_node_ = i;

770 return;

771 }

772 }

773 inactive_node_ = this->Size();

774}

775

776template <bool ignore_path_vars>

778 while (inactive_node_ < this->Size()) {

779 if (!this->IsInactive(inactive_node_) ||

782 ++inactive_node_;

783 } else {

784 return true;

785 }

786 }

787 return false;

788}

789

790

791

792template <bool ignore_path_vars>

795 public:

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

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

802 vars, secondary_vars, 1, std::move(start_empty_path_class),

803 std::move(get_incoming_neighbors),

804 std::move(get_outgoing_neighbors)) {}

807

808 std::string DebugString() const override { return "MakeActiveOperator"; }

809};

810

811template <bool ignore_path_vars>

817

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

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

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

824 if (secondary_vars.empty()) {

826 vars, secondary_vars, std::move(start_empty_path_class),

827 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

828 }

830 vars, secondary_vars, std::move(start_empty_path_class),

831 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors)));

832}

833

834

835

836template <bool ignore_path_vars>

839 public:

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

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

843 std::function<int(int64_t)> start_empty_path_class)

845 vars, secondary_vars, 2, std::move(start_empty_path_class)) {}

848 const int64_t before_node_to_move = this->BaseNode(1);

849 const int64_t node = this->Next(before_node_to_move);

853 }

854

856 return "RelocateAndMakeActiveOperator";

857 }

858};

859

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

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

863 std::function<int(int64_t)> start_empty_path_class) {

864 if (secondary_vars.empty()) {

866 vars, secondary_vars, std::move(start_empty_path_class)));

867 }

869 vars, secondary_vars, std::move(start_empty_path_class)));

870}

871

872

873

874template <bool ignore_path_vars>

877 public:

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

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

881 std::function<int(int64_t)> start_empty_path_class)

883 vars, secondary_vars, 3, std::move(start_empty_path_class)) {}

891 return "ExchangeAndMakeActiveOperator";

892 }

893

894 protected:

896 return base_index == 2;

897 }

898};

899

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

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

903 std::function<int(int64_t)> start_empty_path_class) {

904 if (secondary_vars.empty()) {

906 vars, secondary_vars, std::move(start_empty_path_class)));

907 }

909 vars, secondary_vars, std::move(start_empty_path_class)));

910}

911

912

913

914template <bool ignore_path_vars>

917 public:

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

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

921 std::function<int(int64_t)> start_empty_path_class)

923 vars, secondary_vars, 2, std::move(start_empty_path_class)) {}

926 return (base_index == 1) ? this->Prev(this->EndNode(1))

928 }

930 const int64_t end_node0 = this->Prev(this->EndNode(0));

931 const int64_t end_node1 = this->BaseNode(1);

932 if (end_node0 == end_node1 || end_node1 != this->Prev(this->EndNode(1))) {

933 return false;

934 }

935 const int64_t start_node0 = this->Next(this->StartNode(0));

936 const int64_t start_node1 = this->Next(this->StartNode(1));

937 DCHECK_NE(start_node0, start_node1);

938 return this->SwapNodes(end_node0, end_node1) &&

939 this->SwapNodes(start_node0, start_node1) &&

941 }

943 return "ExchangePathEndsAndMakeActiveOperator";

944 }

945};

946

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

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

950 std::function<int(int64_t)> start_empty_path_class) {

951 if (secondary_vars.empty()) {

954 vars, secondary_vars, std::move(start_empty_path_class)));

955 }

957 vars, secondary_vars, std::move(start_empty_path_class)));

958}

959

960

961

962template <bool ignore_path_vars>

965 public:

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

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

969 std::function<int(int64_t)> start_empty_path_class)

971 vars, secondary_vars, 2, std::move(start_empty_path_class)) {}

974

976 return "MakeActiveAndRelocateOperator";

977 }

978};

979

980template <bool ignore_path_vars>

982 const int64_t before_chain = this->BaseNode(1);

983 const int64_t chain_end = this->Next(before_chain);

984 const int64_t destination = this->BaseNode(0);

985 return !this->IsPathEnd(chain_end) &&

986 this->MoveChain(before_chain, chain_end, destination) &&

988}

989

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

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

993 std::function<int(int64_t)> start_empty_path_class) {

994 if (secondary_vars.empty()) {

996 vars, secondary_vars, std::move(start_empty_path_class)));

997 }

999 vars, secondary_vars, std::move(start_empty_path_class)));

1000}

1001

1002

1003

1004template <bool ignore_path_vars>

1006 public:

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

1009 std::function<int(int64_t)> start_empty_path_class)

1010 : PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,

1011 std::move(start_empty_path_class),

1012 nullptr, nullptr) {}

1018

1019 std::string DebugString() const override { return "MakeInactiveOperator"; }

1020};

1021

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

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

1025 std::function<int(int64_t)> start_empty_path_class) {

1026 if (secondary_vars.empty()) {

1028 vars, secondary_vars, std::move(start_empty_path_class)));

1029 }

1031 vars, secondary_vars, std::move(start_empty_path_class)));

1032}

1033

1034

1035

1036template <bool ignore_path_vars>

1038 public:

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

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

1042 std::function<int(int64_t)> start_empty_path_class)

1043 : PathOperator<ignore_path_vars>(vars, secondary_vars, 2, true, false,

1044 std::move(start_empty_path_class),

1045 nullptr, nullptr) {}

1048 const int64_t destination = this->BaseNode(1);

1049 const int64_t before_to_move = this->BaseNode(0);

1050 const int64_t node_to_inactivate = this->Next(destination);

1051 if (node_to_inactivate == before_to_move ||

1052 this->IsPathEnd(node_to_inactivate) ||

1054 return false;

1055 }

1056 const int64_t node = this->Next(before_to_move);

1057 return !this->IsPathEnd(node) &&

1058 this->MoveChain(before_to_move, node, destination);

1059 }

1060

1062 return "RelocateAndMakeInactiveOperator";

1063 }

1064};

1065

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

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

1069 std::function<int(int64_t)> start_empty_path_class) {

1070 if (secondary_vars.empty()) {

1072 vars, secondary_vars, std::move(start_empty_path_class)));

1073 }

1075 vars, secondary_vars, std::move(start_empty_path_class)));

1076}

1077

1078

1079

1080template <bool ignore_path_vars>

1082 public:

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

1085 std::function<int(int64_t)> start_empty_path_class)

1086 : PathOperator<ignore_path_vars>(vars, secondary_vars, 2,

1087 true,

1088 false,

1089 std::move(start_empty_path_class),

1090 nullptr, nullptr) {}

1093 const int64_t chain_end = this->BaseNode(1);

1094 if (!this->IsPathEnd(chain_end) && chain_end != this->BaseNode(0) &&

1095 !this->Var(chain_end)->Contains(chain_end)) {

1096

1097

1099 return false;

1100 }

1102 }

1103

1105 return "MakeChainInactiveOperator";

1106 }

1107

1108 protected:

1110

1111

1112 return true;

1113 }

1114

1116

1117 return (base_index == 0) ? this->StartNode(base_index)

1118 : this->BaseNode(base_index - 1);

1119 }

1120};

1121

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

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

1125 std::function<int(int64_t)> start_empty_path_class) {

1126 if (secondary_vars.empty()) {

1128 vars, secondary_vars, std::move(start_empty_path_class)));

1129 }

1131 vars, secondary_vars, std::move(start_empty_path_class)));

1132}

1133

1134

1135

1136template <bool ignore_path_vars>

1139 public:

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

1142 std::function<int(int64_t)> start_empty_path_class)

1144 vars, secondary_vars, 1, std::move(start_empty_path_class)) {}

1151

1152 std::string DebugString() const override { return "SwapActiveOperator"; }

1153};

1154

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

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

1158 std::function<int(int64_t)> start_empty_path_class) {

1159 if (secondary_vars.empty()) {

1161 vars, secondary_vars, std::move(start_empty_path_class)));

1162 }

1164 vars, secondary_vars, std::move(start_empty_path_class)));

1165}

1166

1167

1168

1169template <bool ignore_path_vars>

1172 public:

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

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

1176 int max_chain_size)

1178 vars, secondary_vars, 2, std::move(start_empty_path_class)),

1179 last_before_chain_(-1),

1180 last_chain_end_(-1),

1181 current_chain_size_(0),

1182 max_chain_size_(max_chain_size) {

1183 DCHECK_GE(max_chain_size_, 1);

1184 }

1188

1189 protected:

1191 last_chain_end_ = -1;

1192 current_chain_size_ = 0;

1193 }

1197

1198

1199

1200

1201

1202

1203

1204

1205

1206

1207 std::string DebugString() const override { return "SwapActiveChainOperator"; }

1208

1209 private:

1211 last_chain_end_ = -1;

1212 current_chain_size_ = 0;

1213 }

1214

1215 int64_t last_before_chain_;

1216 int64_t last_chain_end_;

1217 int current_chain_size_;

1218 const int max_chain_size_;

1219};

1220

1221template <bool ignore_path_vars>

1223 const int64_t before_chain = this->BaseNode(0);

1224 const int64_t chain_end = this->BaseNode(1);

1225 if (last_before_chain_ != before_chain || last_chain_end_ == -1) {

1226 this->RevertChanges(false);

1227 last_before_chain_ = before_chain;

1229 if (!this->IsPathEnd(chain_end) && before_chain != chain_end &&

1232 ++current_chain_size_;

1233 return true;

1234 } else {

1235 last_chain_end_ = -1;

1236 current_chain_size_ = 0;

1237 return false;

1238 }

1239 }

1240 if (current_chain_size_ >= max_chain_size_) {

1241

1243 current_chain_size_ = 0;

1244 return false;

1245 }

1246 if (!this->IsPathEnd(last_chain_end_) &&

1248 ++current_chain_size_;

1249 return true;

1250 }

1251 last_chain_end_ = -1;

1252 current_chain_size_ = 0;

1253 return false;

1254}

1255

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

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

1259 std::function<int(int64_t)> start_empty_path_class, int max_chain_size) {

1260 if (secondary_vars.empty()) {

1262 vars, secondary_vars, std::move(start_empty_path_class),

1263 max_chain_size));

1264 }

1266 vars, secondary_vars, std::move(start_empty_path_class), max_chain_size));

1267}

1268

1269

1270

1271template <bool ignore_path_vars>

1274 public:

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

1277 std::function<int(int64_t)> start_empty_path_class)

1279 vars, secondary_vars, 2, std::move(start_empty_path_class)) {}

1282 const int64_t base0 = this->BaseNode(0);

1283 const int64_t base1 = this->BaseNode(1);

1284 if (this->Next(base0) == base1) {

1285 return false;

1286 }

1289 }

1290

1292 return "ExtendedSwapActiveOperator";

1293 }

1294};

1295

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

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

1299 std::function<int(int64_t)> start_empty_path_class) {

1300 if (secondary_vars.empty()) {

1302 vars, secondary_vars, std::move(start_empty_path_class)));

1303 }

1305 vars, secondary_vars, std::move(start_empty_path_class)));

1306}

1307

1308

1309

1310template <bool ignore_path_vars>

1312 public:

1313 TSPOpt(const std::vector<IntVar*>& vars,

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

1318

1319 std::string DebugString() const override { return "TSPOpt"; }

1320

1321 private:

1322 std::vector<std::vector<int64_t>> cost_;

1324 hamiltonian_path_solver_;

1326 const int chain_length_;

1327};

1328

1329template <bool ignore_path_vars>

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

1333 int chain_length)

1334 : PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,

1335 nullptr, nullptr, nullptr),

1336 hamiltonian_path_solver_(cost_),

1337 evaluator_(std::move(evaluator)),

1338 chain_length_(chain_length) {}

1339

1340template <bool ignore_path_vars>

1342 std::vector<int64_t> nodes;

1343 int64_t chain_end = this->BaseNode(0);

1344 for (int i = 0; i < chain_length_ + 1; ++i) {

1345 nodes.push_back(chain_end);

1346 if (this->IsPathEnd(chain_end)) {

1347 break;

1348 }

1349 chain_end = this->Next(chain_end);

1350 }

1351 if (nodes.size() <= 3) {

1352 return false;

1353 }

1354 int64_t chain_path = this->Path(this->BaseNode(0));

1355 const int size = nodes.size() - 1;

1356 cost_.resize(size);

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

1358 cost_[i].resize(size);

1359 cost_[i][0] = evaluator_(nodes[i], nodes[size], chain_path);

1360 for (int j = 1; j < size; ++j) {

1361 cost_[i][j] = evaluator_(nodes[i], nodes[j], chain_path);

1362 }

1363 }

1364 hamiltonian_path_solver_.ChangeCostMatrix(cost_);

1365 std::vector<PathNodeIndex> path;

1366 hamiltonian_path_solver_.TravelingSalesmanPath(&path);

1367 CHECK_EQ(size + 1, path.size());

1368 for (int i = 0; i < size - 1; ++i) {

1369 this->SetNext(nodes[path[i]], nodes[path[i + 1]], chain_path);

1370 }

1371 this->SetNext(nodes[path[size - 1]], nodes[size], chain_path);

1372 return true;

1373}

1374

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

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

1379 int chain_length) {

1380 if (secondary_vars.empty()) {

1382 vars, secondary_vars, std::move(evaluator), chain_length));

1383 }

1385 vars, secondary_vars, std::move(evaluator), chain_length));

1386}

1387

1388template <bool ignore_path_vars>

1390 public:

1391 TSPLns(const std::vector<IntVar*>& vars,

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

1396

1397 std::string DebugString() const override { return "TSPLns"; }

1398

1399 protected:

1401

1402 private:

1404

1405 has_long_enough_paths_ = this->Size() != 0;

1406 }

1407

1408 std::vector<std::vector<int64_t>> cost_;

1409 HamiltonianPathSolver<int64_t, std::vector<std::vector<int64_t>>>

1410 hamiltonian_path_solver_;

1412 const int tsp_size_;

1413 std::mt19937 rand_;

1414 bool has_long_enough_paths_;

1415};

1416

1417template <bool ignore_path_vars>

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

1421 int tsp_size)

1422 : PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,

1423 nullptr, nullptr, nullptr),

1424 hamiltonian_path_solver_(cost_),

1425 evaluator_(std::move(evaluator)),

1426 tsp_size_(tsp_size),

1428 has_long_enough_paths_(true) {

1429 CHECK_GE(tsp_size_, 0);

1430 cost_.resize(tsp_size_);

1431 for (int i = 0; i < tsp_size_; ++i) {

1432 cost_[i].resize(tsp_size_);

1433 }

1434}

1435

1436template <bool ignore_path_vars>

1438 while (has_long_enough_paths_) {

1439 has_long_enough_paths_ = false;

1441 return true;

1442 }

1443 this->Var(0)->solver()->TopPeriodicCheck();

1444 }

1445 return false;

1446}

1447

1448template <bool ignore_path_vars>

1450 const int64_t base_node = this->BaseNode(0);

1451 std::vector<int64_t> nodes;

1453 node = this->Next(node)) {

1454 nodes.push_back(node);

1455 }

1456 if (nodes.size() <= tsp_size_) {

1457 return false;

1458 }

1459 has_long_enough_paths_ = true;

1460

1461

1462 absl::flat_hash_set<int64_t> breaks_set;

1463

1464 breaks_set.insert(base_node);

1465 CHECK(!nodes.empty());

1466 while (breaks_set.size() < tsp_size_) {

1467 breaks_set.insert(nodes[absl::Uniform<int>(rand_, 0, nodes.size())]);

1468 }

1469 CHECK_EQ(breaks_set.size(), tsp_size_);

1470

1471

1472

1473

1474 std::vector<int> breaks;

1475 std::vector<int64_t> meta_node_costs;

1476 int64_t cost = 0;

1477 int64_t node = this->StartNode(0);

1478 int64_t node_path = this->Path(node);

1479 while (!this->IsPathEnd(node)) {

1480 int64_t next = this->Next(node);

1481 if (breaks_set.contains(node)) {

1482 breaks.push_back(node);

1483 meta_node_costs.push_back(cost);

1484 cost = 0;

1485 } else {

1486 cost = CapAdd(cost, evaluator_(node, next, node_path));

1487 }

1488 node = next;

1489 }

1490 meta_node_costs[0] += cost;

1491 CHECK_EQ(breaks.size(), tsp_size_);

1492

1493 CHECK_EQ(meta_node_costs.size(), tsp_size_);

1494 for (int i = 0; i < tsp_size_; ++i) {

1495 cost_[i][0] = CapAdd(

1496 meta_node_costs[i],

1497 evaluator_(breaks[i], this->Next(breaks[tsp_size_ - 1]), node_path));

1498 for (int j = 1; j < tsp_size_; ++j) {

1499 cost_[i][j] =

1500 CapAdd(meta_node_costs[i],

1501 evaluator_(breaks[i], this->Next(breaks[j - 1]), node_path));

1502 }

1503 cost_[i][i] = 0;

1504 }

1505

1506 hamiltonian_path_solver_.ChangeCostMatrix(cost_);

1507 std::vector<PathNodeIndex> path;

1508 hamiltonian_path_solver_.TravelingSalesmanPath(&path);

1509 bool nochange = true;

1510 for (int i = 0; i < path.size() - 1; ++i) {

1511 if (path[i] != i) {

1512 nochange = false;

1513 break;

1514 }

1515 }

1516 if (nochange) {

1517 return false;

1518 }

1519 CHECK_EQ(0, path[path.size() - 1]);

1520 for (int i = 0; i < tsp_size_ - 1; ++i) {

1521 this->SetNext(breaks[path[i]], this->OldNext(breaks[path[i + 1] - 1]),

1522 node_path);

1523 }

1524 this->SetNext(breaks[path[tsp_size_ - 1]],

1525 this->OldNext(breaks[tsp_size_ - 1]), node_path);

1526 return true;

1527}

1528

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

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

1533 int tsp_size) {

1534 if (secondary_vars.empty()) {

1536 new TSPLns<true>(vars, secondary_vars, std::move(evaluator), tsp_size));

1537 }

1539 new TSPLns<false>(vars, secondary_vars, std::move(evaluator), tsp_size));

1540}

1541

1542

1543

1544

1545

1546

1547

1548

1549

1550template <bool ignore_path_vars>

1552 public:

1555 int size);

1556

1557

1560

1562 void Initialize(absl::Span<const int> path);

1563 const std::vector<int>& Neighbors(int index) const;

1564

1565 virtual std::string DebugString() const { return "NearestNeighbors"; }

1566

1567 private:

1568 void ComputeNearest(int row, absl::Span<const int> path);

1569

1570 std::vector<std::vector<int>> neighbors_;

1573 const int size_;

1574};

1575

1576template <bool ignore_path_vars>

1580 : neighbors_(path_operator.number_of_nexts()),

1581 evaluator_(std::move(evaluator)),

1582 path_operator_(path_operator),

1583 size_(size) {}

1584

1585template <bool ignore_path_vars>

1587 absl::Span<const int> path) {

1588 for (int node : path) {

1589 if (node < path_operator_.number_of_nexts()) ComputeNearest(node, path);

1590 }

1591}

1592

1593template <bool ignore_path_vars>

1595 int index) const {

1596 return neighbors_[index];

1597}

1598

1599template <bool ignore_path_vars>

1600void NearestNeighbors<ignore_path_vars>::ComputeNearest(

1601 int row, absl::Span<const int> path_nodes) {

1602

1603 const int path = path_operator_.Path(row);

1604 const IntVar* var = path_operator_.Var(row);

1605 using ValuedIndex = std::pair<int64_t , int >;

1606 std::vector<ValuedIndex> neighbors;

1607 for (int index : path_nodes) {

1608 if (!var->Contains(index)) continue;

1609 neighbors.push_back({evaluator_(row, index, path), index});

1610 }

1611 const int neighbors_size = neighbors.size();

1612 if (neighbors_size > size_) {

1613 std::nth_element(neighbors.begin(), neighbors.begin() + size_ - 1,

1614 neighbors.end());

1615 }

1616

1617

1618 neighbors_[row].clear();

1619 for (int i = 0; i < std::min(size_, neighbors_size); ++i) {

1620 neighbors_[row].push_back(neighbors[i].second);

1621 }

1622 std::sort(neighbors_[row].begin(), neighbors_[row].end());

1623}

1624

1625template <bool ignore_path_vars>

1627 public:

1628 LinKernighan(const std::vector<IntVar*>& vars,

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

1633

1634 std::string DebugString() const override { return "LinKernighan"; }

1635

1636 private:

1638

1639 bool GetBestOut(int64_t in_i, int64_t in_j, int64_t* out, int64_t* gain);

1640

1643 absl::flat_hash_set<int64_t> marked_;

1644 const bool topt_;

1645 std::vector<int> old_path_starts_;

1646};

1647

1648

1649

1650

1651

1652template <bool ignore_path_vars>

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

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

1657 : PathOperator<ignore_path_vars>(vars, secondary_vars, 1, true, false,

1658 nullptr, nullptr, nullptr),

1659 evaluator_(evaluator),

1660 neighbors_(evaluator, *this, 5 + 1),

1661 topt_(topt) {

1663}

1664

1665template <bool ignore_path_vars>

1667 absl::flat_hash_set<int> touched_paths;

1668 for (int i = 0; i < this->number_of_nexts(); ++i) {

1669 if (this->IsPathStart(i)) {

1670 for (int node = i; !this->IsPathEnd(node); node = this->Next(node)) {

1671 if (i != old_path_starts_[node]) {

1672 touched_paths.insert(old_path_starts_[node]);

1673 touched_paths.insert(i);

1674 old_path_starts_[node] = i;

1675 }

1676 }

1677 } else if (this->Next(i) == i) {

1678 touched_paths.insert(old_path_starts_[i]);

1679 old_path_starts_[i] = -1;

1680 }

1681 }

1682 for (int touched_path_start : touched_paths) {

1683 if (touched_path_start == -1) continue;

1684 std::vector<int> path;

1685 int node = touched_path_start;

1686 while (!this->IsPathEnd(node)) {

1687 path.push_back(node);

1688 node = this->Next(node);

1689 }

1690 path.push_back(node);

1691 neighbors_.Initialize(path);

1692 }

1693}

1694

1695template <bool ignore_path_vars>

1697 marked_.clear();

1698 int64_t node = this->BaseNode(0);

1699 int64_t path = this->Path(node);

1700 int64_t base = node;

1701 int64_t next = this->Next(node);

1702 if (this->IsPathEnd(next)) return false;

1703 int64_t out = -1;

1704 int64_t gain = 0;

1705 marked_.insert(node);

1706 if (topt_) {

1707 if (!GetBestOut(node, next, &out, &gain)) return false;

1708 marked_.insert(next);

1709 marked_.insert(out);

1710 const int64_t node1 = out;

1711 if (this->IsPathEnd(node1)) return false;

1712 const int64_t next1 = this->Next(node1);

1713 if (this->IsPathEnd(next1)) return false;

1714 if (!GetBestOut(node1, next1, &out, &gain)) return false;

1715 marked_.insert(next1);

1716 marked_.insert(out);

1718 !this->MoveChain(out, node1, node)) {

1719 return false;

1720 }

1721 const int64_t next_out = this->Next(out);

1722 const int64_t in_cost = evaluator_(node, next_out, path);

1723 const int64_t out_cost = evaluator_(out, next_out, path);

1724 if (CapAdd(CapSub(gain, in_cost), out_cost) > 0) return true;

1725 node = out;

1726 if (this->IsPathEnd(node)) return false;

1727 next = next_out;

1728 if (this->IsPathEnd(next)) return false;

1729 }

1730

1731 while (GetBestOut(node, next, &out, &gain)) {

1732 marked_.insert(next);

1733 marked_.insert(out);

1734 int64_t chain_last;

1735 if (this->Next(base) == out ||

1737 return false;

1738 }

1739 const bool success = this->ReverseChain(base, out, &chain_last) ||

1741 if (!success) {

1742#ifndef NDEBUG

1743 LOG(ERROR) << "ReverseChain failed: " << base << " " << out;

1745 node = this->Next(node)) {

1746 LOG(ERROR) << "node: " << node;

1747 }

1748 LOG(ERROR) << "node: " << node;

1749 DCHECK(false);

1750#endif

1751 }

1752 const int64_t in_cost = evaluator_(base, chain_last, path);

1753 const int64_t out_cost = evaluator_(chain_last, out, path);

1754 if (CapAdd(CapSub(gain, in_cost), out_cost) > 0) {

1755 return true;

1756 }

1757 node = out;

1759 return false;

1760 }

1761 next = chain_last;

1763 return false;

1764 }

1765 }

1766 return false;

1767}

1768

1769template <bool ignore_path_vars>

1770bool LinKernighan<ignore_path_vars>::GetBestOut(int64_t in_i, int64_t in_j,

1771 int64_t* out, int64_t* gain) {

1772 int64_t best_gain = std::numeric_limits<int64_t>::min();

1773 const int64_t path = this->Path(in_i);

1774 const int64_t out_cost = evaluator_(in_i, in_j, path);

1775 const int64_t current_gain = CapAdd(*gain, out_cost);

1776 for (int next : neighbors_.Neighbors(in_j)) {

1777 if (next != in_j && next != this->Next(in_j) && !marked_.contains(in_j) &&

1778 !marked_.contains(next)) {

1779 const int64_t in_cost = evaluator_(in_j, next, path);

1780 const int64_t new_gain = CapSub(current_gain, in_cost);

1781 if (new_gain > 0 && best_gain < new_gain) {

1782 *out = next;

1783 best_gain = new_gain;

1784 }

1785 }

1786 }

1787 *gain = best_gain;

1788 return (best_gain > std::numeric_limits<int64_t>::min());

1789}

1790

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

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

1795 if (secondary_vars.empty()) {

1797 std::move(evaluator), topt));

1798 }

1800 std::move(evaluator), topt));

1801}

1802

1803

1804

1805template <bool ignore_path_vars>

1807 public:

1808 PathLns(const std::vector<IntVar*>& vars,

1809 const std::vector<IntVar*>& secondary_vars, int number_of_chunks,

1810 int chunk_size, bool unactive_fragments)

1811 : PathOperator<ignore_path_vars>(vars, secondary_vars, number_of_chunks,

1812 true, true, nullptr, nullptr, nullptr),

1813 number_of_chunks_(number_of_chunks),

1814 chunk_size_(chunk_size),

1815 unactive_fragments_(unactive_fragments) {

1816 CHECK_GE(chunk_size_, 0);

1817 }

1820

1821 std::string DebugString() const override { return "PathLns"; }

1823

1824 private:

1825 inline bool ChainsAreFullPaths() const { return chunk_size_ == 0; }

1826 void DeactivateChain(int64_t node);

1827 void DeactivateUnactives();

1828

1829 const int number_of_chunks_;

1830 const int chunk_size_;

1831 const bool unactive_fragments_;

1832};

1833

1834template <bool ignore_path_vars>

1836 if (ChainsAreFullPaths()) {

1837

1838

1839

1840 for (int i = 0; i < number_of_chunks_; ++i) {

1842 }

1843 }

1844 for (int i = 0; i < number_of_chunks_; ++i) {

1845 DeactivateChain(this->BaseNode(i));

1846 }

1847 DeactivateUnactives();

1848 return true;

1849}

1850

1851template <bool ignore_path_vars>

1852void PathLns<ignore_path_vars>::DeactivateChain(int64_t node) {

1853 for (int i = 0, current = node;

1854 (ChainsAreFullPaths() || i < chunk_size_) && !this->IsPathEnd(current);

1855 ++i, current = this->Next(current)) {

1856 this->Deactivate(current);

1857 if constexpr (!ignore_path_vars) {

1858 this->Deactivate(this->number_of_nexts_ + current);

1859 }

1860 }

1861}

1862

1863template <bool ignore_path_vars>

1864void PathLns<ignore_path_vars>::DeactivateUnactives() {

1865 if (unactive_fragments_) {

1866 for (int i = 0; i < this->Size(); ++i) {

1867 if (this->IsInactive(i)) {

1868 this->Deactivate(i);

1869 if constexpr (!ignore_path_vars) {

1870 this->Deactivate(this->number_of_nexts_ + i);

1871 }

1872 }

1873 }

1874 }

1875}

1876

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

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

1880 int number_of_chunks, int chunk_size,

1881 bool unactive_fragments) {

1882 if (secondary_vars.empty()) {

1884 number_of_chunks, chunk_size,

1885 unactive_fragments));

1886 }

1888 vars, secondary_vars, number_of_chunks, chunk_size, unactive_fragments));

1889}

1890

1891

1892

1894 public:

1896 : operator_(op), limit_(limit), next_neighborhood_calls_(0) {

1897 CHECK(op != nullptr);

1898 CHECK_GT(limit, 0);

1899 }

1900

1902 next_neighborhood_calls_ = 0;

1903 operator_->Start(assignment);

1904 }

1905

1907 if (next_neighborhood_calls_ >= limit_) {

1908 return false;

1909 }

1910 ++next_neighborhood_calls_;

1911 return operator_->MakeNextNeighbor(delta, deltadelta);

1912 }

1913

1914 bool HoldsDelta() const override { return operator_->HoldsDelta(); }

1915

1916 std::string DebugString() const override { return "NeighborhoodLimit"; }

1917

1918 private:

1920 const int64_t limit_;

1921 int64_t next_neighborhood_calls_;

1922};

1923

1928

1929

1930

1931namespace {

1933 public:

1934 CompoundOperator(std::vector<LocalSearchOperator*> operators,

1935 std::function<int64_t(int, int)> evaluator);

1936 ~CompoundOperator() override {}

1937 void EnterSearch() override;

1938 void Reset() override;

1939 void Start(const Assignment* assignment) override;

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

1941 bool HasFragments() const override { return has_fragments_; }

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

1943

1944 std::string DebugString() const override {

1945 return operators_.empty()

1946 ? ""

1947 : operators_[operator_indices_[index_]]->DebugString();

1948 }

1949 const LocalSearchOperator* Self() const override {

1950 return operators_.empty() ? this

1951 : operators_[operator_indices_[index_]]->Self();

1952 }

1953

1954 private:

1955 class OperatorComparator {

1956 public:

1957 OperatorComparator(std::function<int64_t(int, int)> evaluator,

1958 int active_operator)

1959 : evaluator_(std::move(evaluator)), active_operator_(active_operator) {}

1960 bool operator()(int lhs, int rhs) const {

1961 const int64_t lhs_value = Evaluate(lhs);

1962 const int64_t rhs_value = Evaluate(rhs);

1963 return lhs_value < rhs_value || (lhs_value == rhs_value && lhs < rhs);

1964 }

1965

1966 private:

1967 int64_t Evaluate(int operator_index) const {

1968 return evaluator_(active_operator_, operator_index);

1969 }

1970

1971 std::function<int64_t(int, int)> evaluator_;

1972 const int active_operator_;

1973 };

1974

1975 int64_t index_;

1976 std::vector<LocalSearchOperator*> operators_;

1977 std::vector<int> operator_indices_;

1978 std::function<int64_t(int, int)> evaluator_;

1979 Bitset64<> started_;

1980 const Assignment* start_assignment_;

1981 bool has_fragments_;

1982};

1983

1984CompoundOperator::CompoundOperator(std::vector<LocalSearchOperator*> operators,

1985 std::function<int64_t(int, int)> evaluator)

1986 : index_(0),

1987 operators_(std::move(operators)),

1988 evaluator_(std::move(evaluator)),

1989 started_(operators_.size()),

1990 start_assignment_(nullptr),

1991 has_fragments_(false) {

1992 operators_.erase(std::remove(operators_.begin(), operators_.end(), nullptr),

1993 operators_.end());

1994 operator_indices_.resize(operators_.size());

1995 absl::c_iota(operator_indices_, 0);

1996 for (LocalSearchOperator* const op : operators_) {

1997 if (op->HasFragments()) {

1998 has_fragments_ = true;

1999 break;

2000 }

2001 }

2002}

2003

2004void CompoundOperator::EnterSearch() {

2005 absl::c_iota(operator_indices_, 0);

2006 index_ = 0;

2007 for (LocalSearchOperator* const op : operators_) {

2008 op->EnterSearch();

2009 }

2010}

2011

2012void CompoundOperator::Reset() {

2013 for (LocalSearchOperator* const op : operators_) {

2014 op->Reset();

2015 }

2016}

2017

2018void CompoundOperator::Start(const Assignment* assignment) {

2019 start_assignment_ = assignment;

2021 if (!operators_.empty()) {

2022 std::sort(operator_indices_.begin(), operator_indices_.end(),

2023 OperatorComparator(evaluator_, operator_indices_[index_]));

2024 index_ = 0;

2025 }

2026}

2027

2028bool CompoundOperator::MakeNextNeighbor(Assignment* delta,

2029 Assignment* deltadelta) {

2030 const auto is_leaf = [](const LocalSearchOperator* op) {

2031 return op == op->Self();

2032 };

2033 if (!operators_.empty()) {

2034 Solver* solver = delta->solver();

2035 do {

2036

2037

2038 const int64_t operator_index = operator_indices_[index_];

2039 LocalSearchOperator* op = operators_[operator_index];

2040 if (!started_[operator_index]) {

2041 op->Start(start_assignment_);

2042 started_.Set(operator_index);

2043 }

2044 if (!op->HoldsDelta()) {

2045 delta->Clear();

2046 }

2047 if (is_leaf(op)) {

2048 solver->GetLocalSearchMonitor()->BeginMakeNextNeighbor(op);

2049 }

2050 if (op->MakeNextNeighbor(delta, deltadelta)) return true;

2051 if (is_leaf(op)) {

2052 solver->GetLocalSearchMonitor()->EndMakeNextNeighbor(

2053 op, false, delta, deltadelta);

2054 }

2055 ++index_;

2056 delta->Clear();

2057 if (index_ == operators_.size()) {

2058 index_ = 0;

2059 }

2060 } while (index_ != 0);

2061 }

2062 return false;

2063}

2064

2065int64_t CompoundOperatorNoRestart(int size, int active_index,

2066 int operator_index) {

2067 return (operator_index < active_index) ? size + operator_index - active_index

2068 : operator_index - active_index;

2069}

2070}

2071

2073 const std::vector<LocalSearchOperator*>& ops) {

2075}

2076

2078 const std::vector<LocalSearchOperator*>& ops, bool restart) {

2079 if (restart) {

2081 ops, std::function<int64_t(int, int)>([](int, int) { return 0; }));

2082 }

2083 const int size = ops.size();

2085 return CompoundOperatorNoRestart(size, i, j);

2086 });

2087}

2088

2090 const std::vector<LocalSearchOperator*>& ops,

2091 std::function<int64_t(int, int)> evaluator) {

2092 return RevAlloc(new CompoundOperator(ops, std::move(evaluator)));

2093}

2094

2095namespace {

2097 public:

2098 explicit RandomCompoundOperator(std::vector<LocalSearchOperator*> operators);

2099 RandomCompoundOperator(std::vector<LocalSearchOperator*> operators,

2100 int32_t seed);

2101 ~RandomCompoundOperator() override {}

2102 void EnterSearch() override;

2103 void Reset() override;

2104 void Start(const Assignment* assignment) override;

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

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

2107

2108 std::string DebugString() const override { return "RandomCompoundOperator"; }

2109

2110

2111 private:

2112 std::mt19937 rand_;

2113 const std::vector<LocalSearchOperator*> operators_;

2114 bool has_fragments_;

2115};

2116

2117void RandomCompoundOperator::Start(const Assignment* assignment) {

2118 for (LocalSearchOperator* const op : operators_) {

2119 op->Start(assignment);

2120 }

2121}

2122

2123RandomCompoundOperator::RandomCompoundOperator(

2124 std::vector<LocalSearchOperator*> operators)

2125 : RandomCompoundOperator(std::move(operators), CpRandomSeed()) {}

2126

2127RandomCompoundOperator::RandomCompoundOperator(

2128 std::vector<LocalSearchOperator*> operators, int32_t seed)

2129 : rand_(seed), operators_(std::move(operators)), has_fragments_(false) {

2130 for (LocalSearchOperator* const op : operators_) {

2131 if (op->HasFragments()) {

2132 has_fragments_ = true;

2133 break;

2134 }

2135 }

2136}

2137

2138void RandomCompoundOperator::EnterSearch() {

2139 for (LocalSearchOperator* const op : operators_) {

2140 op->EnterSearch();

2141 }

2142}

2143

2144void RandomCompoundOperator::Reset() {

2145 for (LocalSearchOperator* const op : operators_) {

2146 op->Reset();

2147 }

2148}

2149

2150bool RandomCompoundOperator::MakeNextNeighbor(Assignment* delta,

2151 Assignment* deltadelta) {

2152 const int size = operators_.size();

2153 std::vector<int> indices(size);

2154 absl::c_iota(indices, 0);

2155 std::shuffle(indices.begin(), indices.end(), rand_);

2156 for (int index : indices) {

2157 if (!operators_[index]->HoldsDelta()) {

2158 delta->Clear();

2159 }

2160 if (operators_[index]->MakeNextNeighbor(delta, deltadelta)) {

2161 return true;

2162 }

2163 delta->Clear();

2164 }

2165 return false;

2166}

2167}

2168

2170 const std::vector<LocalSearchOperator*>& ops) {

2171 return RevAlloc(new RandomCompoundOperator(ops));

2172}

2173

2175 const std::vector<LocalSearchOperator*>& ops, int32_t seed) {

2176 return RevAlloc(new RandomCompoundOperator(ops, seed));

2177}

2178

2179namespace {

2181 public:

2182 explicit MultiArmedBanditCompoundOperator(

2183 std::vector<LocalSearchOperator*> operators, double memory_coefficient,

2184 double exploration_coefficient, bool maximize);

2185 ~MultiArmedBanditCompoundOperator() override {}

2186 void EnterSearch() override;

2187 void Reset() override;

2188 void Start(const Assignment* assignment) override;

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

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

2191

2192 std::string DebugString() const override {

2193 return operators_.empty()

2194 ? ""

2195 : operators_[operator_indices_[index_]]->DebugString();

2196 }

2197 const LocalSearchOperator* Self() const override {

2198 return operators_.empty() ? this

2199 : operators_[operator_indices_[index_]]->Self();

2200 }

2201

2202 private:

2203 double Score(int index);

2204 int index_;

2205 std::vector<LocalSearchOperator*> operators_;

2206 Bitset64<> started_;

2207 const Assignment* start_assignment_;

2208 bool has_fragments_;

2209 std::vector<int> operator_indices_;

2210 int64_t last_objective_;

2211 std::vector<double> avg_improvement_;

2212 int num_neighbors_;

2213 std::vector<double> num_neighbors_per_operator_;

2214 const bool maximize_;

2215

2216

2217

2218

2219 const double memory_coefficient_;

2220

2221

2222

2223

2224

2225

2226 const double exploration_coefficient_;

2227};

2228

2229MultiArmedBanditCompoundOperator::MultiArmedBanditCompoundOperator(

2230 std::vector<LocalSearchOperator*> operators, double memory_coefficient,

2231 double exploration_coefficient, bool maximize)

2232 : index_(0),

2233 operators_(std::move(operators)),

2234 started_(operators_.size()),

2235 start_assignment_(nullptr),

2236 has_fragments_(false),

2237 last_objective_(std::numeric_limits<int64_t>::max()),

2238 num_neighbors_(0),

2239 maximize_(maximize),

2240 memory_coefficient_(memory_coefficient),

2241 exploration_coefficient_(exploration_coefficient) {

2242 DCHECK_GE(memory_coefficient_, 0);

2243 DCHECK_LE(memory_coefficient_, 1);

2244 DCHECK_GE(exploration_coefficient_, 0);

2245 operators_.erase(std::remove(operators_.begin(), operators_.end(), nullptr),

2246 operators_.end());

2247 operator_indices_.resize(operators_.size());

2248 absl::c_iota(operator_indices_, 0);

2249 num_neighbors_per_operator_.resize(operators_.size(), 0);

2250 avg_improvement_.resize(operators_.size(), 0);

2251 for (LocalSearchOperator* const op : operators_) {

2252 if (op->HasFragments()) {

2253 has_fragments_ = true;

2254 break;

2255 }

2256 }

2257}

2258

2259void MultiArmedBanditCompoundOperator::EnterSearch() {

2260 last_objective_ = std::numeric_limits<int64_t>::max();

2261 num_neighbors_ = 0;

2262 absl::c_iota(operator_indices_, 0);

2263 index_ = 0;

2264 num_neighbors_per_operator_.resize(operators_.size(), 0);

2265 avg_improvement_.resize(operators_.size(), 0);

2266 for (LocalSearchOperator* const op : operators_) {

2267 op->EnterSearch();

2268 }

2269}

2270

2271void MultiArmedBanditCompoundOperator::Reset() {

2272 for (LocalSearchOperator* const op : operators_) {

2273 op->Reset();

2274 }

2275}

2276

2277double MultiArmedBanditCompoundOperator::Score(int index) {

2278 return avg_improvement_[index] +

2279 exploration_coefficient_ *

2280 sqrt(2 * log(1 + num_neighbors_) /

2281 (1 + num_neighbors_per_operator_[index]));

2282}

2283

2284void MultiArmedBanditCompoundOperator::Start(const Assignment* assignment) {

2285 start_assignment_ = assignment;

2287 if (operators_.empty()) return;

2288

2289 const double objective = assignment->ObjectiveValue();

2290

2291 if (objective == last_objective_) return;

2292

2293 if (last_objective_ == std::numeric_limits<int64_t>::max()) {

2294 last_objective_ = objective;

2295 return;

2296 }

2297

2298 const double improvement =

2299 maximize_ ? objective - last_objective_ : last_objective_ - objective;

2300 if (improvement < 0) {

2301 return;

2302 }

2303 last_objective_ = objective;

2304 avg_improvement_[operator_indices_[index_]] +=

2305 memory_coefficient_ *

2306 (improvement - avg_improvement_[operator_indices_[index_]]);

2307

2308 std::sort(operator_indices_.begin(), operator_indices_.end(),

2309 [this](int lhs, int rhs) {

2310 const double lhs_score = Score(lhs);

2311 const double rhs_score = Score(rhs);

2312 return lhs_score > rhs_score ||

2313 (lhs_score == rhs_score && lhs < rhs);

2314 });

2315

2316 index_ = 0;

2317}

2318

2319bool MultiArmedBanditCompoundOperator::MakeNextNeighbor(

2320 Assignment* delta, Assignment* deltadelta) {

2321 if (operators_.empty()) return false;

2322 do {

2323 const int operator_index = operator_indices_[index_];

2324 if (!started_[operator_index]) {

2325 operators_[operator_index]->Start(start_assignment_);

2326 started_.Set(operator_index);

2327 }

2328 if (!operators_[operator_index]->HoldsDelta()) {

2329 delta->Clear();

2330 }

2331 if (operators_[operator_index]->MakeNextNeighbor(delta, deltadelta)) {

2332 ++num_neighbors_;

2333 ++num_neighbors_per_operator_[operator_index];

2334 return true;

2335 }

2336 ++index_;

2337 delta->Clear();

2338 if (index_ == operators_.size()) {

2339 index_ = 0;

2340 }

2341 } while (index_ != 0);

2342 return false;

2343}

2344}

2345

2347 const std::vector<LocalSearchOperator*>& ops, double memory_coefficient,

2348 double exploration_coefficient, bool maximize) {

2349 return RevAlloc(new MultiArmedBanditCompoundOperator(

2350 ops, memory_coefficient, exploration_coefficient, maximize));

2351}

2352

2353

2354

2359 return MakeOperator(vars, std::vector<IntVar*>(), op,

2360 std::move(get_incoming_neighbors),

2361 std::move(get_outgoing_neighbors));

2362}

2363

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

2369 switch (op) {

2371 return MakeTwoOpt(this, vars, secondary_vars, nullptr,

2372 std::move(get_incoming_neighbors),

2373 std::move(get_outgoing_neighbors));

2374 }

2376 std::vector<LocalSearchOperator*> operators;

2377 for (int i = 1; i < 4; ++i) {

2378 operators.push_back(MakeRelocate(this, vars, secondary_vars,

2379 nullptr,

2380 nullptr,

2381 nullptr,

2382 i,

2383 true,

2384 "OrOpt"));

2385 }

2387 }

2390 this, vars, secondary_vars, nullptr,

2391 std::move(get_incoming_neighbors), std::move(get_outgoing_neighbors));

2392 }

2394 return MakeExchange(this, vars, secondary_vars, nullptr,

2395 std::move(get_incoming_neighbors),

2396 std::move(get_outgoing_neighbors));

2397 }

2399 return MakeCross(this, vars, secondary_vars, nullptr,

2400 std::move(get_incoming_neighbors),

2401 std::move(get_outgoing_neighbors));

2402 }

2404 return MakeActive(this, vars, secondary_vars, nullptr);

2405 }

2407 return MakeInactive(this, vars, secondary_vars, nullptr);

2408 }

2411 }

2413 return MakeSwapActive(this, vars, secondary_vars, nullptr);

2414 }

2418 }

2421 }

2423 return MakePathLns(this, vars, secondary_vars, 2,

2424 3, false);

2425 }

2427 return MakePathLns(this, vars, secondary_vars,

2428 1,

2429 0,

2430 true);

2431 }

2433 return MakePathLns(this, vars, secondary_vars, 1,

2434 6, true);

2435 }

2437 if (!secondary_vars.empty()) {

2438 LOG(FATAL) << "Operator " << op

2439 << " does not support secondary variables";

2440 }

2441 return RevAlloc(new IncrementValue(vars));

2442 }

2444 if (!secondary_vars.empty()) {

2445 LOG(FATAL) << "Operator " << op

2446 << " does not support secondary variables";

2447 }

2448 return RevAlloc(new DecrementValue(vars));

2449 }

2451 if (!secondary_vars.empty()) {

2452 LOG(FATAL) << "Operator " << op

2453 << " does not support secondary variables";

2454 }

2455 return RevAlloc(new SimpleLns(vars, 1));

2456 }

2457 default:

2458 LOG(FATAL) << "Unknown operator " << op;

2459 }

2460 return nullptr;

2461}

2462

2466 return MakeOperator(vars, std::vector<IntVar*>(), std::move(evaluator), op);

2467}

2468

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

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

2474 switch (op) {

2476 std::vector<LocalSearchOperator*> operators;

2477 operators.push_back(MakeLinKernighan(this, vars, secondary_vars,

2478 evaluator, false));

2479 operators.push_back(MakeLinKernighan(this, vars, secondary_vars,

2480 evaluator, true));

2482 }

2484 return MakeTSPOpt(this, vars, secondary_vars, std::move(evaluator),

2485 absl::GetFlag(FLAGS_cp_local_search_tsp_opt_size));

2486 }

2488 return MakeTSPLns(this, vars, secondary_vars, std::move(evaluator),

2489 absl::GetFlag(FLAGS_cp_local_search_tsp_lns_size));

2490 }

2491 default:

2492 LOG(FATAL) << "Unknown operator " << op;

2493 }

2494 return nullptr;

2495}

2496

2497namespace {

2498

2500 public:

2501 std::string DebugString() const override { return "AcceptFilter"; }

2502 bool Accept(const Assignment*, const Assignment*, int64_t, int64_t) override {

2503 return true;

2504 }

2505 void Synchronize(const Assignment*, const Assignment*) override {}

2506};

2507}

2508

2510 return RevAlloc(new AcceptFilter());

2511}

2512

2513namespace {

2514

2516 public:

2517 std::string DebugString() const override { return "RejectFilter"; }

2518 bool Accept(const Assignment*, const Assignment*, int64_t, int64_t) override {

2519 return false;

2520 }

2521 void Synchronize(const Assignment*, const Assignment*) override {}

2522};

2523}

2524

2526 return RevAlloc(new RejectFilter());

2527}

2528

2529namespace {

2530

2531

2532

2534 public:

2535 VariableDomainFilter() {}

2536 ~VariableDomainFilter() override {}

2537 bool Accept(const Assignment* delta, const Assignment* deltadelta,

2538 int64_t objective_min, int64_t objective_max) override;

2539 void Synchronize(const Assignment*, const Assignment*) override {}

2540

2541 std::string DebugString() const override { return "VariableDomainFilter"; }

2542};

2543

2544bool VariableDomainFilter::Accept(const Assignment* delta, const Assignment*,

2545 int64_t, int64_t) {

2546 const Assignment::IntContainer& container = delta->IntVarContainer();

2547 const int size = container.Size();

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

2549 const IntVarElement& element = container.Element(i);

2550 if (element.Activated() && !element.Var()->Contains(element.Value())) {

2551 return false;

2552 }

2553 }

2554 return true;

2555}

2556}

2557

2559 return RevAlloc(new VariableDomainFilter());

2560}

2561

2562

2563

2564const int IntVarLocalSearchFilter::kUnassigned = -1;

2565

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

2569}

2570

2572 if (!vars.empty()) {

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

2574 const int index = vars[i]->index();

2575 if (index >= var_index_to_index_.size()) {

2576 var_index_to_index_.resize(index + 1, kUnassigned);

2577 }

2578 var_index_to_index_[index] = i + vars_.size();

2579 }

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

2581 values_.resize(vars_.size(), 0);

2582 var_synced_.resize(vars_.size(), false);

2583 }

2584}

2585

2587

2590 if (delta == nullptr || delta->Empty()) {

2591 var_synced_.assign(var_synced_.size(), false);

2593 } else {

2595 }

2597}

2598

2602 const int size = container.Size();

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

2605 IntVar* const var = element.Var();

2606 if (var != nullptr) {

2607 if (i < vars_.size() && vars_[i] == var) {

2608 values_[i] = element.Value();

2609 var_synced_[i] = true;

2610 } else {

2611 const int64_t kUnallocated = -1;

2612 int64_t index = kUnallocated;

2614 values_[index] = element.Value();

2615 var_synced_[index] = true;

2616 }

2617 }

2618 }

2619 }

2620}

2621

2622

2623

2624

2625

2626

2627

2628

2629

2630

2631namespace {

2632template <typename Filter>

2634 public:

2635 SumObjectiveFilter(const std::vector<IntVar*>& vars, Filter filter)

2637 primary_vars_size_(vars.size()),

2638 synchronized_costs_(vars.size()),

2639 delta_costs_(vars.size()),

2640 filter_(std::move(filter)),

2641 synchronized_sum_(std::numeric_limits<int64_t>::min()),

2642 delta_sum_(std::numeric_limits<int64_t>::min()),

2643 incremental_(false) {}

2644 ~SumObjectiveFilter() override {}

2645 bool Accept(const Assignment* delta, const Assignment* deltadelta,

2646 int64_t objective_min, int64_t objective_max) override {

2647 if (delta == nullptr) return false;

2648 if (deltadelta->Empty()) {

2649 if (incremental_) {

2650 for (int i = 0; i < primary_vars_size_; ++i) {

2651 delta_costs_[i] = synchronized_costs_[i];

2652 }

2653 }

2654 incremental_ = false;

2655 delta_sum_ = CapAdd(synchronized_sum_, CostOfChanges(delta, false));

2656 } else {

2657 if (incremental_) {

2658 delta_sum_ = CapAdd(delta_sum_, CostOfChanges(deltadelta, true));

2659 } else {

2660 delta_sum_ = CapAdd(synchronized_sum_, CostOfChanges(delta, true));

2661 }

2662 incremental_ = true;

2663 }

2664 return filter_(delta_sum_, objective_min, objective_max);

2665 }

2666

2667

2668 virtual int64_t CostOfSynchronizedVariable(int64_t index) = 0;

2669

2670 virtual int64_t CostOfChanges(const Assignment* changes,

2671 bool incremental) = 0;

2672 bool IsIncremental() const override { return true; }

2673

2674 std::string DebugString() const override { return "SumObjectiveFilter"; }

2675

2676 int64_t GetSynchronizedObjectiveValue() const override {

2677 return synchronized_sum_;

2678 }

2679 int64_t GetAcceptedObjectiveValue() const override { return delta_sum_; }

2680

2681 protected:

2682 const int primary_vars_size_;

2683 std::vector<int64_t> synchronized_costs_;

2684 std::vector<int64_t> delta_costs_;

2685 Filter filter_;

2686 int64_t synchronized_sum_;

2687 int64_t delta_sum_;

2688 bool incremental_;

2689

2690 private:

2691 void OnSynchronize(const Assignment*) override {

2692 synchronized_sum_ = 0;

2693 for (int i = 0; i < primary_vars_size_; ++i) {

2694 const int64_t cost = CostOfSynchronizedVariable(i);

2695 synchronized_costs_[i] = cost;

2696 delta_costs_[i] = cost;

2697 synchronized_sum_ = CapAdd(synchronized_sum_, cost);

2698 }

2699 delta_sum_ = synchronized_sum_;

2700 incremental_ = false;

2701 }

2702};

2703

2704template <typename Filter>

2705class BinaryObjectiveFilter : public SumObjectiveFilter<Filter> {

2706 public:

2707 BinaryObjectiveFilter(const std::vector<IntVar*>& vars,

2708 Solver::IndexEvaluator2 value_evaluator, Filter filter)

2709 : SumObjectiveFilter<Filter>(vars, std::move(filter)),

2710 value_evaluator_(std::move(value_evaluator)) {}

2711 ~BinaryObjectiveFilter() override {}

2712 int64_t CostOfSynchronizedVariable(int64_t index) override {

2713 return IntVarLocalSearchFilter::IsVarSynced(index)

2714 ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index))

2715 : 0;

2716 }

2717 int64_t CostOfChanges(const Assignment* changes, bool incremental) override {

2718 int64_t total_cost = 0;

2719 const Assignment::IntContainer& container = changes->IntVarContainer();

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

2721 IntVar* const var = new_element.Var();

2722 int64_t index = -1;

2723 if (this->FindIndex(var, &index)) {

2724 total_cost = CapSub(total_cost, this->delta_costs_[index]);

2725 int64_t new_cost = 0LL;

2726 if (new_element.Activated()) {

2727 new_cost = value_evaluator_(index, new_element.Value());

2728 } else if (var->Bound()) {

2729 new_cost = value_evaluator_(index, var->Min());

2730 }

2731 total_cost = CapAdd(total_cost, new_cost);

2732 if (incremental) {

2733 this->delta_costs_[index] = new_cost;

2734 }

2735 }

2736 }

2737 return total_cost;

2738 }

2739

2740 private:

2741 Solver::IndexEvaluator2 value_evaluator_;

2742};

2743

2744template <typename Filter>

2745class TernaryObjectiveFilter : public SumObjectiveFilter<Filter> {

2746 public:

2747 TernaryObjectiveFilter(const std::vector<IntVar*>& vars,

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

2749 Solver::IndexEvaluator3 value_evaluator, Filter filter)

2750 : SumObjectiveFilter<Filter>(vars, std::move(filter)),

2751 secondary_vars_offset_(vars.size()),

2752 secondary_values_(vars.size(), -1),

2753 value_evaluator_(std::move(value_evaluator)) {

2754 IntVarLocalSearchFilter::AddVars(secondary_vars);

2755 CHECK_GE(IntVarLocalSearchFilter::Size(), 0);

2756 }

2757 ~TernaryObjectiveFilter() override {}

2758 int64_t CostOfSynchronizedVariable(int64_t index) override {

2759 DCHECK_LT(index, secondary_vars_offset_);

2760 return IntVarLocalSearchFilter::IsVarSynced(index)

2761 ? value_evaluator_(index, IntVarLocalSearchFilter::Value(index),

2762 IntVarLocalSearchFilter::Value(

2763 index + secondary_vars_offset_))

2764 : 0;

2765 }

2766 int64_t CostOfChanges(const Assignment* changes, bool incremental) override {

2767 int64_t total_cost = 0;

2768 const Assignment::IntContainer& container = changes->IntVarContainer();

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

2770 IntVar* const var = new_element.Var();

2771 int64_t index = -1;

2772 if (this->FindIndex(var, &index) && index < secondary_vars_offset_) {

2773 secondary_values_[index] = -1;

2774 }

2775 }

2776

2777

2778

2779 const int max_secondary_index = 2 * secondary_vars_offset_;

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

2781 IntVar* const var = new_element.Var();

2782 int64_t index = -1;

2783 if (new_element.Activated() && this->FindIndex(var, &index) &&

2784 index >= secondary_vars_offset_ &&

2785

2786 index < max_secondary_index) {

2787 secondary_values_[index - secondary_vars_offset_] = new_element.Value();

2788 }

2789 }

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

2791 IntVar* const var = new_element.Var();

2792 int64_t index = -1;

2793 if (this->FindIndex(var, &index) && index < secondary_vars_offset_) {

2794 total_cost = CapSub(total_cost, this->delta_costs_[index]);

2795 int64_t new_cost = 0LL;

2796 if (new_element.Activated()) {

2797 new_cost = value_evaluator_(index, new_element.Value(),

2798 secondary_values_[index]);

2799 } else if (var->Bound() &&

2800 IntVarLocalSearchFilter::Var(index + secondary_vars_offset_)

2801 ->Bound()) {

2802 new_cost = value_evaluator_(

2803 index, var->Min(),

2804 IntVarLocalSearchFilter::Var(index + secondary_vars_offset_)

2805 ->Min());

2806 }

2807 total_cost = CapAdd(total_cost, new_cost);

2808 if (incremental) {

2809 this->delta_costs_[index] = new_cost;

2810 }

2811 }

2812 }

2813 return total_cost;

2814 }

2815

2816 private:

2817 int secondary_vars_offset_;

2818 std::vector<int64_t> secondary_values_;

2819 Solver::IndexEvaluator3 value_evaluator_;

2820};

2821}

2822

2826 switch (filter_enum) {

2828 auto filter = [](int64_t value, int64_t, int64_t max_value) {

2829 return value <= max_value;

2830 };

2831 return RevAlloc(new BinaryObjectiveFilter<decltype(filter)>(

2832 vars, std::move(values), std::move(filter)));

2833 }

2835 auto filter = [](int64_t value, int64_t min_value, int64_t) {

2836 return value >= min_value;

2837 };

2838 return RevAlloc(new BinaryObjectiveFilter<decltype(filter)>(

2839 vars, std::move(values), std::move(filter)));

2840 }

2842 auto filter = [](int64_t value, int64_t min_value, int64_t max_value) {

2843 return min_value <= value && value <= max_value;

2844 };

2845 return RevAlloc(new BinaryObjectiveFilter<decltype(filter)>(

2846 vars, std::move(values), std::move(filter)));

2847 }

2848 default: {

2849 LOG(ERROR) << "Unknown local search filter enum value";

2850 return nullptr;

2851 }

2852 }

2853}

2854

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

2859 switch (filter_enum) {

2861 auto filter = [](int64_t value, int64_t, int64_t max_value) {

2862 return value <= max_value;

2863 };

2864 return RevAlloc(new TernaryObjectiveFilter<decltype(filter)>(

2865 vars, secondary_vars, std::move(values), std::move(filter)));

2866 }

2868 auto filter = [](int64_t value, int64_t min_value, int64_t) {

2869 return value >= min_value;

2870 };

2871 return RevAlloc(new TernaryObjectiveFilter<decltype(filter)>(

2872 vars, secondary_vars, std::move(values), std::move(filter)));

2873 }

2875 auto filter = [](int64_t value, int64_t min_value, int64_t max_value) {

2876 return min_value <= value && value <= max_value;

2877 };

2878 return RevAlloc(new TernaryObjectiveFilter<decltype(filter)>(

2879 vars, secondary_vars, std::move(values), std::move(filter)));

2880 }

2881 default: {

2882 LOG(ERROR) << "Unknown local search filter enum value";

2883 return nullptr;

2884 }

2885 }

2886}

2887

2889 DCHECK_GE(num_nodes, num_nodes_);

2890 DCHECK(!graph_was_built_);

2891 graph_was_built_ = true;

2892 std::sort(arcs_.begin(), arcs_.end());

2893 arcs_of_node_.clear();

2894 NodeId prev_tail(-1);

2895 for (int a = 0; a < arcs_.size(); ++a) {

2896 const NodeId tail = arcs_[a].tail;

2897 if (tail != prev_tail) {

2898 prev_tail = tail;

2899 arcs_of_node_.resize(tail.value() + 1, a);

2900 }

2901 }

2902 num_nodes_ = std::max(num_nodes_, num_nodes);

2903 arcs_of_node_.resize(num_nodes_ + 1, arcs_.size());

2904 DCHECK(!HasDirectedCycle()) << "Graph has a directed cycle";

2905}

2906

2907bool SubDagComputer::HasDirectedCycle() const {

2908 DCHECK(graph_was_built_);

2911

2912

2913 struct DFSEvent {

2915 bool to_open;

2916 };

2917 std::vector<DFSEvent> event_stack;

2918

2919 for (NodeId node(0); node.value() < num_nodes_; ++node) {

2920 if (node_was_visited[node]) continue;

2921 event_stack.push_back({node, true});

2922 while (!event_stack.empty()) {

2923 const auto [node, to_open] = event_stack.back();

2924 event_stack.pop_back();

2925 if (node_was_visited[node]) continue;

2926 if (to_open) {

2927 if (node_is_open[node]) return true;

2928 node_is_open[node] = true;

2929 event_stack.push_back({node, false});

2930 for (int a = arcs_of_node_[node];

2931 a < arcs_of_node_[NodeId(node.value() + 1)]; ++a) {

2932 const NodeId head = arcs_[a].head;

2933 if (node_was_visited[head]) continue;

2934 event_stack.push_back({head, true});

2935 }

2936 } else {

2937 node_was_visited[node] = true;

2938 node_is_open[node] = false;

2939 }

2940 }

2941 }

2942 return false;

2943}

2944

2945const std::vector<SubDagComputer::ArcId>&

2947 DCHECK_LT(node.value(), num_nodes_);

2948 DCHECK(graph_was_built_);

2949 if (indegree_of_node_.size() < num_nodes_) {

2950 indegree_of_node_.resize(num_nodes_, 0);

2951 }

2952

2953 nodes_to_visit_.clear();

2954 nodes_to_visit_.push_back(node);

2955 while (!nodes_to_visit_.empty()) {

2956 const NodeId node = nodes_to_visit_.back();

2957 nodes_to_visit_.pop_back();

2958 const NodeId next(node.value() + 1);

2959 for (int a = arcs_of_node_[node]; a < arcs_of_node_[next]; ++a) {

2960 const NodeId head = arcs_[a].head;

2961 if (indegree_of_node_[head] == 0) {

2962 nodes_to_visit_.push_back(head);

2963 }

2964 ++indegree_of_node_[head];

2965 }

2966 }

2967

2968 sorted_arcs_.clear();

2969 nodes_to_visit_.push_back(node);

2970 while (!nodes_to_visit_.empty()) {

2971 const NodeId node = nodes_to_visit_.back();

2972 nodes_to_visit_.pop_back();

2973 const NodeId next(node.value() + 1);

2974 for (int a = arcs_of_node_[node]; a < arcs_of_node_[next]; ++a) {

2975 const NodeId head = arcs_[a].head;

2976 --indegree_of_node_[head];

2977 if (indegree_of_node_[head] == 0) {

2978 nodes_to_visit_.push_back(head);

2979 }

2980 sorted_arcs_.push_back(arcs_[a].arc_id);

2981 }

2982 }

2983

2984 DCHECK(absl::c_all_of(indegree_of_node_, [](int x) { return x == 0; }));

2985 return sorted_arcs_;

2986}

2987

2990 int64_t relaxed_max) {

2991 DCHECK(state_domains_are_all_nonempty_);

2992 DCHECK_LE(relaxed_min, relaxed_max);

2993 relaxed_domains_.push_back({relaxed_min, relaxed_max});

2994 current_domains_.push_back({relaxed_min, relaxed_max});

2995 domain_is_trailed_.push_back(false);

2997}

2998

3001 return {this, domain_id};

3002}

3003

3005 int64_t min, int64_t max) {

3007 return {this, domain_id};

3008}

3009

3013

3015 DCHECK(state_domains_are_all_nonempty_);

3016 if (!state_has_relaxed_domains_) {

3017 trailed_num_committed_empty_domains_ = num_committed_empty_domains_;

3018 }

3019 state_has_relaxed_domains_ = true;

3020 if (!domain_is_trailed_[domain_id]) {

3021 domain_is_trailed_[domain_id] = true;

3022 trailed_domains_.push_back({current_domains_[domain_id], domain_id});

3023 if (IntersectionIsEmpty(relaxed_domains_[domain_id],

3024 current_domains_[domain_id])) {

3025 DCHECK_GT(num_committed_empty_domains_, 0);

3026 --num_committed_empty_domains_;

3027 }

3028 current_domains_[domain_id] = relaxed_domains_[domain_id];

3029 return true;

3030 }

3031 return false;

3032}

3033

3035 DCHECK(state_domains_are_all_nonempty_);

3036 return current_domains_[domain_id].min;

3037}

3038

3040 DCHECK(state_domains_are_all_nonempty_);

3041 return current_domains_[domain_id].max;

3042}

3043

3045 int64_t min_value) {

3046 DCHECK(state_domains_are_all_nonempty_);

3047 DCHECK(domain_is_trailed_[domain_id]);

3048 VariableDomain& domain = current_domains_[domain_id];

3049 if (domain.max < min_value) {

3050 state_domains_are_all_nonempty_ = false;

3051 }

3052 domain.min = std::max(domain.min, min_value);

3053 return state_domains_are_all_nonempty_;

3054}

3055

3057 int64_t max_value) {

3058 DCHECK(state_domains_are_all_nonempty_);

3059 DCHECK(domain_is_trailed_[domain_id]);

3060 VariableDomain& domain = current_domains_[domain_id];

3061 if (domain.min > max_value) {

3062 state_domains_are_all_nonempty_ = false;

3063 }

3064 domain.max = std::min(domain.max, max_value);

3065 return state_domains_are_all_nonempty_;

3066}

3067

3069 int64_t min, int64_t max) {

3070 DCHECK(state_domains_are_all_nonempty_);

3071 DCHECK(!domain_is_trailed_[domain_id]);

3072 const bool domain_was_empty = IntersectionIsEmpty(

3073 relaxed_domains_[domain_id], current_domains_[domain_id]);

3074 relaxed_domains_[domain_id] = {min, max};

3075 const bool domain_is_empty =

3076 IntersectionIsEmpty({min, max}, current_domains_[domain_id]);

3077

3078 if (!domain_was_empty && domain_is_empty) {

3079 num_committed_empty_domains_++;

3080 } else if (domain_was_empty && !domain_is_empty) {

3081 num_committed_empty_domains_--;

3082 }

3083}

3084

3085

3086

3087

3090

3091 state_has_relaxed_domains_ = false;

3092 trailed_domains_.clear();

3093 domain_is_trailed_.assign(domain_is_trailed_.size(), false);

3094

3095 for (Constraint* constraint : trailed_constraints_) {

3096 constraint->Commit();

3097 }

3098 trailed_constraints_.clear();

3099}

3100

3102

3103 for (const auto& [domain, id] : trailed_domains_) {

3104 DCHECK(domain_is_trailed_[id]);

3105 current_domains_[id] = domain;

3106 }

3107 trailed_domains_.clear();

3108 state_has_relaxed_domains_ = false;

3109 domain_is_trailed_.assign(domain_is_trailed_.size(), false);

3110 state_domains_are_all_nonempty_ = true;

3111 num_committed_empty_domains_ = trailed_num_committed_empty_domains_;

3112

3113 for (Constraint* constraint : trailed_constraints_) {

3114 constraint->Revert();

3115 }

3116 trailed_constraints_.clear();

3117}

3118

3119using NodeId = SubDagComputer::NodeId;

3120NodeId LocalSearchState::DependencyGraph::GetOrCreateNodeOfDomainId(

3122 if (domain_id.value() >= dag_node_of_domain_.size()) {

3123 dag_node_of_domain_.resize(domain_id.value() + 1, NodeId(0));

3124 }

3125 if (dag_node_of_domain_[domain_id] == NodeId(0)) {

3126 dag_node_of_domain_[domain_id] = NodeId(num_dag_nodes_++);

3127 }

3128 return dag_node_of_domain_[domain_id];

3129}

3130

3131NodeId LocalSearchState::DependencyGraph::GetOrCreateNodeOfConstraintId(

3132 ConstraintId constraint_id) {

3133 if (constraint_id.value() >= dag_node_of_constraint_.size()) {

3134 dag_node_of_constraint_.resize(constraint_id.value() + 1, NodeId(0));

3135 }

3136 if (dag_node_of_constraint_[constraint_id] == NodeId(0)) {

3137 dag_node_of_constraint_[constraint_id] = NodeId(num_dag_nodes_++);

3138 }

3139 return dag_node_of_constraint_[constraint_id];

3140}

3141

3142void LocalSearchState::DependencyGraph::AddDomainsConstraintDependencies(

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

3144 ConstraintId constraint_id) {

3145 const NodeId cnode = GetOrCreateNodeOfConstraintId(constraint_id);

3146 for (int i = 0; i < domain_ids.size(); ++i) {

3147 const NodeId dnode = GetOrCreateNodeOfDomainId(domain_ids[i]);

3148 dag_.AddArc(dnode, cnode);

3149 dependency_of_dag_arc_.push_back({.domain_id = domain_ids[i],

3150 .input_index = i,

3151 .constraint_id = constraint_id});

3152 }

3153}

3154

3155void LocalSearchState::DependencyGraph::AddConstraintDomainDependency(

3157 const NodeId cnode = GetOrCreateNodeOfConstraintId(constraint_id);

3158 const NodeId dnode = GetOrCreateNodeOfDomainId(domain_id);

3159 dag_.AddArc(cnode, dnode);

3160 dependency_of_dag_arc_.push_back({.domain_id = domain_id,

3161 .input_index = -1,

3162 .constraint_id = constraint_id});

3163}

3164

3165using ArcId = SubDagComputer::ArcId;

3166const std::vector<LocalSearchState::DependencyGraph::Dependency>&

3167LocalSearchState::DependencyGraph::ComputeSortedDependencies(

3169 sorted_dependencies_.clear();

3170 const NodeId node = dag_node_of_domain_[domain_id];

3171 for (const ArcId a : dag_.ComputeSortedSubDagArcs(node)) {

3172 if (dependency_of_dag_arc_[a].input_index == -1) continue;

3173 sorted_dependencies_.push_back(dependency_of_dag_arc_[a]);

3174 }

3175 return sorted_dependencies_;

3176}

3177

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

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

3182 DCHECK_EQ(input_domain_ids.size(), input_weights.size());

3183

3184 const ConstraintId constraint_id(constraints_.size());

3185 dependency_graph_.AddDomainsConstraintDependencies(input_domain_ids,

3186 constraint_id);

3187 dependency_graph_.AddConstraintDomainDependency(constraint_id,

3188 output_domain_id);

3189

3190 auto constraint = std::make_unique<WeightedSum>(

3191 this, input_domain_ids, input_weights, input_offset, output_domain_id);

3192 constraints_.push_back(std::move(constraint));

3193}

3194

3195void LocalSearchState::DependencyGraph::BuildDependencyDAG(int num_domains) {

3196 dag_.BuildGraph(num_dag_nodes_);

3197

3198 const int num_assigned_nodes = dag_node_of_domain_.size();

3199 DCHECK_GE(num_domains, num_assigned_nodes);

3200 num_domains = std::max(num_domains, num_assigned_nodes);

3201 dag_node_of_domain_.resize(num_domains, NodeId(0));

3202}

3203

3205 triggers_.clear();

3206 triggers_of_domain_.clear();

3207 const int num_domains = current_domains_.size();

3208 dependency_graph_.BuildDependencyDAG(num_domains);

3209 for (int vid = 0; vid < num_domains; ++vid) {

3210 triggers_of_domain_.push_back(triggers_.size());

3211 for (const auto& [domain_id, input_index, constraint_id] :

3212 dependency_graph_.ComputeSortedDependencies(VariableDomainId(vid))) {

3213 triggers_.push_back({.constraint = constraints_[constraint_id].get(),

3214 .input_index = input_index});

3215 }

3216 }

3217 triggers_of_domain_.push_back(triggers_.size());

3218}

3219

3220LocalSearchState::WeightedSum::WeightedSum(

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

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

3225 : output_(output), state_(state) {

3226

3227

3228 invariants_.num_neg_inf = 0;

3229 invariants_.num_pos_inf = 0;

3230 invariants_.wsum_mins = input_offset;

3231 invariants_.wsum_maxs = input_offset;

3232 for (int i = 0; i < input_domain_ids.size(); ++i) {

3234 const int64_t weight = input_weights[i];

3237 inputs_.push_back({.min = min,

3238 .max = max,

3239 .committed_min = min,

3240 .committed_max = max,

3241 .weight = weight,

3242 .domain = domain_id,

3243 .is_trailed = false});

3244

3245 if (weight > 0) {

3247 ++invariants_.num_neg_inf;

3248 } else {

3249 invariants_.wsum_mins =

3250 CapAdd(invariants_.wsum_mins, CapProd(weight, min));

3251 }

3253 ++invariants_.num_pos_inf;

3254 } else {

3255 invariants_.wsum_maxs =

3256 CapAdd(invariants_.wsum_maxs, CapProd(weight, max));

3257 }

3258 } else {

3260 ++invariants_.num_pos_inf;

3261 } else {

3262 invariants_.wsum_maxs =

3263 CapAdd(invariants_.wsum_maxs, CapProd(weight, min));

3264 }

3266 ++invariants_.num_neg_inf;

3267 } else {

3268 invariants_.wsum_mins =

3269 CapAdd(invariants_.wsum_mins, CapProd(weight, max));

3270 }

3271 }

3272 }

3273 committed_invariants_ = invariants_;

3274}

3275

3276LocalSearchState::VariableDomain LocalSearchState::WeightedSum::Propagate(

3277 int input_index) {

3278 if (!constraint_is_trailed_) {

3279 constraint_is_trailed_ = true;

3280 state_->TrailConstraint(this);

3281 }

3282 WeightedVariable& input = inputs_[input_index];

3283 if (!input.is_trailed) {

3284 input.is_trailed = true;

3285 trailed_inputs_.push_back(&input);

3286 }

3287 const int64_t new_min = state_->VariableDomainMin(input.domain);

3288 const int64_t new_max = state_->VariableDomainMax(input.domain);

3289 const int64_t weight = input.weight;

3290 if (weight > 0) {

3291 if (input.min != new_min) {

3292

3294 --invariants_.num_neg_inf;

3295 } else {

3296 invariants_.wsum_mins =

3298 }

3299

3301 ++invariants_.num_neg_inf;

3302 } else {

3303 invariants_.wsum_mins =

3304 CapAdd(invariants_.wsum_mins, CapProd(weight, new_min));

3305 }

3306 input.min = new_min;

3307 }

3308 if (input.max != new_max) {

3309

3311 --invariants_.num_pos_inf;

3312 } else {

3313 invariants_.wsum_maxs =

3315 }

3316

3318 ++invariants_.num_pos_inf;

3319 } else {

3320 invariants_.wsum_maxs =

3321 CapAdd(invariants_.wsum_maxs, CapProd(weight, new_max));

3322 }

3323 input.max = new_max;

3324 }

3325 } else {

3326 if (input.min != new_min) {

3327

3329 --invariants_.num_pos_inf;

3330 } else {

3331 invariants_.wsum_maxs =

3333 }

3334

3336 ++invariants_.num_pos_inf;

3337 } else {

3338 invariants_.wsum_maxs =

3339 CapAdd(invariants_.wsum_maxs, CapProd(weight, new_min));

3340 }

3341 input.min = new_min;

3342 }

3343 if (input.max != new_max) {

3344

3346 --invariants_.num_neg_inf;

3347 } else {

3348 invariants_.wsum_mins =

3350 }

3351

3353 ++invariants_.num_neg_inf;

3354 } else {

3355 invariants_.wsum_mins =

3356 CapAdd(invariants_.wsum_mins, CapProd(weight, new_max));

3357 }

3358 input.max = new_max;

3359 }

3360 }

3361 return {invariants_.num_neg_inf == 0 ? invariants_.wsum_mins : kint64min,

3362 invariants_.num_pos_inf == 0 ? invariants_.wsum_maxs : kint64max};

3363}

3364

3365void LocalSearchState::WeightedSum::Commit() {

3366 committed_invariants_ = invariants_;

3367 constraint_is_trailed_ = false;

3368 for (WeightedVariable* wv : trailed_inputs_) wv->Commit();

3369 trailed_inputs_.clear();

3370}

3371

3372void LocalSearchState::WeightedSum::Revert() {

3373 invariants_ = committed_invariants_;

3374 constraint_is_trailed_ = false;

3375 for (WeightedVariable* wv : trailed_inputs_) wv->Revert();

3376 trailed_inputs_.clear();

3377}

3378

3381 for (int t = triggers_of_domain_[domain_id]; t < triggers_of_domain_[next_id];

3382 ++t) {

3383 const auto& [constraint, input_index] = triggers_[t];

3384 constraint->Propagate(input_index);

3386 }

3387}

3388

3391 for (int t = triggers_of_domain_[domain_id]; t < triggers_of_domain_[next_id];

3392 ++t) {

3393 const auto& [constraint, input_index] = triggers_[t];

3394 const auto [output_min, output_max] = constraint->Propagate(input_index);

3397 return false;

3398 }

3401 return false;

3402 }

3403 }

3404 return true;

3405}

3406

3407

3408

3410 public:

3412 std::string DebugString() const override { return "LocalSearchProfiler"; }

3414 operator_stats_.clear();

3415 filter_stats_per_context_.clear();

3416 last_operator_ = nullptr;

3417 }

3419

3420 UpdateTime();

3421 last_operator_ = nullptr;

3422 }

3423 template <typename Callback>

3426 if (db->seconds() == 0) continue;

3427 callback(db->name(), db->seconds());

3428 }

3429 }

3430

3431 template <typename Callback>

3433 std::vector<const LocalSearchOperator*> operators;

3434 for (const auto& stat : operator_stats_) {

3435 operators.push_back(stat.first);

3436 }

3437 std::sort(

3438 operators.begin(), operators.end(),

3440 return gtl::FindOrDie(operator_stats_, op1).neighbors >

3441 gtl::FindOrDie(operator_stats_, op2).neighbors;

3442 });

3444 const OperatorStats& stats = gtl::FindOrDie(operator_stats_, op);

3445 const std::string& label = op->DebugString();

3446

3447 if (label.empty() &&

3448 dynamic_cast<const CompoundOperator*>(op) != nullptr) {

3449 continue;

3450 }

3451 callback(label, stats.neighbors, stats.filtered_neighbors,

3452 stats.accepted_neighbors, stats.seconds,

3453 stats.make_next_neighbor_seconds, stats.accept_neighbor_seconds);

3454 }

3455 }

3456

3457 template <typename Callback>

3459 for (const auto& [context, filter_stats] : filter_stats_per_context_) {

3460 std::vector<const LocalSearchFilter*> filters;

3461 for (const auto& [filter, stats] : filter_stats) {

3462 filters.push_back(filter);

3463 }

3464 std::sort(

3465 filters.begin(), filters.end(),

3466 [filter_stats_ptr = &filter_stats](const LocalSearchFilter* filter1,

3468 return gtl::FindOrDie(*filter_stats_ptr, filter1).calls >

3469 gtl::FindOrDie(*filter_stats_ptr, filter2).calls;

3470 });

3472 const FilterStats& stats = gtl::FindOrDie(filter_stats, filter);

3473 callback(context, filter->DebugString(), stats.calls, stats.rejects,

3474 stats.seconds);

3475 }

3476 }

3477 }

3481 [&statistics_proto](absl::string_view name, double duration_seconds) {

3483 first_solution_statistics =

3485 first_solution_statistics->set_strategy(name);

3487 });

3489 [&statistics_proto](

3490 absl::string_view name, int64_t num_neighbors,

3491 int64_t num_filtered_neighbors, int64_t num_accepted_neighbors,

3492 double duration_seconds, double make_next_neighbor_duration_seconds,

3493 double accept_neighbor_duration_seconds) {

3495 local_search_operator_statistics =

3498 local_search_operator_statistics->set_num_neighbors(num_neighbors);

3500 num_filtered_neighbors);

3502 num_accepted_neighbors);

3504 duration_seconds);

3505 local_search_operator_statistics

3507 make_next_neighbor_duration_seconds);

3508 local_search_operator_statistics

3510 accept_neighbor_duration_seconds);

3511 });

3513 absl::string_view context,

3514 absl::string_view name,

3515 int64_t num_calls, int64_t num_rejects,

3516 double duration_seconds) {

3518 local_search_filter_statistics =

3521 local_search_filter_statistics->set_num_calls(num_calls);

3522 local_search_filter_statistics->set_num_rejects(num_rejects);

3525 num_rejects / duration_seconds);

3526 local_search_filter_statistics->set_context(context);

3527 });

3530 solver()->filtered_neighbors());

3532 solver()->accepted_neighbors());

3533 return statistics_proto;

3534 }

3536 std::string overview;

3537 size_t max_name_size = 0;

3539 [&max_name_size](absl::string_view name, double) {

3540 max_name_size = std::max(max_name_size, name.length());

3541 });

3542 if (max_name_size > 0) {

3543 absl::StrAppendFormat(&overview,

3544 "First solution statistics:\n%*s | Time (s)\n",

3545 max_name_size, "");

3547 [&overview, max_name_size](absl::string_view name,

3548 double duration_seconds) {

3549 absl::StrAppendFormat(&overview, "%*s | %7.2g\n", max_name_size,

3550 name, duration_seconds);

3551 });

3552 }

3553 max_name_size = 0;

3555 [&max_name_size](absl::string_view name, int64_t, int64_t, int64_t,

3556 double, double, double) {

3557 max_name_size = std::max(max_name_size, name.length());

3558 });

3559 if (max_name_size > 0) {

3560 absl::StrAppendFormat(

3561 &overview,

3562 "Local search operator statistics:\n%*s | Neighbors | Filtered "

3563 "| Accepted | Time (s)\n",

3564 max_name_size, "");

3565 OperatorStats total_stats;

3567 [&overview, &total_stats, max_name_size](

3568 absl::string_view name, int64_t num_neighbors,

3569 int64_t num_filtered_neighbors, int64_t num_accepted_neighbors,

3570 double duration_seconds,

3571 double ,

3572 double ) {

3573

3574

3575 absl::StrAppendFormat(

3576 &overview, "%*s | %9ld | %8ld | %8ld | %7.2g\n", max_name_size,

3577 name, num_neighbors, num_filtered_neighbors,

3578 num_accepted_neighbors, duration_seconds);

3579 total_stats.neighbors += num_neighbors;

3580 total_stats.filtered_neighbors += num_filtered_neighbors;

3581 total_stats.accepted_neighbors += num_accepted_neighbors;

3582 total_stats.seconds += duration_seconds;

3583 });

3584 absl::StrAppendFormat(

3585 &overview, "%*s | %9ld | %8ld | %8ld | %7.2g\n", max_name_size,

3586 "Total", total_stats.neighbors, total_stats.filtered_neighbors,

3587 total_stats.accepted_neighbors, total_stats.seconds);

3588 }

3589 max_name_size = 0;

3591 [&max_name_size](absl::string_view, absl::string_view name, int64_t,

3592 int64_t, double) {

3593 max_name_size = std::max(max_name_size, name.length());

3594 });

3595 if (max_name_size > 0) {

3596 std::optional<std::string> filter_context;

3597 FilterStats total_filter_stats;

3599 [&overview, &filter_context, &total_filter_stats, max_name_size](

3600 const std::string& context, const std::string& name,

3601 int64_t num_calls, int64_t num_rejects, double duration_seconds) {

3602 if (!filter_context.has_value() ||

3603 filter_context.value() != context) {

3604 if (filter_context.has_value()) {

3605 absl::StrAppendFormat(

3606 &overview, "%*s | %9ld | %9ld | %7.2g | %7.2g\n",

3607 max_name_size, "Total", total_filter_stats.calls,

3608 total_filter_stats.rejects, total_filter_stats.seconds,

3609 total_filter_stats.rejects / total_filter_stats.seconds);

3610 total_filter_stats = {};

3611 }

3612 filter_context = context;

3613 absl::StrAppendFormat(

3614 &overview,

3615 "Local search filter statistics%s:\n%*s | Calls | "

3616 " Rejects | Time (s) | Rejects/s\n",

3617 context.empty() ? "" : " (" + context + ")", max_name_size,

3618 "");

3619 }

3620 absl::StrAppendFormat(

3621 &overview, "%*s | %9ld | %9ld | %7.2g | %7.2g\n",

3622 max_name_size, name, num_calls, num_rejects, duration_seconds,

3623 num_rejects / duration_seconds);

3624 total_filter_stats.calls += num_calls;

3625 total_filter_stats.rejects += num_rejects;

3626 total_filter_stats.seconds += duration_seconds;

3627 });

3628 absl::StrAppendFormat(

3629 &overview, "%*s | %9ld | %9ld | %7.2g | %7.2g\n", max_name_size,

3630 "Total", total_filter_stats.calls, total_filter_stats.rejects,

3631 total_filter_stats.seconds,

3632 total_filter_stats.rejects / total_filter_stats.seconds);

3633 }

3634 return overview;

3635 }

3639 if (last_operator_ != op->Self()) {

3640 UpdateTime();

3641 last_operator_ = op->Self();

3642 }

3643 make_next_neighbor_timer_.Start();

3644 }

3647

3648

3649 if (!make_next_neighbor_timer_.IsRunning()) return;

3650 make_next_neighbor_timer_.Stop();

3651 operator_stats_[op->Self()].make_next_neighbor_seconds +=

3652 make_next_neighbor_timer_.Get();

3653 if (neighbor_found) {

3654 operator_stats_[op->Self()].neighbors++;

3655 }

3656 }

3659 bool neighbor_found) override {

3660 if (neighbor_found) {

3661 operator_stats_[op->Self()].filtered_neighbors++;

3662 }

3663 }

3665 accept_neighbor_timer_.Start();

3666 }

3668 bool neighbor_found) override {

3669 accept_neighbor_timer_.Stop();

3670 operator_stats_[op->Self()].accept_neighbor_seconds +=

3671 accept_neighbor_timer_.Get();

3672 if (neighbor_found) {

3673 operator_stats_[op->Self()].accepted_neighbors++;

3674 }

3675 }

3677 FilterStats& filter_stats =

3678 filter_stats_per_context_[solver()->context()][filter];

3679 filter_stats.calls++;

3680 filter_timer_.Start();

3681 }

3683 filter_timer_.Stop();

3684 auto& stats = filter_stats_per_context_[solver()->context()][filter];

3685 stats.seconds += filter_timer_.Get();

3686 if (reject) {

3687 stats.rejects++;

3688 }

3689 }

3692 profiled_decision_builders_.push_back(profiled_db);

3693 }

3694 bool IsActive() const override { return true; }

3696

3697 private:

3698 void UpdateTime() {

3699 if (last_operator_ != nullptr) {

3700 timer_.Stop();

3701 operator_stats_[last_operator_].seconds += timer_.Get();

3702 }

3703 timer_.Start();

3704 }

3705

3706 struct OperatorStats {

3707 int64_t neighbors = 0;

3708 int64_t filtered_neighbors = 0;

3709 int64_t accepted_neighbors = 0;

3710 double seconds = 0;

3711 double make_next_neighbor_seconds = 0;

3712 double accept_neighbor_seconds = 0;

3713 };

3714

3715 struct FilterStats {

3716 int64_t calls = 0;

3717 int64_t rejects = 0;

3718 double seconds = 0;

3719 };

3720 WallTimer timer_;

3721 WallTimer make_next_neighbor_timer_;

3722 WallTimer accept_neighbor_timer_;

3723 WallTimer filter_timer_;

3724 const LocalSearchOperator* last_operator_ = nullptr;

3725 absl::flat_hash_map<const LocalSearchOperator*, OperatorStats>

3726 operator_stats_;

3727 absl::flat_hash_map<

3728 std::string, absl::flat_hash_map<const LocalSearchFilter*, FilterStats>>

3729 filter_stats_per_context_;

3730

3731 std::vector<ProfiledDecisionBuilder*> profiled_decision_builders_;

3732};

3733

3739 local_search_profiler_->AddFirstSolutionProfiledDecisionBuilder(

3740 profiled_db);

3741 return profiled_db;

3742 }

3743 return db;

3744}

3745

3749

3753 }

3754 return nullptr;

3755}

3756

3758

3760 if (local_search_profiler_ != nullptr) {

3761 return local_search_profiler_->PrintOverview();

3762 }

3763 return "";

3764}

3765

3767 if (local_search_profiler_ != nullptr) {

3768 return local_search_profiler_->ExportToLocalSearchStatistics();

3769 }

3771}

3772

3773void LocalSearchFilterManager::FindIncrementalEventEnd() {

3774 const int num_events = events_.size();

3775 incremental_events_end_ = num_events;

3776 int last_priority = -1;

3777 for (int e = num_events - 1; e >= 0; --e) {

3778 const auto& [filter, event_type, priority] = events_[e];

3779 if (priority != last_priority) {

3780 incremental_events_end_ = e + 1;

3781 last_priority = priority;

3782 }

3783 if (filter->IsIncremental()) break;

3784 }

3785}

3786

3788 std::vector<LocalSearchFilter*> filters)

3789 : synchronized_value_(std::numeric_limits<int64_t>::min()),

3790 accepted_value_(std::numeric_limits<int64_t>::min()) {

3791 events_.reserve(2 * filters.size());

3792 int priority = 0;

3795 }

3798 }

3799 FindIncrementalEventEnd();

3800}

3801

3803 std::vector<FilterEvent> filter_events)

3804 : events_(std::move(filter_events)),

3805 synchronized_value_(std::numeric_limits<int64_t>::min()),

3806 accepted_value_(std::numeric_limits<int64_t>::min()) {

3807 std::sort(events_.begin(), events_.end(),

3809 return e1.priority < e2.priority;

3810 });

3811 FindIncrementalEventEnd();

3812}

3813

3814

3815

3817 for (int e = last_event_called_; e >= 0; --e) {

3818 const auto [filter, event_type, _priority] = events_[e];

3820 }

3821 last_event_called_ = -1;

3822}

3823

3824

3825

3826

3830 int64_t objective_min,

3831 int64_t objective_max) {

3833 accepted_value_ = 0;

3834 bool feasible = true;

3835 bool reordered = false;

3836 int events_end = events_.size();

3837 for (int e = 0; e < events_end; ++e) {

3838 last_event_called_ = e;

3839 const auto [filter, event_type, priority] = events_[e];

3840 switch (event_type) {

3842 if (!feasible && !filter->IsIncremental()) continue;

3843 if (monitor != nullptr) monitor->BeginFiltering(filter);

3844 const bool accept = filter->Accept(

3845 delta, deltadelta, CapSub(objective_min, accepted_value_),

3846 CapSub(objective_max, accepted_value_));

3847 feasible &= accept;

3848 if (monitor != nullptr) monitor->EndFiltering(filter, !accept);

3849 if (feasible) {

3850 accepted_value_ =

3851 CapAdd(accepted_value_, filter->GetAcceptedObjectiveValue());

3852

3853 feasible = accepted_value_ <= objective_max;

3854 }

3855 if (!feasible) {

3856 events_end = incremental_events_end_;

3857 if (!reordered) {

3858

3859

3860 reordered = true;

3861 int to_move = e - 1;

3862 if (to_move >= 0 && events_[to_move].filter == filter) --to_move;

3863 if (to_move >= 0 && events_[to_move].priority == priority) {

3864 std::rotate(events_.begin() + to_move,

3865 events_.begin() + to_move + 1,

3866 events_.begin() + e + 1);

3867 }

3868 }

3869 }

3870 break;

3871 }

3873 filter->Relax(delta, deltadelta);

3874 break;

3875 }

3876 default:

3877 LOG(FATAL) << "Unknown filter event type.";

3878 }

3879 }

3880 return feasible;

3881}

3882

3885

3886

3887

3888 const bool reset_to_assignment = delta == nullptr || delta->Empty();

3889

3890 for (auto [filter, event_type, unused_priority] : events_) {

3891 switch (event_type) {

3893 break;

3894 }

3896 if (reset_to_assignment) {

3897 filter->Reset();

3898 filter->Relax(assignment, nullptr);

3899 } else {

3900 filter->Relax(delta, nullptr);

3901 }

3902 break;

3903 }

3904 default:

3905 LOG(FATAL) << "Unknown filter event type.";

3906 }

3907 }

3908

3909

3910 synchronized_value_ = 0;

3911 for (auto [filter, event_type, _priority] : ::gtl::reversed_view(events_)) {

3912 switch (event_type) {

3914 filter->Synchronize(assignment, delta);

3915 synchronized_value_ = CapAdd(synchronized_value_,

3916 filter->GetSynchronizedObjectiveValue());

3917 break;

3918 }

3920 filter->Commit(assignment, delta);

3921 break;

3922 }

3923 default:

3924 LOG(FATAL) << "Unknown filter event type.";

3925 }

3926 }

3927}

3928

3929

3930

3932 public:

3941 std::string DebugString() const override { return "FindOneNeighbor"; }

3942

3943 private:

3945 int64_t objective_min, int64_t objective_max);

3946 void SynchronizeAll(Solver* solver);

3947

3949 IntVar* const objective_;

3950 std::unique_ptr<Assignment> reference_assignment_;

3951 std::unique_ptr<Assignment> last_synchronized_assignment_;

3952 Assignment* const filter_assignment_delta_;

3958 bool neighbor_found_;

3960 int64_t solutions_since_last_check_;

3961 int64_t check_period_;

3962 Assignment last_checked_assignment_;

3963 bool has_checked_assignment_ = false;

3964};

3965

3966

3967

3968

3969

3970

3971

3978 : assignment_(assignment),

3979 objective_(objective),

3980 reference_assignment_(new Assignment(assignment_)),

3981 filter_assignment_delta_(assignment->solver()->MakeAssignment()),

3982 pool_(pool),

3983 ls_operator_(ls_operator),

3984 sub_decision_builder_(sub_decision_builder),

3985 limit_(nullptr),

3986 original_limit_(limit),

3987 neighbor_found_(false),

3988 filter_manager_(filter_manager),

3989 solutions_since_last_check_(0),

3990 check_period_(

3991 assignment_->solver()->parameters().check_solution_period()),

3992 last_checked_assignment_(assignment) {

3993 CHECK(nullptr != assignment);

3994 CHECK(nullptr != ls_operator);

3995

3996 Solver* const solver = assignment_->solver();

3997

3998 if (nullptr == limit) {

4000 } else {

4002

4003

4004

4005 if (limit_->solutions() != 1) {

4006 VLOG(1) << "Disabling neighbor-check skipping outside of first accept.";

4007 check_period_ = 1;

4008 }

4009 }

4010

4011

4013 VLOG(1) << "Disabling neighbor-check skipping for LNS.";

4014 check_period_ = 1;

4015 }

4016

4017 if (!reference_assignment_->HasObjective()) {

4018 reference_assignment_->AddObjective(objective_);

4019 }

4020}

4021

4023

4024

4025 neighbor_found_ = false;

4026 last_synchronized_assignment_.reset();

4027}

4028

4030 CHECK(nullptr != solver);

4031

4032 if (original_limit_ != nullptr) {

4033 limit_->Copy(original_limit_);

4034 }

4035

4036 if (!last_checked_assignment_.HasObjective()) {

4037 last_checked_assignment_.AddObjective(assignment_->Objective());

4038 }

4039

4040 if (!neighbor_found_) {

4041

4042

4043

4044

4045

4046

4047 pool_->Initialize(assignment_);

4048 SynchronizeAll(solver);

4049 }

4050

4051 {

4052

4054 solver->MakeAssignment(reference_assignment_.get());

4055 int counter = 0;

4056

4058 if (sub_decision_builder_) {

4059 restore = solver->Compose(restore, sub_decision_builder_);

4060 }

4063 while (true) {

4064 if (!ls_operator_->HoldsDelta()) {

4066 }

4068 deltadelta->Clear();

4070 if (++counter >= absl::GetFlag(FLAGS_cp_local_search_sync_frequency) &&

4071 pool_->SyncNeeded(reference_assignment_.get())) {

4072

4073 counter = 0;

4074 SynchronizeAll(solver);

4075 }

4076

4077 bool has_neighbor = false;

4078 if (!limit_->Check()) {

4080 has_neighbor = ls_operator_->MakeNextNeighbor(delta, deltadelta);

4082 ls_operator_, has_neighbor, delta, deltadelta);

4083 }

4084

4085 if (has_neighbor && !solver->IsUncheckedSolutionLimitReached()) {

4086 solver->neighbors_ += 1;

4087

4088

4089

4090

4091

4093 const bool mh_filter =

4094 AcceptDelta(solver->ParentSearch(), delta, deltadelta);

4095 int64_t objective_min = std::numeric_limits<int64_t>::min();

4096 int64_t objective_max = std::numeric_limits<int64_t>::max();

4097 if (objective_) {

4098 objective_min = objective_->Min();

4099 objective_max = objective_->Max();

4100 }

4102 objective_min = std::max(objective_min, delta->ObjectiveMin());

4103 objective_max = std::min(objective_max, delta->ObjectiveMax());

4104 }

4105 const bool move_filter = FilterAccept(solver, delta, deltadelta,

4106 objective_min, objective_max);

4108 ls_operator_, mh_filter && move_filter);

4109 if (!mh_filter || !move_filter) {

4110 if (filter_manager_ != nullptr) filter_manager_->Revert();

4111 continue;

4112 }

4113 solver->filtered_neighbors_ += 1;

4117 }

4118 if (!assignment_->HasObjective()) {

4119 assignment_->AddObjective(delta->Objective());

4120 last_checked_assignment_.AddObjective(delta->Objective());

4121 }

4122 }

4123 assignment_copy->CopyIntersection(reference_assignment_.get());

4126 const bool check_solution = (solutions_since_last_check_ == 0) ||

4128

4130 if (has_checked_assignment_) solutions_since_last_check_++;

4131 if (solutions_since_last_check_ >= check_period_) {

4132 solutions_since_last_check_ = 0;

4133 }

4134 const bool accept = !check_solution ||

4138 accept);

4139 if (accept) {

4140 solver->accepted_neighbors_ += 1;

4141 if (check_solution) {

4143 ls_operator_->DebugString());

4144 assignment_->Store();

4145 last_checked_assignment_.CopyIntersection(assignment_);

4146 neighbor_found_ = true;

4147 has_checked_assignment_ = true;

4148 return nullptr;

4149 }

4151 ls_operator_->DebugString());

4152 assignment_->CopyIntersection(assignment_copy);

4153 assignment_->SetObjectiveValue(

4154 filter_manager_ ? filter_manager_->GetAcceptedObjectiveValue()

4155 : 0);

4156

4157

4158

4159

4161 solver->IncrementUncheckedSolutionCounter();

4162 pool_->RegisterNewSolution(assignment_);

4163 SynchronizeAll(solver);

4164

4165

4166 neighbor_found_ = true;

4167 } else {

4168 if (filter_manager_ != nullptr) filter_manager_->Revert();

4169 if (check_period_ > 1 && has_checked_assignment_) {

4170

4171

4172

4173

4174

4175 VLOG(1) << "Imperfect filtering detected, backtracking to last "

4176 "checked solution and checking all solutions.";

4177 check_period_ = 1;

4178 solutions_since_last_check_ = 0;

4179 pool_->RegisterNewSolution(&last_checked_assignment_);

4180 SynchronizeAll(solver);

4181 assignment_->CopyIntersection(&last_checked_assignment_);

4182 }

4183 }

4184 } else {

4185

4186

4187 last_synchronized_assignment_.reset();

4188 if (neighbor_found_) {

4189

4190

4191

4192

4193 if (last_checked_assignment_.ObjectiveValue() !=

4194 assignment_->ObjectiveValue()) {

4195

4196

4199 last_checked_assignment_.CopyIntersection(assignment_);

4200 has_checked_assignment_ = true;

4201 return nullptr;

4202 }

4204

4205

4206

4207 pool_->RegisterNewSolution(assignment_);

4208 SynchronizeAll(solver);

4209 } else {

4210 break;

4211 }

4212 }

4213 }

4214 }

4215

4216

4217

4218 last_synchronized_assignment_.reset();

4219 solver->Fail();

4220 return nullptr;

4221}

4222

4223bool FindOneNeighbor::FilterAccept(Solver* solver, Assignment* delta,

4225 int64_t objective_min,

4226 int64_t objective_max) {

4227 if (filter_manager_ == nullptr) return true;

4229 return filter_manager_->Accept(monitor, delta, deltadelta, objective_min,

4230 objective_max);

4231}

4232

4233namespace {

4234

4235template <typename Container>

4236void AddDeltaElements(const Container& old_container,

4237 const Container& new_container, Assignment* delta) {

4238 for (const auto& new_element : new_container.elements()) {

4239 const auto var = new_element.Var();

4240 const auto old_element_ptr = old_container.ElementPtrOrNull(var);

4241 if (old_element_ptr == nullptr || *old_element_ptr != new_element) {

4242 delta->FastAdd(var)->Copy(new_element);

4243 }

4244 }

4245}

4246

4247void MakeDelta(const Assignment* old_assignment,

4249 DCHECK_NE(delta, nullptr);

4250 delta->Clear();

4251 AddDeltaElements(old_assignment->IntVarContainer(),

4252 new_assignment->IntVarContainer(), delta);

4253 AddDeltaElements(old_assignment->IntervalVarContainer(),

4254 new_assignment->IntervalVarContainer(), delta);

4255 AddDeltaElements(old_assignment->SequenceVarContainer(),

4256 new_assignment->SequenceVarContainer(), delta);

4257}

4258}

4259

4260void FindOneNeighbor::SynchronizeAll(Solver* solver) {

4261 Assignment* const reference_assignment = reference_assignment_.get();

4262 pool_->GetNextSolution(reference_assignment);

4263 neighbor_found_ = false;

4264 limit_->Init();

4265 solver->GetLocalSearchMonitor()->BeginOperatorStart();

4266 ls_operator_->Start(reference_assignment);

4267 if (filter_manager_ != nullptr) {

4268 Assignment* delta = nullptr;

4269 if (last_synchronized_assignment_ == nullptr) {

4270 last_synchronized_assignment_ =

4271 std::make_unique<Assignment>(reference_assignment);

4272 } else {

4273 MakeDelta(last_synchronized_assignment_.get(), reference_assignment,

4274 filter_assignment_delta_);

4275 delta = filter_assignment_delta_;

4276 last_synchronized_assignment_->Copy(reference_assignment);

4277 }

4278 filter_manager_->Synchronize(reference_assignment_.get(), delta);

4279 }

4280 solver->GetLocalSearchMonitor()->EndOperatorStart();

4281}

4282

4283

4284

4286 public:

4293 solution_pool_(pool),

4300 return "LocalSearchPhaseParameters";

4301 }

4302

4307 return sub_decision_builder_;

4308 }

4311

4312 private:

4313 IntVar* const objective_;

4319};

4320

4325 ls_operator, sub_decision_builder,

4326 nullptr, nullptr);

4327}

4328

4333 ls_operator, sub_decision_builder,

4334 limit, nullptr);

4335}

4336

4342 ls_operator, sub_decision_builder,

4343 limit, filter_manager);

4344}

4345

4351 sub_decision_builder, nullptr, nullptr);

4352}

4353

4359 sub_decision_builder, limit, nullptr);

4360}

4361

4368 sub_decision_builder, limit,

4369 filter_manager));

4370}

4371

4372namespace {

4373

4374

4375

4376

4377

4378

4379

4380

4381

4382class NestedSolveDecision : public Decision {

4383 public:

4384

4385 enum StateType { DECISION_PENDING, DECISION_FAILED, DECISION_FOUND };

4386

4387 NestedSolveDecision(DecisionBuilder* absl_nonnull db, bool restore,

4388 const std::vector<SearchMonitor*>& monitors);

4389 NestedSolveDecision(DecisionBuilder* absl_nonnull db, bool restore);

4390 ~NestedSolveDecision() override {}

4391 void Apply(Solver* solver) override;

4392 void Refute(Solver* solver) override;

4393 std::string DebugString() const override { return "NestedSolveDecision"; }

4394 int state() const { return state_; }

4395

4396 private:

4397 DecisionBuilder* const db_;

4398 const bool restore_;

4399 const std::vector<SearchMonitor*> monitors_;

4400 int state_;

4401};

4402

4403NestedSolveDecision::NestedSolveDecision(

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

4406 : db_(db),

4407 restore_(restore),

4408 monitors_(monitors),

4409 state_(DECISION_PENDING) {}

4410

4411NestedSolveDecision::NestedSolveDecision(DecisionBuilder* absl_nonnull db,

4412 bool restore)

4413 : NestedSolveDecision(db, restore, {}) {}

4414

4415void NestedSolveDecision::Apply(Solver* const solver) {

4416 CHECK(nullptr != solver);

4417 if (restore_) {

4418 if (solver->Solve(db_, monitors_)) {

4419 solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FOUND));

4420 } else {

4421 solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FAILED));

4422 }

4423 } else {

4424 if (solver->SolveAndCommit(db_, monitors_)) {

4425 solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FOUND));

4426 } else {

4427 solver->SaveAndSetValue(&state_, static_cast<int>(DECISION_FAILED));

4428 }

4429 }

4430}

4431

4432void NestedSolveDecision::Refute(Solver* const) {}

4433}

4434

4435

4436

4437

4438

4439

4440

4441

4442

4443

4445 public:

4450

4451

4452 LocalSearch(const std::vector<IntVar*>& vars, IntVar* objective,

4457 LocalSearch(const std::vector<IntVar*>& vars, IntVar* objective,

4463 LocalSearch(const std::vector<SequenceVar*>& vars, IntVar* objective,

4470 std::string DebugString() const override { return "LocalSearch"; }

4471 void Accept(ModelVisitor* visitor) const override;

4472

4473 protected:

4474 void PushFirstSolutionDecision(DecisionBuilder* first_solution);

4475 void PushLocalSearchDecision();

4476

4477 private:

4479 IntVar* const objective_ = nullptr;

4482 DecisionBuilder* const first_solution_sub_decision_builder_;

4485 std::vector<NestedSolveDecision*> nested_decisions_;

4486 int nested_decision_index_;

4489 bool has_started_;

4490};

4491

4498 : assignment_(nullptr),

4499 objective_(objective),

4500 pool_(pool),

4501 ls_operator_(ls_operator),

4502 first_solution_sub_decision_builder_(sub_decision_builder),

4503 sub_decision_builder_(sub_decision_builder),

4504 nested_decision_index_(0),

4505 limit_(limit),

4506 filter_manager_(filter_manager),

4507 has_started_(false) {

4508 CHECK(nullptr != assignment);

4509 CHECK(nullptr != ls_operator);

4510 Solver* const solver = assignment->solver();

4512 assignment_->Copy(assignment);

4516}

4517

4525 : assignment_(nullptr),

4526 objective_(objective),

4527 pool_(pool),

4528 ls_operator_(ls_operator),

4529 first_solution_sub_decision_builder_(sub_decision_builder),

4530 sub_decision_builder_(sub_decision_builder),

4531 nested_decision_index_(0),

4532 limit_(limit),

4533 filter_manager_(filter_manager),

4534 has_started_(false) {

4535 CHECK(nullptr != first_solution);

4536 CHECK(nullptr != ls_operator);

4537 CHECK(!vars.empty());

4538 Solver* const solver = vars[0]->solver();

4540 assignment_->Add(vars);

4543}

4544

4546 const std::vector<IntVar*>& vars, IntVar* objective,

4548 DecisionBuilder* const first_solution_sub_decision_builder,

4552 : assignment_(nullptr),

4553 objective_(objective),

4554 pool_(pool),

4555 ls_operator_(ls_operator),

4556 first_solution_sub_decision_builder_(first_solution_sub_decision_builder),

4557 sub_decision_builder_(sub_decision_builder),

4558 nested_decision_index_(0),

4559 limit_(limit),

4560 filter_manager_(filter_manager),

4561 has_started_(false) {

4562 CHECK(nullptr != first_solution);

4563 CHECK(nullptr != ls_operator);

4564 CHECK(!vars.empty());

4565 Solver* const solver = vars[0]->solver();

4567 assignment_->Add(vars);

4570}

4571

4579 : assignment_(nullptr),

4580 objective_(objective),

4581 pool_(pool),

4582 ls_operator_(ls_operator),

4583 first_solution_sub_decision_builder_(sub_decision_builder),

4584 sub_decision_builder_(sub_decision_builder),

4585 nested_decision_index_(0),

4586 limit_(limit),

4587 filter_manager_(filter_manager),

4588 has_started_(false) {

4589 CHECK(nullptr != first_solution);

4590 CHECK(nullptr != ls_operator);

4591 CHECK(!vars.empty());

4592 Solver* const solver = vars[0]->solver();

4594 assignment_->Add(vars);

4597}

4598

4600

4601

4603 DCHECK(assignment_ != nullptr);

4605

4606 const std::vector<IntVarElement>& elements =

4607 assignment_->IntVarContainer().elements();

4608 if (!elements.empty()) {

4609 std::vector<IntVar*> vars;

4611 vars.push_back(elem.Var());

4612 }

4614 vars);

4615 }

4616 const std::vector<IntervalVarElement>& interval_elements =

4617 assignment_->IntervalVarContainer().elements();

4618 if (!interval_elements.empty()) {

4619 std::vector<IntervalVar*> interval_vars;

4621 interval_vars.push_back(elem.Var());

4622 }

4624 interval_vars);

4625 }

4627}

4628

4629

4630

4631

4632

4633

4635 CHECK(nullptr != solver);

4636 CHECK_LT(0, nested_decisions_.size());

4637 if (!has_started_) {

4638 nested_decision_index_ = 0;

4640 find_neighbors_db_->EnterSearch();

4641 ls_operator_->EnterSearch();

4642 } else if (nested_decision_index_ < 0) {

4643 solver->Fail();

4644 }

4645 NestedSolveDecision* decision = nested_decisions_[nested_decision_index_];

4646 const int state = decision->state();

4647 switch (state) {

4648 case NestedSolveDecision::DECISION_FAILED: {

4649

4650

4651

4652

4653 const bool continue_at_local_optimum =

4654 nested_decision_index_ == nested_decisions_.size() - 1 &&

4656 if (continue_at_local_optimum) {

4657

4658

4659

4660 ls_operator_->Reset();

4661 }

4662 if (!continue_at_local_optimum ||

4663 solver->IsUncheckedSolutionLimitReached()) {

4664 nested_decision_index_ = -1;

4665 }

4666 solver->Fail();

4667 return nullptr;

4668 }

4669 case NestedSolveDecision::DECISION_PENDING: {

4670

4671

4672 const int32_t kLocalSearchBalancedTreeDepth = 32;

4673 const int depth = solver->SearchDepth();

4674 if (depth < kLocalSearchBalancedTreeDepth) {

4676 }

4677 if (depth > kLocalSearchBalancedTreeDepth) {

4678 solver->Fail();

4679 }

4680 return decision;

4681 }

4682 case NestedSolveDecision::DECISION_FOUND: {

4683

4684 if (nested_decision_index_ + 1 < nested_decisions_.size()) {

4685 ++nested_decision_index_;

4686 }

4687 return nullptr;

4688 }

4689 default: {

4690 LOG(ERROR) << "Unknown local search state";

4691 return nullptr;

4692 }

4693 }

4694 return nullptr;

4695}

4696

4698 CHECK(first_solution);

4699 Solver* const solver = assignment_->solver();

4703 first_solution_sub_decision_builder_, store);

4704 std::vector<SearchMonitor*> monitor;

4705 monitor.push_back(limit_);

4706 nested_decisions_.push_back(solver->RevAlloc(

4707 new NestedSolveDecision(first_solution_and_store, false, monitor)));

4708}

4709

4711 Solver* const solver = assignment_->solver();

4712 find_neighbors_db_ = solver->RevAlloc(

4713 new FindOneNeighbor(assignment_, objective_, pool_, ls_operator_,

4714 sub_decision_builder_, limit_, filter_manager_));

4715 nested_decisions_.push_back(

4716 solver->RevAlloc(new NestedSolveDecision(find_neighbors_db_, false)));

4717}

4718

4720 public:

4722

4724

4726 reference_assignment_ = std::make_unique<Assignment>(assignment);

4727 }

4728

4730 reference_assignment_->CopyIntersection(assignment);

4731 }

4732

4736

4738

4739 std::string DebugString() const override { return "DefaultSolutionPool"; }

4740

4741 private:

4742 std::unique_ptr<Assignment> reference_assignment_;

4743};

4744

4748

4756

4758 const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,

4762 first_solution, parameters->ls_operator(),

4765}

4766

4768 const std::vector<IntVar*>& vars, DecisionBuilder* first_solution,

4773 first_solution, first_solution_sub_decision_builder,

4776}

4777

4779 const std::vector<SequenceVar*>& vars, DecisionBuilder* first_solution,

4783 first_solution, parameters->ls_operator(),

4786}

4787

4788template <bool is_profile_active>

4789Assignment* Solver::RunUncheckedLocalSearchInternal(

4792 const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,

4793 absl::flat_hash_set<IntVar*>* touched) {

4794 DCHECK(initial_solution != nullptr);

4795 DCHECK(initial_solution->Objective() != nullptr);

4796 DCHECK(filter_manager != nullptr);

4797 if (limit != nullptr) limit->Init();

4801 current_solution->Copy(initial_solution);

4806 const auto sync_with_solution =

4807 [this, ls_monitor, ls_operator,

4808

4809 filter_manager, current_solution](Assignment* delta) {

4810 IncrementUncheckedSolutionCounter();

4811 if constexpr (is_profile_active) {

4813 }

4814 ls_operator->Start(current_solution);

4815 filter_manager->Synchronize(current_solution, delta);

4816 if constexpr (is_profile_active) {

4818 }

4819 };

4820 sync_with_solution(nullptr);

4821 while (true) {

4822 if (!ls_operator->HoldsDelta()) {

4823 delta.Clear();

4824 }

4825 delta.ClearObjective();

4826 deltadelta.Clear();

4827 if (limit != nullptr && (limit->CheckWithOffset(absl::ZeroDuration()) ||

4829 break;

4830 }

4831 if constexpr (is_profile_active) {

4833 }

4834 const bool has_neighbor =

4835 ls_operator->MakeNextNeighbor(&delta, &deltadelta);

4836 if constexpr (is_profile_active) {

4838 &deltadelta);

4839 }

4840 if (!has_neighbor) {

4841 break;

4842 }

4843 if constexpr (is_profile_active) {

4845 }

4847 const bool mh_accept = monitor->AcceptDelta(&delta, &deltadelta);

4848 DCHECK(mh_accept);

4849 }

4850 const bool filter_accept =

4851 filter_manager->Accept(ls_monitor, &delta, &deltadelta,

4852 delta.ObjectiveMin(), delta.ObjectiveMax());

4853 if constexpr (is_profile_active) {

4857 }

4858 if (!filter_accept) {

4859 filter_manager->Revert();

4860 continue;

4861 }

4862 filtered_neighbors_ += 1;

4865 filter_manager->GetAcceptedObjectiveValue());

4866 DCHECK(delta.AreAllElementsBound());

4867 accepted_neighbors_ += 1;

4871 }

4872 if (touched != nullptr) {

4873 for (const auto& element : delta.IntVarContainer().elements()) {

4874 touched->insert(element.Var());

4875 }

4876 }

4877

4878 sync_with_solution(&delta);

4879 }

4880 if (parameters_.print_local_search_profile()) {

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

4883 }

4885}

4886

4890 const std::vector<SearchMonitor*>& monitors, RegularLimit* limit,

4891 absl::flat_hash_set<IntVar*>* touched) {

4893 return RunUncheckedLocalSearchInternal<true>(initial_solution,

4894 filter_manager, ls_operator,

4895 monitors, limit, touched);

4896 } else {

4897 return RunUncheckedLocalSearchInternal<false>(initial_solution,

4898 filter_manager, ls_operator,

4899 monitors, limit, touched);

4900 }

4901}

4902

4903}

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

const std::vector< E > & elements() const

bool HasObjective() const

void SetObjectiveValue(int64_t value)

IntVarElement * Add(IntVar *var)

std::string DebugString() const override

bool AreAllElementsBound() const

void Copy(const Assignment *assignment)

int64_t ObjectiveMin() const

AssignmentContainer< IntVar, IntVarElement > IntContainer

IntVar * Objective() const

int64_t ObjectiveMax() const

const IntContainer & IntVarContainer() const

void CopyIntersection(const Assignment *assignment)

void AddObjective(IntVar *const v)

BaseInactiveNodeToPathOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_base_nodes, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors=nullptr, NeighborAccessor get_outgoing_neighbors=nullptr)

Definition local_search.cc:739

~BaseInactiveNodeToPathOperator() override=default

int64_t GetInactiveNode() const

Definition local_search.cc:757

bool MakeOneNeighbor() override

MakeNextNeighbor() in a subclass of IntVarLocalSearchOperator.

Definition local_search.cc:777

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

void AppendToFragment(int index)

Definition local_search.cc:126

~BaseLns() override

Definition local_search.cc:109

virtual void InitFragments()

Definition local_search.cc:124

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

Definition local_search.cc:106

bool MakeOneNeighbor() override

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

Definition local_search.cc:111

int FragmentSize() const

Definition local_search.cc:132

virtual bool NextFragment()=0

virtual std::string DebugString() const

~ChangeValue() override

Definition local_search.cc:303

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

bool MakeOneNeighbor() override

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

Definition local_search.cc:305

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

Definition local_search.cc:300

Definition local_search.cc:620

bool MakeNeighbor() override

Definition local_search.cc:644

std::string DebugString() const override

Definition local_search.cc:640

Cross(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)

Definition local_search.cc:622

~Cross() override=default

Definition local_search.cc:4719

DefaultSolutionPool()

Definition local_search.cc:4721

void GetNextSolution(Assignment *const assignment) override

Definition local_search.cc:4733

std::string DebugString() const override

Definition local_search.cc:4739

bool SyncNeeded(Assignment *const) override

Definition local_search.cc:4737

~DefaultSolutionPool() override

Definition local_search.cc:4723

void Initialize(Assignment *const assignment) override

Definition local_search.cc:4725

void RegisterNewSolution(Assignment *const assignment) override

Definition local_search.cc:4729

Definition local_search.cc:876

bool MakeNeighbor() override

Definition local_search.cc:885

ExchangeAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:878

bool OnSamePathAsPreviousBase(int64_t base_index) override

it's currently way more complicated to implement.

Definition local_search.cc:895

std::string DebugString() const override

Definition local_search.cc:890

~ExchangeAndMakeActiveOperator() override

Definition local_search.cc:884

Definition local_search.cc:916

ExchangePathStartEndsAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:918

int64_t GetBaseNodeRestartPosition(int base_index) override

Definition local_search.cc:925

std::string DebugString() const override

Definition local_search.cc:942

~ExchangePathStartEndsAndMakeActiveOperator() override=default

bool MakeNeighbor() override

Definition local_search.cc:929

Definition local_search.cc:560

bool MakeNeighbor() override

Definition local_search.cc:584

~Exchange() override=default

Exchange(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)

Definition local_search.cc:562

std::string DebugString() const override

Definition local_search.cc:580

Definition local_search.cc:1273

std::string DebugString() const override

Definition local_search.cc:1291

ExtendedSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:1275

bool MakeNeighbor() override

Definition local_search.cc:1281

~ExtendedSwapActiveOperator() override=default

Definition local_search.cc:3931

std::string DebugString() const override

Definition local_search.cc:3941

Decision * Next(Solver *solver) override

Definition local_search.cc:4029

~FindOneNeighbor() override

Definition local_search.cc:3938

FindOneNeighbor(Assignment *assignment, IntVar *objective, SolutionPool *pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, const RegularLimit *limit, LocalSearchFilterManager *filter_manager)

Definition local_search.cc:3972

void EnterSearch()

Definition local_search.cc:4022

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

Definition local_search.cc:2566

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

virtual void OnSynchronize(const Assignment *)

void SynchronizeOnAssignment(const Assignment *assignment)

Definition local_search.cc:2599

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

Add variables to "track" to the filter.

Definition local_search.cc:2571

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

Definition local_search.cc:2588

~IntVarLocalSearchFilter() override

Definition local_search.cc:2586

void SetValue(int64_t index, int64_t value)

void RevertChanges(bool change_was_incremental)

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

Definition local_search.cc:80

void Deactivate(int64_t index)

IntVar * Var(int64_t index) const

Returns the variable of given index.

int64_t Value(int64_t index) const

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

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

virtual bool MakeOneNeighbor()

MakeNextNeighbor() in a subclass of IntVarLocalSearchOperator.

Definition local_search.cc:102

IntVar * Var() override

Creates a variable from the expression.

virtual bool Contains(int64_t v) const =0

Definition local_search.cc:1626

std::string DebugString() const override

Definition local_search.cc:1634

~LinKernighan() override=default

LinKernighan(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)

Definition local_search.cc:1653

bool MakeNeighbor() override

Definition local_search.cc:1696

LocalSearchFilterManager(std::vector< FilterEvent > filter_events)

Definition local_search.cc:3802

void Revert()

Definition local_search.cc:3816

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

Synchronizes all filters to assignment.

Definition local_search.cc:3883

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

Definition local_search.cc:3827

LocalSearchMonitor(Solver *solver)

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

virtual void BeginAcceptNeighbor(const LocalSearchOperator *op)=0

virtual void BeginMakeNextNeighbor(const LocalSearchOperator *op)=0

virtual void BeginOperatorStart()=0

Local search operator events.

virtual void BeginFilterNeighbor(const LocalSearchOperator *op)=0

virtual void BeginFiltering(const LocalSearchFilter *filter)=0

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

virtual void EndOperatorStart()=0

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

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

The base class for all local search operators.

virtual const LocalSearchOperator * Self() const

virtual bool HasFragments() const

Definition local_search.cc:4285

SolutionPool * solution_pool() const

Definition local_search.cc:4304

~LocalSearchPhaseParameters() override

Definition local_search.cc:4298

LocalSearchFilterManager * filter_manager() const

Definition local_search.cc:4310

IntVar * objective() const

Definition local_search.cc:4303

LocalSearchPhaseParameters(IntVar *objective, SolutionPool *const pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *const limit, LocalSearchFilterManager *filter_manager)

Definition local_search.cc:4287

LocalSearchOperator * ls_operator() const

Definition local_search.cc:4305

RegularLimit * limit() const

Definition local_search.cc:4309

std::string DebugString() const override

Definition local_search.cc:4299

DecisionBuilder * sub_decision_builder() const

Definition local_search.cc:4306

Definition local_search.cc:3409

void BeginOperatorStart() override

Local search operator events.

Definition local_search.cc:3636

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

Definition local_search.cc:3682

void BeginMakeNextNeighbor(const LocalSearchOperator *op) override

Definition local_search.cc:3638

std::string DebugString() const override

Definition local_search.cc:3412

LocalSearchProfiler(Solver *solver)

Definition local_search.cc:3411

void BeginFiltering(const LocalSearchFilter *filter) override

Definition local_search.cc:3676

LocalSearchStatistics ExportToLocalSearchStatistics() const

Definition local_search.cc:3478

void ExitSearch() override

End of the search.

Definition local_search.cc:3418

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

Definition local_search.cc:3667

void EndOperatorStart() override

Definition local_search.cc:3637

void ParseLocalSearchOperatorStatistics(const Callback &callback) const

Definition local_search.cc:3432

std::string PrintOverview() const

Definition local_search.cc:3535

void ParseLocalSearchFilterStatistics(const Callback &callback) const

Definition local_search.cc:3458

void AddFirstSolutionProfiledDecisionBuilder(ProfiledDecisionBuilder *profiled_db)

Definition local_search.cc:3690

void BeginAcceptNeighbor(const LocalSearchOperator *) override

Definition local_search.cc:3664

bool IsActive() const override

Definition local_search.cc:3694

void Install() override

Install itself on the solver.

Definition local_search.cc:3695

void BeginFilterNeighbor(const LocalSearchOperator *) override

Definition local_search.cc:3657

void ParseFirstSolutionStatistics(const Callback &callback) const

Definition local_search.cc:3424

void RestartSearch() override

Restart the search.

Definition local_search.cc:3413

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

Definition local_search.cc:3658

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

Definition local_search.cc:3645

void AddWeightedSumConstraint(const std::vector< VariableDomainId > &input_domain_ids, const std::vector< int64_t > &input_weights, int64_t input_offset, VariableDomainId output_domain_id)

Definition local_search.cc:3178

bool StateIsFeasible() const

int64_t VariableDomainMin(VariableDomainId domain_id) const

Definition local_search.cc:3034

VariableDomainId AddVariableDomain(int64_t relaxed_min, int64_t relaxed_max)

Definition local_search.cc:2989

bool TightenVariableDomainMin(VariableDomainId domain_id, int64_t value)

Definition local_search.cc:3044

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

Definition local_search.cc:3068

void PropagateRelax(VariableDomainId domain_id)

Definition local_search.cc:3379

static Variable DummyVariable()

Definition local_search.cc:3010

Variable MakeVariable(VariableDomainId domain_id)

Definition local_search.cc:2999

Variable MakeVariableWithRelaxedDomain(int64_t min, int64_t max)

Definition local_search.cc:3004

void Revert()

Definition local_search.cc:3101

bool TightenVariableDomainMax(VariableDomainId domain_id, int64_t value)

Definition local_search.cc:3056

void Commit()

Definition local_search.cc:3088

void CompileConstraints()

Definition local_search.cc:3204

int64_t VariableDomainMax(VariableDomainId domain_id) const

Definition local_search.cc:3039

bool PropagateTighten(VariableDomainId domain_id)

Definition local_search.cc:3389

bool RelaxVariableDomain(VariableDomainId domain_id)

Definition local_search.cc:3014

void set_duration_seconds(double value)

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

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

void set_num_rejects(::int64_t value)

void set_num_calls(::int64_t value)

void set_num_rejects_per_second(double value)

void set_duration_seconds(double value)

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

void set_num_filtered_neighbors(::int64_t value)

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

void set_num_neighbors(::int64_t value)

void set_make_next_neighbor_duration_seconds(double value)

void set_num_accepted_neighbors(::int64_t value)

void set_duration_seconds(double value)

void set_accept_neighbor_duration_seconds(double value)

LocalSearchStatistics_FirstSolutionStatistics FirstSolutionStatistics

void set_total_num_neighbors(::int64_t value)

void set_total_num_filtered_neighbors(::int64_t value)

::operations_research::LocalSearchStatistics_LocalSearchOperatorStatistics *PROTOBUF_NONNULL add_local_search_operator_statistics()

void set_total_num_accepted_neighbors(::int64_t value)

::operations_research::LocalSearchStatistics_LocalSearchFilterStatistics *PROTOBUF_NONNULL add_local_search_filter_statistics()

LocalSearchStatistics_LocalSearchFilterStatistics LocalSearchFilterStatistics

LocalSearchStatistics_LocalSearchOperatorStatistics LocalSearchOperatorStatistics

::operations_research::LocalSearchStatistics_FirstSolutionStatistics *PROTOBUF_NONNULL add_first_solution_statistics()

void PushFirstSolutionDecision(DecisionBuilder *first_solution)

Definition local_search.cc:4697

std::string DebugString() const override

Definition local_search.cc:4470

LocalSearch(Assignment *assignment, IntVar *objective, SolutionPool *pool, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder, RegularLimit *limit, LocalSearchFilterManager *filter_manager)

Definition local_search.cc:4492

void Accept(ModelVisitor *visitor) const override

Definition local_search.cc:4602

~LocalSearch() override

Definition local_search.cc:4599

Decision * Next(Solver *solver) override

Definition local_search.cc:4634

void PushLocalSearchDecision()

Definition local_search.cc:4710

Definition local_search.cc:964

bool MakeNeighbor() override

Definition local_search.cc:981

~MakeActiveAndRelocateOperator() override=default

std::string DebugString() const override

Definition local_search.cc:975

MakeActiveAndRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:966

Definition local_search.cc:794

~MakeActiveOperator() override=default

bool MakeNeighbor() override

Definition local_search.cc:812

std::string DebugString() const override

Definition local_search.cc:808

MakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)

Definition local_search.cc:796

Definition local_search.cc:1081

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition local_search.cc:1109

MakeChainInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:1083

std::string DebugString() const override

Definition local_search.cc:1104

int64_t GetBaseNodeRestartPosition(int base_index) override

Definition local_search.cc:1115

bool MakeNeighbor() override

Definition local_search.cc:1092

~MakeChainInactiveOperator() override=default

Definition local_search.cc:1005

std::string DebugString() const override

Definition local_search.cc:1019

MakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:1007

bool MakeNeighbor() override

Definition local_search.cc:1014

~MakeInactiveOperator() override=default

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

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

static const char kVariableGroupExtension[]

static const char kVarsArgument[]

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

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

static const char kIntervalsArgument[]

Definition local_search.cc:1551

const std::vector< int > & Neighbors(int index) const

Definition local_search.cc:1594

virtual ~NearestNeighbors()=default

NearestNeighbors & operator=(const NearestNeighbors &)=delete

virtual std::string DebugString() const

Definition local_search.cc:1565

NearestNeighbors(const NearestNeighbors &)=delete

NearestNeighbors(Solver::IndexEvaluator3 evaluator, const PathOperator< ignore_path_vars > &path_operator, int size)

Definition local_search.cc:1577

void Initialize(absl::Span< const int > path)

Definition local_search.cc:1586

Definition local_search.cc:1893

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

Definition local_search.cc:1906

NeighborhoodLimit(LocalSearchOperator *const op, int64_t limit)

Definition local_search.cc:1895

std::string DebugString() const override

Definition local_search.cc:1916

void Start(const Assignment *assignment) override

Definition local_search.cc:1901

bool HoldsDelta() const override

Definition local_search.cc:1914

Definition local_search.cc:1806

bool HasFragments() const override

Definition local_search.cc:1822

std::string DebugString() const override

Definition local_search.cc:1821

PathLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments)

Definition local_search.cc:1808

bool MakeNeighbor() override

Definition local_search.cc:1835

~PathLns() override=default

bool HasNeighbors() const

int number_of_nexts() const

Number of next variables.

bool MakeChainInactive(int64_t before_chain, int64_t chain_end)

int64_t Prev(int64_t node) const

Returns the node before node in the current delta.

int PathClassFromStartNode(int64_t start_node) const

int64_t Path(int64_t node) const

bool MakeActive(int64_t node, int64_t destination)

Insert the inactive node after destination.

int64_t OldNext(int64_t node) const

bool SwapNodes(int64_t node1, int64_t node2)

Swaps the nodes node1 and node2.

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

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

int CurrentNodePathStart(int64_t node) const

virtual void OnNodeInitialization()

bool IsPathStart(int64_t node) const

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

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

bool IsPathEnd(int64_t node) const

int64_t EndNode(int i) const

Returns the end node of the ith base node.

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.

bool IsInactive(int64_t node) const

Returns true if node is inactive.

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

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

virtual void SetNextBaseToIncrement(int64_t base_index)

Neighbor GetNeighborForBaseNode(int64_t base_index) const

bool MakeOneNeighbor() override

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

int64_t StartNode(int i) const

Returns the start node of the ith base node.

int64_t BaseNode(int i) const

Returns the ith base node of the operator.

int CurrentNodePathEnd(int64_t node) const

bool IsUncheckedSolutionLimitReached() override

bool CheckWithOffset(absl::Duration offset) override

void Init() override

This method is called when the search limit is initialized.

RegularLimit * MakeIdenticalClone() const

Definition local_search.cc:838

std::string DebugString() const override

Definition local_search.cc:855

bool MakeNeighbor() override

Definition local_search.cc:847

RelocateAndMakeActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:840

~RelocateAndMakeActiveOperator() override=default

Definition local_search.cc:1037

std::string DebugString() const override

Definition local_search.cc:1061

RelocateAndMakeInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:1039

~RelocateAndMakeInactiveOperator() override=default

bool MakeNeighbor() override

Definition local_search.cc:1047

Definition local_search.cc:464

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition local_search.cc:493

std::string DebugString() const override

Definition local_search.cc:490

~Relocate() override=default

bool MakeNeighbor() override

Definition local_search.cc:506

Relocate(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, absl::string_view name, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors, int64_t chain_length=1LL, bool single_path=false)

Definition local_search.cc:466

virtual bool AtSolution()

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

Search * ActiveSearch() const

Returns the active search, nullptr outside search.

bool IsLocalSearchProfilingEnabled() const

Returns whether we are profiling local search.

DecisionBuilder * MakeRestoreAssignment(Assignment *assignment)

LocalSearchOperator * MakeMoveTowardTargetOperator(const Assignment &target)

Definition local_search.cc:276

LocalSearchOperator * ConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)

Example:

Definition local_search.cc:2072

LocalSearchFilter * MakeVariableDomainFilter()

Definition local_search.cc:2558

ABSL_MUST_USE_RESULT RegularLimit * MakeSolutionsLimit(int64_t solutions)

LocalSearchPhaseParameters * MakeLocalSearchPhaseParameters(IntVar *objective, LocalSearchOperator *ls_operator, DecisionBuilder *sub_decision_builder)

Local Search Phase Parameters.

Definition local_search.cc:4321

void Fail()

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

Decision * balancing_decision() const

IntVarLocalSearchFilter * MakeSumObjectiveFilter(const std::vector< IntVar * > &vars, IndexEvaluator2 values, Solver::LocalSearchFilterBound filter_enum)

Definition local_search.cc:2823

DecisionBuilder * MakeProfiledDecisionBuilderWrapper(DecisionBuilder *db)

Activates profiling on a decision builder.

Definition local_search.cc:3734

bool UseFastLocalSearch() const

Returns true if fast local search is enabled.

LocalSearchMonitor * GetLocalSearchMonitor() const

Returns the local search monitor.

Assignment * RunUncheckedLocalSearch(const Assignment *initial_solution, LocalSearchFilterManager *filter_manager, LocalSearchOperator *ls_operator, const std::vector< SearchMonitor * > &monitors, RegularLimit *limit, absl::flat_hash_set< IntVar * > *touched=nullptr)

Definition local_search.cc:4887

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

LocalSearchStatistics GetLocalSearchStatistics() const

Returns detailed local search statistics.

Definition local_search.cc:3766

DecisionBuilder * Compose(DecisionBuilder *db1, DecisionBuilder *db2)

std::string LocalSearchProfile() const

Returns local search profiling information in a human readable format.

Definition local_search.cc:3759

LocalSearchOperator * RandomConcatenateOperators(const std::vector< LocalSearchOperator * > &ops)

Definition local_search.cc:2169

void SaveAndSetValue(T *adr, T val)

All-in-one SaveAndSetValue.

LocalSearchFilter * MakeAcceptFilter()

Local Search Filters.

Definition local_search.cc:2509

SolutionPool * MakeDefaultSolutionPool()

Solution Pool.

Definition local_search.cc:4745

LocalSearchOperator * MakeNeighborhoodLimit(LocalSearchOperator *op, int64_t limit)

Definition local_search.cc:1924

DecisionBuilder * MakeLocalSearchPhase(Assignment *assignment, LocalSearchPhaseParameters *parameters)

Definition local_search.cc:4749

LocalSearchOperator * MakeOperator(const std::vector< IntVar * > &vars, LocalSearchOperators op, std::function< const std::vector< int > &(int, int)> get_incoming_neighbors=nullptr, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors=nullptr)

Local Search Operators.

Definition local_search.cc:2355

@ LE

Move is accepted when the current objective value <= objective.Max.

@ GE

Move is accepted when the current objective value >= objective.Min.

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

LocalSearchFilter * MakeRejectFilter()

Definition local_search.cc:2525

friend class SearchMonitor

DecisionBuilder * MakeStoreAssignment(Assignment *assignment)

LocalSearchOperator * MultiArmedBanditConcatenateOperators(const std::vector< LocalSearchOperator * > &ops, double memory_coefficient, double exploration_coefficient, bool maximize)

Definition local_search.cc:2346

Assignment * MakeAssignment()

This method creates an empty assignment.

EvaluatorLocalSearchOperators

@ RELOCATE

Relocate neighborhood with length of 1 (see OROPT comment).

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

ConstraintSolverParameters parameters() const

Stored Parameters.

Assignment * GetOrCreateLocalSearchState()

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

bool AcceptSolution(Search *search) const

LocalSearchOperator * MakeRandomLnsOperator(const std::vector< IntVar * > &vars, int number_of_variables)

Definition local_search.cc:198

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

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

Definition local_search.cc:2946

void BuildGraph(int num_nodes)

Definition local_search.cc:2888

Definition local_search.cc:1171

bool MakeNeighbor() override

Definition local_search.cc:1222

void ResetIncrementalism() override

Definition local_search.cc:1190

~SwapActiveChainOperator() override=default

SwapActiveChainOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, int max_chain_size)

Definition local_search.cc:1173

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition local_search.cc:1194

std::string DebugString() const override

Definition local_search.cc:1207

bool IsIncremental() const override

Definition local_search.cc:1187

Definition local_search.cc:1138

~SwapActiveOperator() override=default

SwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class)

Definition local_search.cc:1140

bool MakeNeighbor() override

Definition local_search.cc:1146

std::string DebugString() const override

Definition local_search.cc:1152

Definition local_search.cc:1389

~TSPLns() override=default

std::string DebugString() const override

Definition local_search.cc:1397

bool MakeNeighbor() override

Definition local_search.cc:1449

bool MakeOneNeighbor() override

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

Definition local_search.cc:1437

TSPLns(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)

Definition local_search.cc:1418

Definition local_search.cc:1311

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

Definition local_search.cc:1330

~TSPOpt() override=default

std::string DebugString() const override

Definition local_search.cc:1319

bool MakeNeighbor() override

Definition local_search.cc:1341

Definition local_search.cc:352

bool IsIncremental() const override

Definition local_search.cc:373

void ResetIncrementalism() override

Definition local_search.cc:378

bool OnSamePathAsPreviousBase(int64_t) override

it's currently way more complicated to implement.

Definition local_search.cc:379

int64_t GetBaseNodeRestartPosition(int base_index) override

Definition local_search.cc:383

~TwoOpt() override=default

std::string DebugString() const override

Definition local_search.cc:375

TwoOpt(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, NeighborAccessor get_incoming_neighbors, NeighborAccessor get_outgoing_neighbors)

Definition local_search.cc:354

bool MakeNeighbor() override

Definition local_search.cc:395

ABSL_FLAG(int, cp_local_search_sync_frequency, 16, "Frequency of checks for better solutions in the solution pool.")

ReverseView< Container > reversed_view(const Container &c)

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

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

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

Definition local_search.cc:346

void DeleteLocalSearchProfiler(LocalSearchProfiler *monitor)

Definition local_search.cc:3757

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 --—

Definition local_search.cc:1296

int64_t CapAdd(int64_t x, int64_t y)

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 --—

Definition local_search.cc:1066

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

--— TSP-based operators --—

Definition local_search.cc:1375

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 --—

Definition local_search.cc:717

SubDagComputer::ArcId ArcId

Definition local_search.cc:3165

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 --—

Definition local_search.cc:1155

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

Definition local_search.cc:900

void AcceptNeighbor(Search *search)

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 --—

Definition local_search.cc:601

void AcceptUncheckedNeighbor(Search *search)

int64_t CapSub(int64_t x, int64_t y)

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 --—

Definition local_search.cc:990

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

Definition local_search.cc:1529

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 --—

Definition local_search.cc:538

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 --—

Definition local_search.cc:860

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 --—

Definition local_search.cc:1877

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 --—

Definition local_search.cc:1022

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 --—

Definition local_search.cc:445

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

--— MakeChainInactive --—

Definition local_search.cc:1122

void InstallLocalSearchProfiler(LocalSearchProfiler *monitor)

Definition local_search.cc:3746

int64_t CapProd(int64_t x, int64_t y)

LocalSearchProfiler * BuildLocalSearchProfiler(Solver *solver)

Definition local_search.cc:3750

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

Definition local_search.cc:947

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 --—

Definition local_search.cc:1256

LocalSearchOperator * MakeLinKernighan(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, const Solver::IndexEvaluator3 &evaluator, bool topt)

--— Lin-Kernighan --—

Definition local_search.cc:1791

bool ContinueAtLocalOptimum(Search *search)

LocalSearchState::VariableDomainId VariableDomainId

Definition local_search.cc:2988

ClosedInterval::Iterator begin(ClosedInterval interval)

LocalSearchOperator * MakeActive(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)

--— MakeActive --—

Definition local_search.cc:818

bool AcceptDelta(Search *search, Assignment *delta, Assignment *deltadelta)

SubDagComputer::NodeId NodeId

Definition local_search.cc:3119

static int input(yyscan_t yyscanner)

static const int64_t kint64max

static const int32_t kint32max

static const int64_t kint64min