Google OR-Tools: ortools/constraint_solver/sched

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

14#include <algorithm>

15#include <cstdint>

16#include <cstring>

17#include <limits>

18#include <string>

19#include <utility>

20#include <vector>

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

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

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

31namespace {

32int64_t ValueToIndex(int64_t value) { return value - 1; }

34int64_t IndexToValue(int64_t index) { return index + 1; }

35}

43 const std::vector<IntervalVar*>& intervals,

44 const std::vector<IntVar*>& nexts,

45 const std::string& name)

47 intervals_(intervals),

48 nexts_(nexts),

49 previous_(nexts.size() + 1, -1) {

51}

56 return intervals_[index];

57}

62 int64_t hmin, hmax, dmin, dmax;

65 int unperformed = 0;

66 int ranked = 0;

67 int not_ranked = 0;

69 return absl::StrFormat(

70 "%s(horizon = %d..%d, duration = %d..%d, not ranked = %d, ranked = %d, "

71 "nexts = [%s])",

72 name(), hmin, hmax, dmin, dmax, not_ranked, ranked,

74}

81 int64_t* const dmax) const {

82 int64_t dur_min = 0;

83 int64_t dur_max = 0;

84 for (int i = 0; i < intervals_.size(); ++i) {

89 }

91 }

92 }

93 *dmin = dur_min;

94 *dmax = dur_max;

95}

98 int64_t hor_min = std::numeric_limits<int64_t>::max();

99 int64_t hor_max = std::numeric_limits<int64_t>::min();

100 for (int i = 0; i < intervals_.size(); ++i) {

104 hor_min = std::min(hor_min, t->StartMin());

105 hor_max = std::max(hor_max, t->EndMax());

106 }

107 }

108 *hmin = hor_min;

109 *hmax = hor_max;

110}

111

113 int64_t* const hmax) const {

114 absl::flat_hash_set<int> decided;

115 for (int i = 0; i < intervals_.size(); ++i) {

116 if (intervals_[i]->CannotBePerformed()) {

117 decided.insert(i);

118 }

119 }

120 int first = 0;

121 while (nexts_[first]->Bound()) {

122 first = nexts_[first]->Min();

123 if (first < nexts_.size()) {

124 decided.insert(ValueToIndex(first));

125 } else {

126 break;

127 }

128 }

129 if (first != nexts_.size()) {

130 UpdatePrevious();

131 int last = nexts_.size();

132 while (previous_[last] != -1) {

133 last = previous_[last];

134 decided.insert(ValueToIndex(last));

135 }

136 }

137 int64_t hor_min = std::numeric_limits<int64_t>::max();

138 int64_t hor_max = std::numeric_limits<int64_t>::min();

139 for (int i = 0; i < intervals_.size(); ++i) {

140 if (!decided.contains(i)) {

142 hor_min = std::min(hor_min, t->StartMin());

143 hor_max = std::max(hor_max, t->EndMax());

144 }

145 }

146 *hmin = hor_min;

147 *hmax = hor_max;

148}

149

151 int* const unperformed) const {

152 *unperformed = 0;

153 for (int i = 0; i < intervals_.size(); ++i) {

154 if (intervals_[i]->CannotBePerformed()) {

155 (*unperformed)++;

156 }

157 }

158 *ranked = 0;

159 int first = 0;

160 while (first < nexts_.size() && nexts_[first]->Bound()) {

161 first = nexts_[first]->Min();

162 (*ranked)++;

163 }

164 if (first != nexts_.size()) {

165 UpdatePrevious();

166 int last = nexts_.size();

167 while (previous_[last] != -1) {

168 last = previous_[last];

169 (*ranked)++;

170 }

171 } else {

172 (*ranked)--;

173 }

174 *not_ranked = intervals_.size() - *ranked - *unperformed;

175}

176

177int SequenceVar::ComputeForwardFrontier() {

178 int first = 0;

179 while (first != nexts_.size() && nexts_[first]->Bound()) {

180 first = nexts_[first]->Min();

181 }

182 return first;

183}

184

185int SequenceVar::ComputeBackwardFrontier() {

186 UpdatePrevious();

187 int last = nexts_.size();

188 while (previous_[last] != -1) {

189 last = previous_[last];

190 }

191 return last;

192}

193

195 std::vector<int>* const possible_firsts,

196 std::vector<int>* const possible_lasts) {

197 possible_firsts->clear();

198 possible_lasts->clear();

199 absl::flat_hash_set<int> to_check;

200 for (int i = 0; i < intervals_.size(); ++i) {

201 if (intervals_[i]->MayBePerformed()) {

202 to_check.insert(i);

203 }

204 }

205 int first = 0;

206 while (nexts_[first]->Bound()) {

207 first = nexts_[first]->Min();

208 if (first == nexts_.size()) {

209 return;

210 }

211 to_check.erase(ValueToIndex(first));

212 }

213

214 IntVar* const forward_var = nexts_[first];

215 std::vector<int> candidates;

216 int64_t smallest_start_max = std::numeric_limits<int64_t>::max();

217 int ssm_support = -1;

218 for (int64_t i = forward_var->Min(); i <= forward_var->Max(); ++i) {

219

220 if (i != 0 && i < IndexToValue(intervals_.size()) &&

221 intervals_[ValueToIndex(i)]->MayBePerformed() &&

223 const int candidate = ValueToIndex(i);

224 candidates.push_back(candidate);

225 if (intervals_[candidate]->MustBePerformed()) {

226 if (smallest_start_max > intervals_[candidate]->StartMax()) {

227 smallest_start_max = intervals_[candidate]->StartMax();

228 ssm_support = candidate;

229 }

230 }

231 }

232 }

233 for (int i = 0; i < candidates.size(); ++i) {

234 const int candidate = candidates[i];

235 if (candidate == ssm_support ||

236 intervals_[candidate]->EndMin() <= smallest_start_max) {

237 possible_firsts->push_back(candidate);

238 }

239 }

240

241 UpdatePrevious();

242 int last = nexts_.size();

243 while (previous_[last] != -1) {

244 last = previous_[last];

245 to_check.erase(ValueToIndex(last));

246 }

247

248 candidates.clear();

249 int64_t biggest_end_min = std::numeric_limits<int64_t>::min();

250 int bem_support = -1;

251 for (const int candidate : to_check) {

252 if (nexts_[IndexToValue(candidate)]->Contains(last)) {

253 candidates.push_back(candidate);

254 if (intervals_[candidate]->MustBePerformed()) {

255 if (biggest_end_min < intervals_[candidate]->EndMin()) {

256 biggest_end_min = intervals_[candidate]->EndMin();

257 bem_support = candidate;

258 }

259 }

260 }

261 }

262

263 for (int i = 0; i < candidates.size(); ++i) {

264 const int candidate = candidates[i];

265 if (candidate == bem_support ||

266 intervals_[candidate]->StartMax() >= biggest_end_min) {

267 possible_lasts->push_back(candidate);

268 }

269 }

270}

271

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

274 const std::vector<int>& unperformed) {

276 unperformed);

277

278 for (const int value : unperformed) {

279 intervals_[value]->SetPerformed(false);

280 }

281

282 int forward = 0;

283 for (int i = 0; i < rank_first.size(); ++i) {

284 const int next = 1 + rank_first[i];

285 nexts_[forward]->SetValue(next);

286 forward = next;

287 }

288

289 int backward = IndexToValue(intervals_.size());

290 for (int i = 0; i < rank_last.size(); ++i) {

291 const int next = 1 + rank_last[i];

292 nexts_[next]->SetValue(backward);

293 backward = next;

294 }

295}

296

299 intervals_[index]->SetPerformed(true);

300 int forward_frontier = 0;

301 while (forward_frontier != nexts_.size() &&

302 nexts_[forward_frontier]->Bound()) {

303 forward_frontier = nexts_[forward_frontier]->Min();

304 if (forward_frontier == IndexToValue(index)) {

305 return;

306 }

307 }

308 DCHECK_LT(forward_frontier, nexts_.size());

309 nexts_[forward_frontier]->SetValue(IndexToValue(index));

310}

311

314 const int forward_frontier = ComputeForwardFrontier();

315 if (forward_frontier < nexts_.size()) {

316 nexts_[forward_frontier]->RemoveValue(IndexToValue(index));

317 }

318}

319

322 intervals_[index]->SetPerformed(true);

323 UpdatePrevious();

324 int backward_frontier = nexts_.size();

325 while (previous_[backward_frontier] != -1) {

326 backward_frontier = previous_[backward_frontier];

327 if (backward_frontier == IndexToValue(index)) {

328 return;

329 }

330 }

331 DCHECK_NE(backward_frontier, 0);

332 nexts_[IndexToValue(index)]->SetValue(backward_frontier);

333}

334

337 const int backward_frontier = ComputeBackwardFrontier();

338 nexts_[IndexToValue(index)]->RemoveValue(backward_frontier);

339}

340

341void SequenceVar::UpdatePrevious() const {

342 for (int i = 0; i < intervals_.size() + 2; ++i) {

343 previous_[i] = -1;

344 }

345 for (int i = 0; i < nexts_.size(); ++i) {

346 if (nexts_[i]->Bound()) {

347 previous_[nexts_[i]->Min()] = i;

348 }

349 }

350}

351

353 std::vector<int>* const rank_last,

354 std::vector<int>* const unperformed) const {

355 CHECK(rank_first != nullptr);

356 CHECK(rank_last != nullptr);

357 CHECK(unperformed != nullptr);

358 rank_first->clear();

359 rank_last->clear();

360 unperformed->clear();

361 for (int i = 0; i < intervals_.size(); ++i) {

362 if (intervals_[i]->CannotBePerformed()) {

363 unperformed->push_back(i);

364 }

365 }

366 int first = 0;

367 while (nexts_[first]->Bound()) {

368 first = nexts_[first]->Min();

369 if (first < nexts_.size()) {

370 rank_first->push_back(ValueToIndex(first));

371 } else {

372 break;

373 }

374 }

375 if (first != nexts_.size()) {

376 UpdatePrevious();

377 int last = nexts_.size();

378 while (previous_[last] != -1) {

379 last = previous_[last];

380 rank_last->push_back(ValueToIndex(last));

381 }

382 }

383}

384

385

386

387

388

389namespace {

390

391

392

393class ScheduleOrPostpone : public Decision {

394 public:

395 ScheduleOrPostpone(IntervalVar* const var, int64_t est, int64_t* const marker)

396 : var_(var), est_(est), marker_(marker) {}

397 ~ScheduleOrPostpone() override {}

398

399 void Apply(Solver* const s) override {

400 var_->SetPerformed(true);

401 if (est_.Value() < var_->StartMin()) {

402 est_.SetValue(s, var_->StartMin());

403 }

404 var_->SetStartRange(est_.Value(), est_.Value());

405 }

406

407 void Refute(Solver* const s) override {

408 s->SaveAndSetValue(marker_, est_.Value());

409 }

410

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

412 CHECK(visitor != nullptr);

413 visitor->VisitScheduleOrPostpone(var_, est_.Value());

414 }

415

416 std::string DebugString() const override {

417 return absl::StrFormat("ScheduleOrPostpone(%s at %d)", var_->DebugString(),

418 est_.Value());

419 }

420

421 private:

422 IntervalVar* const var_;

423 NumericalRev<int64_t> est_;

424 int64_t* const marker_;

425};

426

428 public:

429 explicit SetTimesForward(const std::vector<IntervalVar*>& vars)

430 : vars_(vars),

431 markers_(vars.size(), std::numeric_limits<int64_t>::min()) {}

432

433 ~SetTimesForward() override {}

434

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

436 int64_t best_est = std::numeric_limits<int64_t>::max();

437 int64_t best_lct = std::numeric_limits<int64_t>::max();

438 int support = -1;

439

440

441

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

443 IntervalVar* const v = vars_[i];

444 if (v->MayBePerformed() && v->StartMax() != v->StartMin() &&

445 !IsPostponed(i) &&

446 (v->StartMin() < best_est ||

447 (v->StartMin() == best_est && v->EndMax() < best_lct))) {

448 best_est = v->StartMin();

449 best_lct = v->EndMax();

450 support = i;

451 }

452 }

453

454

455 if (support == -1) {

456 UnperformPostponedTaskBefore(std::numeric_limits<int64_t>::max());

457 return nullptr;

458 }

459 UnperformPostponedTaskBefore(best_est);

460 return s->RevAlloc(

461 new ScheduleOrPostpone(vars_[support], best_est, &markers_[support]));

462 }

463

464 std::string DebugString() const override { return "SetTimesForward()"; }

465

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

469 vars_);

471 }

472

473 private:

474 bool IsPostponed(int index) {

475 DCHECK(vars_[index]->MayBePerformed());

476 return vars_[index]->StartMin() <= markers_[index];

477 }

478

479 void UnperformPostponedTaskBefore(int64_t date) {

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

481 IntervalVar* const v = vars_[i];

482 if (v->MayBePerformed() && v->StartMin() != v->StartMax() &&

483 IsPostponed(i) &&

484

485

486

487

488

489

490

491 (v->EndMin() <= date || v->StartMax() <= date)) {

492 v->SetPerformed(false);

493 }

494 }

495 }

496

497 const std::vector<IntervalVar*> vars_;

498 std::vector<int64_t> markers_;

499};

500

501

502

503

504class ScheduleOrExpedite : public Decision {

505 public:

506 ScheduleOrExpedite(IntervalVar* const var, int64_t est, int64_t* const marker)

507 : var_(var), est_(est), marker_(marker) {}

508 ~ScheduleOrExpedite() override {}

509

510 void Apply(Solver* const s) override {

511 var_->SetPerformed(true);

512 if (est_.Value() > var_->EndMax()) {

513 est_.SetValue(s, var_->EndMax());

514 }

515 var_->SetEndRange(est_.Value(), est_.Value());

516 }

517

518 void Refute(Solver* const s) override {

519 s->SaveAndSetValue(marker_, est_.Value() - 1);

520 }

521

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

523 CHECK(visitor != nullptr);

524 visitor->VisitScheduleOrExpedite(var_, est_.Value());

525 }

526

527 std::string DebugString() const override {

528 return absl::StrFormat("ScheduleOrExpedite(%s at %d)", var_->DebugString(),

529 est_.Value());

530 }

531

532 private:

533 IntervalVar* const var_;

534 NumericalRev<int64_t> est_;

535 int64_t* const marker_;

536};

537

539 public:

540 explicit SetTimesBackward(const std::vector<IntervalVar*>& vars)

541 : vars_(vars),

542 markers_(vars.size(), std::numeric_limits<int64_t>::max()) {}

543

544 ~SetTimesBackward() override {}

545

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

547 int64_t best_end = std::numeric_limits<int64_t>::min();

548 int64_t best_start = std::numeric_limits<int64_t>::min();

549 int support = -1;

550 int refuted = 0;

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

552 IntervalVar* const v = vars_[i];

553 if (v->MayBePerformed() && v->EndMax() > v->EndMin()) {

554 if (v->EndMax() <= markers_[i] &&

555 (v->EndMax() > best_end ||

556 (v->EndMax() == best_end && v->StartMin() > best_start))) {

557 best_end = v->EndMax();

558 best_start = v->StartMin();

559 support = i;

560 } else {

561 refuted++;

562 }

563 }

564 }

565

566

567 if (support == -1) {

568 if (refuted == 0) {

569 return nullptr;

570 } else {

571 s->Fail();

572 }

573 }

574 return s->RevAlloc(new ScheduleOrExpedite(

575 vars_[support], vars_[support]->EndMax(), &markers_[support]));

576 }

577

578 std::string DebugString() const override { return "SetTimesBackward()"; }

579

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

583 vars_);

585 }

586

587 private:

588 const std::vector<IntervalVar*> vars_;

589 std::vector<int64_t> markers_;

590};

591

592

593

594class RankFirst : public Decision {

595 public:

596 RankFirst(SequenceVar* const seq, int index)

597 : sequence_(seq), index_(index) {}

598 ~RankFirst() override {}

599

600 void Apply(Solver* const s) override { sequence_->RankFirst(index_); }

601

602 void Refute(Solver* const s) override { sequence_->RankNotFirst(index_); }

603

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

605 CHECK(visitor != nullptr);

606 visitor->VisitRankFirstInterval(sequence_, index_);

607 }

608

609 std::string DebugString() const override {

610 return absl::StrFormat("RankFirst(%s, %d)", sequence_->DebugString(),

611 index_);

612 }

613

614 private:

615 SequenceVar* const sequence_;

616 const int index_;

617};

618

619class RankLast : public Decision {

620 public:

621 RankLast(SequenceVar* const seq, int index) : sequence_(seq), index_(index) {}

622 ~RankLast() override {}

623

624 void Apply(Solver* const s) override { sequence_->RankLast(index_); }

625

626 void Refute(Solver* const s) override { sequence_->RankNotLast(index_); }

627

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

629 CHECK(visitor != nullptr);

630 visitor->VisitRankLastInterval(sequence_, index_);

631 }

632

633 std::string DebugString() const override {

634 return absl::StrFormat("RankLast(%s, %d)", sequence_->DebugString(),

635 index_);

636 }

637

638 private:

639 SequenceVar* const sequence_;

640 const int index_;

641};

642

644 public:

645 RankFirstIntervalVars(const std::vector<SequenceVar*>& sequences,

647 : sequences_(sequences), strategy_(str) {}

648

649 ~RankFirstIntervalVars() override {}

650

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

652 SequenceVar* best_sequence = nullptr;

653 best_possible_firsts_.clear();

654 while (true) {

655 if (FindSequenceVar(s, &best_sequence)) {

656

657 DCHECK(best_sequence != nullptr);

658 if (best_possible_firsts_.size() == 1 &&

659 best_sequence->Interval(best_possible_firsts_.back())

660 ->MustBePerformed()) {

661 best_sequence->RankFirst(best_possible_firsts_.back());

662 continue;

663 }

664 int best_interval = -1;

665 if (!FindIntervalVar(s, best_sequence, &best_interval)) {

666 s->Fail();

667 }

668 CHECK_NE(-1, best_interval);

669 return s->RevAlloc(new RankFirst(best_sequence, best_interval));

670 } else {

671 return nullptr;

672 }

673 }

674 }

675

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

679 sequences_);

681 }

682

683 private:

684

685 bool FindIntervalVarOnStartMin(Solver* const s,

686 SequenceVar* const best_sequence,

687 int* const best_interval_index) {

688 int best_interval = -1;

689 int64_t best_start_min = std::numeric_limits<int64_t>::max();

690 for (int index = 0; index < best_possible_firsts_.size(); ++index) {

691 const int candidate = best_possible_firsts_[index];

692 IntervalVar* const interval = best_sequence->Interval(candidate);

693 if (interval->StartMin() < best_start_min) {

694 best_interval = candidate;

695 best_start_min = interval->StartMin();

696 }

697 }

698 if (best_interval == -1) {

699 return false;

700 } else {

701 *best_interval_index = best_interval;

702 return true;

703 }

704 }

705

706 bool FindIntervalVarRandomly(Solver* const s,

707 SequenceVar* const best_sequence,

708 int* const best_interval_index) {

709 DCHECK(!best_possible_firsts_.empty());

710 const int index = s->Rand32(best_possible_firsts_.size());

711 *best_interval_index = best_possible_firsts_[index];

712 return true;

713 }

714

715 bool FindIntervalVar(Solver* const s, SequenceVar* const best_sequence,

716 int* const best_interval_index) {

717 switch (strategy_) {

721 return FindIntervalVarOnStartMin(s, best_sequence, best_interval_index);

723 return FindIntervalVarRandomly(s, best_sequence, best_interval_index);

724 default:

725 LOG(FATAL) << "Unknown strategy " << strategy_;

726 return false;

727 }

728 }

729

730

731 bool FindSequenceVarOnSlack(Solver* const s,

732 SequenceVar** const best_sequence) {

733 int64_t best_slack = std::numeric_limits<int64_t>::max();

734 int64_t best_ahmin = std::numeric_limits<int64_t>::max();

735 *best_sequence = nullptr;

736 best_possible_firsts_.clear();

737 for (int i = 0; i < sequences_.size(); ++i) {

738 SequenceVar* const candidate_sequence = sequences_[i];

739 int ranked = 0;

740 int not_ranked = 0;

741 int unperformed = 0;

742 candidate_sequence->ComputeStatistics(&ranked, &not_ranked, &unperformed);

743 if (not_ranked > 0) {

744 candidate_possible_firsts_.clear();

745 candidate_possible_lasts_.clear();

746 candidate_sequence->ComputePossibleFirstsAndLasts(

747 &candidate_possible_firsts_, &candidate_possible_lasts_);

748

749 if (candidate_possible_firsts_.empty()) {

750 s->Fail();

751 }

752

753 if (candidate_possible_firsts_.size() == 1 &&

754 candidate_sequence->Interval(candidate_possible_firsts_.back())

755 ->MustBePerformed()) {

756 *best_sequence = candidate_sequence;

757 best_possible_firsts_ = candidate_possible_firsts_;

758 return true;

759 }

760

761

762 int64_t hmin, hmax, dmin, dmax;

763 candidate_sequence->HorizonRange(&hmin, &hmax);

764 candidate_sequence->DurationRange(&dmin, &dmax);

765 int64_t ahmin, ahmax;

766 candidate_sequence->ActiveHorizonRange(&ahmin, &ahmax);

767 const int64_t current_slack = (hmax - hmin - dmax);

768 if (current_slack < best_slack ||

769 (current_slack == best_slack && ahmin < best_ahmin)) {

770 best_slack = current_slack;

771 *best_sequence = candidate_sequence;

772 best_possible_firsts_ = candidate_possible_firsts_;

773 best_ahmin = ahmin;

774 }

775 }

776 }

777 return *best_sequence != nullptr;

778 }

779

780 bool FindSequenceVarRandomly(Solver* const s,

781 SequenceVar** const best_sequence) {

782 std::vector<SequenceVar*> all_candidates;

783 std::vector<std::vector<int>> all_possible_firsts;

784 for (int i = 0; i < sequences_.size(); ++i) {

785 SequenceVar* const candidate_sequence = sequences_[i];

786 int ranked = 0;

787 int not_ranked = 0;

788 int unperformed = 0;

789 candidate_sequence->ComputeStatistics(&ranked, &not_ranked, &unperformed);

790 if (not_ranked > 0) {

791 candidate_possible_firsts_.clear();

792 candidate_possible_lasts_.clear();

793 candidate_sequence->ComputePossibleFirstsAndLasts(

794 &candidate_possible_firsts_, &candidate_possible_lasts_);

795

796 if (candidate_possible_firsts_.empty()) {

797 s->Fail();

798 }

799

800 if (candidate_possible_firsts_.size() == 1 &&

801 candidate_sequence->Interval(candidate_possible_firsts_.back())

802 ->MustBePerformed()) {

803 *best_sequence = candidate_sequence;

804 best_possible_firsts_ = candidate_possible_firsts_;

805 return true;

806 }

807

808 all_candidates.push_back(candidate_sequence);

809 all_possible_firsts.push_back(candidate_possible_firsts_);

810 }

811 }

812 if (all_candidates.empty()) {

813 return false;

814 }

815 const int chosen = s->Rand32(all_candidates.size());

816 *best_sequence = all_candidates[chosen];

817 best_possible_firsts_ = std::move(all_possible_firsts[chosen]);

818 return true;

819 }

820

821 bool FindSequenceVar(Solver* const s, SequenceVar** const best_sequence) {

822 switch (strategy_) {

826 return FindSequenceVarOnSlack(s, best_sequence);

828 return FindSequenceVarRandomly(s, best_sequence);

829 default:

830 LOG(FATAL) << "Unknown strategy " << strategy_;

831 }

832 }

833

834 const std::vector<SequenceVar*> sequences_;

836 std::vector<int> best_possible_firsts_;

837 std::vector<int> candidate_possible_firsts_;

838 std::vector<int> candidate_possible_lasts_;

839};

840}

841

843 int64_t* const marker) {

844 CHECK(var != nullptr);

845 CHECK(marker != nullptr);

846 return RevAlloc(new ScheduleOrPostpone(var, est, marker));

847}

848

850 int64_t* const marker) {

851 CHECK(var != nullptr);

852 CHECK(marker != nullptr);

853 return RevAlloc(new ScheduleOrExpedite(var, est, marker));

854}

855

858 switch (str) {

862 return RevAlloc(new SetTimesForward(intervals));

864 return RevAlloc(new SetTimesBackward(intervals));

865 default:

866 LOG(FATAL) << "Unknown strategy " << str;

867 }

868}

869

871 int index) {

872 CHECK(sequence != nullptr);

873 return RevAlloc(new RankFirst(sequence, index));

874}

875

877 CHECK(sequence != nullptr);

878 return RevAlloc(new RankLast(sequence, index));

879}

880

883 return RevAlloc(new RankFirstIntervalVars(sequences, str));

884}

885

886}

virtual int64_t Min() const =0

virtual bool Contains(int64_t v) const =0

virtual int64_t DurationMax() const =0

virtual int64_t EndMax() const =0

virtual bool MayBePerformed() const =0

virtual int64_t DurationMin() const =0

These methods query, set, and watch the duration of the interval var.

virtual int64_t StartMin() const =0

virtual bool MustBePerformed() const =0

virtual void VisitSequenceVariable(const SequenceVar *variable)

static const char kSequencesArgument[]

static const char kVariableGroupExtension[]

static const char kIntervalsArgument[]

virtual std::string name() const

Object naming.

void set_name(absl::string_view name)

PropagationBaseObject(Solver *const s)

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

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

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

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

SequenceVar modifiers.

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

void RankNotFirst(int index)

Definition sched_search.cc:312

void HorizonRange(int64_t *hmin, int64_t *hmax) const

Definition sched_search.cc:97

~SequenceVar() override

Definition sched_search.cc:53

virtual void Accept(ModelVisitor *visitor) const

Accepts the given visitor.

Definition sched_search.cc:76

void RankNotLast(int index)

Definition sched_search.cc:335

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

Definition sched_search.cc:272

IntervalVar * Interval(int index) const

Returns the index_th interval of the sequence.

Definition sched_search.cc:55

void ComputePossibleFirstsAndLasts(std::vector< int > *possible_firsts, std::vector< int > *possible_lasts)

Definition sched_search.cc:194

void RankLast(int index)

Definition sched_search.cc:320

int64_t size() const

Returns the number of interval vars in the sequence.

IntVar * Next(int index) const

Returns the next of the index_th interval of the sequence.

Definition sched_search.cc:59

SequenceVar(Solver *s, const std::vector< IntervalVar * > &intervals, const std::vector< IntVar * > &nexts, const std::string &name)

Definition sched_search.cc:42

void RankFirst(int index)

Definition sched_search.cc:297

void ComputeStatistics(int *ranked, int *not_ranked, int *unperformed) const

Compute statistics on the sequence.

Definition sched_search.cc:150

void FillSequence(std::vector< int > *rank_first, std::vector< int > *rank_last, std::vector< int > *unperformed) const

Definition sched_search.cc:352

std::string DebugString() const override

Definition sched_search.cc:61

void ActiveHorizonRange(int64_t *hmin, int64_t *hmax) const

Definition sched_search.cc:112

void DurationRange(int64_t *dmin, int64_t *dmax) const

Definition sched_search.cc:80

Decision * MakeRankLastInterval(SequenceVar *sequence, int index)

Definition sched_search.cc:876

DecisionBuilder * MakePhase(const std::vector< IntVar * > &vars, IntVarStrategy var_str, IntValueStrategy val_str)

Phases on IntVar arrays.

Decision * MakeScheduleOrExpedite(IntervalVar *var, int64_t est, int64_t *marker)

Definition sched_search.cc:849

SequenceStrategy

Used for scheduling. Not yet implemented.

@ CHOOSE_RANDOM_RANK_FORWARD

@ CHOOSE_MIN_SLACK_RANK_FORWARD

Decision * MakeRankFirstInterval(SequenceVar *sequence, int index)

Definition sched_search.cc:870

Decision * MakeScheduleOrPostpone(IntervalVar *var, int64_t est, int64_t *marker)

Definition sched_search.cc:842

@ INTERVAL_SET_TIMES_FORWARD

@ INTERVAL_DEFAULT

The default is INTERVAL_SET_TIMES_FORWARD.

@ INTERVAL_SET_TIMES_BACKWARD

@ INTERVAL_SIMPLE

The simple is INTERVAL_SET_TIMES_FORWARD.

PropagationMonitor * GetPropagationMonitor() const

Returns the propagation monitor.

std::string JoinDebugStringPtr(const std::vector< T > &v, absl::string_view separator)