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

16#include <algorithm>

17#include <cstddef>

18#include <cstdint>

19#include <memory>

20#include <string>

21#include <utility>

22#include <vector>

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

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

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

37 public:

39 : solver_(s), pack_(pack) {}

42 virtual void Post() = 0;

43 virtual void InitialPropagate(int bin_index, const std::vector<int>& forced,

44 const std::vector<int>& undecided) = 0;

46 const std::vector<int>& assigned, const std::vector<int>& unassigned) = 0;

48 virtual void Propagate(int bin_index, const std::vector<int>& forced,

49 const std::vector<int>& removed) = 0;

51 const std::vector<int>& unassigned) = 0;

53 std::string DebugString() const override { return "Dimension"; }

58 bool IsUndecided(int var_index, int bin_index) const {

59 return pack_->IsUndecided(var_index, bin_index);

60 }

62 bool IsPossible(int var_index, int bin_index) const {

63 return pack_->IsPossible(var_index, bin_index);

64 }

67 return pack_->AssignVar(var_index, bin_index);

68 }

71 pack_->SetImpossible(var_index, bin_index);

72 }

74 void Assign(int var_index, int bin_index) {

75 pack_->Assign(var_index, bin_index);

76 }

79 return pack_->IsAssignedStatusKnown(var_index);

80 }

82 void SetAssigned(int var_index) { pack_->SetAssigned(var_index); }

84 void SetUnassigned(int var_index) { pack_->SetUnassigned(var_index); }

87 pack_->RemoveAllPossibleFromBin(bin_index);

88 }

91 pack_->AssignAllPossibleToBin(bin_index);

92 }

95 pack_->AssignFirstPossibleToBin(bin_index);

96 }

101

102 private:

103 Solver* const solver_;

104 Pack* const pack_;

105};

106

107

108

110 int number_of_bins)

112 vars_(vars),

113 bins_(number_of_bins),

114 unprocessed_(new RevBitMatrix(bins_ + 1, vars_.size())),

115 forced_(bins_ + 1),

116 removed_(bins_ + 1),

117 holes_(vars_.size()),

118 stamp_(uint64_t{0}),

119 demon_(nullptr),

120 in_process_(false) {

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

122 holes_[i] = vars_[i]->MakeHoleIterator(true);

123 }

124}

125

127

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

130 IntVar* const var = vars_[i];

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

133 "OneDomain", i);

135 }

136 }

137 for (int i = 0; i < dims_.size(); ++i) {

138 dims_[i]->Post();

139 }

142}

143

145 for (int bin_index = 0; bin_index <= bins_; ++bin_index) {

146 forced_[bin_index].clear();

147 removed_[bin_index].clear();

148 }

149 to_set_.clear();

150 to_unset_.clear();

151 in_process_ = false;

153}

154

156 for (int i = 0; i < to_set_.size(); ++i) {

157 vars_[to_set_[i].first]->SetValue(to_set_[i].second);

158 }

159 for (int i = 0; i < to_unset_.size(); ++i) {

160 vars_[to_unset_[i].first]->RemoveValue(to_unset_[i].second);

161 }

162}

163

164

165

166namespace {

167class InitialPropagateData : public BaseObject {

168 public:

169 explicit InitialPropagateData(size_t num_bins)

170 : BaseObject(), undecided_(num_bins) {}

171 void PushAssigned(int index) { assigned_.push_back(index); }

172 void PushUnassigned(int index) { unassigned_.push_back(index); }

173 void PushUndecided(int bin, int index) {

174 undecided_.at(bin).push_back(index);

175 }

176 const std::vector<int>& undecided(int bin) const {

177 return undecided_.at(bin);

178 }

179 const std::vector<int>& assigned() const { return assigned_; }

180 const std::vector<int>& unassigned() const { return unassigned_; }

181

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

183

184 private:

185 std::vector<std::vector<int>> undecided_;

186 std::vector<int> unassigned_;

187 std::vector<int> assigned_;

188};

189}

190

195 in_process_ = true;

196 InitialPropagateData* data = s->RevAlloc(new InitialPropagateData(bins_));

197 for (int var_index = 0; var_index < vars_.size(); ++var_index) {

198 IntVar* const var = vars_[var_index];

199 var->SetRange(0, bins_);

200 if (var->Bound()) {

201 const int64_t value = var->Min();

202 if (value < bins_) {

203 forced_[value].push_back(var_index);

204 data->PushAssigned(var_index);

205 } else {

206 data->PushUnassigned(var_index);

207 }

208 } else {

209 DCHECK_GT(bins_, var->Min())

210 << "The variable maximum should be at most " << bins_

211 << ", and it should be unbound, so its min is expected to be less "

212 << "than " << bins_;

213 if (var->Max() < bins_) {

214 data->PushAssigned(var_index);

215 }

218 if (value >= 0 && value <= bins_) {

219 unprocessed_->SetToOne(s, value, var_index);

220 if (value != bins_) {

221 data->PushUndecided(value, var_index);

222 }

223 }

224 }

225 }

226 }

227 for (int bin_index = 0; bin_index < bins_; ++bin_index) {

228 if (need_context) {

230 absl::StrFormat("Pack(bin %d, forced = [%s], undecided = [%s])",

231 bin_index, absl::StrJoin(forced_[bin_index], ", "),

232 absl::StrJoin(data->undecided(bin_index), ", ")));

233 }

234

235 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {

236 if (need_context) {

238 "InitialProgateDimension(%s)", dims_[dim_index]->DebugString()));

239 }

240 dims_[dim_index]->InitialPropagate(bin_index, forced_[bin_index],

241 data->undecided(bin_index));

242 if (need_context) {

244 }

245 }

246 if (need_context) {

248 }

249 }

250 if (need_context) {

252 absl::StrFormat("Pack(assigned = [%s], unassigned = [%s])",

253 absl::StrJoin(data->assigned(), ", "),

254 absl::StrJoin(data->unassigned(), ", ")));

255 }

256 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {

257 if (need_context) {

259 "InitialProgateDimension(%s)", dims_[dim_index]->DebugString()));

260 }

261 dims_[dim_index]->InitialPropagateUnassigned(data->assigned(),

262 data->unassigned());

263 dims_[dim_index]->EndInitialPropagate();

264 if (need_context) {

266 }

267 }

268 if (need_context) {

270 }

271

274}

275

278 in_process_ = true;

279 DCHECK_EQ(stamp_, solver()->fail_stamp());

280 for (int bin_index = 0; bin_index < bins_; ++bin_index) {

281 if (!removed_[bin_index].empty() || !forced_[bin_index].empty()) {

282 if (need_context) {

284 absl::StrFormat("Pack(bin %d, forced = [%s], removed = [%s])",

285 bin_index, absl::StrJoin(forced_[bin_index], ", "),

286 absl::StrJoin(removed_[bin_index], ", ")));

287 }

288

289 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {

290 if (need_context) {

292 "ProgateDimension(%s)", dims_[dim_index]->DebugString()));

293 }

294 dims_[dim_index]->Propagate(bin_index, forced_[bin_index],

295 removed_[bin_index]);

296 if (need_context) {

298 }

299 }

300 if (need_context) {

302 }

303 }

304 }

305 if (!removed_[bins_].empty() || !forced_[bins_].empty()) {

306 if (need_context) {

308 absl::StrFormat("Pack(removed = [%s], forced = [%s])",

309 absl::StrJoin(removed_[bins_], ", "),

310 absl::StrJoin(forced_[bins_], ", ")));

311 }

312

313 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {

314 if (need_context) {

316 "ProgateDimension(%s)", dims_[dim_index]->DebugString()));

317 }

318 dims_[dim_index]->PropagateUnassigned(removed_[bins_], forced_[bins_]);

319 if (need_context) {

321 }

322 }

323 if (need_context) {

325 }

326 }

327 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {

328 dims_[dim_index]->EndPropagate();

329 }

330

333}

334

336

337

339 const uint64_t current_stamp = s->fail_stamp();

340 if (stamp_ < current_stamp) {

341 stamp_ = current_stamp;

343 }

344 IntVar* const var = vars_[var_index];

345 bool bound = var->Bound();

346 const int64_t oldmin = var->OldMin();

347 const int64_t oldmax = var->OldMax();

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

349 const int64_t vmax = var->Max();

350 for (int64_t value = std::max(oldmin, int64_t{0});

351 value < std::min(vmin, bins_ + int64_t{1}); ++value) {

352 if (unprocessed_->IsSet(value, var_index)) {

353 unprocessed_->SetToZero(s, value, var_index);

354 removed_[value].push_back(var_index);

355 }

356 }

357 if (!bound) {

358 for (const int64_t value : InitAndGetValues(holes_[var_index])) {

359 if (value >= std::max(int64_t{0}, vmin) &&

360 value <= std::min(static_cast<int64_t>(bins_), vmax)) {

361 DCHECK(unprocessed_->IsSet(value, var_index));

362 unprocessed_->SetToZero(s, value, var_index);

363 removed_[value].push_back(var_index);

364 }

365 }

366 }

367 for (int64_t value = std::max(vmax + 1, int64_t{0});

368 value <= std::min(oldmax, static_cast<int64_t>(bins_)); ++value) {

369 if (unprocessed_->IsSet(value, var_index)) {

370 unprocessed_->SetToZero(s, value, var_index);

371 removed_[value].push_back(var_index);

372 }

373 }

374 if (bound) {

375 unprocessed_->SetToZero(s, var->Min(), var_index);

376 forced_[var->Min()].push_back(var_index);

377 }

379}

380

382 std::string result = "Pack([";

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

384 result += vars_[i]->DebugString() + " ";

385 }

386 result += "], dimensions = [";

387 for (int i = 0; i < dims_.size(); ++i) {

388 result += dims_[i]->DebugString() + " ";

389 }

390 absl::StrAppendFormat(&result, "], bins = %d)", bins_);

391 return result;

392}

393

397 vars_);

399 for (int i = 0; i < dims_.size(); ++i) {

400 dims_[i]->Accept(visitor);

401 }

403}

404

406 return unprocessed_->IsSet(bin_index, var_index);

407}

408

410 if (IsInProcess()) {

411 to_unset_.push_back(std::make_pair(var_index, bin_index));

412 } else {

413 vars_[var_index]->RemoveValue(bin_index);

414 }

415}

416

418 if (IsInProcess()) {

419 to_set_.push_back(std::make_pair(var_index, bin_index));

420 } else {

421 vars_[var_index]->SetValue(bin_index);

422 }

423}

424

426 return !unprocessed_->IsSet(bins_, var_index);

427}

428

430 return vars_[var_index]->Contains(bin_index);

431}

432

436

438 if (IsInProcess()) {

439 to_unset_.push_back(std::make_pair(var_index, bins_));

440 } else {

441 vars_[var_index]->RemoveValue(bins_);

442 }

443}

444

446 if (IsInProcess()) {

447 to_set_.push_back(std::make_pair(var_index, bins_));

448 } else {

449 vars_[var_index]->SetValue(bins_);

450 }

451}

452

453bool Pack::IsInProcess() const {

455}

456

458 int var_index = unprocessed_->GetFirstBit(bin_index, 0);

459 while (var_index != -1 && var_index < vars_.size()) {

461 var_index = var_index == vars_.size() - 1

462 ? -1

463 : unprocessed_->GetFirstBit(bin_index, var_index + 1);

464 }

465}

466

468 int var_index = unprocessed_->GetFirstBit(bin_index, 0);

469 while (var_index != -1 && var_index < vars_.size()) {

470 Assign(var_index, bin_index);

471 var_index = var_index == vars_.size() - 1

472 ? -1

473 : unprocessed_->GetFirstBit(bin_index, var_index + 1);

474 }

475}

476

478 int var_index = unprocessed_->GetFirstBit(bin_index, 0);

479 if (var_index != -1 && var_index < vars_.size()) {

480 Assign(var_index, bin_index);

481 }

482}

483

485 int var_index = unprocessed_->GetFirstBit(bins_, 0);

486 while (var_index != -1 && var_index < vars_.size()) {

488 var_index = var_index == vars_.size() - 1

489 ? -1

490 : unprocessed_->GetFirstBit(bins_, var_index + 1);

491 }

492}

493

495 int var_index = unprocessed_->GetFirstBit(bins_, 0);

496 while (var_index != -1 && var_index < vars_.size()) {

498 var_index = var_index == vars_.size() - 1

499 ? -1

500 : unprocessed_->GetFirstBit(bins_, var_index + 1);

501 }

502}

503

504

505

506

507

508namespace {

509struct WeightContainer {

510 int index;

511 int64_t weight;

512 WeightContainer(int i, int64_t w) : index(i), weight(w) {}

513 bool operator<(const WeightContainer& c) const { return (weight < c.weight); }

514};

515

516void SortWeightVector(std::vector<int>* const indices,

517 std::vector<WeightContainer>* const to_sort) {

518 std::sort(to_sort->begin(), to_sort->end());

519 for (int index = 0; index < to_sort->size(); ++index) {

520 (*indices)[index] = (*to_sort)[index].index;

521 }

522 indices->resize(to_sort->size());

523}

524

525void SortIndexByWeight(std::vector<int>* const indices,

526 absl::Span<const int64_t> weights) {

527 std::vector<WeightContainer> to_sort;

528 for (int index = 0; index < indices->size(); ++index) {

529 if (weights[index] != 0) {

530 to_sort.push_back(WeightContainer((*indices)[index], weights[index]));

531 }

532 }

533 SortWeightVector(indices, &to_sort);

534}

535

536void SortIndexByWeight(std::vector<int>* const indices,

538 std::vector<WeightContainer> to_sort;

539 for (int index = 0; index < indices->size(); ++index) {

540 const int w = weights(index);

541 if (w != 0) {

542 to_sort.push_back(WeightContainer((*indices)[index], w));

543 }

544 }

545 SortWeightVector(indices, &to_sort);

546}

547

548void SortIndexByWeight(std::vector<int>* const indices,

550 std::vector<WeightContainer> to_sort;

551 for (int index = 0; index < indices->size(); ++index) {

552 const int w = weights(index, bin_index);

553 if (w != 0) {

554 to_sort.push_back(WeightContainer((*indices)[index], w));

555 }

556 }

557 SortWeightVector(indices, &to_sort);

558}

559

560class DimensionLessThanConstant : public Dimension {

561 public:

562 DimensionLessThanConstant(Solver* const s, Pack* const p,

563 const std::vector<int64_t>& weights,

564 const std::vector<int64_t>& upper_bounds)

565 : Dimension(s, p),

566 vars_count_(weights.size()),

567 weights_(weights),

568 bins_count_(upper_bounds.size()),

569 upper_bounds_(upper_bounds),

570 first_unbound_backward_vector_(bins_count_, 0),

571 sum_of_bound_variables_vector_(bins_count_, 0LL),

572 ranked_(vars_count_) {

573 for (int i = 0; i < vars_count_; ++i) {

574 ranked_[i] = i;

575 }

576 SortIndexByWeight(&ranked_, weights_);

577 }

578

579 ~DimensionLessThanConstant() override {}

580

581 void Post() override {}

582

583 void PushFromTop(int bin_index) {

584 const int64_t slack =

585 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];

586 if (slack < 0) {

587 solver()->Fail();

588 }

589 int last_unbound = first_unbound_backward_vector_[bin_index];

590 for (; last_unbound >= 0; --last_unbound) {

591 const int var_index = ranked_[last_unbound];

592 if (IsUndecided(var_index, bin_index)) {

593 if (weights_[var_index] > slack) {

594 SetImpossible(var_index, bin_index);

595 } else {

596 break;

597 }

598 }

599 }

600 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);

601 }

602

603 void InitialPropagate(int bin_index, const std::vector<int>& forced,

604 const std::vector<int>& undecided) override {

605 Solver* const s = solver();

606 int64_t sum = 0LL;

607 for (const int value : forced) {

608 sum += weights_[value];

609 }

610 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

611 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);

612 PushFromTop(bin_index);

613 }

614

615 void EndInitialPropagate() override {}

616

617 void Propagate(int bin_index, const std::vector<int>& forced,

618 const std::vector<int>& removed) override {

619 if (!forced.empty()) {

620 Solver* const s = solver();

621 int64_t sum = sum_of_bound_variables_vector_[bin_index];

622 for (const int value : forced) {

623 sum += weights_[value];

624 }

625 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

626 PushFromTop(bin_index);

627 }

628 }

629 void InitialPropagateUnassigned(const std::vector<int>& assigned,

630 const std::vector<int>& unassigned) override {

631 }

632 void PropagateUnassigned(const std::vector<int>& assigned,

633 const std::vector<int>& unassigned) override {}

634

635 void EndPropagate() override {}

636

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

640 weights_);

642 upper_bounds_);

644 }

645

646 private:

647 const int vars_count_;

648 const std::vector<int64_t> weights_;

649 const int bins_count_;

650 const std::vector<int64_t> upper_bounds_;

651 RevArray<int> first_unbound_backward_vector_;

652 RevArray<int64_t> sum_of_bound_variables_vector_;

653 std::vector<int> ranked_;

654};

655

656class DimensionSumCallbackLessThanConstant : public Dimension {

657 public:

658 DimensionSumCallbackLessThanConstant(Solver* const s, Pack* const p,

660 int vars_count,

661 const std::vector<int64_t>& upper_bounds)

662 : Dimension(s, p),

663 vars_count_(vars_count),

664 weights_(weights),

665 bins_count_(upper_bounds.size()),

666 upper_bounds_(upper_bounds),

667 first_unbound_backward_vector_(bins_count_, 0),

668 sum_of_bound_variables_vector_(bins_count_, 0LL),

669 ranked_(vars_count_) {

670 DCHECK(weights);

671 DCHECK_GT(vars_count, 0);

672 for (int i = 0; i < vars_count_; ++i) {

673 ranked_[i] = i;

674 }

675 SortIndexByWeight(&ranked_, weights_);

676 }

677

678 ~DimensionSumCallbackLessThanConstant() override {}

679

680 void Post() override {}

681

682 void PushFromTop(int bin_index) {

683 const int64_t slack =

684 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];

685 if (slack < 0) {

686 solver()->Fail();

687 }

688 int last_unbound = first_unbound_backward_vector_[bin_index];

689 for (; last_unbound >= 0; --last_unbound) {

690 const int var_index = ranked_[last_unbound];

691 if (IsUndecided(var_index, bin_index)) {

692 if (weights_(var_index) > slack) {

693 SetImpossible(var_index, bin_index);

694 } else {

695 break;

696 }

697 }

698 }

699 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);

700 }

701

702 void InitialPropagate(int bin_index, const std::vector<int>& forced,

703 const std::vector<int>& undecided) override {

704 Solver* const s = solver();

705 int64_t sum = 0LL;

706 for (const int value : forced) {

707 sum += weights_(value);

708 }

709 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

710 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);

711 PushFromTop(bin_index);

712 }

713

714 void EndInitialPropagate() override {}

715

716 void Propagate(int bin_index, const std::vector<int>& forced,

717 const std::vector<int>& removed) override {

718 if (!forced.empty()) {

719 Solver* const s = solver();

720 int64_t sum = sum_of_bound_variables_vector_[bin_index];

721 for (const int value : forced) {

722 sum += weights_(value);

723 }

724 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

725 PushFromTop(bin_index);

726 }

727 }

728 void InitialPropagateUnassigned(const std::vector<int>& assigned,

729 const std::vector<int>& unassigned) override {

730 }

731 void PropagateUnassigned(const std::vector<int>& assigned,

732 const std::vector<int>& unassigned) override {}

733

734 void EndPropagate() override {}

735

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

738

739

740

742 upper_bounds_);

744 }

745

746 private:

747 const int vars_count_;

749 const int bins_count_;

750 const std::vector<int64_t> upper_bounds_;

751 RevArray<int> first_unbound_backward_vector_;

752 RevArray<int64_t> sum_of_bound_variables_vector_;

753 std::vector<int> ranked_;

754};

755

756class DimensionLessThanConstantCallback2 : public Dimension {

757 public:

758 DimensionLessThanConstantCallback2(Solver* const s, Pack* const p,

760 int vars_count,

761 const std::vector<int64_t>& upper_bounds)

762 : Dimension(s, p),

763 vars_count_(vars_count),

764 weights_(weights),

765 bins_count_(upper_bounds.size()),

766 upper_bounds_(upper_bounds),

767 first_unbound_backward_vector_(bins_count_, 0),

768 sum_of_bound_variables_vector_(bins_count_, 0LL),

769 ranked_(bins_count_) {

770 DCHECK(weights);

771 DCHECK_GT(vars_count, 0);

772 for (int b = 0; b < bins_count_; ++b) {

773 ranked_[b].resize(vars_count);

774 for (int i = 0; i < vars_count_; ++i) {

775 ranked_[b][i] = i;

776 }

777 SortIndexByWeight(&ranked_[b], weights_, b);

778 }

779 }

780

781 ~DimensionLessThanConstantCallback2() override {}

782

783 void Post() override {}

784

785 void PushFromTop(int bin_index) {

786 const int64_t slack =

787 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];

788 if (slack < 0) {

789 solver()->Fail();

790 }

791 int last_unbound = first_unbound_backward_vector_[bin_index];

792 for (; last_unbound >= 0; --last_unbound) {

793 const int var_index = ranked_[bin_index][last_unbound];

794 if (IsUndecided(var_index, bin_index)) {

795 if (weights_(var_index, bin_index) > slack) {

796 SetImpossible(var_index, bin_index);

797 } else {

798 break;

799 }

800 }

801 }

802 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);

803 }

804

805 void InitialPropagate(int bin_index, const std::vector<int>& forced,

806 const std::vector<int>& undecided) override {

807 Solver* const s = solver();

808 int64_t sum = 0LL;

809 for (const int value : forced) {

810 sum += weights_(value, bin_index);

811 }

812 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

813 first_unbound_backward_vector_.SetValue(s, bin_index,

814 ranked_[bin_index].size() - 1);

815 PushFromTop(bin_index);

816 }

817

818 void EndInitialPropagate() override {}

819

820 void Propagate(int bin_index, const std::vector<int>& forced,

821 const std::vector<int>& removed) override {

822 if (!forced.empty()) {

823 Solver* const s = solver();

824 int64_t sum = sum_of_bound_variables_vector_[bin_index];

825 for (const int value : forced) {

826 sum += weights_(value, bin_index);

827 }

828 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

829 PushFromTop(bin_index);

830 }

831 }

832 void InitialPropagateUnassigned(const std::vector<int>& assigned,

833 const std::vector<int>& unassigned) override {

834 }

835 void PropagateUnassigned(const std::vector<int>& assigned,

836 const std::vector<int>& unassigned) override {}

837

838 void EndPropagate() override {}

839

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

842

843

844

846 upper_bounds_);

848 }

849

850 private:

851 const int vars_count_;

853 const int bins_count_;

854 const std::vector<int64_t> upper_bounds_;

855 RevArray<int> first_unbound_backward_vector_;

856 RevArray<int64_t> sum_of_bound_variables_vector_;

857 std::vector<std::vector<int>> ranked_;

858};

859

860class DimensionWeightedSumEqVar : public Dimension {

861 public:

862 class VarDemon : public Demon {

863 public:

864 VarDemon(DimensionWeightedSumEqVar* const dim, int index)

865 : dim_(dim), index_(index) {}

866 ~VarDemon() override {}

867

868 void Run(Solver* const s) override { dim_->PushFromTop(index_); }

869

870 private:

871 DimensionWeightedSumEqVar* const dim_;

872 const int index_;

873 };

874

875 DimensionWeightedSumEqVar(Solver* const s, Pack* const p,

876 const std::vector<int64_t>& weights,

877 const std::vector<IntVar*>& loads)

878 : Dimension(s, p),

879 vars_count_(weights.size()),

880 weights_(weights),

881 bins_count_(loads.size()),

882 loads_(loads),

883 first_unbound_backward_vector_(bins_count_, 0),

884 sum_of_bound_variables_vector_(bins_count_, 0LL),

885 sum_of_all_variables_vector_(bins_count_, 0LL),

886 ranked_(vars_count_) {

887 DCHECK_GT(vars_count_, 0);

888 DCHECK_GT(bins_count_, 0);

889 for (int i = 0; i < vars_count_; ++i) {

890 ranked_[i] = i;

891 }

892 SortIndexByWeight(&ranked_, weights_);

893 }

894

895 ~DimensionWeightedSumEqVar() override {}

896

897 std::string DebugString() const override {

898 return "DimensionWeightedSumEqVar";

899 }

900

901 void Post() override {

902 for (int i = 0; i < bins_count_; ++i) {

903 Demon* const d = solver()->RevAlloc(new VarDemon(this, i));

904 loads_[i]->WhenRange(d);

905 }

906 }

907

908 void PushFromTop(int bin_index) {

909 IntVar* const load = loads_[bin_index];

910 const int64_t sum_min = sum_of_bound_variables_vector_[bin_index];

911 const int64_t sum_max = sum_of_all_variables_vector_[bin_index];

912 load->SetRange(sum_min, sum_max);

913 const int64_t slack_up = load->Max() - sum_min;

914 const int64_t slack_down = sum_max - load->Min();

915 DCHECK_GE(slack_down, 0);

916 DCHECK_GE(slack_up, 0);

917 int last_unbound = first_unbound_backward_vector_[bin_index];

918 for (; last_unbound >= 0; --last_unbound) {

919 const int var_index = ranked_[last_unbound];

920 const int64_t weight = weights_[var_index];

921 if (IsUndecided(var_index, bin_index)) {

922 if (weight > slack_up) {

923 SetImpossible(var_index, bin_index);

924 } else if (weight > slack_down) {

925 Assign(var_index, bin_index);

926 } else {

927 break;

928 }

929 }

930 }

931 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);

932 }

933

934 void InitialPropagate(int bin_index, const std::vector<int>& forced,

935 const std::vector<int>& undecided) override {

936 Solver* const s = solver();

937 int64_t sum = 0LL;

938 for (const int value : forced) {

939 sum += weights_[value];

940 }

941 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

942 for (const int value : undecided) {

943 sum += weights_[value];

944 }

945 sum_of_all_variables_vector_.SetValue(s, bin_index, sum);

946 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);

947 PushFromTop(bin_index);

948 }

949

950 void EndInitialPropagate() override {}

951

952 void Propagate(int bin_index, const std::vector<int>& forced,

953 const std::vector<int>& removed) override {

954 Solver* const s = solver();

955 int64_t down = sum_of_bound_variables_vector_[bin_index];

956 for (const int value : forced) {

957 down += weights_[value];

958 }

959 sum_of_bound_variables_vector_.SetValue(s, bin_index, down);

960 int64_t up = sum_of_all_variables_vector_[bin_index];

961 for (const int value : removed) {

962 up -= weights_[value];

963 }

964 sum_of_all_variables_vector_.SetValue(s, bin_index, up);

965 PushFromTop(bin_index);

966 }

967 void InitialPropagateUnassigned(const std::vector<int>& assigned,

968 const std::vector<int>& unassigned) override {

969 }

970 void PropagateUnassigned(const std::vector<int>& assigned,

971 const std::vector<int>& unassigned) override {}

972

973 void EndPropagate() override {}

974

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

978 weights_);

980 loads_);

982 }

983

984 private:

985 const int vars_count_;

986 const std::vector<int64_t> weights_;

987 const int bins_count_;

988 const std::vector<IntVar*> loads_;

989 RevArray<int> first_unbound_backward_vector_;

990 RevArray<int64_t> sum_of_bound_variables_vector_;

991 RevArray<int64_t> sum_of_all_variables_vector_;

992 std::vector<int> ranked_;

993};

994

995class DimensionWeightedCallback2SumEqVar : public Dimension {

996 public:

997 class VarDemon : public Demon {

998 public:

999 VarDemon(DimensionWeightedCallback2SumEqVar* const dim, int index)

1000 : dim_(dim), index_(index) {}

1001 ~VarDemon() override {}

1002

1003 void Run(Solver* const s) override { dim_->PushFromTop(index_); }

1004

1005 private:

1006 DimensionWeightedCallback2SumEqVar* const dim_;

1007 const int index_;

1008 };

1009

1010 DimensionWeightedCallback2SumEqVar(Solver* const s, Pack* const p,

1012 int vars_count,

1013 const std::vector<IntVar*>& loads)

1014 : Dimension(s, p),

1015 vars_count_(vars_count),

1016 weights_(weights),

1017 bins_count_(loads.size()),

1018 loads_(loads),

1019 first_unbound_backward_vector_(bins_count_, 0),

1020 sum_of_bound_variables_vector_(bins_count_, 0LL),

1021 sum_of_all_variables_vector_(bins_count_, 0LL),

1022 ranked_(bins_count_) {

1023 DCHECK(weights);

1024 DCHECK_GT(vars_count_, 0);

1025 DCHECK_GT(bins_count_, 0);

1026 for (int b = 0; b < bins_count_; ++b) {

1027 ranked_[b].resize(vars_count);

1028 for (int i = 0; i < vars_count_; ++i) {

1029 ranked_[b][i] = i;

1030 }

1031 SortIndexByWeight(&ranked_[b], weights_, b);

1032 }

1033 }

1034

1035 ~DimensionWeightedCallback2SumEqVar() override {}

1036

1037 std::string DebugString() const override {

1038 return "DimensionWeightedCallback2SumEqVar";

1039 }

1040

1041 void Post() override {

1042 for (int i = 0; i < bins_count_; ++i) {

1043 Demon* const d = solver()->RevAlloc(new VarDemon(this, i));

1044 loads_[i]->WhenRange(d);

1045 }

1046 }

1047

1048 void PushFromTop(int bin_index) {

1049 IntVar* const load = loads_[bin_index];

1050 const int64_t sum_min = sum_of_bound_variables_vector_[bin_index];

1051 const int64_t sum_max = sum_of_all_variables_vector_[bin_index];

1052 load->SetRange(sum_min, sum_max);

1053 const int64_t slack_up = load->Max() - sum_min;

1054 const int64_t slack_down = sum_max - load->Min();

1055 DCHECK_GE(slack_down, 0);

1056 DCHECK_GE(slack_up, 0);

1057 int last_unbound = first_unbound_backward_vector_[bin_index];

1058 for (; last_unbound >= 0; --last_unbound) {

1059 const int var_index = ranked_[bin_index][last_unbound];

1060 const int64_t weight = weights_(var_index, bin_index);

1061 if (IsUndecided(var_index, bin_index)) {

1062 if (weight > slack_up) {

1063 SetImpossible(var_index, bin_index);

1064 } else if (weight > slack_down) {

1065 Assign(var_index, bin_index);

1066 } else {

1067 break;

1068 }

1069 }

1070 }

1071 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);

1072 }

1073

1074 void InitialPropagate(int bin_index, const std::vector<int>& forced,

1075 const std::vector<int>& undecided) override {

1076 Solver* const s = solver();

1077 int64_t sum = 0LL;

1078 for (const int value : forced) {

1079 sum += weights_(value, bin_index);

1080 }

1081 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);

1082 for (const int value : undecided) {

1083 sum += weights_(value, bin_index);

1084 }

1085 sum_of_all_variables_vector_.SetValue(s, bin_index, sum);

1086 first_unbound_backward_vector_.SetValue(s, bin_index,

1087 ranked_[bin_index].size() - 1);

1088 PushFromTop(bin_index);

1089 }

1090

1091 void EndInitialPropagate() override {}

1092

1093 void Propagate(int bin_index, const std::vector<int>& forced,

1094 const std::vector<int>& removed) override {

1095 Solver* const s = solver();

1096 int64_t down = sum_of_bound_variables_vector_[bin_index];

1097 for (const int value : forced) {

1098 down += weights_(value, bin_index);

1099 }

1100 sum_of_bound_variables_vector_.SetValue(s, bin_index, down);

1101 int64_t up = sum_of_all_variables_vector_[bin_index];

1102 for (const int value : removed) {

1103 up -= weights_(value, bin_index);

1104 }

1105 sum_of_all_variables_vector_.SetValue(s, bin_index, up);

1106 PushFromTop(bin_index);

1107 }

1108 void InitialPropagateUnassigned(const std::vector<int>& assigned,

1109 const std::vector<int>& unassigned) override {

1110 }

1111 void PropagateUnassigned(const std::vector<int>& assigned,

1112 const std::vector<int>& unassigned) override {}

1113

1114 void EndPropagate() override {}

1115

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

1118

1119

1120

1122 loads_);

1124 }

1125

1126 private:

1127 const int vars_count_;

1129 const int bins_count_;

1130 const std::vector<IntVar*> loads_;

1131 RevArray<int> first_unbound_backward_vector_;

1132 RevArray<int64_t> sum_of_bound_variables_vector_;

1133 RevArray<int64_t> sum_of_all_variables_vector_;

1134 std::vector<std::vector<int>> ranked_;

1135};

1136

1137class AssignedWeightedSumDimension : public Dimension {

1138 public:

1139 class VarDemon : public Demon {

1140 public:

1141 explicit VarDemon(AssignedWeightedSumDimension* const dim) : dim_(dim) {}

1142 ~VarDemon() override {}

1143

1144 void Run(Solver* const s) override { dim_->PropagateAll(); }

1145

1146 private:

1147 AssignedWeightedSumDimension* const dim_;

1148 };

1149

1150 AssignedWeightedSumDimension(Solver* const s, Pack* const p,

1151 const std::vector<int64_t>& weights,

1152 int bins_count, IntVar* const cost_var)

1153 : Dimension(s, p),

1154 vars_count_(weights.size()),

1155 weights_(weights),

1156 bins_count_(bins_count),

1157 cost_var_(cost_var),

1158 first_unbound_backward_(0),

1159 sum_of_assigned_items_(0LL),

1160 sum_of_unassigned_items_(0LL),

1161 ranked_(vars_count_),

1162 sum_all_weights_(0LL) {

1163 DCHECK(cost_var);

1164 DCHECK_GT(vars_count_, 0);

1165 DCHECK_GT(bins_count_, 0);

1166 for (int i = 0; i < vars_count_; ++i) {

1167 ranked_[i] = i;

1168 }

1169 SortIndexByWeight(&ranked_, weights_);

1170 first_unbound_backward_.SetValue(s, ranked_.size() - 1);

1171 }

1172

1173 ~AssignedWeightedSumDimension() override {}

1174

1175 void Post() override {

1176 Demon* const uv = solver()->RevAlloc(new VarDemon(this));

1177 cost_var_->WhenRange(uv);

1178 }

1179

1180 void PropagateAll() {

1181 cost_var_->SetRange(sum_of_assigned_items_.Value(),

1182 sum_all_weights_ - sum_of_unassigned_items_.Value());

1183 const int64_t slack_up = cost_var_->Max() - sum_of_assigned_items_.Value();

1184 const int64_t slack_down = sum_all_weights_ - cost_var_->Min();

1185 int last_unbound = first_unbound_backward_.Value();

1186 for (; last_unbound >= 0; --last_unbound) {

1187 const int var_index = ranked_[last_unbound];

1188 if (!IsAssignedStatusKnown(var_index)) {

1189 const int64_t coefficient = weights_[var_index];

1190 if (coefficient > slack_up) {

1191 SetUnassigned(var_index);

1192 } else if (coefficient > slack_down) {

1193 SetAssigned(var_index);

1194 } else {

1195 break;

1196 }

1197 }

1198 }

1199 first_unbound_backward_.SetValue(solver(), last_unbound);

1200 }

1201

1202 void InitialPropagate(int bin_index, const std::vector<int>& forced,

1203 const std::vector<int>& undecided) override {}

1204

1205 void EndInitialPropagate() override {}

1206

1207 void InitialPropagateUnassigned(const std::vector<int>& assigned,

1208 const std::vector<int>& unassigned) override {

1209 for (int index = 0; index < vars_count_; ++index) {

1210 sum_all_weights_ += weights_[index];

1211 }

1212

1213 PropagateUnassigned(assigned, unassigned);

1214 }

1215

1216 void Propagate(int bin_index, const std::vector<int>& forced,

1217 const std::vector<int>& removed) override {}

1218

1219 void PropagateUnassigned(const std::vector<int>& assigned,

1220 const std::vector<int>& unassigned) override {

1221 int64_t sum_assigned = sum_of_assigned_items_.Value();

1222 for (int index = 0; index < assigned.size(); ++index) {

1223 const int var_index = assigned[index];

1224 sum_assigned += weights_[var_index];

1225 }

1226

1227 int64_t sum_unassigned = sum_of_unassigned_items_.Value();

1228 for (int index = 0; index < unassigned.size(); ++index) {

1229 const int var_index = unassigned[index];

1230 sum_unassigned += weights_[var_index];

1231 }

1232

1233 Solver* const s = solver();

1234 sum_of_assigned_items_.SetValue(s, sum_assigned);

1235 sum_of_unassigned_items_.SetValue(s, sum_unassigned);

1236 PropagateAll();

1237 }

1238

1239 void EndPropagate() override {}

1240

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

1242 visitor->BeginVisitExtension(

1245 weights_);

1247 cost_var_);

1248 visitor->EndVisitExtension(

1250 }

1251

1252 private:

1253 const int vars_count_;

1254 const std::vector<int64_t> weights_;

1255 const int bins_count_;

1256 IntVar* const cost_var_;

1257 Rev<int> first_unbound_backward_;

1258 Rev<int64_t> sum_of_assigned_items_;

1259 Rev<int64_t> sum_of_unassigned_items_;

1260 std::vector<int> ranked_;

1261 int64_t sum_all_weights_;

1262};

1263

1264

1265

1266class CountAssignedItemsDimension : public Dimension {

1267 public:

1268 class VarDemon : public Demon {

1269 public:

1270 explicit VarDemon(CountAssignedItemsDimension* const dim) : dim_(dim) {}

1271 ~VarDemon() override {}

1272

1273 void Run(Solver* const s) override { dim_->PropagateAll(); }

1274

1275 private:

1276 CountAssignedItemsDimension* const dim_;

1277 };

1278

1279 CountAssignedItemsDimension(Solver* const s, Pack* const p, int vars_count,

1280 int bins_count, IntVar* const cost_var)

1281 : Dimension(s, p),

1282 vars_count_(vars_count),

1283 bins_count_(bins_count),

1284 cost_var_(cost_var),

1285 first_unbound_backward_(0),

1286 assigned_count_(0),

1287 unassigned_count_(0) {

1288 DCHECK(cost_var);

1289 DCHECK_GT(vars_count, 0);

1290 DCHECK_GT(bins_count, 0);

1291 }

1292

1293 ~CountAssignedItemsDimension() override {}

1294

1295 void Post() override {

1296 Demon* const uv = solver()->RevAlloc(new VarDemon(this));

1297 cost_var_->WhenRange(uv);

1298 }

1299

1300 void PropagateAll() {

1301 cost_var_->SetRange(assigned_count_.Value(),

1302 vars_count_ - unassigned_count_.Value());

1303 if (assigned_count_.Value() == cost_var_->Max()) {

1304 UnassignAllRemainingItems();

1305 } else if (cost_var_->Min() == vars_count_ - unassigned_count_.Value()) {

1306 AssignAllRemainingItems();

1307 }

1308 }

1309

1310 void InitialPropagate(int bin_index, const std::vector<int>& forced,

1311 const std::vector<int>& undecided) override {}

1312

1313 void EndInitialPropagate() override {}

1314

1315 void InitialPropagateUnassigned(const std::vector<int>& assigned,

1316 const std::vector<int>& unassigned) override {

1317 PropagateUnassigned(assigned, unassigned);

1318 }

1319

1320 void Propagate(int bin_index, const std::vector<int>& forced,

1321 const std::vector<int>& removed) override {}

1322

1323 void PropagateUnassigned(const std::vector<int>& assigned,

1324 const std::vector<int>& unassigned) override {

1325 Solver* const s = solver();

1326 assigned_count_.SetValue(s, assigned_count_.Value() + assigned.size());

1327 unassigned_count_.SetValue(s,

1328 unassigned_count_.Value() + unassigned.size());

1329 PropagateAll();

1330 }

1331

1332 void EndPropagate() override {}

1333

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

1337 cost_var_);

1339 }

1340

1341 private:

1342 const int vars_count_;

1343 const int bins_count_;

1344 IntVar* const cost_var_;

1345 Rev<int> first_unbound_backward_;

1346 Rev<int> assigned_count_;

1347 Rev<int> unassigned_count_;

1348};

1349

1350

1351

1352class CountUsedBinDimension : public Dimension {

1353 public:

1354 class VarDemon : public Demon {

1355 public:

1356 explicit VarDemon(CountUsedBinDimension* const dim) : dim_(dim) {}

1357 ~VarDemon() override {}

1358

1359 void Run(Solver* const s) override { dim_->PropagateAll(); }

1360

1361 private:

1362 CountUsedBinDimension* const dim_;

1363 };

1364

1365 CountUsedBinDimension(Solver* const s, Pack* const p, int vars_count,

1366 int bins_count, IntVar* const count_var)

1367 : Dimension(s, p),

1368 vars_count_(vars_count),

1369 bins_count_(bins_count),

1370 count_var_(count_var),

1371 used_(bins_count_),

1372 candidates_(bins_count_, 0),

1373 card_min_(0),

1374 card_max_(bins_count_),

1375 initial_min_(0),

1376 initial_max_(0) {

1377 DCHECK(count_var);

1378 DCHECK_GT(vars_count, 0);

1379 DCHECK_GT(bins_count, 0);

1380 }

1381

1382 ~CountUsedBinDimension() override {}

1383

1384 void Post() override {

1385 Demon* const uv = solver()->RevAlloc(new VarDemon(this));

1386 count_var_->WhenRange(uv);

1387 initial_min_ = 0;

1388 initial_max_ = bins_count_;

1389 }

1390

1391 void PropagateAll() {

1392 count_var_->SetRange(card_min_.Value(), card_max_.Value());

1393 if (card_min_.Value() == count_var_->Max()) {

1394 for (int bin_index = 0; bin_index < bins_count_; ++bin_index) {

1395 if (!used_.IsSet(bin_index) && candidates_[bin_index] > 0) {

1396 RemoveAllPossibleFromBin(bin_index);

1397 }

1398 }

1399 } else if (card_max_.Value() == count_var_->Min()) {

1400 for (int bin_index = 0; bin_index < bins_count_; ++bin_index) {

1401 if (candidates_[bin_index] == 1) {

1402 AssignFirstPossibleToBin(bin_index);

1403 }

1404 }

1405 }

1406 }

1407

1408 void InitialPropagate(int bin_index, const std::vector<int>& forced,

1409 const std::vector<int>& undecided) override {

1410 if (!forced.empty()) {

1411 used_.SetToOne(solver(), bin_index);

1412 initial_min_++;

1413 } else if (!undecided.empty()) {

1414 candidates_.SetValue(solver(), bin_index, undecided.size());

1415 } else {

1416 initial_max_--;

1417 }

1418 }

1419

1420 void EndInitialPropagate() override {

1421 card_min_.SetValue(solver(), initial_min_);

1422 card_max_.SetValue(solver(), initial_max_);

1423 PropagateAll();

1424 }

1425

1426 void InitialPropagateUnassigned(const std::vector<int>& assigned,

1427 const std::vector<int>& unassigned) override {

1428 }

1429

1430 void Propagate(int bin_index, const std::vector<int>& forced,

1431 const std::vector<int>& removed) override {

1432 if (!used_.IsSet(bin_index)) {

1433 if (!forced.empty()) {

1434 used_.SetToOne(solver(), bin_index);

1435 card_min_.SetValue(solver(), card_min_.Value() + 1);

1436 } else if (!removed.empty()) {

1437 candidates_.SetValue(solver(), bin_index,

1438 candidates_.Value(bin_index) - removed.size());

1439 if (candidates_[bin_index] == 0) {

1440 card_max_.SetValue(solver(), card_max_.Value() - 1);

1441 }

1442 }

1443 }

1444 }

1445

1446 void PropagateUnassigned(const std::vector<int>& assigned,

1447 const std::vector<int>& unassigned) override {}

1448

1449 void EndPropagate() override { PropagateAll(); }

1450

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

1454 count_var_);

1456 }

1457

1458 private:

1459 const int vars_count_;

1460 const int bins_count_;

1461 IntVar* const count_var_;

1462 RevBitSet used_;

1463 RevArray<int> candidates_;

1464 Rev<int> card_min_;

1465 Rev<int> card_max_;

1466 int initial_min_;

1467 int initial_max_;

1468};

1469

1470

1471

1472

1473class VariableUsageDimension : public Dimension {

1474 public:

1475 VariableUsageDimension(Solver* const solver, Pack* const pack,

1476 const std::vector<int64_t>& capacities,

1477 const std::vector<IntVar*>& weights)

1478 : Dimension(solver, pack), capacities_(capacities), weights_(weights) {}

1479

1480 ~VariableUsageDimension() override {}

1481

1482 void Post() override {

1483 Solver* const s = solver();

1484 const int num_bins = capacities_.size();

1485 const int num_items = weights_.size();

1486

1487 for (int bin_index = 0; bin_index < num_bins; ++bin_index) {

1488 std::vector<IntVar*> terms;

1489 for (int item_index = 0; item_index < num_items; ++item_index) {

1490 IntVar* const assign_var = AssignVar(item_index, bin_index);

1491 terms.push_back(s->MakeProd(assign_var, weights_[item_index])->Var());

1492 }

1493 s->AddConstraint(s->MakeSumLessOrEqual(terms, capacities_[bin_index]));

1494 }

1495 }

1496

1497 void InitialPropagate(int bin_index, const std::vector<int>& forced,

1498 const std::vector<int>& undecided) override {}

1499 void InitialPropagateUnassigned(const std::vector<int>& assigned,

1500 const std::vector<int>& unassigned) override {

1501 }

1502 void EndInitialPropagate() override {}

1503 void Propagate(int bin_index, const std::vector<int>& forced,

1504 const std::vector<int>& removed) override {}

1505 void PropagateUnassigned(const std::vector<int>& assigned,

1506 const std::vector<int>& unassigned) override {}

1507 void EndPropagate() override {}

1508

1509 std::string DebugString() const override { return "VariableUsageDimension"; }

1510

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

1512 visitor->BeginVisitExtension(

1515 capacities_);

1517 weights_);

1518 visitor->EndVisitExtension(

1520 }

1521

1522 private:

1523 const std::vector<int64_t> capacities_;

1524 const std::vector<IntVar*> weights_;

1525};

1526}

1527

1528

1529

1531 const std::vector<int64_t>& weights, const std::vector<int64_t>& bounds) {

1532 CHECK_EQ(weights.size(), vars_.size());

1533 CHECK_EQ(bounds.size(), bins_);

1536 s->RevAlloc(new DimensionLessThanConstant(s, this, weights, bounds));

1537 dims_.push_back(dim);

1538}

1539

1542 CHECK(weights != nullptr);

1543 CHECK_EQ(bounds.size(), bins_);

1545 Dimension* const dim = s->RevAlloc(new DimensionSumCallbackLessThanConstant(

1546 s, this, weights, vars_.size(), bounds));

1547 dims_.push_back(dim);

1548}

1549

1552 CHECK(weights != nullptr);

1553 CHECK_EQ(bounds.size(), bins_);

1555 Dimension* const dim = s->RevAlloc(new DimensionLessThanConstantCallback2(

1556 s, this, weights, vars_.size(), bounds));

1557 dims_.push_back(dim);

1558}

1559

1561 const std::vector<IntVar*>& loads) {

1562 CHECK_EQ(weights.size(), vars_.size());

1563 CHECK_EQ(loads.size(), bins_);

1566 s->RevAlloc(new DimensionWeightedSumEqVar(s, this, weights, loads));

1567 dims_.push_back(dim);

1568}

1569

1571 const std::vector<IntVar*>& loads) {

1572 CHECK(weights != nullptr);

1573 CHECK_EQ(loads.size(), bins_);

1575 Dimension* const dim = s->RevAlloc(new DimensionWeightedCallback2SumEqVar(

1576 s, this, weights, vars_.size(), loads));

1577 dims_.push_back(dim);

1578}

1579

1581 const std::vector<int64_t>& weights, IntVar* const cost_var) {

1582 CHECK_EQ(weights.size(), vars_.size());

1585 new AssignedWeightedSumDimension(s, this, weights, bins_, cost_var));

1586 dims_.push_back(dim);

1587}

1588

1590 const std::vector<IntVar*>& usage, const std::vector<int64_t>& capacity) {

1591 CHECK_EQ(usage.size(), vars_.size());

1592 CHECK_EQ(capacity.size(), bins_);

1595 s->RevAlloc(new VariableUsageDimension(s, this, capacity, usage));

1596 dims_.push_back(dim);

1597}

1598

1602 new CountUsedBinDimension(s, this, vars_.size(), bins_, count_var));

1603 dims_.push_back(dim);

1604}

1605

1609 new CountAssignedItemsDimension(s, this, vars_.size(), bins_, count_var));

1610 dims_.push_back(dim);

1611}

1612

1614 return RevAlloc(new Pack(this, vars, number_of_bins));

1615}

1616}

Constraint(Solver *const solver)

void SetUnassigned(int var_index)

Definition pack.cc:84

void AssignAllRemainingItems()

Definition pack.cc:98

void SetAssigned(int var_index)

Definition pack.cc:82

virtual void EndInitialPropagate()=0

bool IsPossible(int var_index, int bin_index) const

Definition pack.cc:62

virtual void EndPropagate()=0

~Dimension() override

Definition pack.cc:40

void AssignFirstPossibleToBin(int bin_index)

Definition pack.cc:94

void UnassignAllRemainingItems()

Definition pack.cc:100

void SetImpossible(int var_index, int bin_index)

Definition pack.cc:70

void AssignAllPossibleToBin(int bin_index)

Definition pack.cc:90

bool IsUndecided(int var_index, int bin_index) const

Definition pack.cc:58

std::string DebugString() const override

Definition pack.cc:53

virtual void PropagateUnassigned(const std::vector< int > &assigned, const std::vector< int > &unassigned)=0

virtual void Propagate(int bin_index, const std::vector< int > &forced, const std::vector< int > &removed)=0

virtual void InitialPropagate(int bin_index, const std::vector< int > &forced, const std::vector< int > &undecided)=0

void RemoveAllPossibleFromBin(int bin_index)

Definition pack.cc:86

IntVar * AssignVar(int var_index, int bin_index) const

Definition pack.cc:66

void Assign(int var_index, int bin_index)

Definition pack.cc:74

virtual void Accept(ModelVisitor *visitor) const =0

Solver * solver() const

Definition pack.cc:56

bool IsAssignedStatusKnown(int var_index) const

Definition pack.cc:78

virtual void InitialPropagateUnassigned(const std::vector< int > &assigned, const std::vector< int > &unassigned)=0

Dimension(Solver *const s, Pack *const pack)

Definition pack.cc:38

virtual bool Bound() const

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

virtual void SetRange(int64_t l, int64_t u)

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

virtual int64_t Min() const =0

virtual int64_t Max() const =0

virtual void WhenDomain(Demon *d)=0

virtual IntVarIterator * MakeDomainIterator(bool reversible) const =0

virtual int64_t OldMax() const =0

Returns the previous max.

virtual int64_t OldMin() const =0

Returns the previous min.

static const char kVariableUsageLessConstantExtension[]

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

Visit integer arguments.

static const char kCoefficientsArgument[]

static const char kTargetArgument[]

static const char kSizeArgument[]

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

static const char kValuesArgument[]

static const char kPack[]

static const char kUsageLessConstantExtension[]

static const char kVarsArgument[]

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

static const char kUsageEqualVariableExtension[]

static const char kCountAssignedItemsExtension[]

Extension names:

static const char kCountUsedBinsExtension[]

static const char kWeightedSumOfAssignedEqualVariableExtension[]

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

void SetUnassigned(int var_index)

Definition pack.cc:445

void SetAssigned(int var_index)

Definition pack.cc:437

void Assign(int var_index, int bin_index)

Definition pack.cc:417

bool IsPossible(int var_index, int bin_index) const

Definition pack.cc:429

void Post() override

Definition pack.cc:128

void AddCountUsedBinDimension(IntVar *count_var)

Definition pack.cc:1599

void Propagate()

Definition pack.cc:276

Pack(Solver *s, const std::vector< IntVar * > &vars, int number_of_bins)

Definition pack.cc:109

void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64_t > &weights, const std::vector< int64_t > &bounds)

Definition pack.cc:1530

void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64_t > &capacity)

Definition pack.cc:1589

void AddCountAssignedItemsDimension(IntVar *count_var)

Definition pack.cc:1606

void UnassignAllRemainingItems()

Definition pack.cc:494

void AssignAllRemainingItems()

Definition pack.cc:484

std::string DebugString() const override

Definition pack.cc:381

void AssignAllPossibleToBin(int bin_index)

Definition pack.cc:467

void Accept(ModelVisitor *visitor) const override

Accepts the given visitor.

Definition pack.cc:394

IntVar * AssignVar(int var_index, int bin_index) const

Definition pack.cc:433

bool IsAssignedStatusKnown(int var_index) const

Definition pack.cc:425

void AssignFirstPossibleToBin(int bin_index)

Definition pack.cc:477

void AddWeightedSumEqualVarDimension(const std::vector< int64_t > &weights, const std::vector< IntVar * > &loads)

Definition pack.cc:1560

void RemoveAllPossibleFromBin(int bin_index)

Definition pack.cc:457

void PropagateDelayed()

Definition pack.cc:155

~Pack() override

Definition pack.cc:126

void AddWeightedSumOfAssignedDimension(const std::vector< int64_t > &weights, IntVar *cost_var)

Definition pack.cc:1580

void InitialPropagate() override

Definition pack.cc:191

void SetImpossible(int var_index, int bin_index)

Definition pack.cc:409

void ClearAll()

Definition pack.cc:144

void OneDomain(int var_index)

Definition pack.cc:335

bool IsUndecided(int var_index, int bin_index) const

Definition pack.cc:405

void EnqueueDelayedDemon(Demon *const d)

virtual void PopContext()=0

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

Matrix version of the RevBitSet class.

Demon * RegisterDemon(Demon *demon)

Adds a new demon and wraps it inside a DemonProfiler if necessary.

uint64_t fail_stamp() const

The fail_stamp() is incremented after each backtrack.

IntVar * MakeIsEqualCstVar(IntExpr *var, int64_t value)

status var of (var == value)

std::function< int64_t(int64_t)> IndexEvaluator1

Callback typedefs.

Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)

Definition pack.cc:1613

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

PropagationMonitor * GetPropagationMonitor() const

Returns the propagation monitor.

bool InstrumentsVariables() const

Returns whether we are tracing variables.

Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)

Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)

trees with all degrees equal w the current value of w