OR-Tools  8.2
pack.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Packing constraints
15
16#include <algorithm>
17#include <cstddef>
18#include <memory>
19#include <string>
20#include <utility>
21#include <vector>
22
23#include "absl/strings/str_format.h"
24#include "absl/strings/str_join.h"
29
30namespace operations_research {
31
32// ---------- Dimension ----------
33
34class Dimension : public BaseObject {
35 public:
36 explicit Dimension(Solver* const s, Pack* const pack)
37 : solver_(s), pack_(pack) {}
38 ~Dimension() override {}
39
40 virtual void Post() = 0;
41 virtual void InitialPropagate(int bin_index, const std::vector<int>& forced,
42 const std::vector<int>& undecided) = 0;
44 const std::vector<int>& assigned, const std::vector<int>& unassigned) = 0;
45 virtual void EndInitialPropagate() = 0;
46 virtual void Propagate(int bin_index, const std::vector<int>& forced,
47 const std::vector<int>& removed) = 0;
48 virtual void PropagateUnassigned(const std::vector<int>& assigned,
49 const std::vector<int>& unassigned) = 0;
50 virtual void EndPropagate() = 0;
51 std::string DebugString() const override { return "Dimension"; }
52 virtual void Accept(ModelVisitor* const visitor) const = 0;
53
54 Solver* solver() const { return solver_; }
55
56 bool IsUndecided(int var_index, int bin_index) const {
57 return pack_->IsUndecided(var_index, bin_index);
58 }
59
60 bool IsPossible(int var_index, int bin_index) const {
61 return pack_->IsPossible(var_index, bin_index);
62 }
63
64 IntVar* AssignVar(int var_index, int bin_index) const {
65 return pack_->AssignVar(var_index, bin_index);
66 }
67
68 void SetImpossible(int var_index, int bin_index) {
69 pack_->SetImpossible(var_index, bin_index);
70 }
71
72 void Assign(int var_index, int bin_index) {
73 pack_->Assign(var_index, bin_index);
74 }
75
76 bool IsAssignedStatusKnown(int var_index) const {
77 return pack_->IsAssignedStatusKnown(var_index);
78 }
79
80 void SetAssigned(int var_index) { pack_->SetAssigned(var_index); }
81
82 void SetUnassigned(int var_index) { pack_->SetUnassigned(var_index); }
83
84 void RemoveAllPossibleFromBin(int bin_index) {
85 pack_->RemoveAllPossibleFromBin(bin_index);
86 }
87
88 void AssignAllPossibleToBin(int bin_index) {
89 pack_->AssignAllPossibleToBin(bin_index);
90 }
91
92 void AssignFirstPossibleToBin(int bin_index) {
93 pack_->AssignFirstPossibleToBin(bin_index);
94 }
95
97
99
100 private:
101 Solver* const solver_;
102 Pack* const pack_;
103};
104
105// ----- Pack -----
106
107Pack::Pack(Solver* const s, const std::vector<IntVar*>& vars,
108 int number_of_bins)
109 : Constraint(s),
110 vars_(vars),
111 bins_(number_of_bins),
112 unprocessed_(new RevBitMatrix(bins_ + 1, vars_.size())),
113 forced_(bins_ + 1),
114 removed_(bins_ + 1),
115 holes_(vars_.size()),
116 stamp_(uint64_t{0}),
117 demon_(nullptr),
118 in_process_(false) {
119 for (int i = 0; i < vars_.size(); ++i) {
120 holes_[i] = vars_[i]->MakeHoleIterator(true);
121 }
122}
123
125
127 for (int i = 0; i < vars_.size(); ++i) {
128 IntVar* const var = vars_[i];
129 if (!var->Bound()) {
131 "OneDomain", i);
132 var->WhenDomain(d);
133 }
134 }
135 for (int i = 0; i < dims_.size(); ++i) {
136 dims_[i]->Post();
137 }
139 solver(), this, &Pack::Propagate, "Propagate"));
140}
141
143 for (int bin_index = 0; bin_index <= bins_; ++bin_index) {
144 forced_[bin_index].clear();
145 removed_[bin_index].clear();
146 }
147 to_set_.clear();
148 to_unset_.clear();
149 in_process_ = false;
150 stamp_ = solver()->fail_stamp();
151}
152
154 for (int i = 0; i < to_set_.size(); ++i) {
155 vars_[to_set_[i].first]->SetValue(to_set_[i].second);
156 }
157 for (int i = 0; i < to_unset_.size(); ++i) {
158 vars_[to_unset_[i].first]->RemoveValue(to_unset_[i].second);
159 }
160}
161
162// A reversibly-allocable container for the data needed in
163// Pack::InitialPropagate()
164namespace {
165class InitialPropagateData : public BaseObject {
166 public:
167 explicit InitialPropagateData(size_t num_bins)
168 : BaseObject(), undecided_(num_bins) {}
169 void PushAssigned(int index) { assigned_.push_back(index); }
170 void PushUnassigned(int index) { unassigned_.push_back(index); }
171 void PushUndecided(int bin, int index) {
172 undecided_.at(bin).push_back(index);
173 }
174 const std::vector<int>& undecided(int bin) const {
175 return undecided_.at(bin);
176 }
177 const std::vector<int>& assigned() const { return assigned_; }
178 const std::vector<int>& unassigned() const { return unassigned_; }
179
180 std::string DebugString() const override { return "InitialPropagateData"; }
181
182 private:
183 std::vector<std::vector<int>> undecided_;
184 std::vector<int> unassigned_;
185 std::vector<int> assigned_;
186};
187} // namespace
188
190 const bool need_context = solver()->InstrumentsVariables();
191 ClearAll();
192 Solver* const s = solver();
193 in_process_ = true;
194 InitialPropagateData* data = s->RevAlloc(new InitialPropagateData(bins_));
195 for (int var_index = 0; var_index < vars_.size(); ++var_index) {
196 IntVar* const var = vars_[var_index];
197 var->SetRange(0, bins_); // bins_ -> item is not assigned to a bin.
198 if (var->Bound()) {
199 const int64 value = var->Min();
200 if (value < bins_) {
201 forced_[value].push_back(var_index);
202 data->PushAssigned(var_index);
203 } else {
204 data->PushUnassigned(var_index);
205 }
206 } else {
207 DCHECK_GT(bins_, var->Min())
208 << "The variable maximum should be at most " << bins_
209 << ", and it should be unbound, so its min is expected to be less "
210 << "than " << bins_;
211 if (var->Max() < bins_) {
212 data->PushAssigned(var_index);
213 }
214 std::unique_ptr<IntVarIterator> it(var->MakeDomainIterator(false));
215 for (const int64 value : InitAndGetValues(it.get())) {
216 if (value >= 0 && value <= bins_) {
217 unprocessed_->SetToOne(s, value, var_index);
218 if (value != bins_) {
219 data->PushUndecided(value, var_index);
220 }
221 }
222 }
223 }
224 }
225 for (int bin_index = 0; bin_index < bins_; ++bin_index) {
226 if (need_context) {
228 absl::StrFormat("Pack(bin %d, forced = [%s], undecided = [%s])",
229 bin_index, absl::StrJoin(forced_[bin_index], ", "),
230 absl::StrJoin(data->undecided(bin_index), ", ")));
231 }
232
233 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {
234 if (need_context) {
235 solver()->GetPropagationMonitor()->PushContext(absl::StrFormat(
236 "InitialProgateDimension(%s)", dims_[dim_index]->DebugString()));
237 }
238 dims_[dim_index]->InitialPropagate(bin_index, forced_[bin_index],
239 data->undecided(bin_index));
240 if (need_context) {
242 }
243 }
244 if (need_context) {
246 }
247 }
248 if (need_context) {
250 absl::StrFormat("Pack(assigned = [%s], unassigned = [%s])",
251 absl::StrJoin(data->assigned(), ", "),
252 absl::StrJoin(data->unassigned(), ", ")));
253 }
254 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {
255 if (need_context) {
256 solver()->GetPropagationMonitor()->PushContext(absl::StrFormat(
257 "InitialProgateDimension(%s)", dims_[dim_index]->DebugString()));
258 }
259 dims_[dim_index]->InitialPropagateUnassigned(data->assigned(),
260 data->unassigned());
261 dims_[dim_index]->EndInitialPropagate();
262 if (need_context) {
264 }
265 }
266 if (need_context) {
268 }
269
271 ClearAll();
272}
273
275 const bool need_context = solver()->InstrumentsVariables();
276 in_process_ = true;
277 DCHECK_EQ(stamp_, solver()->fail_stamp());
278 for (int bin_index = 0; bin_index < bins_; ++bin_index) {
279 if (!removed_[bin_index].empty() || !forced_[bin_index].empty()) {
280 if (need_context) {
282 absl::StrFormat("Pack(bin %d, forced = [%s], removed = [%s])",
283 bin_index, absl::StrJoin(forced_[bin_index], ", "),
284 absl::StrJoin(removed_[bin_index], ", ")));
285 }
286
287 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {
288 if (need_context) {
289 solver()->GetPropagationMonitor()->PushContext(absl::StrFormat(
290 "ProgateDimension(%s)", dims_[dim_index]->DebugString()));
291 }
292 dims_[dim_index]->Propagate(bin_index, forced_[bin_index],
293 removed_[bin_index]);
294 if (need_context) {
296 }
297 }
298 if (need_context) {
300 }
301 }
302 }
303 if (!removed_[bins_].empty() || !forced_[bins_].empty()) {
304 if (need_context) {
306 absl::StrFormat("Pack(removed = [%s], forced = [%s])",
307 absl::StrJoin(removed_[bins_], ", "),
308 absl::StrJoin(forced_[bins_], ", ")));
309 }
310
311 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {
312 if (need_context) {
313 solver()->GetPropagationMonitor()->PushContext(absl::StrFormat(
314 "ProgateDimension(%s)", dims_[dim_index]->DebugString()));
315 }
316 dims_[dim_index]->PropagateUnassigned(removed_[bins_], forced_[bins_]);
317 if (need_context) {
319 }
320 }
321 if (need_context) {
323 }
324 }
325 for (int dim_index = 0; dim_index < dims_.size(); ++dim_index) {
326 dims_[dim_index]->EndPropagate();
327 }
328
330 ClearAll();
331}
332
333void Pack::OneDomain(int var_index) {
334 // TODO(user): We know var ranges from 0 to bins_. There are lots
335 // of simplifications possible.
336 Solver* const s = solver();
337 const uint64 current_stamp = s->fail_stamp();
338 if (stamp_ < current_stamp) {
339 stamp_ = current_stamp;
340 ClearAll();
341 }
342 IntVar* const var = vars_[var_index];
343 bool bound = var->Bound();
344 const int64 oldmin = var->OldMin();
345 const int64 oldmax = var->OldMax();
346 const int64 vmin = var->Min();
347 const int64 vmax = var->Max();
348 for (int64 value = std::max(oldmin, int64{0});
349 value < std::min(vmin, bins_ + int64{1}); ++value) {
350 if (unprocessed_->IsSet(value, var_index)) {
351 unprocessed_->SetToZero(s, value, var_index);
352 removed_[value].push_back(var_index);
353 }
354 }
355 if (!bound) {
356 for (const int64 value : InitAndGetValues(holes_[var_index])) {
357 if (value >= std::max(int64{0}, vmin) &&
358 value <= std::min(static_cast<int64>(bins_), vmax)) {
359 DCHECK(unprocessed_->IsSet(value, var_index));
360 unprocessed_->SetToZero(s, value, var_index);
361 removed_[value].push_back(var_index);
362 }
363 }
364 }
365 for (int64 value = std::max(vmax + 1, int64{0});
366 value <= std::min(oldmax, static_cast<int64>(bins_)); ++value) {
367 if (unprocessed_->IsSet(value, var_index)) {
368 unprocessed_->SetToZero(s, value, var_index);
369 removed_[value].push_back(var_index);
370 }
371 }
372 if (bound) {
373 unprocessed_->SetToZero(s, var->Min(), var_index);
374 forced_[var->Min()].push_back(var_index);
375 }
376 EnqueueDelayedDemon(demon_);
377}
378
379std::string Pack::DebugString() const {
380 std::string result = "Pack([";
381 for (int i = 0; i < vars_.size(); ++i) {
382 result += vars_[i]->DebugString() + " ";
383 }
384 result += "], dimensions = [";
385 for (int i = 0; i < dims_.size(); ++i) {
386 result += dims_[i]->DebugString() + " ";
387 }
388 absl::StrAppendFormat(&result, "], bins = %d)", bins_);
389 return result;
390}
391
392void Pack::Accept(ModelVisitor* const visitor) const {
395 vars_);
397 for (int i = 0; i < dims_.size(); ++i) {
398 dims_[i]->Accept(visitor);
399 }
401}
402
403bool Pack::IsUndecided(int var_index, int bin_index) const {
404 return unprocessed_->IsSet(bin_index, var_index);
405}
406
407void Pack::SetImpossible(int var_index, int bin_index) {
408 if (IsInProcess()) {
409 to_unset_.push_back(std::make_pair(var_index, bin_index));
410 } else {
411 vars_[var_index]->RemoveValue(bin_index);
412 }
413}
414
415void Pack::Assign(int var_index, int bin_index) {
416 if (IsInProcess()) {
417 to_set_.push_back(std::make_pair(var_index, bin_index));
418 } else {
419 vars_[var_index]->SetValue(bin_index);
420 }
421}
422
423bool Pack::IsAssignedStatusKnown(int var_index) const {
424 return !unprocessed_->IsSet(bins_, var_index);
425}
426
427bool Pack::IsPossible(int var_index, int bin_index) const {
428 return vars_[var_index]->Contains(bin_index);
429}
430
431IntVar* Pack::AssignVar(int var_index, int bin_index) const {
432 return solver()->MakeIsEqualCstVar(vars_[var_index], bin_index);
433}
434
435void Pack::SetAssigned(int var_index) {
436 if (IsInProcess()) {
437 to_unset_.push_back(std::make_pair(var_index, bins_));
438 } else {
439 vars_[var_index]->RemoveValue(bins_);
440 }
441}
442
443void Pack::SetUnassigned(int var_index) {
444 if (IsInProcess()) {
445 to_set_.push_back(std::make_pair(var_index, bins_));
446 } else {
447 vars_[var_index]->SetValue(bins_);
448 }
449}
450
451bool Pack::IsInProcess() const {
452 return in_process_ && (solver()->fail_stamp() == stamp_);
453}
454
456 int var_index = unprocessed_->GetFirstBit(bin_index, 0);
457 while (var_index != -1 && var_index < vars_.size()) {
458 SetImpossible(var_index, bin_index);
459 var_index = var_index == vars_.size() - 1
460 ? -1
461 : unprocessed_->GetFirstBit(bin_index, var_index + 1);
462 }
463}
464
465void Pack::AssignAllPossibleToBin(int bin_index) {
466 int var_index = unprocessed_->GetFirstBit(bin_index, 0);
467 while (var_index != -1 && var_index < vars_.size()) {
468 Assign(var_index, bin_index);
469 var_index = var_index == vars_.size() - 1
470 ? -1
471 : unprocessed_->GetFirstBit(bin_index, var_index + 1);
472 }
473}
474
476 int var_index = unprocessed_->GetFirstBit(bin_index, 0);
477 if (var_index != -1 && var_index < vars_.size()) {
478 Assign(var_index, bin_index);
479 }
480}
481
483 int var_index = unprocessed_->GetFirstBit(bins_, 0);
484 while (var_index != -1 && var_index < vars_.size()) {
485 SetAssigned(var_index);
486 var_index = var_index == vars_.size() - 1
487 ? -1
488 : unprocessed_->GetFirstBit(bins_, var_index + 1);
489 }
490}
491
493 int var_index = unprocessed_->GetFirstBit(bins_, 0);
494 while (var_index != -1 && var_index < vars_.size()) {
495 SetUnassigned(var_index);
496 var_index = var_index == vars_.size() - 1
497 ? -1
498 : unprocessed_->GetFirstBit(bins_, var_index + 1);
499 }
500}
501
502// ----- Dimension -----
503
504// ----- Class Dimension Less Than Constant -----
505
506namespace {
507struct WeightContainer {
508 int index;
510 WeightContainer(int i, int64 w) : index(i), weight(w) {}
511 bool operator<(const WeightContainer& c) const { return (weight < c.weight); }
512};
513
514void SortWeightVector(std::vector<int>* const indices,
515 std::vector<WeightContainer>* const to_sort) {
516 std::sort(to_sort->begin(), to_sort->end());
517 for (int index = 0; index < to_sort->size(); ++index) {
518 (*indices)[index] = (*to_sort)[index].index;
519 }
520 indices->resize(to_sort->size());
521}
522
523void SortIndexByWeight(std::vector<int>* const indices,
524 const std::vector<int64>& weights) {
525 std::vector<WeightContainer> to_sort;
526 for (int index = 0; index < indices->size(); ++index) {
527 if (weights[index] != 0) {
528 to_sort.push_back(WeightContainer((*indices)[index], weights[index]));
529 }
530 }
531 SortWeightVector(indices, &to_sort);
532}
533
534void SortIndexByWeight(std::vector<int>* const indices,
535 const Solver::IndexEvaluator1& weights) {
536 std::vector<WeightContainer> to_sort;
537 for (int index = 0; index < indices->size(); ++index) {
538 const int w = weights(index);
539 if (w != 0) {
540 to_sort.push_back(WeightContainer((*indices)[index], w));
541 }
542 }
543 SortWeightVector(indices, &to_sort);
544}
545
546void SortIndexByWeight(std::vector<int>* const indices,
547 const Solver::IndexEvaluator2& weights, int bin_index) {
548 std::vector<WeightContainer> to_sort;
549 for (int index = 0; index < indices->size(); ++index) {
550 const int w = weights(index, bin_index);
551 if (w != 0) {
552 to_sort.push_back(WeightContainer((*indices)[index], w));
553 }
554 }
555 SortWeightVector(indices, &to_sort);
556}
557
558class DimensionLessThanConstant : public Dimension {
559 public:
560 DimensionLessThanConstant(Solver* const s, Pack* const p,
561 const std::vector<int64>& weights,
562 const std::vector<int64>& upper_bounds)
563 : Dimension(s, p),
564 vars_count_(weights.size()),
565 weights_(weights),
566 bins_count_(upper_bounds.size()),
567 upper_bounds_(upper_bounds),
568 first_unbound_backward_vector_(bins_count_, 0),
569 sum_of_bound_variables_vector_(bins_count_, 0LL),
570 ranked_(vars_count_) {
571 for (int i = 0; i < vars_count_; ++i) {
572 ranked_[i] = i;
573 }
574 SortIndexByWeight(&ranked_, weights_);
575 }
576
577 ~DimensionLessThanConstant() override {}
578
579 void Post() override {}
580
581 void PushFromTop(int bin_index) {
582 const int64 slack =
583 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];
584 if (slack < 0) {
585 solver()->Fail();
586 }
587 int last_unbound = first_unbound_backward_vector_[bin_index];
588 for (; last_unbound >= 0; --last_unbound) {
589 const int var_index = ranked_[last_unbound];
590 if (IsUndecided(var_index, bin_index)) {
591 if (weights_[var_index] > slack) {
592 SetImpossible(var_index, bin_index);
593 } else {
594 break;
595 }
596 }
597 }
598 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);
599 }
600
601 void InitialPropagate(int bin_index, const std::vector<int>& forced,
602 const std::vector<int>& undecided) override {
603 Solver* const s = solver();
604 int64 sum = 0LL;
605 for (const int value : forced) {
606 sum += weights_[value];
607 }
608 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
609 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);
610 PushFromTop(bin_index);
611 }
612
613 void EndInitialPropagate() override {}
614
615 void Propagate(int bin_index, const std::vector<int>& forced,
616 const std::vector<int>& removed) override {
617 if (!forced.empty()) {
618 Solver* const s = solver();
619 int64 sum = sum_of_bound_variables_vector_[bin_index];
620 for (const int value : forced) {
621 sum += weights_[value];
622 }
623 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
624 PushFromTop(bin_index);
625 }
626 }
627 void InitialPropagateUnassigned(const std::vector<int>& assigned,
628 const std::vector<int>& unassigned) override {
629 }
630 void PropagateUnassigned(const std::vector<int>& assigned,
631 const std::vector<int>& unassigned) override {}
632
633 void EndPropagate() override {}
634
635 void Accept(ModelVisitor* const visitor) const override {
636 visitor->BeginVisitExtension(ModelVisitor::kUsageLessConstantExtension);
637 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
638 weights_);
639 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument,
640 upper_bounds_);
641 visitor->EndVisitExtension(ModelVisitor::kUsageLessConstantExtension);
642 }
643
644 private:
645 const int vars_count_;
646 const std::vector<int64> weights_;
647 const int bins_count_;
648 const std::vector<int64> upper_bounds_;
649 RevArray<int> first_unbound_backward_vector_;
650 RevArray<int64> sum_of_bound_variables_vector_;
651 std::vector<int> ranked_;
652};
653
654class DimensionSumCallbackLessThanConstant : public Dimension {
655 public:
656 DimensionSumCallbackLessThanConstant(Solver* const s, Pack* const p,
657 const Solver::IndexEvaluator1& weights,
658 int vars_count,
659 const std::vector<int64>& upper_bounds)
660 : Dimension(s, p),
661 vars_count_(vars_count),
662 weights_(weights),
663 bins_count_(upper_bounds.size()),
664 upper_bounds_(upper_bounds),
665 first_unbound_backward_vector_(bins_count_, 0),
666 sum_of_bound_variables_vector_(bins_count_, 0LL),
667 ranked_(vars_count_) {
668 DCHECK(weights);
669 DCHECK_GT(vars_count, 0);
670 for (int i = 0; i < vars_count_; ++i) {
671 ranked_[i] = i;
672 }
673 SortIndexByWeight(&ranked_, weights_);
674 }
675
676 ~DimensionSumCallbackLessThanConstant() override {}
677
678 void Post() override {}
679
680 void PushFromTop(int bin_index) {
681 const int64 slack =
682 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];
683 if (slack < 0) {
684 solver()->Fail();
685 }
686 int last_unbound = first_unbound_backward_vector_[bin_index];
687 for (; last_unbound >= 0; --last_unbound) {
688 const int var_index = ranked_[last_unbound];
689 if (IsUndecided(var_index, bin_index)) {
690 if (weights_(var_index) > slack) {
691 SetImpossible(var_index, bin_index);
692 } else {
693 break;
694 }
695 }
696 }
697 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);
698 }
699
700 void InitialPropagate(int bin_index, const std::vector<int>& forced,
701 const std::vector<int>& undecided) override {
702 Solver* const s = solver();
703 int64 sum = 0LL;
704 for (const int value : forced) {
705 sum += weights_(value);
706 }
707 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
708 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);
709 PushFromTop(bin_index);
710 }
711
712 void EndInitialPropagate() override {}
713
714 void Propagate(int bin_index, const std::vector<int>& forced,
715 const std::vector<int>& removed) override {
716 if (!forced.empty()) {
717 Solver* const s = solver();
718 int64 sum = sum_of_bound_variables_vector_[bin_index];
719 for (const int value : forced) {
720 sum += weights_(value);
721 }
722 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
723 PushFromTop(bin_index);
724 }
725 }
726 void InitialPropagateUnassigned(const std::vector<int>& assigned,
727 const std::vector<int>& unassigned) override {
728 }
729 void PropagateUnassigned(const std::vector<int>& assigned,
730 const std::vector<int>& unassigned) override {}
731
732 void EndPropagate() override {}
733
734 void Accept(ModelVisitor* const visitor) const override {
735 visitor->BeginVisitExtension(ModelVisitor::kUsageLessConstantExtension);
736 // TODO(user) : Visit weight correctly.
737 // visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
738 // weights_);
739 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument,
740 upper_bounds_);
741 visitor->EndVisitExtension(ModelVisitor::kUsageLessConstantExtension);
742 }
743
744 private:
745 const int vars_count_;
747 const int bins_count_;
748 const std::vector<int64> upper_bounds_;
749 RevArray<int> first_unbound_backward_vector_;
750 RevArray<int64> sum_of_bound_variables_vector_;
751 std::vector<int> ranked_;
752};
753
754class DimensionLessThanConstantCallback2 : public Dimension {
755 public:
756 DimensionLessThanConstantCallback2(Solver* const s, Pack* const p,
757 const Solver::IndexEvaluator2& weights,
758 int vars_count,
759 const std::vector<int64>& upper_bounds)
760 : Dimension(s, p),
761 vars_count_(vars_count),
762 weights_(weights),
763 bins_count_(upper_bounds.size()),
764 upper_bounds_(upper_bounds),
765 first_unbound_backward_vector_(bins_count_, 0),
766 sum_of_bound_variables_vector_(bins_count_, 0LL),
767 ranked_(bins_count_) {
768 DCHECK(weights);
769 DCHECK_GT(vars_count, 0);
770 for (int b = 0; b < bins_count_; ++b) {
771 ranked_[b].resize(vars_count);
772 for (int i = 0; i < vars_count_; ++i) {
773 ranked_[b][i] = i;
774 }
775 SortIndexByWeight(&ranked_[b], weights_, b);
776 }
777 }
778
779 ~DimensionLessThanConstantCallback2() override {}
780
781 void Post() override {}
782
783 void PushFromTop(int bin_index) {
784 const int64 slack =
785 upper_bounds_[bin_index] - sum_of_bound_variables_vector_[bin_index];
786 if (slack < 0) {
787 solver()->Fail();
788 }
789 int last_unbound = first_unbound_backward_vector_[bin_index];
790 for (; last_unbound >= 0; --last_unbound) {
791 const int var_index = ranked_[bin_index][last_unbound];
792 if (IsUndecided(var_index, bin_index)) {
793 if (weights_(var_index, bin_index) > slack) {
794 SetImpossible(var_index, bin_index);
795 } else {
796 break;
797 }
798 }
799 }
800 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);
801 }
802
803 void InitialPropagate(int bin_index, const std::vector<int>& forced,
804 const std::vector<int>& undecided) override {
805 Solver* const s = solver();
806 int64 sum = 0LL;
807 for (const int value : forced) {
808 sum += weights_(value, bin_index);
809 }
810 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
811 first_unbound_backward_vector_.SetValue(s, bin_index,
812 ranked_[bin_index].size() - 1);
813 PushFromTop(bin_index);
814 }
815
816 void EndInitialPropagate() override {}
817
818 void Propagate(int bin_index, const std::vector<int>& forced,
819 const std::vector<int>& removed) override {
820 if (!forced.empty()) {
821 Solver* const s = solver();
822 int64 sum = sum_of_bound_variables_vector_[bin_index];
823 for (const int value : forced) {
824 sum += weights_(value, bin_index);
825 }
826 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
827 PushFromTop(bin_index);
828 }
829 }
830 void InitialPropagateUnassigned(const std::vector<int>& assigned,
831 const std::vector<int>& unassigned) override {
832 }
833 void PropagateUnassigned(const std::vector<int>& assigned,
834 const std::vector<int>& unassigned) override {}
835
836 void EndPropagate() override {}
837
838 void Accept(ModelVisitor* const visitor) const override {
839 visitor->BeginVisitExtension(ModelVisitor::kUsageLessConstantExtension);
840 // TODO(user): Visit weight correctly
841 // visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
842 // weights_);
843 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument,
844 upper_bounds_);
845 visitor->EndVisitExtension(ModelVisitor::kUsageLessConstantExtension);
846 }
847
848 private:
849 const int vars_count_;
851 const int bins_count_;
852 const std::vector<int64> upper_bounds_;
853 RevArray<int> first_unbound_backward_vector_;
854 RevArray<int64> sum_of_bound_variables_vector_;
855 std::vector<std::vector<int>> ranked_;
856};
857
858class DimensionWeightedSumEqVar : public Dimension {
859 public:
860 class VarDemon : public Demon {
861 public:
862 VarDemon(DimensionWeightedSumEqVar* const dim, int index)
863 : dim_(dim), index_(index) {}
864 ~VarDemon() override {}
865
866 void Run(Solver* const s) override { dim_->PushFromTop(index_); }
867
868 private:
869 DimensionWeightedSumEqVar* const dim_;
870 const int index_;
871 };
872
873 DimensionWeightedSumEqVar(Solver* const s, Pack* const p,
874 const std::vector<int64>& weights,
875 const std::vector<IntVar*>& loads)
876 : Dimension(s, p),
877 vars_count_(weights.size()),
878 weights_(weights),
879 bins_count_(loads.size()),
880 loads_(loads),
881 first_unbound_backward_vector_(bins_count_, 0),
882 sum_of_bound_variables_vector_(bins_count_, 0LL),
883 sum_of_all_variables_vector_(bins_count_, 0LL),
884 ranked_(vars_count_) {
885 DCHECK_GT(vars_count_, 0);
886 DCHECK_GT(bins_count_, 0);
887 for (int i = 0; i < vars_count_; ++i) {
888 ranked_[i] = i;
889 }
890 SortIndexByWeight(&ranked_, weights_);
891 }
892
893 ~DimensionWeightedSumEqVar() override {}
894
895 std::string DebugString() const override {
896 return "DimensionWeightedSumEqVar";
897 }
898
899 void Post() override {
900 for (int i = 0; i < bins_count_; ++i) {
901 Demon* const d = solver()->RevAlloc(new VarDemon(this, i));
902 loads_[i]->WhenRange(d);
903 }
904 }
905
906 void PushFromTop(int bin_index) {
907 IntVar* const load = loads_[bin_index];
908 const int64 sum_min = sum_of_bound_variables_vector_[bin_index];
909 const int64 sum_max = sum_of_all_variables_vector_[bin_index];
910 load->SetRange(sum_min, sum_max);
911 const int64 slack_up = load->Max() - sum_min;
912 const int64 slack_down = sum_max - load->Min();
913 DCHECK_GE(slack_down, 0);
914 DCHECK_GE(slack_up, 0);
915 int last_unbound = first_unbound_backward_vector_[bin_index];
916 for (; last_unbound >= 0; --last_unbound) {
917 const int var_index = ranked_[last_unbound];
918 const int64 weight = weights_[var_index];
919 if (IsUndecided(var_index, bin_index)) {
920 if (weight > slack_up) {
921 SetImpossible(var_index, bin_index);
922 } else if (weight > slack_down) {
923 Assign(var_index, bin_index);
924 } else {
925 break;
926 }
927 }
928 }
929 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);
930 }
931
932 void InitialPropagate(int bin_index, const std::vector<int>& forced,
933 const std::vector<int>& undecided) override {
934 Solver* const s = solver();
935 int64 sum = 0LL;
936 for (const int value : forced) {
937 sum += weights_[value];
938 }
939 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
940 for (const int value : undecided) {
941 sum += weights_[value];
942 }
943 sum_of_all_variables_vector_.SetValue(s, bin_index, sum);
944 first_unbound_backward_vector_.SetValue(s, bin_index, ranked_.size() - 1);
945 PushFromTop(bin_index);
946 }
947
948 void EndInitialPropagate() override {}
949
950 void Propagate(int bin_index, const std::vector<int>& forced,
951 const std::vector<int>& removed) override {
952 Solver* const s = solver();
953 int64 down = sum_of_bound_variables_vector_[bin_index];
954 for (const int value : forced) {
955 down += weights_[value];
956 }
957 sum_of_bound_variables_vector_.SetValue(s, bin_index, down);
958 int64 up = sum_of_all_variables_vector_[bin_index];
959 for (const int value : removed) {
960 up -= weights_[value];
961 }
962 sum_of_all_variables_vector_.SetValue(s, bin_index, up);
963 PushFromTop(bin_index);
964 }
965 void InitialPropagateUnassigned(const std::vector<int>& assigned,
966 const std::vector<int>& unassigned) override {
967 }
968 void PropagateUnassigned(const std::vector<int>& assigned,
969 const std::vector<int>& unassigned) override {}
970
971 void EndPropagate() override {}
972
973 void Accept(ModelVisitor* const visitor) const override {
974 visitor->BeginVisitExtension(ModelVisitor::kUsageEqualVariableExtension);
975 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
976 weights_);
977 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
978 loads_);
979 visitor->EndVisitExtension(ModelVisitor::kUsageEqualVariableExtension);
980 }
981
982 private:
983 const int vars_count_;
984 const std::vector<int64> weights_;
985 const int bins_count_;
986 const std::vector<IntVar*> loads_;
987 RevArray<int> first_unbound_backward_vector_;
988 RevArray<int64> sum_of_bound_variables_vector_;
989 RevArray<int64> sum_of_all_variables_vector_;
990 std::vector<int> ranked_;
991};
992
993class DimensionWeightedCallback2SumEqVar : public Dimension {
994 public:
995 class VarDemon : public Demon {
996 public:
997 VarDemon(DimensionWeightedCallback2SumEqVar* const dim, int index)
998 : dim_(dim), index_(index) {}
999 ~VarDemon() override {}
1000
1001 void Run(Solver* const s) override { dim_->PushFromTop(index_); }
1002
1003 private:
1004 DimensionWeightedCallback2SumEqVar* const dim_;
1005 const int index_;
1006 };
1007
1008 DimensionWeightedCallback2SumEqVar(Solver* const s, Pack* const p,
1009 const Solver::IndexEvaluator2& weights,
1010 int vars_count,
1011 const std::vector<IntVar*>& loads)
1012 : Dimension(s, p),
1013 vars_count_(vars_count),
1014 weights_(weights),
1015 bins_count_(loads.size()),
1016 loads_(loads),
1017 first_unbound_backward_vector_(bins_count_, 0),
1018 sum_of_bound_variables_vector_(bins_count_, 0LL),
1019 sum_of_all_variables_vector_(bins_count_, 0LL),
1020 ranked_(bins_count_) {
1021 DCHECK(weights);
1022 DCHECK_GT(vars_count_, 0);
1023 DCHECK_GT(bins_count_, 0);
1024 for (int b = 0; b < bins_count_; ++b) {
1025 ranked_[b].resize(vars_count);
1026 for (int i = 0; i < vars_count_; ++i) {
1027 ranked_[b][i] = i;
1028 }
1029 SortIndexByWeight(&ranked_[b], weights_, b);
1030 }
1031 }
1032
1033 ~DimensionWeightedCallback2SumEqVar() override {}
1034
1035 std::string DebugString() const override {
1036 return "DimensionWeightedCallback2SumEqVar";
1037 }
1038
1039 void Post() override {
1040 for (int i = 0; i < bins_count_; ++i) {
1041 Demon* const d = solver()->RevAlloc(new VarDemon(this, i));
1042 loads_[i]->WhenRange(d);
1043 }
1044 }
1045
1046 void PushFromTop(int bin_index) {
1047 IntVar* const load = loads_[bin_index];
1048 const int64 sum_min = sum_of_bound_variables_vector_[bin_index];
1049 const int64 sum_max = sum_of_all_variables_vector_[bin_index];
1050 load->SetRange(sum_min, sum_max);
1051 const int64 slack_up = load->Max() - sum_min;
1052 const int64 slack_down = sum_max - load->Min();
1053 DCHECK_GE(slack_down, 0);
1054 DCHECK_GE(slack_up, 0);
1055 int last_unbound = first_unbound_backward_vector_[bin_index];
1056 for (; last_unbound >= 0; --last_unbound) {
1057 const int var_index = ranked_[bin_index][last_unbound];
1058 const int64 weight = weights_(var_index, bin_index);
1059 if (IsUndecided(var_index, bin_index)) {
1060 if (weight > slack_up) {
1061 SetImpossible(var_index, bin_index);
1062 } else if (weight > slack_down) {
1063 Assign(var_index, bin_index);
1064 } else {
1065 break;
1066 }
1067 }
1068 }
1069 first_unbound_backward_vector_.SetValue(solver(), bin_index, last_unbound);
1070 }
1071
1072 void InitialPropagate(int bin_index, const std::vector<int>& forced,
1073 const std::vector<int>& undecided) override {
1074 Solver* const s = solver();
1075 int64 sum = 0LL;
1076 for (const int value : forced) {
1077 sum += weights_(value, bin_index);
1078 }
1079 sum_of_bound_variables_vector_.SetValue(s, bin_index, sum);
1080 for (const int value : undecided) {
1081 sum += weights_(value, bin_index);
1082 }
1083 sum_of_all_variables_vector_.SetValue(s, bin_index, sum);
1084 first_unbound_backward_vector_.SetValue(s, bin_index,
1085 ranked_[bin_index].size() - 1);
1086 PushFromTop(bin_index);
1087 }
1088
1089 void EndInitialPropagate() override {}
1090
1091 void Propagate(int bin_index, const std::vector<int>& forced,
1092 const std::vector<int>& removed) override {
1093 Solver* const s = solver();
1094 int64 down = sum_of_bound_variables_vector_[bin_index];
1095 for (const int value : forced) {
1096 down += weights_(value, bin_index);
1097 }
1098 sum_of_bound_variables_vector_.SetValue(s, bin_index, down);
1099 int64 up = sum_of_all_variables_vector_[bin_index];
1100 for (const int value : removed) {
1101 up -= weights_(value, bin_index);
1102 }
1103 sum_of_all_variables_vector_.SetValue(s, bin_index, up);
1104 PushFromTop(bin_index);
1105 }
1106 void InitialPropagateUnassigned(const std::vector<int>& assigned,
1107 const std::vector<int>& unassigned) override {
1108 }
1109 void PropagateUnassigned(const std::vector<int>& assigned,
1110 const std::vector<int>& unassigned) override {}
1111
1112 void EndPropagate() override {}
1113
1114 void Accept(ModelVisitor* const visitor) const override {
1115 visitor->BeginVisitExtension(ModelVisitor::kUsageEqualVariableExtension);
1116 // TODO(user): Visit weight correctly
1117 // visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
1118 // weights_);
1119 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1120 loads_);
1121 visitor->EndVisitExtension(ModelVisitor::kUsageEqualVariableExtension);
1122 }
1123
1124 private:
1125 const int vars_count_;
1126 Solver::IndexEvaluator2 weights_;
1127 const int bins_count_;
1128 const std::vector<IntVar*> loads_;
1129 RevArray<int> first_unbound_backward_vector_;
1130 RevArray<int64> sum_of_bound_variables_vector_;
1131 RevArray<int64> sum_of_all_variables_vector_;
1132 std::vector<std::vector<int>> ranked_;
1133};
1134
1135class AssignedWeightedSumDimension : public Dimension {
1136 public:
1137 class VarDemon : public Demon {
1138 public:
1139 explicit VarDemon(AssignedWeightedSumDimension* const dim) : dim_(dim) {}
1140 ~VarDemon() override {}
1141
1142 void Run(Solver* const s) override { dim_->PropagateAll(); }
1143
1144 private:
1145 AssignedWeightedSumDimension* const dim_;
1146 };
1147
1148 AssignedWeightedSumDimension(Solver* const s, Pack* const p,
1149 const std::vector<int64>& weights,
1150 int bins_count, IntVar* const cost_var)
1151 : Dimension(s, p),
1152 vars_count_(weights.size()),
1153 weights_(weights),
1154 bins_count_(bins_count),
1155 cost_var_(cost_var),
1156 first_unbound_backward_(0),
1157 sum_of_assigned_items_(0LL),
1158 sum_of_unassigned_items_(0LL),
1159 ranked_(vars_count_),
1160 sum_all_weights_(0LL) {
1161 DCHECK(cost_var);
1162 DCHECK_GT(vars_count_, 0);
1163 DCHECK_GT(bins_count_, 0);
1164 for (int i = 0; i < vars_count_; ++i) {
1165 ranked_[i] = i;
1166 }
1167 SortIndexByWeight(&ranked_, weights_);
1168 first_unbound_backward_.SetValue(s, ranked_.size() - 1);
1169 }
1170
1171 ~AssignedWeightedSumDimension() override {}
1172
1173 void Post() override {
1174 Demon* const uv = solver()->RevAlloc(new VarDemon(this));
1175 cost_var_->WhenRange(uv);
1176 }
1177
1178 void PropagateAll() {
1179 cost_var_->SetRange(sum_of_assigned_items_.Value(),
1180 sum_all_weights_ - sum_of_unassigned_items_.Value());
1181 const int64 slack_up = cost_var_->Max() - sum_of_assigned_items_.Value();
1182 const int64 slack_down = sum_all_weights_ - cost_var_->Min();
1183 int last_unbound = first_unbound_backward_.Value();
1184 for (; last_unbound >= 0; --last_unbound) {
1185 const int var_index = ranked_[last_unbound];
1186 if (!IsAssignedStatusKnown(var_index)) {
1187 const int64 coefficient = weights_[var_index];
1188 if (coefficient > slack_up) {
1189 SetUnassigned(var_index);
1190 } else if (coefficient > slack_down) {
1191 SetAssigned(var_index);
1192 } else {
1193 break;
1194 }
1195 }
1196 }
1197 first_unbound_backward_.SetValue(solver(), last_unbound);
1198 }
1199
1200 void InitialPropagate(int bin_index, const std::vector<int>& forced,
1201 const std::vector<int>& undecided) override {}
1202
1203 void EndInitialPropagate() override {}
1204
1205 void InitialPropagateUnassigned(const std::vector<int>& assigned,
1206 const std::vector<int>& unassigned) override {
1207 for (int index = 0; index < vars_count_; ++index) {
1208 sum_all_weights_ += weights_[index];
1209 }
1210
1211 PropagateUnassigned(assigned, unassigned);
1212 }
1213
1214 void Propagate(int bin_index, const std::vector<int>& forced,
1215 const std::vector<int>& removed) override {}
1216
1217 void PropagateUnassigned(const std::vector<int>& assigned,
1218 const std::vector<int>& unassigned) override {
1219 int64 sum_assigned = sum_of_assigned_items_.Value();
1220 for (int index = 0; index < assigned.size(); ++index) {
1221 const int var_index = assigned[index];
1222 sum_assigned += weights_[var_index];
1223 }
1224
1225 int64 sum_unassigned = sum_of_unassigned_items_.Value();
1226 for (int index = 0; index < unassigned.size(); ++index) {
1227 const int var_index = unassigned[index];
1228 sum_unassigned += weights_[var_index];
1229 }
1230
1231 Solver* const s = solver();
1232 sum_of_assigned_items_.SetValue(s, sum_assigned);
1233 sum_of_unassigned_items_.SetValue(s, sum_unassigned);
1234 PropagateAll();
1235 }
1236
1237 void EndPropagate() override {}
1238
1239 void Accept(ModelVisitor* const visitor) const override {
1240 visitor->BeginVisitExtension(
1242 visitor->VisitIntegerArrayArgument(ModelVisitor::kCoefficientsArgument,
1243 weights_);
1244 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
1245 cost_var_);
1246 visitor->EndVisitExtension(
1248 }
1249
1250 private:
1251 const int vars_count_;
1252 const std::vector<int64> weights_;
1253 const int bins_count_;
1254 IntVar* const cost_var_;
1255 Rev<int> first_unbound_backward_;
1256 Rev<int64> sum_of_assigned_items_;
1257 Rev<int64> sum_of_unassigned_items_;
1258 std::vector<int> ranked_;
1259 int64 sum_all_weights_;
1260};
1261
1262// ----- Count unassigned jobs dimension -----
1263
1264class CountAssignedItemsDimension : public Dimension {
1265 public:
1266 class VarDemon : public Demon {
1267 public:
1268 explicit VarDemon(CountAssignedItemsDimension* const dim) : dim_(dim) {}
1269 ~VarDemon() override {}
1270
1271 void Run(Solver* const s) override { dim_->PropagateAll(); }
1272
1273 private:
1274 CountAssignedItemsDimension* const dim_;
1275 };
1276
1277 CountAssignedItemsDimension(Solver* const s, Pack* const p, int vars_count,
1278 int bins_count, IntVar* const cost_var)
1279 : Dimension(s, p),
1280 vars_count_(vars_count),
1281 bins_count_(bins_count),
1282 cost_var_(cost_var),
1283 first_unbound_backward_(0),
1284 assigned_count_(0),
1285 unassigned_count_(0) {
1286 DCHECK(cost_var);
1287 DCHECK_GT(vars_count, 0);
1288 DCHECK_GT(bins_count, 0);
1289 }
1290
1291 ~CountAssignedItemsDimension() override {}
1292
1293 void Post() override {
1294 Demon* const uv = solver()->RevAlloc(new VarDemon(this));
1295 cost_var_->WhenRange(uv);
1296 }
1297
1298 void PropagateAll() {
1299 cost_var_->SetRange(assigned_count_.Value(),
1300 vars_count_ - unassigned_count_.Value());
1301 if (assigned_count_.Value() == cost_var_->Max()) {
1302 UnassignAllRemainingItems();
1303 } else if (cost_var_->Min() == vars_count_ - unassigned_count_.Value()) {
1304 AssignAllRemainingItems();
1305 }
1306 }
1307
1308 void InitialPropagate(int bin_index, const std::vector<int>& forced,
1309 const std::vector<int>& undecided) override {}
1310
1311 void EndInitialPropagate() override {}
1312
1313 void InitialPropagateUnassigned(const std::vector<int>& assigned,
1314 const std::vector<int>& unassigned) override {
1315 PropagateUnassigned(assigned, unassigned);
1316 }
1317
1318 void Propagate(int bin_index, const std::vector<int>& forced,
1319 const std::vector<int>& removed) override {}
1320
1321 void PropagateUnassigned(const std::vector<int>& assigned,
1322 const std::vector<int>& unassigned) override {
1323 Solver* const s = solver();
1324 assigned_count_.SetValue(s, assigned_count_.Value() + assigned.size());
1325 unassigned_count_.SetValue(s,
1326 unassigned_count_.Value() + unassigned.size());
1327 PropagateAll();
1328 }
1329
1330 void EndPropagate() override {}
1331
1332 void Accept(ModelVisitor* const visitor) const override {
1333 visitor->BeginVisitExtension(ModelVisitor::kCountAssignedItemsExtension);
1334 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
1335 cost_var_);
1336 visitor->EndVisitExtension(ModelVisitor::kCountAssignedItemsExtension);
1337 }
1338
1339 private:
1340 const int vars_count_;
1341 const int bins_count_;
1342 IntVar* const cost_var_;
1343 Rev<int> first_unbound_backward_;
1344 Rev<int> assigned_count_;
1345 Rev<int> unassigned_count_;
1346};
1347
1348// ----- Count used bin dimension -----
1349
1350class CountUsedBinDimension : public Dimension {
1351 public:
1352 class VarDemon : public Demon {
1353 public:
1354 explicit VarDemon(CountUsedBinDimension* const dim) : dim_(dim) {}
1355 ~VarDemon() override {}
1356
1357 void Run(Solver* const s) override { dim_->PropagateAll(); }
1358
1359 private:
1360 CountUsedBinDimension* const dim_;
1361 };
1362
1363 CountUsedBinDimension(Solver* const s, Pack* const p, int vars_count,
1364 int bins_count, IntVar* const count_var)
1365 : Dimension(s, p),
1366 vars_count_(vars_count),
1367 bins_count_(bins_count),
1368 count_var_(count_var),
1369 used_(bins_count_),
1370 candidates_(bins_count_, 0),
1371 card_min_(0),
1372 card_max_(bins_count_),
1373 initial_min_(0),
1374 initial_max_(0) {
1375 DCHECK(count_var);
1376 DCHECK_GT(vars_count, 0);
1377 DCHECK_GT(bins_count, 0);
1378 }
1379
1380 ~CountUsedBinDimension() override {}
1381
1382 void Post() override {
1383 Demon* const uv = solver()->RevAlloc(new VarDemon(this));
1384 count_var_->WhenRange(uv);
1385 initial_min_ = 0;
1386 initial_max_ = bins_count_;
1387 }
1388
1389 void PropagateAll() {
1390 count_var_->SetRange(card_min_.Value(), card_max_.Value());
1391 if (card_min_.Value() == count_var_->Max()) {
1392 for (int bin_index = 0; bin_index < bins_count_; ++bin_index) {
1393 if (!used_.IsSet(bin_index) && candidates_[bin_index] > 0) {
1394 RemoveAllPossibleFromBin(bin_index);
1395 }
1396 }
1397 } else if (card_max_.Value() == count_var_->Min()) {
1398 for (int bin_index = 0; bin_index < bins_count_; ++bin_index) {
1399 if (candidates_[bin_index] == 1) {
1400 AssignFirstPossibleToBin(bin_index);
1401 }
1402 }
1403 }
1404 }
1405
1406 void InitialPropagate(int bin_index, const std::vector<int>& forced,
1407 const std::vector<int>& undecided) override {
1408 if (!forced.empty()) {
1409 used_.SetToOne(solver(), bin_index);
1410 initial_min_++;
1411 } else if (!undecided.empty()) {
1412 candidates_.SetValue(solver(), bin_index, undecided.size());
1413 } else {
1414 initial_max_--;
1415 }
1416 }
1417
1418 void EndInitialPropagate() override {
1419 card_min_.SetValue(solver(), initial_min_);
1420 card_max_.SetValue(solver(), initial_max_);
1421 PropagateAll();
1422 }
1423
1424 void InitialPropagateUnassigned(const std::vector<int>& assigned,
1425 const std::vector<int>& unassigned) override {
1426 }
1427
1428 void Propagate(int bin_index, const std::vector<int>& forced,
1429 const std::vector<int>& removed) override {
1430 if (!used_.IsSet(bin_index)) {
1431 if (!forced.empty()) {
1432 used_.SetToOne(solver(), bin_index);
1433 card_min_.SetValue(solver(), card_min_.Value() + 1);
1434 } else if (!removed.empty()) {
1435 candidates_.SetValue(solver(), bin_index,
1436 candidates_.Value(bin_index) - removed.size());
1437 if (candidates_[bin_index] == 0) {
1438 card_max_.SetValue(solver(), card_max_.Value() - 1);
1439 }
1440 }
1441 }
1442 }
1443
1444 void PropagateUnassigned(const std::vector<int>& assigned,
1445 const std::vector<int>& unassigned) override {}
1446
1447 void EndPropagate() override { PropagateAll(); }
1448
1449 void Accept(ModelVisitor* const visitor) const override {
1450 visitor->BeginVisitExtension(ModelVisitor::kCountUsedBinsExtension);
1451 visitor->VisitIntegerExpressionArgument(ModelVisitor::kTargetArgument,
1452 count_var_);
1453 visitor->EndVisitExtension(ModelVisitor::kCountUsedBinsExtension);
1454 }
1455
1456 private:
1457 const int vars_count_;
1458 const int bins_count_;
1459 IntVar* const count_var_;
1460 RevBitSet used_;
1461 RevArray<int> candidates_;
1462 Rev<int> card_min_;
1463 Rev<int> card_max_;
1464 int initial_min_;
1465 int initial_max_;
1466};
1467
1468// ---------- Variable Usage Dimension ----------
1469
1470// This is a very naive, but correct implementation of the constraint.
1471class VariableUsageDimension : public Dimension {
1472 public:
1473 VariableUsageDimension(Solver* const solver, Pack* const pack,
1474 const std::vector<int64>& capacities,
1475 const std::vector<IntVar*>& weights)
1476 : Dimension(solver, pack), capacities_(capacities), weights_(weights) {}
1477
1478 ~VariableUsageDimension() override {}
1479
1480 void Post() override {
1481 Solver* const s = solver();
1482 const int num_bins = capacities_.size();
1483 const int num_items = weights_.size();
1484
1485 for (int bin_index = 0; bin_index < num_bins; ++bin_index) {
1486 std::vector<IntVar*> terms;
1487 for (int item_index = 0; item_index < num_items; ++item_index) {
1488 IntVar* const assign_var = AssignVar(item_index, bin_index);
1489 terms.push_back(s->MakeProd(assign_var, weights_[item_index])->Var());
1490 }
1491 s->AddConstraint(s->MakeSumLessOrEqual(terms, capacities_[bin_index]));
1492 }
1493 }
1494
1495 void InitialPropagate(int bin_index, const std::vector<int>& forced,
1496 const std::vector<int>& undecided) override {}
1497 void InitialPropagateUnassigned(const std::vector<int>& assigned,
1498 const std::vector<int>& unassigned) override {
1499 }
1500 void EndInitialPropagate() override {}
1501 void Propagate(int bin_index, const std::vector<int>& forced,
1502 const std::vector<int>& removed) override {}
1503 void PropagateUnassigned(const std::vector<int>& assigned,
1504 const std::vector<int>& unassigned) override {}
1505 void EndPropagate() override {}
1506
1507 std::string DebugString() const override { return "VariableUsageDimension"; }
1508
1509 void Accept(ModelVisitor* const visitor) const override {
1510 visitor->BeginVisitExtension(
1512 visitor->VisitIntegerArrayArgument(ModelVisitor::kValuesArgument,
1513 capacities_);
1514 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kVarsArgument,
1515 weights_);
1516 visitor->EndVisitExtension(
1518 }
1519
1520 private:
1521 const std::vector<int64> capacities_;
1522 const std::vector<IntVar*> weights_;
1523};
1524} // namespace
1525
1526// ---------- API ----------
1527
1529 const std::vector<int64>& weights, const std::vector<int64>& bounds) {
1530 CHECK_EQ(weights.size(), vars_.size());
1531 CHECK_EQ(bounds.size(), bins_);
1532 Solver* const s = solver();
1533 Dimension* const dim =
1534 s->RevAlloc(new DimensionLessThanConstant(s, this, weights, bounds));
1535 dims_.push_back(dim);
1536}
1537
1539 Solver::IndexEvaluator1 weights, const std::vector<int64>& bounds) {
1540 CHECK(weights != nullptr);
1541 CHECK_EQ(bounds.size(), bins_);
1542 Solver* const s = solver();
1543 Dimension* const dim = s->RevAlloc(new DimensionSumCallbackLessThanConstant(
1544 s, this, weights, vars_.size(), bounds));
1545 dims_.push_back(dim);
1546}
1547
1549 Solver::IndexEvaluator2 weights, const std::vector<int64>& bounds) {
1550 CHECK(weights != nullptr);
1551 CHECK_EQ(bounds.size(), bins_);
1552 Solver* const s = solver();
1553 Dimension* const dim = s->RevAlloc(new DimensionLessThanConstantCallback2(
1554 s, this, weights, vars_.size(), bounds));
1555 dims_.push_back(dim);
1556}
1557
1558void Pack::AddWeightedSumEqualVarDimension(const std::vector<int64>& weights,
1559 const std::vector<IntVar*>& loads) {
1560 CHECK_EQ(weights.size(), vars_.size());
1561 CHECK_EQ(loads.size(), bins_);
1562 Solver* const s = solver();
1563 Dimension* const dim =
1564 s->RevAlloc(new DimensionWeightedSumEqVar(s, this, weights, loads));
1565 dims_.push_back(dim);
1566}
1567
1569 const std::vector<IntVar*>& loads) {
1570 CHECK(weights != nullptr);
1571 CHECK_EQ(loads.size(), bins_);
1572 Solver* const s = solver();
1573 Dimension* const dim = s->RevAlloc(new DimensionWeightedCallback2SumEqVar(
1574 s, this, weights, vars_.size(), loads));
1575 dims_.push_back(dim);
1576}
1577
1578void Pack::AddWeightedSumOfAssignedDimension(const std::vector<int64>& weights,
1579 IntVar* const cost_var) {
1580 CHECK_EQ(weights.size(), vars_.size());
1581 Solver* const s = solver();
1582 Dimension* const dim = s->RevAlloc(
1583 new AssignedWeightedSumDimension(s, this, weights, bins_, cost_var));
1584 dims_.push_back(dim);
1585}
1586
1588 const std::vector<IntVar*>& usage, const std::vector<int64>& capacity) {
1589 CHECK_EQ(usage.size(), vars_.size());
1590 CHECK_EQ(capacity.size(), bins_);
1591 Solver* const s = solver();
1592 Dimension* const dim =
1593 s->RevAlloc(new VariableUsageDimension(s, this, capacity, usage));
1594 dims_.push_back(dim);
1595}
1596
1598 Solver* const s = solver();
1599 Dimension* const dim = s->RevAlloc(
1600 new CountUsedBinDimension(s, this, vars_.size(), bins_, count_var));
1601 dims_.push_back(dim);
1602}
1603
1605 Solver* const s = solver();
1606 Dimension* const dim = s->RevAlloc(
1607 new CountAssignedItemsDimension(s, this, vars_.size(), bins_, count_var));
1608 dims_.push_back(dim);
1609}
1610
1611Pack* Solver::MakePack(const std::vector<IntVar*>& vars, int number_of_bins) {
1612 return RevAlloc(new Pack(this, vars, number_of_bins));
1613}
1614} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
A BaseObject is the root of all reversibly allocated objects.
A constraint is the main modeling object.
A Demon is the base element of a propagation queue.
Solver * solver() const
Definition: pack.cc:54
bool IsAssignedStatusKnown(int var_index) const
Definition: pack.cc:76
virtual void InitialPropagateUnassigned(const std::vector< int > &assigned, const std::vector< int > &unassigned)=0
void SetImpossible(int var_index, int bin_index)
Definition: pack.cc:68
void SetAssigned(int var_index)
Definition: pack.cc:80
bool IsUndecided(int var_index, int bin_index) const
Definition: pack.cc:56
virtual void Accept(ModelVisitor *const visitor) const =0
Dimension(Solver *const s, Pack *const pack)
Definition: pack.cc:36
bool IsPossible(int var_index, int bin_index) const
Definition: pack.cc:60
void AssignFirstPossibleToBin(int bin_index)
Definition: pack.cc:92
void SetUnassigned(int var_index)
Definition: pack.cc:82
virtual void PropagateUnassigned(const std::vector< int > &assigned, const std::vector< int > &unassigned)=0
void AssignAllPossibleToBin(int bin_index)
Definition: pack.cc:88
virtual void InitialPropagate(int bin_index, const std::vector< int > &forced, const std::vector< int > &undecided)=0
void Assign(int var_index, int bin_index)
Definition: pack.cc:72
virtual void Propagate(int bin_index, const std::vector< int > &forced, const std::vector< int > &removed)=0
virtual void EndInitialPropagate()=0
std::string DebugString() const override
Definition: pack.cc:51
IntVar * AssignVar(int var_index, int bin_index) const
Definition: pack.cc:64
void RemoveAllPossibleFromBin(int bin_index)
Definition: pack.cc:84
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
The class IntVar is a subset of IntExpr.
static const char kCountUsedBinsExtension[]
static const char kVariableUsageLessConstantExtension[]
static const char kWeightedSumOfAssignedEqualVariableExtension[]
virtual void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kUsageLessConstantExtension[]
static const char kUsageEqualVariableExtension[]
virtual void VisitIntegerArgument(const std::string &arg_name, int64 value)
Visit integer arguments.
virtual void VisitIntegerVariableArrayArgument(const std::string &arg_name, const std::vector< IntVar * > &arguments)
virtual void BeginVisitConstraint(const std::string &type_name, const Constraint *const constraint)
static const char kCountAssignedItemsExtension[]
Extension names:
void AddWeightedSumOfAssignedDimension(const std::vector< int64 > &weights, IntVar *const cost_var)
This dimension enforces that cost_var == sum of weights[i] for all objects 'i' assigned to a bin.
Definition: pack.cc:1578
bool IsAssignedStatusKnown(int var_index) const
Definition: pack.cc:423
void Post() override
This method is called when the constraint is processed by the solver.
Definition: pack.cc:126
void AddCountAssignedItemsDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of items assigned to a bin in the pack.
Definition: pack.cc:1604
void InitialPropagate() override
This method performs the initial propagation of the constraint.
Definition: pack.cc:189
Pack(Solver *const s, const std::vector< IntVar * > &vars, int number_of_bins)
Definition: pack.cc:107
void SetImpossible(int var_index, int bin_index)
Definition: pack.cc:407
void SetAssigned(int var_index)
Definition: pack.cc:435
void AddWeightedSumEqualVarDimension(const std::vector< int64 > &weights, const std::vector< IntVar * > &loads)
This dimension imposes that for all bins b, the weighted sum (weights[i]) of all objects i assigned t...
Definition: pack.cc:1558
bool IsUndecided(int var_index, int bin_index) const
Definition: pack.cc:403
bool IsPossible(int var_index, int bin_index) const
Definition: pack.cc:427
void AssignFirstPossibleToBin(int bin_index)
Definition: pack.cc:475
void AddCountUsedBinDimension(IntVar *const count_var)
This dimension links 'count_var' to the actual number of bins used in the pack.
Definition: pack.cc:1597
void OneDomain(int var_index)
Definition: pack.cc:333
void SetUnassigned(int var_index)
Definition: pack.cc:443
void AddSumVariableWeightsLessOrEqualConstantDimension(const std::vector< IntVar * > &usage, const std::vector< int64 > &capacity)
This dimension imposes: forall b in bins, sum (i in items: usage[i] * is_assigned(i,...
Definition: pack.cc:1587
void Accept(ModelVisitor *const visitor) const override
Accepts the given visitor.
Definition: pack.cc:392
void AssignAllPossibleToBin(int bin_index)
Definition: pack.cc:465
void Assign(int var_index, int bin_index)
Definition: pack.cc:415
void UnassignAllRemainingItems()
Definition: pack.cc:492
std::string DebugString() const override
Definition: pack.cc:379
void AssignAllRemainingItems()
Definition: pack.cc:482
void AddWeightedSumLessOrEqualConstantDimension(const std::vector< int64 > &weights, const std::vector< int64 > &bounds)
Dimensions are additional constraints than can restrict what is possible with the pack constraint.
Definition: pack.cc:1528
IntVar * AssignVar(int var_index, int bin_index) const
Definition: pack.cc:431
void RemoveAllPossibleFromBin(int bin_index)
Definition: pack.cc:455
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
virtual void PushContext(const std::string &context)=0
Matrix version of the RevBitSet class.
void SetValue(Solver *const s, const T &val)
Pack * MakePack(const std::vector< IntVar * > &vars, int number_of_bins)
This constraint packs all variables onto 'number_of_bins' variables.
Definition: pack.cc:1611
uint64 fail_stamp() const
The fail_stamp() is incremented after each backtrack.
IntVar * MakeIsEqualCstVar(IntExpr *const var, int64 value)
status var of (var == value)
Definition: expr_cst.cc:460
Demon * RegisterDemon(Demon *const demon)
Adds a new demon and wraps it inside a DemonProfiler if necessary.
PropagationMonitor * GetPropagationMonitor() const
Returns the propagation monitor.
bool InstrumentsVariables() const
Returns whether we are tracing variables.
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
std::function< int64(int64, int64)> IndexEvaluator2
T * RevAlloc(T *object)
Registers the given object as being reversible.
std::vector< IntVarIterator * > holes_
SharedBoundsManager * bounds
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
uint64_t uint64
bool in_process_
Definition: interval.cc:419
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
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)
int index
Definition: pack.cc:508
int64 weight
Definition: pack.cc:509
int64 capacity
int64 bound
int64 coefficient
std::vector< double > upper_bounds
const int64 stamp_
Definition: search.cc:3039