OR-Tools  8.2
model.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
15
16#include <set>
17#include <vector>
18
19#include "absl/container/flat_hash_set.h"
20#include "absl/strings/str_cat.h"
21#include "absl/strings/str_format.h"
22#include "absl/strings/str_join.h"
26
27namespace operations_research {
28namespace fz {
29// ----- Domain -----
30
31Domain Domain::IntegerList(std::vector<int64> values) {
32 Domain result;
33 result.is_interval = false;
34 result.values = std::move(values);
36 result.display_as_boolean = false;
37 result.is_a_set = false;
38 return result;
39}
40
42 Domain result;
43 result.is_interval = true;
44 result.display_as_boolean = false;
45 result.is_a_set = false;
46 return result;
47}
48
50 Domain result;
51 result.is_interval = false;
52 result.values.push_back(value);
53 result.display_as_boolean = false;
54 result.is_a_set = false;
55 return result;
56}
57
58Domain Domain::Interval(int64 included_min, int64 included_max) {
59 Domain result;
60 result.is_interval = true;
61 result.display_as_boolean = false;
62 result.values.push_back(included_min);
63 result.values.push_back(included_max);
64 result.is_a_set = false;
65 return result;
66}
67
69 Domain result;
70 result.is_interval = false;
71 result.display_as_boolean = true;
72 result.values.push_back(0);
73 result.values.push_back(1);
74 result.is_a_set = false;
75 return result;
76}
77
78Domain Domain::SetOfIntegerList(std::vector<int64> values) {
79 Domain result = IntegerList(std::move(values));
80 result.is_a_set = true;
81 return result;
82}
83
85 Domain result = AllInt64();
86 result.is_a_set = true;
87 return result;
88}
89
91 Domain result = IntegerValue(value);
92 result.is_a_set = true;
93 return result;
94}
95
96Domain Domain::SetOfInterval(int64 included_min, int64 included_max) {
97 Domain result = Interval(included_min, included_max);
98 result.is_a_set = true;
99 return result;
100}
101
103 Domain result = Boolean();
104 result.is_a_set = true;
105 return result;
106}
107
109 Domain result;
110 result.is_interval = false;
111 result.display_as_boolean = false;
112 result.is_a_set = false;
113 return result;
114}
115
117 if (domain.is_interval) {
118 if (!domain.values.empty()) {
119 return IntersectWithInterval(domain.values[0], domain.values[1]);
120 }
121 return false;
122 }
123 if (is_interval) {
124 is_interval = false; // Other is not an interval.
125 if (values.empty()) {
126 values = domain.values;
127 } else {
128 const int64 imin = values[0];
129 const int64 imax = values[1];
130 values = domain.values;
131 IntersectWithInterval(imin, imax);
132 }
133 return true;
134 }
135 // now deal with the intersection of two lists of values
136 return IntersectWithListOfIntegers(domain.values);
137}
138
141}
142
143bool Domain::IntersectWithInterval(int64 interval_min, int64 interval_max) {
144 if (interval_min > interval_max) { // Empty interval -> empty domain.
145 is_interval = false;
146 values.clear();
147 return true;
148 } else if (is_interval) {
149 if (values.empty()) {
150 values.push_back(interval_min);
151 values.push_back(interval_max);
152 return true;
153 } else {
154 if (values[0] >= interval_min && values[1] <= interval_max) return false;
155 values[0] = std::max(values[0], interval_min);
156 values[1] = std::min(values[1], interval_max);
157 if (values[0] > values[1]) {
158 values.clear();
159 is_interval = false;
160 } else if (values[0] == values[1]) {
161 is_interval = false;
162 values.pop_back();
163 }
164 return true;
165 }
166 } else {
167 if (!values.empty()) {
168 std::sort(values.begin(), values.end());
169 std::vector<int64> new_values;
170 new_values.reserve(values.size());
171 bool changed = false;
172 for (const int64 val : values) {
173 if (val > interval_max) {
174 changed = true;
175 break;
176 }
177 if (val >= interval_min &&
178 (new_values.empty() || val != new_values.back())) {
179 new_values.push_back(val);
180 } else {
181 changed = true;
182 }
183 }
184 values.swap(new_values);
185 return changed;
186 }
187 }
188 return false;
189}
190
191bool Domain::IntersectWithListOfIntegers(const std::vector<int64>& integers) {
192 if (is_interval) {
193 const int64 dmin = values.empty() ? kint64min : values[0];
194 const int64 dmax = values.empty() ? kint64max : values[1];
195 values.clear();
196 for (const int64 v : integers) {
197 if (v >= dmin && v <= dmax) values.push_back(v);
198 }
200 if (!values.empty() &&
201 values.back() - values.front() == values.size() - 1 &&
202 values.size() >= 2) {
203 if (values.size() > 2) {
204 // Contiguous case.
205 const int64 last = values.back();
206 values.resize(2);
207 values[1] = last;
208 }
209 return values[0] != dmin || values[1] != dmax;
210 } else {
211 // This also covers and invalid (empty) domain.
212 is_interval = false;
213 return true;
214 }
215 } else {
216 // TODO(user): Investigate faster code for small arrays.
217 std::sort(values.begin(), values.end());
218 absl::flat_hash_set<int64> other_values(integers.begin(), integers.end());
219 std::vector<int64> new_values;
220 new_values.reserve(std::min(values.size(), integers.size()));
221 bool changed = false;
222 for (const int64 val : values) {
223 if (gtl::ContainsKey(other_values, val)) {
224 if (new_values.empty() || val != new_values.back()) {
225 new_values.push_back(val);
226 }
227 } else {
228 changed = true;
229 }
230 }
231 values.swap(new_values);
232 return changed;
233 }
234}
235
237 return (values.size() == 1 || (values.size() == 2 && values[0] == values[1]));
238}
239
240bool Domain::empty() const {
241 return is_interval ? (values.size() == 2 && values[0] > values[1])
242 : values.empty();
243}
244
246 CHECK(!empty());
247 return is_interval && values.empty() ? kint64min : values.front();
248}
249
251 CHECK(!empty());
252 return is_interval && values.empty() ? kint64max : values.back();
253}
254
257 return values.front();
258}
259
260bool Domain::IsAllInt64() const {
261 return is_interval &&
262 (values.empty() || (values[0] == kint64min && values[1] == kint64max));
263}
264
266 if (is_interval) {
267 if (values.empty()) {
268 return true;
269 } else {
270 return value >= values[0] && value <= values[1];
271 }
272 } else {
273 return std::find(values.begin(), values.end(), value) != values.end();
274 }
275}
276
277namespace {
278bool IntervalOverlapValues(int64 lb, int64 ub,
279 const std::vector<int64>& values) {
280 for (int64 value : values) {
281 if (lb <= value && value <= ub) {
282 return true;
283 }
284 }
285 return false;
286}
287} // namespace
288
289bool Domain::OverlapsIntList(const std::vector<int64>& vec) const {
290 if (IsAllInt64()) {
291 return true;
292 }
293 if (is_interval) {
294 CHECK(!values.empty());
295 return IntervalOverlapValues(values[0], values[1], vec);
296 } else {
297 // TODO(user): Better algorithm, sort and compare increasingly.
298 const std::vector<int64>& to_scan =
299 values.size() <= vec.size() ? values : vec;
300 const absl::flat_hash_set<int64> container =
301 values.size() <= vec.size()
302 ? absl::flat_hash_set<int64>(vec.begin(), vec.end())
303 : absl::flat_hash_set<int64>(values.begin(), values.end());
304 for (int64 value : to_scan) {
305 if (gtl::ContainsKey(container, value)) {
306 return true;
307 }
308 }
309 return false;
310 }
311}
312
314 if (IsAllInt64()) {
315 return true;
316 }
317 if (is_interval) {
318 CHECK(!values.empty());
319 const int64 dlb = values[0];
320 const int64 dub = values[1];
321 return !(dub < lb || dlb > ub);
322 } else {
323 return IntervalOverlapValues(lb, ub, values);
324 }
325}
326
327bool Domain::OverlapsDomain(const Domain& other) const {
328 if (other.is_interval) {
329 if (other.values.empty()) {
330 return true;
331 } else {
332 return OverlapsIntInterval(other.values[0], other.values[1]);
333 }
334 } else {
335 return OverlapsIntList(other.values);
336 }
337}
338
340 if (is_interval) {
341 if (values.empty()) {
342 return false;
343 } else if (value == values[0] && value != values[1]) {
344 values[0]++;
345 return true;
346 } else if (value == values[1] && value != values[0]) {
347 values[1]--;
348 return true;
349 } else if (values[1] - values[0] < 1024 && value > values[0] &&
350 value < values[1]) { // small
351 const int64 vmax = values[1];
352 values.pop_back();
353 values.reserve(vmax - values[0]);
354 for (int64 v = values[0] + 1; v <= vmax; ++v) {
355 if (v != value) {
356 values.push_back(v);
357 }
358 }
359 is_interval = false;
360 return true;
361 }
362 } else {
363 values.erase(std::remove(values.begin(), values.end(), value),
364 values.end());
365 return true;
366 }
367 return false;
368}
369
370std::string Domain::DebugString() const {
371 if (is_interval) {
372 if (values.empty()) {
373 return "int";
374 } else {
375 return absl::StrFormat("[%d..%d]", values[0], values[1]);
376 }
377 } else if (values.size() == 1) {
378 return absl::StrCat(values.back());
379 } else {
380 return absl::StrFormat("[%s]", absl::StrJoin(values, ", "));
381 }
382}
383
384// ----- Argument -----
385
387 Argument result;
388 result.type = INT_VALUE;
389 result.values.push_back(value);
390 return result;
391}
392
394 Argument result;
395 result.type = INT_INTERVAL;
396 result.values.push_back(imin);
397 result.values.push_back(imax);
398 return result;
399}
400
401Argument Argument::IntegerList(std::vector<int64> values) {
402 Argument result;
403 result.type = INT_LIST;
404 result.values = std::move(values);
405 return result;
406}
407
408Argument Argument::DomainList(std::vector<Domain> domains) {
409 Argument result;
410 result.type = DOMAIN_LIST;
411 result.domains = std::move(domains);
412 return result;
413}
414
416 Argument result;
417 result.type = INT_VAR_REF;
418 result.variables.push_back(var);
419 return result;
420}
421
422Argument Argument::IntVarRefArray(std::vector<IntegerVariable*> vars) {
423 Argument result;
424 result.type = INT_VAR_REF_ARRAY;
425 result.variables = std::move(vars);
426 return result;
427}
428
430 Argument result;
431 result.type = VOID_ARGUMENT;
432 return result;
433}
434
436 if (domain.is_interval) {
437 if (domain.values.empty()) {
439 } else {
440 return Argument::Interval(domain.values[0], domain.values[1]);
441 }
442 } else {
443 return Argument::IntegerList(domain.values);
444 }
445}
446
447std::string Argument::DebugString() const {
448 switch (type) {
449 case INT_VALUE:
450 return absl::StrFormat("% d", values[0]);
451 case INT_INTERVAL:
452 return absl::StrFormat("[%d..%d]", values[0], values[1]);
453 case INT_LIST:
454 return absl::StrFormat("[%s]", absl::StrJoin(values, ", "));
455 case DOMAIN_LIST:
456 return absl::StrFormat("[%s]", JoinDebugString(domains, ", "));
457 case INT_VAR_REF:
458 return variables[0]->name;
459 case INT_VAR_REF_ARRAY: {
460 std::string result = "[";
461 for (int i = 0; i < variables.size(); ++i) {
462 result.append(variables[i]->name);
463 result.append(i != variables.size() - 1 ? ", " : "]");
464 }
465 return result;
466 }
467 case VOID_ARGUMENT:
468 return "VoidArgument";
469 }
470 LOG(FATAL) << "Unhandled case in DebugString " << static_cast<int>(type);
471 return "";
472}
473
474bool Argument::IsVariable() const { return type == INT_VAR_REF; }
475
477 return (type == INT_VALUE || (type == INT_LIST && values.size() == 1) ||
478 (type == INT_INTERVAL && values[0] == values[1]) ||
479 (type == INT_VAR_REF && variables[0]->domain.HasOneValue()));
480}
481
483 DCHECK(HasOneValue()) << "Value() called on unbound Argument: "
484 << DebugString();
485 switch (type) {
486 case INT_VALUE:
487 case INT_INTERVAL:
488 case INT_LIST:
489 return values[0];
490 case INT_VAR_REF: {
491 return variables[0]->domain.values[0];
492 }
493 default: {
494 LOG(FATAL) << "Should not be here";
495 return 0;
496 }
497 }
498}
499
501 switch (type) {
502 case INT_VALUE:
503 return false;
504 case INT_INTERVAL:
505 return false;
506 case INT_LIST:
507 return true;
508 case DOMAIN_LIST: {
509 for (const Domain& domain : domains) {
510 if (!domain.HasOneValue()) {
511 return false;
512 }
513 }
514 return true;
515 }
516 case INT_VAR_REF:
517 return false;
518 case INT_VAR_REF_ARRAY: {
519 for (IntegerVariable* var : variables) {
520 if (!var->domain.HasOneValue()) {
521 return false;
522 }
523 }
524 return true;
525 }
526 case VOID_ARGUMENT:
527 return false;
528 }
529}
530
532 switch (type) {
533 case Argument::INT_LIST: {
534 return std::find(values.begin(), values.end(), value) != values.end();
535 }
537 return value >= values.front() && value <= values.back();
538 }
539 case Argument::INT_VALUE: {
540 return value == values.front();
541 }
542 default: {
543 LOG(FATAL) << "Cannot call Contains() on " << DebugString();
544 return false;
545 }
546 }
547}
548
549int64 Argument::ValueAt(int pos) const {
550 switch (type) {
551 case INT_LIST:
552 CHECK_GE(pos, 0);
553 CHECK_LT(pos, values.size());
554 return values[pos];
555 case DOMAIN_LIST: {
556 CHECK_GE(pos, 0);
557 CHECK_LT(pos, domains.size());
558 CHECK(domains[pos].HasOneValue());
559 return domains[pos].Value();
560 }
561 case INT_VAR_REF_ARRAY: {
562 CHECK_GE(pos, 0);
563 CHECK_LT(pos, variables.size());
564 CHECK(variables[pos]->domain.HasOneValue());
565 return variables[pos]->domain.Value();
566 }
567 default: {
568 LOG(FATAL) << "Should not be here";
569 return 0;
570 }
571 }
572}
573
575 return type == INT_VAR_REF ? variables[0] : nullptr;
576}
577
579 return type == INT_VAR_REF_ARRAY ? variables[pos] : nullptr;
580}
581
582// ----- IntegerVariable -----
583
584IntegerVariable::IntegerVariable(const std::string& name_,
585 const Domain& domain_, bool temporary_)
586 : name(name_), domain(domain_), temporary(temporary_), active(true) {
587 if (!domain.is_interval) {
588 gtl::STLSortAndRemoveDuplicates(&domain.values);
589 }
590}
591
592bool IntegerVariable::Merge(const std::string& other_name,
593 const Domain& other_domain, bool other_temporary) {
594 if (temporary && !other_temporary) {
595 temporary = false;
596 name = other_name;
597 }
598 domain.IntersectWithDomain(other_domain);
599 return true;
600}
601
602std::string IntegerVariable::DebugString() const {
603 if (!domain.is_interval && domain.values.size() == 1) {
604 return absl::StrFormat("% d", domain.values.back());
605 } else {
606 return absl::StrFormat("%s(%s%s)%s", name, domain.DebugString(),
607 temporary ? ", temporary" : "",
608 active ? "" : " [removed during presolve]");
609 }
610}
611
612// ----- Constraint -----
613
614std::string Constraint::DebugString() const {
615 const std::string strong = strong_propagation ? "strong propagation" : "";
616 const std::string presolve_status_str =
617 active ? ""
618 : (presolve_propagation_done ? "[propagated during presolve]"
619 : "[removed during presolve]");
620 return absl::StrFormat("%s(%s)%s %s", type, JoinDebugString(arguments, ", "),
621 strong, presolve_status_str);
622}
623
624void Constraint::RemoveArg(int arg_pos) {
625 arguments.erase(arguments.begin() + arg_pos);
626}
627
629 active = false;
630 // TODO(user): Reclaim arguments and memory.
631}
632
634 type = "false_constraint";
635 arguments.clear();
636}
637
638// ----- Annotation -----
639
641 Annotation result;
642 result.type = ANNOTATION_LIST;
643 result.interval_min = 0;
644 result.interval_max = 0;
645 return result;
646}
647
648Annotation Annotation::AnnotationList(std::vector<Annotation> list) {
649 Annotation result;
650 result.type = ANNOTATION_LIST;
651 result.interval_min = 0;
652 result.interval_max = 0;
653 result.annotations = std::move(list);
654 return result;
655}
656
657Annotation Annotation::Identifier(const std::string& id) {
658 Annotation result;
659 result.type = IDENTIFIER;
660 result.interval_min = 0;
661 result.interval_max = 0;
662 result.id = id;
663 return result;
664}
665
667 std::vector<Annotation> args) {
668 Annotation result;
669 result.type = FUNCTION_CALL;
670 result.interval_min = 0;
671 result.interval_max = 0;
672 result.id = id;
673 result.annotations = std::move(args);
674 return result;
675}
676
677Annotation Annotation::FunctionCall(const std::string& id) {
678 Annotation result;
679 result.type = FUNCTION_CALL;
680 result.interval_min = 0;
681 result.interval_max = 0;
682 result.id = id;
683 return result;
684}
685
686Annotation Annotation::Interval(int64 interval_min, int64 interval_max) {
687 Annotation result;
688 result.type = INTERVAL;
689 result.interval_min = interval_min;
690 result.interval_max = interval_max;
691 return result;
692}
693
695 Annotation result;
696 result.type = INT_VALUE;
697 result.interval_min = value;
698 return result;
699}
700
702 Annotation result;
703 result.type = INT_VAR_REF;
704 result.interval_min = 0;
705 result.interval_max = 0;
706 result.variables.push_back(var);
707 return result;
708}
709
710Annotation Annotation::VariableList(std::vector<IntegerVariable*> variables) {
711 Annotation result;
712 result.type = INT_VAR_REF_ARRAY;
713 result.interval_min = 0;
714 result.interval_max = 0;
715 result.variables = std::move(variables);
716 return result;
717}
718
719Annotation Annotation::String(const std::string& str) {
720 Annotation result;
721 result.type = STRING_VALUE;
722 result.interval_min = 0;
723 result.interval_max = 0;
724 result.string_value = str;
725 return result;
726}
727
729 std::vector<IntegerVariable*>* const vars) const {
730 for (const Annotation& ann : annotations) {
731 ann.AppendAllIntegerVariables(vars);
732 }
733 if (!variables.empty()) {
734 vars->insert(vars->end(), variables.begin(), variables.end());
735 }
736}
737
738std::string Annotation::DebugString() const {
739 switch (type) {
740 case ANNOTATION_LIST: {
741 return absl::StrFormat("[%s]", JoinDebugString(annotations, ", "));
742 }
743 case IDENTIFIER: {
744 return id;
745 }
746 case FUNCTION_CALL: {
747 return absl::StrFormat("%s(%s)", id, JoinDebugString(annotations, ", "));
748 }
749 case INTERVAL: {
750 return absl::StrFormat("%d..%d", interval_min, interval_max);
751 }
752 case INT_VALUE: {
753 return absl::StrCat(interval_min);
754 }
755 case INT_VAR_REF: {
756 return variables.front()->name;
757 }
758 case INT_VAR_REF_ARRAY: {
759 std::string result = "[";
760 for (int i = 0; i < variables.size(); ++i) {
761 result.append(variables[i]->DebugString());
762 result.append(i != variables.size() - 1 ? ", " : "]");
763 }
764 return result;
765 }
766 case STRING_VALUE: {
767 return absl::StrFormat("\"%s\"", string_value);
768 }
769 }
770 LOG(FATAL) << "Unhandled case in DebugString " << static_cast<int>(type);
771 return "";
772}
773
774// ----- SolutionOutputSpecs -----
775
777 return absl::StrFormat("%d..%d", min_value, max_value);
778}
779
781 const std::string& name, IntegerVariable* variable,
782 bool display_as_boolean) {
783 SolutionOutputSpecs result;
784 result.name = name;
785 result.variable = variable;
787 return result;
788}
789
791 const std::string& name, std::vector<Bounds> bounds,
792 std::vector<IntegerVariable*> flat_variables, bool display_as_boolean) {
793 SolutionOutputSpecs result;
794 result.variable = nullptr;
795 result.name = name;
796 result.bounds = std::move(bounds);
797 result.flat_variables = std::move(flat_variables);
799 return result;
800}
801
803 SolutionOutputSpecs result;
804 result.variable = nullptr;
805 result.display_as_boolean = false;
806 return result;
807}
808
810 if (variable != nullptr) {
811 return absl::StrFormat("output_var(%s)", variable->name);
812 } else {
813 return absl::StrFormat("output_array([%s] [%s])",
814 JoinDebugString(bounds, ", "),
816 }
817}
818
819// ----- Model -----
820
822 gtl::STLDeleteElements(&variables_);
823 gtl::STLDeleteElements(&constraints_);
824}
825
827 const Domain& domain, bool defined) {
828 IntegerVariable* const var = new IntegerVariable(name, domain, defined);
829 variables_.push_back(var);
830 return var;
831}
832
833// TODO(user): Create only once constant per value.
836 absl::StrCat(value), Domain::IntegerValue(value), true);
837 variables_.push_back(var);
838 return var;
839}
840
841void Model::AddConstraint(const std::string& id,
842 std::vector<Argument> arguments, bool is_domain) {
843 Constraint* const constraint =
844 new Constraint(id, std::move(arguments), is_domain);
845 constraints_.push_back(constraint);
846}
847
848void Model::AddConstraint(const std::string& id,
849 std::vector<Argument> arguments) {
850 AddConstraint(id, std::move(arguments), false);
851}
852
854 output_.push_back(std::move(output));
855}
856
857void Model::Satisfy(std::vector<Annotation> search_annotations) {
858 objective_ = nullptr;
859 search_annotations_ = std::move(search_annotations);
860}
861
863 std::vector<Annotation> search_annotations) {
864 objective_ = obj;
865 maximize_ = false;
866 search_annotations_ = std::move(search_annotations);
867}
868
870 std::vector<Annotation> search_annotations) {
871 objective_ = obj;
872 maximize_ = true;
873 search_annotations_ = std::move(search_annotations);
874}
875
876std::string Model::DebugString() const {
877 std::string output = absl::StrFormat("Model %s\nVariables\n", name_);
878 for (int i = 0; i < variables_.size(); ++i) {
879 absl::StrAppendFormat(&output, " %s\n", variables_[i]->DebugString());
880 }
881 output.append("Constraints\n");
882 for (int i = 0; i < constraints_.size(); ++i) {
883 if (constraints_[i] != nullptr) {
884 absl::StrAppendFormat(&output, " %s\n", constraints_[i]->DebugString());
885 }
886 }
887 if (objective_ != nullptr) {
888 absl::StrAppendFormat(&output, "%s %s\n %s\n",
889 maximize_ ? "Maximize" : "Minimize", objective_->name,
890 JoinDebugString(search_annotations_, ", "));
891 } else {
892 absl::StrAppendFormat(&output, "Satisfy\n %s\n",
893 JoinDebugString(search_annotations_, ", "));
894 }
895 output.append("Output\n");
896 for (int i = 0; i < output_.size(); ++i) {
897 absl::StrAppendFormat(&output, " %s\n", output_[i].DebugString());
898 }
899
900 return output;
901}
902
904 for (IntegerVariable* var : variables_) {
905 if (var->domain.empty()) {
906 return true;
907 }
908 }
909 for (Constraint* ct : constraints_) {
910 if (ct->type == "false_constraint") {
911 return true;
912 }
913 }
914
915 return false;
916}
917
918// ----- Model statistics -----
919
921 FZLOG << "Model " << model_.name() << FZENDL;
922 for (const auto& it : constraints_per_type_) {
923 FZLOG << " - " << it.first << ": " << it.second.size() << FZENDL;
924 }
925 if (model_.objective() == nullptr) {
926 FZLOG << " - Satisfaction problem" << FZENDL;
927 } else {
928 FZLOG << " - " << (model_.maximize() ? "Maximization" : "Minimization")
929 << " problem" << FZENDL;
930 }
931}
932
934 constraints_per_type_.clear();
935 constraints_per_variables_.clear();
936 for (Constraint* const ct : model_.constraints()) {
937 if (ct != nullptr && ct->active) {
938 constraints_per_type_[ct->type].push_back(ct);
939 absl::flat_hash_set<const IntegerVariable*> marked;
940 for (const Argument& arg : ct->arguments) {
941 for (IntegerVariable* const var : arg.variables) {
942 marked.insert(var);
943 }
944 }
945 for (const IntegerVariable* const var : marked) {
946 constraints_per_variables_[var].push_back(ct);
947 }
948 }
949 }
950}
951
952// Flatten Search annotations.
953void FlattenAnnotations(const Annotation& ann, std::vector<Annotation>* out) {
955 ann.IsFunctionCallWithIdentifier("seq_search")) {
956 for (const Annotation& inner : ann.annotations) {
957 FlattenAnnotations(inner, out);
958 }
959 } else {
960 out->push_back(ann);
961 }
962}
963
964} // namespace fz
965} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
IntegerVariable * AddVariable(const std::string &name, const Domain &domain, bool defined)
Definition: model.cc:826
void Satisfy(std::vector< Annotation > search_annotations)
Definition: model.cc:857
void Maximize(IntegerVariable *obj, std::vector< Annotation > search_annotations)
Definition: model.cc:869
std::string DebugString() const
Definition: model.cc:876
void AddOutput(SolutionOutputSpecs output)
Definition: model.cc:853
IntegerVariable * AddConstant(int64 value)
Definition: model.cc:834
void AddConstraint(const std::string &id, std::vector< Argument > arguments, bool is_domain)
Definition: model.cc:841
void Minimize(IntegerVariable *obj, std::vector< Annotation > search_annotations)
Definition: model.cc:862
bool IsInconsistent() const
Definition: model.cc:903
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
#define FZLOG
#define FZENDL
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int FATAL
Definition: log_severity.h:32
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
void STLDeleteElements(T *container)
Definition: stl_util.h:372
void STLSortAndRemoveDuplicates(T *v, const LessFunc &less_func)
Definition: stl_util.h:58
void FlattenAnnotations(const Annotation &ann, std::vector< Annotation > *out)
Definition: model.cc:953
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::string JoinDebugString(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:38
std::string JoinNameFieldPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:58
const bool maximize_
Definition: search.cc:2499
IntVar *const objective_
Definition: search.cc:2951
static Annotation IntegerValue(int64 value)
Definition: model.cc:694
std::vector< IntegerVariable * > variables
static Annotation Variable(IntegerVariable *const var)
Definition: model.cc:701
std::string DebugString() const
Definition: model.cc:738
static Annotation FunctionCall(const std::string &id)
Definition: model.cc:677
static Annotation AnnotationList(std::vector< Annotation > list)
Definition: model.cc:648
static Annotation String(const std::string &str)
Definition: model.cc:719
static Annotation Identifier(const std::string &id)
Definition: model.cc:657
bool IsFunctionCallWithIdentifier(const std::string &identifier) const
std::vector< Annotation > annotations
static Annotation Empty()
Definition: model.cc:640
static Annotation Interval(int64 interval_min, int64 interval_max)
Definition: model.cc:686
void AppendAllIntegerVariables(std::vector< IntegerVariable * > *vars) const
Definition: model.cc:728
static Annotation FunctionCallWithArguments(const std::string &id, std::vector< Annotation > args)
Definition: model.cc:666
static Annotation VariableList(std::vector< IntegerVariable * > variables)
Definition: model.cc:710
int64 ValueAt(int pos) const
Definition: model.cc:549
IntegerVariable * Var() const
Definition: model.cc:574
static Argument DomainList(std::vector< Domain > domains)
Definition: model.cc:408
std::vector< IntegerVariable * > variables
IntegerVariable * VarAt(int pos) const
Definition: model.cc:578
static Argument VoidArgument()
Definition: model.cc:429
static Argument Interval(int64 imin, int64 imax)
Definition: model.cc:393
static Argument IntVarRefArray(std::vector< IntegerVariable * > vars)
Definition: model.cc:422
std::string DebugString() const
Definition: model.cc:447
static Argument IntegerList(std::vector< int64 > values)
Definition: model.cc:401
bool Contains(int64 value) const
Definition: model.cc:531
static Argument IntVarRef(IntegerVariable *const var)
Definition: model.cc:415
static Argument FromDomain(const Domain &domain)
Definition: model.cc:435
static Argument IntegerValue(int64 value)
Definition: model.cc:386
void RemoveArg(int arg_pos)
Definition: model.cc:624
std::string DebugString() const
Definition: model.cc:614
std::vector< Argument > arguments
bool OverlapsIntList(const std::vector< int64 > &vec) const
Definition: model.cc:289
static Domain IntegerList(std::vector< int64 > values)
Definition: model.cc:31
static Domain EmptyDomain()
Definition: model.cc:108
bool IntersectWithSingleton(int64 value)
Definition: model.cc:139
static Domain SetOfIntegerValue(int64 value)
Definition: model.cc:90
bool OverlapsDomain(const Domain &other) const
Definition: model.cc:327
static Domain SetOfAllInt64()
Definition: model.cc:84
static Domain Boolean()
Definition: model.cc:68
static Domain SetOfIntegerList(std::vector< int64 > values)
Definition: model.cc:78
bool IntersectWithInterval(int64 interval_min, int64 interval_max)
Definition: model.cc:143
bool RemoveValue(int64 value)
Definition: model.cc:339
std::string DebugString() const
Definition: model.cc:370
static Domain Interval(int64 included_min, int64 included_max)
Definition: model.cc:58
bool IntersectWithListOfIntegers(const std::vector< int64 > &integers)
Definition: model.cc:191
static Domain AllInt64()
Definition: model.cc:41
bool IntersectWithDomain(const Domain &domain)
Definition: model.cc:116
bool Contains(int64 value) const
Definition: model.cc:265
bool OverlapsIntInterval(int64 lb, int64 ub) const
Definition: model.cc:313
static Domain SetOfBoolean()
Definition: model.cc:102
static Domain SetOfInterval(int64 included_min, int64 included_max)
Definition: model.cc:96
static Domain IntegerValue(int64 value)
Definition: model.cc:49
std::vector< int64 > values
bool Merge(const std::string &other_name, const Domain &other_domain, bool other_temporary)
Definition: model.cc:592
static SolutionOutputSpecs MultiDimensionalArray(const std::string &name, std::vector< Bounds > bounds, std::vector< IntegerVariable * > flat_variables, bool display_as_boolean)
Definition: model.cc:790
std::vector< IntegerVariable * > flat_variables
static SolutionOutputSpecs VoidOutput()
Definition: model.cc:802
static SolutionOutputSpecs SingleVariable(const std::string &name, IntegerVariable *variable, bool display_as_boolean)
Definition: model.cc:780