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