Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model.cc
Go to the documentation of this file.
1// Copyright 2010-2025 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 <cstdint>
17#include <initializer_list>
18#include <limits>
19#include <ostream>
20#include <string>
21#include <vector>
22
23#include "absl/container/flat_hash_map.h"
24#include "absl/log/check.h"
25#include "absl/strings/str_cat.h"
26#include "absl/strings/str_format.h"
27#include "absl/strings/string_view.h"
28#include "absl/types/span.h"
29#include "ortools/sat/cp_model.pb.h"
32
33namespace operations_research {
34namespace sat {
35
36BoolVar::BoolVar(int index, CpModelBuilder* builder)
37 : builder_(builder), index_(index) {}
38
39BoolVar BoolVar::WithName(absl::string_view name) {
40 DCHECK(builder_ != nullptr);
41 if (builder_ == nullptr) return *this;
42 builder_->MutableProto()
43 ->mutable_variables(PositiveRef(index_))
44 ->set_name(name);
45 return *this;
46}
47
48std::string BoolVar::Name() const {
49 if (builder_ == nullptr) return "null";
50 const std::string& name =
51 builder_->Proto().variables(PositiveRef(index_)).name();
52 if (RefIsPositive(index_)) {
53 return name;
54 } else {
55 return absl::StrCat("Not(", name, ")");
56 }
57}
58
59std::string BoolVar::DebugString() const {
60 if (builder_ == nullptr) return "null";
61 if (index_ < 0) {
62 return absl::StrFormat("Not(%s)", Not().DebugString());
63 } else {
64 std::string output;
65 const IntegerVariableProto& var_proto = builder_->Proto().variables(index_);
66 // Special case for constant variables without names.
67 if (var_proto.name().empty() && var_proto.domain_size() == 2 &&
68 var_proto.domain(0) == var_proto.domain(1)) {
69 output.append(var_proto.domain(0) == 0 ? "false" : "true");
70 } else {
71 if (var_proto.name().empty()) {
72 absl::StrAppendFormat(&output, "BoolVar%i(", index_);
73 } else {
74 absl::StrAppendFormat(&output, "%s(", var_proto.name());
75 }
76 if (var_proto.domain(0) == var_proto.domain(1)) {
77 output.append(var_proto.domain(0) == 0 ? "false)" : "true)");
78 } else {
79 absl::StrAppend(&output, var_proto.domain(0), ", ", var_proto.domain(1),
80 ")");
81 }
82 }
83 return output;
84 }
85}
86
87BoolVar Not(BoolVar x) { return x.Not(); }
88
89std::ostream& operator<<(std::ostream& os, const BoolVar& var) {
90 os << var.DebugString();
91 return os;
92}
93
94IntVar::IntVar(int index, CpModelBuilder* builder)
95 : builder_(builder), index_(index) {
96 DCHECK(RefIsPositive(index_));
97}
98
100 if (var.builder_ == nullptr) {
101 *this = IntVar();
102 return;
103 }
104 builder_ = var.builder_;
105 index_ = builder_->GetOrCreateIntegerIndex(var.index_);
106 DCHECK(RefIsPositive(index_));
107}
108
110 if (builder_ != nullptr) {
111 const IntegerVariableProto& proto = builder_->Proto().variables(index_);
112 DCHECK_EQ(2, proto.domain_size());
113 DCHECK_GE(proto.domain(0), 0);
114 DCHECK_LE(proto.domain(1), 1);
115 }
116 return BoolVar(index_, builder_);
117}
118
119IntVar IntVar::WithName(absl::string_view name) {
120 DCHECK(builder_ != nullptr);
121 if (builder_ == nullptr) return *this;
122 builder_->MutableProto()->mutable_variables(index_)->set_name(name);
123 return *this;
124}
125
126std::string IntVar::Name() const {
127 if (builder_ == nullptr) return "null";
128 return builder_->Proto().variables(index_).name();
129}
130
132 if (builder_ == nullptr) return Domain();
133 return ReadDomainFromProto(builder_->Proto().variables(index_));
134}
135
136std::string IntVar::DebugString() const {
137 if (builder_ == nullptr) return "null";
138 return VarDebugString(builder_->Proto(), index_);
139}
140
141// TODO(user): unfortunately, we need this indirection to get a DebugString()
142// in a const way from an index. Because building an IntVar is non-const.
143std::string VarDebugString(const CpModelProto& proto, int index) {
144 std::string output;
145
146 // Special case for constant variables without names.
147 const IntegerVariableProto& var_proto = proto.variables(index);
148 if (var_proto.name().empty() && var_proto.domain_size() == 2 &&
149 var_proto.domain(0) == var_proto.domain(1)) {
150 absl::StrAppend(&output, var_proto.domain(0));
151 } else {
152 if (var_proto.name().empty()) {
153 absl::StrAppend(&output, "V", index, "(");
154 } else {
155 absl::StrAppend(&output, var_proto.name(), "(");
156 }
157
158 // TODO(user): Use domain pretty print function.
159 if (var_proto.domain_size() == 2 &&
160 var_proto.domain(0) == var_proto.domain(1)) {
161 absl::StrAppend(&output, var_proto.domain(0), ")");
162 } else {
163 absl::StrAppend(&output, var_proto.domain(0), ", ", var_proto.domain(1),
164 ")");
165 }
166 }
167
168 return output;
169}
170
171std::ostream& operator<<(std::ostream& os, const IntVar& var) {
172 os << var.DebugString();
173 return os;
174}
175
177 DCHECK(var.builder_ != nullptr);
178 const int index = var.index_;
179 if (RefIsPositive(index)) {
180 variables_.push_back(index);
181 coefficients_.push_back(1);
182 } else {
183 // We add 1 - var instead.
184 variables_.push_back(PositiveRef(index));
185 coefficients_.push_back(-1);
186 constant_ += 1;
187 }
188}
189
191 DCHECK(var.builder_ != nullptr);
192 variables_.push_back(var.index_);
193 coefficients_.push_back(1);
194}
195
196LinearExpr::LinearExpr(int64_t constant) { constant_ = constant; }
197
198LinearExpr LinearExpr::FromProto(const LinearExpressionProto& expr_proto) {
199 LinearExpr result(expr_proto.offset());
200 for (int i = 0; i < expr_proto.vars_size(); ++i) {
201 result.variables_.push_back(expr_proto.vars(i));
202 result.coefficients_.push_back(expr_proto.coeffs(i));
203 }
204 return result;
205}
206
207LinearExpr LinearExpr::Sum(absl::Span<const IntVar> vars) {
208 LinearExpr result;
209 for (const IntVar& var : vars) {
210 result += var;
211 }
212 return result;
213}
214
215LinearExpr LinearExpr::Sum(absl::Span<const BoolVar> vars) {
216 LinearExpr result;
217 for (const BoolVar& var : vars) {
218 result += var;
219 }
220 return result;
221}
222
223LinearExpr LinearExpr::WeightedSum(absl::Span<const IntVar> vars,
224 absl::Span<const int64_t> coeffs) {
225 CHECK_EQ(vars.size(), coeffs.size());
226 LinearExpr result;
227 for (int i = 0; i < vars.size(); ++i) {
228 result += vars[i] * coeffs[i];
229 }
230 return result;
231}
232
233LinearExpr LinearExpr::WeightedSum(absl::Span<const BoolVar> vars,
234 absl::Span<const int64_t> coeffs) {
235 CHECK_EQ(vars.size(), coeffs.size());
236 LinearExpr result;
237 for (int i = 0; i < vars.size(); ++i) {
238 result += vars[i] * coeffs[i];
239 }
240 return result;
241}
242
243LinearExpr LinearExpr::Term(IntVar var, int64_t coefficient) {
244 LinearExpr result;
245 result += var * coefficient;
246 return result;
247}
248
249LinearExpr LinearExpr::Term(BoolVar var, int64_t coefficient) {
250 LinearExpr result;
251 result += var * coefficient;
252 return result;
253}
254
256 constant_ += other.constant_;
257 variables_.insert(variables_.end(), other.variables_.begin(),
258 other.variables_.end());
259 coefficients_.insert(coefficients_.end(), other.coefficients_.begin(),
260 other.coefficients_.end());
261 return *this;
262}
263
265 constant_ -= other.constant_;
266 variables_.insert(variables_.end(), other.variables_.begin(),
267 other.variables_.end());
268 for (const int64_t coeff : other.coefficients_) {
269 coefficients_.push_back(-coeff);
270 }
271 return *this;
272}
273
275 constant_ *= factor;
276 for (int64_t& coeff : coefficients_) coeff *= factor;
277 return *this;
278}
279
280std::string LinearExpr::DebugString(const CpModelProto* proto) const {
281 std::string result;
282 for (int i = 0; i < variables_.size(); ++i) {
283 const int64_t coeff = coefficients_[i];
284 const std::string var_string = proto == nullptr
285 ? absl::StrCat("V", variables_[i])
286 : VarDebugString(*proto, variables_[i]);
287 if (i == 0) {
288 if (coeff == 1) {
289 absl::StrAppend(&result, var_string);
290 } else if (coeff == -1) {
291 absl::StrAppend(&result, "-", var_string);
292 } else if (coeff != 0) {
293 absl::StrAppend(&result, coeff, " * ", var_string);
294 }
295 } else if (coeff == 1) {
296 absl::StrAppend(&result, " + ", var_string);
297 } else if (coeff > 0) {
298 absl::StrAppend(&result, " + ", coeff, " * ", var_string);
299 } else if (coeff == -1) {
300 absl::StrAppend(&result, " - ", var_string);
301 } else if (coeff < 0) {
302 absl::StrAppend(&result, " - ", -coeff, " * ", var_string);
303 }
304 }
305
306 if (constant_ != 0) {
307 if (variables_.empty()) {
308 return absl::StrCat(constant_);
309 } else if (constant_ > 0) {
310 absl::StrAppend(&result, " + ", constant_);
311 } else {
312 absl::StrAppend(&result, " - ", -constant_);
313 }
314 }
315 return result;
316}
317
318std::ostream& operator<<(std::ostream& os, const LinearExpr& e) {
319 os << e.DebugString();
320 return os;
321}
322
323DoubleLinearExpr::DoubleLinearExpr() = default;
324
326
328
330
331DoubleLinearExpr DoubleLinearExpr::Sum(absl::Span<const IntVar> vars) {
332 DoubleLinearExpr result;
333 for (const IntVar& var : vars) {
334 result.AddTerm(var, 1.0);
335 }
336 return result;
337}
338
339DoubleLinearExpr DoubleLinearExpr::Sum(absl::Span<const BoolVar> vars) {
340 DoubleLinearExpr result;
341 for (const BoolVar& var : vars) {
342 result.AddTerm(var, 1.0);
343 }
344 return result;
345}
346
348 absl::Span<const IntVar> vars, absl::Span<const double> coeffs) {
349 CHECK_EQ(vars.size(), coeffs.size());
350 DoubleLinearExpr result;
351 for (int i = 0; i < vars.size(); ++i) {
352 result.AddTerm(vars[i], coeffs[i]);
353 }
354 return result;
355}
356
358 absl::Span<const BoolVar> vars, absl::Span<const double> coeffs) {
359 CHECK_EQ(vars.size(), coeffs.size());
360 DoubleLinearExpr result;
361 for (int i = 0; i < vars.size(); ++i) {
362 result.AddTerm(vars[i], coeffs[i]);
363 }
364 return result;
365}
366
368 constant_ += value;
369 return *this;
370}
371
373 AddTerm(var, 1);
374 return *this;
375}
376
378 AddTerm(var, 1);
379 return *this;
380}
381
383 constant_ += expr.constant_;
384 variables_.insert(variables_.end(), expr.variables_.begin(),
385 expr.variables_.end());
386 coefficients_.insert(coefficients_.end(), expr.coefficients_.begin(),
387 expr.coefficients_.end());
388 return *this;
389}
390
392 variables_.push_back(var.index_);
393 coefficients_.push_back(coeff);
394 return *this;
395}
396
398 const int index = var.index_;
399 if (RefIsPositive(index)) {
400 variables_.push_back(index);
401 coefficients_.push_back(coeff);
402 } else {
403 variables_.push_back(PositiveRef(index));
404 coefficients_.push_back(-coeff);
405 constant_ += coeff;
406 }
407 return *this;
408}
409
411 double coeff) {
412 const std::vector<int>& indices = expr.variables();
413 const std::vector<int64_t> coefficients = expr.coefficients();
414 for (int i = 0; i < indices.size(); ++i) {
415 variables_.push_back(indices[i]);
416 coefficients_.push_back(1.0 * static_cast<double>(coefficients[i]) * coeff);
417 }
418
419 return *this;
420}
421
423 constant_ -= value;
424 return *this;
425}
426
428 AddTerm(var, -1.0);
429 return *this;
430}
431
433 constant_ -= expr.constant_;
434 variables_.insert(variables_.end(), expr.variables_.begin(),
435 expr.variables_.end());
436 for (const double coeff : expr.coefficients()) {
437 coefficients_.push_back(-coeff);
438 }
439 return *this;
440}
441
443 constant_ *= coeff;
444 for (double& c : coefficients_) {
445 c *= coeff;
446 }
447 return *this;
448}
449
450std::string DoubleLinearExpr::DebugString(const CpModelProto* proto) const {
451 std::string result;
452 for (int i = 0; i < variables_.size(); ++i) {
453 const double coeff = coefficients_[i];
454 const std::string var_string = proto == nullptr
455 ? absl::StrCat("V", variables_[i])
456 : VarDebugString(*proto, variables_[i]);
457 if (i == 0) {
458 if (coeff == 1.0) {
459 absl::StrAppend(&result, var_string);
460 } else if (coeff == -1.0) {
461 absl::StrAppend(&result, "-", var_string);
462 } else if (coeff != 0.0) {
463 absl::StrAppend(&result, coeff, " * ", var_string);
464 }
465 } else if (coeff == 1.0) {
466 absl::StrAppend(&result, " + ", var_string);
467 } else if (coeff > 0.0) {
468 absl::StrAppend(&result, " + ", coeff, " * ", var_string);
469 } else if (coeff == -1.0) {
470 absl::StrAppend(&result, " - ", var_string);
471 } else if (coeff < 0.0) {
472 absl::StrAppend(&result, " - ", -coeff, " * ", var_string);
473 }
474 }
475
476 if (constant_ != 0.0) {
477 if (variables_.empty()) {
478 return absl::StrCat(constant_);
479 } else if (constant_ > 0.0) {
480 absl::StrAppend(&result, " + ", constant_);
481 } else {
482 absl::StrAppend(&result, " - ", -constant_);
483 }
484 }
485 return result;
486}
487
488std::ostream& operator<<(std::ostream& os, const DoubleLinearExpr& e) {
489 os << e.DebugString();
490 return os;
491}
492
493Constraint::Constraint(ConstraintProto* proto) : proto_(proto) {}
494
495Constraint Constraint::WithName(absl::string_view name) {
496 proto_->set_name(name);
497 return *this;
498}
499
500absl::string_view Constraint::Name() const { return proto_->name(); }
501
502Constraint Constraint::OnlyEnforceIf(absl::Span<const BoolVar> literals) {
503 for (const BoolVar& var : literals) {
504 proto_->add_enforcement_literal(var.index_);
505 }
506 return *this;
507}
508
510 proto_->add_enforcement_literal(literal.index_);
511 return *this;
512}
513
514void CircuitConstraint::AddArc(int tail, int head, BoolVar literal) {
515 proto_->mutable_circuit()->add_tails(tail);
516 proto_->mutable_circuit()->add_heads(head);
517 proto_->mutable_circuit()->add_literals(literal.index_);
518}
519
520void MultipleCircuitConstraint::AddArc(int tail, int head, BoolVar literal) {
521 proto_->mutable_routes()->add_tails(tail);
522 proto_->mutable_routes()->add_heads(head);
523 proto_->mutable_routes()->add_literals(literal.index_);
524}
525
526void TableConstraint::AddTuple(absl::Span<const int64_t> tuple) {
527 CHECK_EQ(tuple.size(), proto_->table().exprs_size());
528 for (const int64_t t : tuple) {
529 proto_->mutable_table()->add_values(t);
530 }
531}
532
533ReservoirConstraint::ReservoirConstraint(ConstraintProto* proto,
534 CpModelBuilder* builder)
535 : Constraint(proto), builder_(builder) {}
536
537void ReservoirConstraint::AddEvent(LinearExpr time, int64_t level_change) {
538 *proto_->mutable_reservoir()->add_time_exprs() =
539 builder_->LinearExprToProto(time);
540 proto_->mutable_reservoir()->add_level_changes()->set_offset(level_change);
541 proto_->mutable_reservoir()->add_active_literals(
542 builder_->IndexFromConstant(1));
543}
544
546 int64_t level_change,
547 BoolVar is_active) {
548 *proto_->mutable_reservoir()->add_time_exprs() =
549 builder_->LinearExprToProto(time);
550 proto_->mutable_reservoir()->add_level_changes()->set_offset(level_change);
551 proto_->mutable_reservoir()->add_active_literals(is_active.index_);
552}
553
555 int64_t transition_label) {
556 proto_->mutable_automaton()->add_transition_tail(tail);
557 proto_->mutable_automaton()->add_transition_head(head);
558 proto_->mutable_automaton()->add_transition_label(transition_label);
559}
560
562 IntervalVar y_coordinate) {
563 proto_->mutable_no_overlap_2d()->add_x_intervals(x_coordinate.index_);
564 proto_->mutable_no_overlap_2d()->add_y_intervals(y_coordinate.index_);
565}
566
567CumulativeConstraint::CumulativeConstraint(ConstraintProto* proto,
568 CpModelBuilder* builder)
569 : Constraint(proto), builder_(builder) {}
570
572 proto_->mutable_cumulative()->add_intervals(interval.index_);
573 *proto_->mutable_cumulative()->add_demands() =
574 builder_->LinearExprToProto(demand);
575}
576
577IntervalVar::IntervalVar() : builder_(nullptr), index_() {}
578
579IntervalVar::IntervalVar(int index, CpModelBuilder* builder)
580 : builder_(builder), index_(index) {}
581
582IntervalVar IntervalVar::WithName(absl::string_view name) {
583 DCHECK(builder_ != nullptr);
584 if (builder_ == nullptr) return *this;
585 builder_->MutableProto()->mutable_constraints(index_)->set_name(name);
586 return *this;
587}
588
590 DCHECK(builder_ != nullptr);
591 if (builder_ == nullptr) return LinearExpr();
593 builder_->Proto().constraints(index_).interval().start());
594}
595
597 DCHECK(builder_ != nullptr);
598 if (builder_ == nullptr) return LinearExpr();
600 builder_->Proto().constraints(index_).interval().size());
601}
602
604 DCHECK(builder_ != nullptr);
605 if (builder_ == nullptr) return LinearExpr();
607 builder_->Proto().constraints(index_).interval().end());
608}
609
611 DCHECK(builder_ != nullptr);
612 if (builder_ == nullptr) return BoolVar();
613 return BoolVar(builder_->Proto().constraints(index_).enforcement_literal(0),
614 builder_);
615}
616
617std::string IntervalVar::Name() const {
618 if (builder_ == nullptr) return "null";
619 return builder_->Proto().constraints(index_).name();
620}
621
622std::string IntervalVar::DebugString() const {
623 if (builder_ == nullptr) return "null";
624
625 CHECK_GE(index_, 0);
626 const CpModelProto& proto = builder_->Proto();
627 const ConstraintProto& ct_proto = proto.constraints(index_);
628 std::string output;
629 if (ct_proto.name().empty()) {
630 absl::StrAppend(&output, "IntervalVar", index_, "(");
631 } else {
632 absl::StrAppend(&output, ct_proto.name(), "(");
633 }
634 absl::StrAppend(&output, StartExpr().DebugString(&proto), ", ",
635 SizeExpr().DebugString(&proto), ", ",
636 EndExpr().DebugString(&proto), ", ",
638 return output;
639}
640
641std::ostream& operator<<(std::ostream& os, const IntervalVar& var) {
642 os << var.DebugString();
643 return os;
644}
645
646void CpModelBuilder::SetName(absl::string_view name) {
647 cp_model_.set_name(name);
648}
649
650int CpModelBuilder::IndexFromConstant(int64_t value) {
651 if (!constant_to_index_map_.contains(value)) {
652 const int index = cp_model_.variables_size();
653 IntegerVariableProto* const var_proto = cp_model_.add_variables();
654 var_proto->add_domain(value);
655 var_proto->add_domain(value);
656 constant_to_index_map_[value] = index;
657 }
658 return constant_to_index_map_[value];
659}
660
661int CpModelBuilder::GetOrCreateIntegerIndex(int index) {
662 if (index >= 0) {
663 return index;
664 }
665 if (!bool_to_integer_index_map_.contains(index)) {
666 const int var = PositiveRef(index);
667 const IntegerVariableProto& old_var = cp_model_.variables(var);
668 const int new_index = cp_model_.variables_size();
669 IntegerVariableProto* const new_var = cp_model_.add_variables();
670 new_var->add_domain(0);
671 new_var->add_domain(1);
672 if (!old_var.name().empty()) {
673 new_var->set_name(absl::StrCat("Not(", old_var.name(), ")"));
674 }
675 AddEquality(IntVar(new_index, this), BoolVar(index, this));
676 bool_to_integer_index_map_[index] = new_index;
677 return new_index;
678 }
679 return bool_to_integer_index_map_[index];
680}
681
683 const int index = cp_model_.variables_size();
684 IntegerVariableProto* const var_proto = cp_model_.add_variables();
685 for (const auto& interval : domain) {
686 var_proto->add_domain(interval.start);
687 var_proto->add_domain(interval.end);
688 }
689 return IntVar(index, this);
690}
691
693 const int index = cp_model_.variables_size();
694 IntegerVariableProto* const var_proto = cp_model_.add_variables();
695 var_proto->add_domain(0);
696 var_proto->add_domain(1);
697 return BoolVar(index, this);
698}
699
701 return IntVar(IndexFromConstant(value), this);
702}
703
705 return BoolVar(IndexFromConstant(1), this);
706}
707
709 return BoolVar(IndexFromConstant(0), this);
710}
711
713 const LinearExpr& size,
714 const LinearExpr& end) {
715 return NewOptionalIntervalVar(start, size, end, TrueVar());
716}
717
719 int64_t size) {
720 return NewOptionalFixedSizeIntervalVar(start, size, TrueVar());
721}
722
724 const LinearExpr& size,
725 const LinearExpr& end,
726 BoolVar presence) {
727 const int index = cp_model_.constraints_size();
728 ConstraintProto* const ct = cp_model_.add_constraints();
729 ct->add_enforcement_literal(presence.index_);
730 IntervalConstraintProto* const interval = ct->mutable_interval();
731 *interval->mutable_start() = LinearExprToProto(start);
732 *interval->mutable_size() = LinearExprToProto(size);
733 *interval->mutable_end() = LinearExprToProto(end);
734 return IntervalVar(index, this);
735}
736
738 const LinearExpr& start, int64_t size, BoolVar presence) {
739 const int index = cp_model_.constraints_size();
740 ConstraintProto* const ct = cp_model_.add_constraints();
741 ct->add_enforcement_literal(presence.index_);
742 IntervalConstraintProto* const interval = ct->mutable_interval();
743 *interval->mutable_start() = LinearExprToProto(start);
744 interval->mutable_size()->set_offset(size);
745 *interval->mutable_end() = LinearExprToProto(start);
746 interval->mutable_end()->set_offset(interval->end().offset() + size);
747 return IntervalVar(index, this);
748}
749
750void CpModelBuilder::FixVariable(IntVar var, int64_t value) {
751 FillDomainInProto(Domain(value), cp_model_.mutable_variables(var.index()));
752}
753
755 const int index = var.index();
756 if (RefIsPositive(index)) {
757 FillDomainInProto(Domain(value), cp_model_.mutable_variables(index));
758 } else {
760 cp_model_.mutable_variables(NegatedRef(index)));
761 }
762}
763
764Constraint CpModelBuilder::AddBoolOr(absl::Span<const BoolVar> literals) {
765 ConstraintProto* const proto = cp_model_.add_constraints();
766 BoolArgumentProto* const bool_or = proto->mutable_bool_or();
767 for (const BoolVar& lit : literals) bool_or->add_literals(lit.index_);
768 return Constraint(proto);
769}
770
771Constraint CpModelBuilder::AddAtLeastOne(absl::Span<const BoolVar> literals) {
772 return AddBoolOr(literals);
773}
774
775Constraint CpModelBuilder::AddAtMostOne(absl::Span<const BoolVar> literals) {
776 ConstraintProto* const proto = cp_model_.add_constraints();
777 for (const BoolVar& lit : literals) {
778 proto->mutable_at_most_one()->add_literals(lit.index_);
779 }
780 return Constraint(proto);
781}
782
783Constraint CpModelBuilder::AddExactlyOne(absl::Span<const BoolVar> literals) {
784 ConstraintProto* const proto = cp_model_.add_constraints();
785 BoolArgumentProto* const exactly_one = proto->mutable_exactly_one();
786 for (const BoolVar& lit : literals) exactly_one->add_literals(lit.index_);
787 return Constraint(proto);
788}
789
790Constraint CpModelBuilder::AddBoolAnd(absl::Span<const BoolVar> literals) {
791 ConstraintProto* const proto = cp_model_.add_constraints();
792 for (const BoolVar& lit : literals) {
793 proto->mutable_bool_and()->add_literals(lit.index_);
794 }
795 return Constraint(proto);
796}
797
798Constraint CpModelBuilder::AddBoolXor(absl::Span<const BoolVar> literals) {
799 ConstraintProto* const proto = cp_model_.add_constraints();
800 for (const BoolVar& lit : literals) {
801 proto->mutable_bool_xor()->add_literals(lit.index_);
802 }
803 return Constraint(proto);
804}
805
806void CpModelBuilder::FillLinearTerms(const LinearExpr& left,
807 const LinearExpr& right,
808 LinearConstraintProto* proto) {
809 for (const int x : left.variables()) {
810 proto->add_vars(x);
811 }
812 for (const int64_t coeff : left.coefficients()) {
813 proto->add_coeffs(coeff);
814 }
815 for (const int x : right.variables()) {
816 proto->add_vars(x);
817 }
818 for (const int64_t coeff : right.coefficients()) {
819 proto->add_coeffs(-coeff);
820 }
821}
822
824 const LinearExpr& right) {
825 ConstraintProto* const proto = cp_model_.add_constraints();
826 FillLinearTerms(left, right, proto->mutable_linear());
827 const int64_t rhs = right.constant() - left.constant();
828 proto->mutable_linear()->add_domain(rhs);
829 proto->mutable_linear()->add_domain(rhs);
830 return Constraint(proto);
831}
832
834 const LinearExpr& right) {
835 ConstraintProto* const proto = cp_model_.add_constraints();
836 FillLinearTerms(left, right, proto->mutable_linear());
837 const int64_t rhs = right.constant() - left.constant();
838 proto->mutable_linear()->add_domain(rhs);
839 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::max());
840 return Constraint(proto);
841}
842
844 const LinearExpr& right) {
845 ConstraintProto* const proto = cp_model_.add_constraints();
846 FillLinearTerms(left, right, proto->mutable_linear());
847 const int64_t rhs = right.constant() - left.constant();
848 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::min());
849 proto->mutable_linear()->add_domain(rhs);
850 return Constraint(proto);
851}
852
854 const LinearExpr& right) {
855 ConstraintProto* const proto = cp_model_.add_constraints();
856 FillLinearTerms(left, right, proto->mutable_linear());
857 const int64_t rhs = right.constant() - left.constant();
858 proto->mutable_linear()->add_domain(rhs + 1);
859 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::max());
860 return Constraint(proto);
861}
862
864 const LinearExpr& right) {
865 ConstraintProto* const proto = cp_model_.add_constraints();
866 FillLinearTerms(left, right, proto->mutable_linear());
867 const int64_t rhs = right.constant() - left.constant();
868 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::min());
869 proto->mutable_linear()->add_domain(rhs - 1);
870 return Constraint(proto);
871}
872
874 const Domain& domain) {
875 ConstraintProto* const proto = cp_model_.add_constraints();
876 for (const int x : expr.variables()) {
877 proto->mutable_linear()->add_vars(x);
878 }
879 for (const int64_t coeff : expr.coefficients()) {
880 proto->mutable_linear()->add_coeffs(coeff);
881 }
882 const int64_t cst = expr.constant();
883 for (const auto& i : domain) {
884 proto->mutable_linear()->add_domain(i.start - cst);
885 proto->mutable_linear()->add_domain(i.end - cst);
886 }
887 return Constraint(proto);
888}
889
891 const LinearExpr& right) {
892 ConstraintProto* const proto = cp_model_.add_constraints();
893 FillLinearTerms(left, right, proto->mutable_linear());
894 const int64_t rhs = right.constant() - left.constant();
895 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::min());
896 proto->mutable_linear()->add_domain(rhs - 1);
897 proto->mutable_linear()->add_domain(rhs + 1);
898 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::max());
899 return Constraint(proto);
900}
901
902Constraint CpModelBuilder::AddAllDifferent(absl::Span<const IntVar> vars) {
903 ConstraintProto* const proto = cp_model_.add_constraints();
904 for (const IntVar& var : vars) {
905 auto* expr = proto->mutable_all_diff()->add_exprs();
906 expr->add_vars(var.index_);
907 expr->add_coeffs(1);
908 }
909 return Constraint(proto);
910}
911
912Constraint CpModelBuilder::AddAllDifferent(absl::Span<const LinearExpr> exprs) {
913 ConstraintProto* const proto = cp_model_.add_constraints();
914 for (const LinearExpr& expr : exprs) {
915 *proto->mutable_all_diff()->add_exprs() = LinearExprToProto(expr);
916 }
917 return Constraint(proto);
918}
919
921 std::initializer_list<LinearExpr> exprs) {
922 ConstraintProto* const proto = cp_model_.add_constraints();
923 for (const LinearExpr& expr : exprs) {
924 *proto->mutable_all_diff()->add_exprs() = LinearExprToProto(expr);
925 }
926 return Constraint(proto);
927}
928
930 LinearExpr index, absl::Span<const IntVar> variables, LinearExpr target) {
931 ConstraintProto* const proto = cp_model_.add_constraints();
932 *proto->mutable_element()->mutable_linear_index() = LinearExprToProto(index);
933 *proto->mutable_element()->mutable_linear_target() =
934 LinearExprToProto(target);
935 for (const IntVar& var : variables) {
936 *proto->mutable_element()->add_exprs() = LinearExprToProto(var);
937 }
938 return Constraint(proto);
939}
940
942 absl::Span<const int64_t> values,
943 LinearExpr target) {
944 ConstraintProto* const proto = cp_model_.add_constraints();
945 *proto->mutable_element()->mutable_linear_index() = LinearExprToProto(index);
946 *proto->mutable_element()->mutable_linear_target() =
947 LinearExprToProto(target);
948 for (int64_t value : values) {
949 proto->mutable_element()->add_exprs()->set_offset(value);
950 }
951 return Constraint(proto);
952}
953
955 absl::Span<const LinearExpr> expressions,
956 LinearExpr target) {
957 ConstraintProto* const proto = cp_model_.add_constraints();
958 *proto->mutable_element()->mutable_linear_index() = LinearExprToProto(index);
959 *proto->mutable_element()->mutable_linear_target() =
960 LinearExprToProto(target);
961 for (const LinearExpr& expr : expressions) {
962 *proto->mutable_element()->add_exprs() = LinearExprToProto(expr);
963 }
964 return Constraint(proto);
965}
966
968 LinearExpr index, std::initializer_list<LinearExpr> expressions,
969 LinearExpr target) {
970 ConstraintProto* const proto = cp_model_.add_constraints();
971 *proto->mutable_element()->mutable_linear_index() = LinearExprToProto(index);
972 *proto->mutable_element()->mutable_linear_target() =
973 LinearExprToProto(target);
974 for (const LinearExpr& expr : expressions) {
975 *proto->mutable_element()->add_exprs() = LinearExprToProto(expr);
976 }
977 return Constraint(proto);
978}
979
981 return CircuitConstraint(cp_model_.add_constraints());
982}
983
987
989 absl::Span<const LinearExpr> expressions) {
990 ConstraintProto* const proto = cp_model_.add_constraints();
991 for (const LinearExpr& expr : expressions) {
992 *proto->mutable_table()->add_exprs() = LinearExprToProto(expr);
993 }
994 return TableConstraint(proto);
995}
996
998 absl::Span<const IntVar> variables) {
999 ConstraintProto* const proto = cp_model_.add_constraints();
1000 for (const IntVar var : variables) {
1001 LinearExpressionProto* expr = proto->mutable_table()->add_exprs();
1002 expr->add_vars(var.index_);
1003 expr->add_coeffs(1);
1004 }
1005 return TableConstraint(proto);
1006}
1007
1009 std::initializer_list<LinearExpr> expressions) {
1010 ConstraintProto* const proto = cp_model_.add_constraints();
1011 for (const LinearExpr& expr : expressions) {
1012 *proto->mutable_table()->add_exprs() = LinearExprToProto(expr);
1013 }
1014 return TableConstraint(proto);
1015}
1016
1018 absl::Span<const LinearExpr> expressions) {
1019 TableConstraint ct = AddAllowedAssignments(expressions);
1020 ct.MutableProto()->mutable_table()->set_negated(true);
1021 return ct;
1022}
1023
1025 absl::Span<const IntVar> variables) {
1026 TableConstraint ct = AddAllowedAssignments(variables);
1027 ct.MutableProto()->mutable_table()->set_negated(true);
1028 return ct;
1029}
1030
1032 std::initializer_list<LinearExpr> expressions) {
1033 TableConstraint ct = AddAllowedAssignments(expressions);
1034 ct.MutableProto()->mutable_table()->set_negated(true);
1035 return ct;
1036}
1037
1039 absl::Span<const IntVar> variables,
1040 absl::Span<const IntVar> inverse_variables) {
1041 ConstraintProto* const proto = cp_model_.add_constraints();
1042 for (const IntVar& var : variables) {
1043 proto->mutable_inverse()->add_f_direct(var.index_);
1044 }
1045 for (const IntVar& var : inverse_variables) {
1046 proto->mutable_inverse()->add_f_inverse(var.index_);
1047 }
1048 return Constraint(proto);
1049}
1050
1052 int64_t max_level) {
1053 ConstraintProto* const proto = cp_model_.add_constraints();
1054 proto->mutable_reservoir()->set_min_level(min_level);
1055 proto->mutable_reservoir()->set_max_level(max_level);
1056 return ReservoirConstraint(proto, this);
1057}
1058
1060 absl::Span<const LinearExpr> transition_expressions, int starting_state,
1061 absl::Span<const int> final_states) {
1062 ConstraintProto* const proto = cp_model_.add_constraints();
1063 for (const LinearExpr& expr : transition_expressions) {
1064 *proto->mutable_automaton()->add_exprs() = LinearExprToProto(expr);
1065 }
1066 proto->mutable_automaton()->set_starting_state(starting_state);
1067 for (const int final_state : final_states) {
1068 proto->mutable_automaton()->add_final_states(final_state);
1069 }
1070 return AutomatonConstraint(proto);
1071}
1072
1074 absl::Span<const IntVar> transition_variables, int starting_state,
1075 absl::Span<const int> final_states) {
1076 ConstraintProto* const proto = cp_model_.add_constraints();
1077 for (const IntVar& var : transition_variables) {
1078 LinearExpressionProto* expr = proto->mutable_automaton()->add_exprs();
1079 expr->add_vars(var.index_);
1080 expr->add_coeffs(1);
1081 }
1082 proto->mutable_automaton()->set_starting_state(starting_state);
1083 for (const int final_state : final_states) {
1084 proto->mutable_automaton()->add_final_states(final_state);
1085 }
1086 return AutomatonConstraint(proto);
1087}
1088
1090 std::initializer_list<LinearExpr> transition_expressions,
1091 int starting_state, absl::Span<const int> final_states) {
1092 ConstraintProto* const proto = cp_model_.add_constraints();
1093 for (const LinearExpr& expr : transition_expressions) {
1094 *proto->mutable_automaton()->add_exprs() = LinearExprToProto(expr);
1095 }
1096 proto->mutable_automaton()->set_starting_state(starting_state);
1097 for (const int final_state : final_states) {
1098 proto->mutable_automaton()->add_final_states(final_state);
1099 }
1100 return AutomatonConstraint(proto);
1101}
1102
1103LinearExpressionProto CpModelBuilder::LinearExprToProto(const LinearExpr& expr,
1104 bool negate) {
1105 LinearExpressionProto expr_proto;
1106 for (const int var : expr.variables()) {
1107 expr_proto.add_vars(var);
1108 }
1109 const int64_t mult = negate ? -1 : 1;
1110 for (const int64_t coeff : expr.coefficients()) {
1111 expr_proto.add_coeffs(coeff * mult);
1112 }
1113 expr_proto.set_offset(expr.constant() * mult);
1114 return expr_proto;
1115}
1116
1118 absl::Span<const IntVar> vars) {
1119 ConstraintProto* ct = cp_model_.add_constraints();
1120 *ct->mutable_lin_max()->mutable_target() =
1121 LinearExprToProto(target, /*negate=*/true);
1122 for (const IntVar& var : vars) {
1123 *ct->mutable_lin_max()->add_exprs() =
1124 LinearExprToProto(var, /*negate=*/true);
1125 }
1126 return Constraint(ct);
1127}
1128
1130 absl::Span<const LinearExpr> exprs) {
1131 ConstraintProto* ct = cp_model_.add_constraints();
1132 *ct->mutable_lin_max()->mutable_target() =
1133 LinearExprToProto(target, /*negate=*/true);
1134 for (const LinearExpr& expr : exprs) {
1135 *ct->mutable_lin_max()->add_exprs() =
1136 LinearExprToProto(expr, /*negate=*/true);
1137 }
1138 return Constraint(ct);
1139}
1140
1142 const LinearExpr& target, std::initializer_list<LinearExpr> exprs) {
1143 ConstraintProto* ct = cp_model_.add_constraints();
1144 *ct->mutable_lin_max()->mutable_target() =
1145 LinearExprToProto(target, /*negate=*/true);
1146 for (const LinearExpr& expr : exprs) {
1147 *ct->mutable_lin_max()->add_exprs() =
1148 LinearExprToProto(expr, /*negate=*/true);
1149 }
1150 return Constraint(ct);
1151}
1152
1154 absl::Span<const IntVar> vars) {
1155 ConstraintProto* ct = cp_model_.add_constraints();
1156 *ct->mutable_lin_max()->mutable_target() = LinearExprToProto(target);
1157 for (const IntVar& var : vars) {
1158 *ct->mutable_lin_max()->add_exprs() = LinearExprToProto(var);
1159 }
1160 return Constraint(ct);
1161}
1162
1164 absl::Span<const LinearExpr> exprs) {
1165 ConstraintProto* ct = cp_model_.add_constraints();
1166 *ct->mutable_lin_max()->mutable_target() = LinearExprToProto(target);
1167 for (const LinearExpr& expr : exprs) {
1168 *ct->mutable_lin_max()->add_exprs() = LinearExprToProto(expr);
1169 }
1170 return Constraint(ct);
1171}
1172
1174 const LinearExpr& target, std::initializer_list<LinearExpr> exprs) {
1175 ConstraintProto* ct = cp_model_.add_constraints();
1176 *ct->mutable_lin_max()->mutable_target() = LinearExprToProto(target);
1177 for (const LinearExpr& expr : exprs) {
1178 *ct->mutable_lin_max()->add_exprs() = LinearExprToProto(expr);
1179 }
1180 return Constraint(ct);
1181}
1182
1184 const LinearExpr& numerator,
1185 const LinearExpr& denominator) {
1186 ConstraintProto* const proto = cp_model_.add_constraints();
1187 *proto->mutable_int_div()->mutable_target() = LinearExprToProto(target);
1188 *proto->mutable_int_div()->add_exprs() = LinearExprToProto(numerator);
1189 *proto->mutable_int_div()->add_exprs() = LinearExprToProto(denominator);
1190 return Constraint(proto);
1191}
1192
1194 const LinearExpr& expr) {
1195 ConstraintProto* const proto = cp_model_.add_constraints();
1196 *proto->mutable_lin_max()->mutable_target() = LinearExprToProto(target);
1197 *proto->mutable_lin_max()->add_exprs() = LinearExprToProto(expr);
1198 *proto->mutable_lin_max()->add_exprs() =
1199 LinearExprToProto(expr, /*negate=*/true);
1200 return Constraint(proto);
1201}
1202
1204 const LinearExpr& var,
1205 const LinearExpr& mod) {
1206 ConstraintProto* const proto = cp_model_.add_constraints();
1207 *proto->mutable_int_mod()->mutable_target() = LinearExprToProto(target);
1208 *proto->mutable_int_mod()->add_exprs() = LinearExprToProto(var);
1209 *proto->mutable_int_mod()->add_exprs() = LinearExprToProto(mod);
1210 return Constraint(proto);
1211}
1212
1214 const LinearExpr& target, absl::Span<const IntVar> vars) {
1215 ConstraintProto* const proto = cp_model_.add_constraints();
1216 *proto->mutable_int_prod()->mutable_target() = LinearExprToProto(target);
1217 for (const IntVar& var : vars) {
1218 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(var);
1219 }
1220 return Constraint(proto);
1221}
1222
1224 const LinearExpr& target, absl::Span<const LinearExpr> exprs) {
1225 ConstraintProto* const proto = cp_model_.add_constraints();
1226 *proto->mutable_int_prod()->mutable_target() = LinearExprToProto(target);
1227 for (const LinearExpr& expr : exprs) {
1228 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(expr);
1229 }
1230 return Constraint(proto);
1231}
1232
1234 const LinearExpr& target, std::initializer_list<LinearExpr> exprs) {
1235 ConstraintProto* const proto = cp_model_.add_constraints();
1236 *proto->mutable_int_prod()->mutable_target() = LinearExprToProto(target);
1237 for (const LinearExpr& expr : exprs) {
1238 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(expr);
1239 }
1240 return Constraint(proto);
1241}
1243 const LinearExpr& left,
1244 const LinearExpr& right) {
1245 ConstraintProto* const proto = cp_model_.add_constraints();
1246 *proto->mutable_int_prod()->mutable_target() = LinearExprToProto(target);
1247 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(left);
1248 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(right);
1249
1250 return Constraint(proto);
1251}
1252
1253Constraint CpModelBuilder::AddNoOverlap(absl::Span<const IntervalVar> vars) {
1254 ConstraintProto* const proto = cp_model_.add_constraints();
1255 for (const IntervalVar& var : vars) {
1256 proto->mutable_no_overlap()->add_intervals(var.index_);
1257 }
1258 return Constraint(proto);
1259}
1260
1262 return NoOverlap2DConstraint(cp_model_.add_constraints());
1263}
1264
1266 ConstraintProto* const proto = cp_model_.add_constraints();
1267 *proto->mutable_cumulative()->mutable_capacity() =
1268 LinearExprToProto(capacity);
1269 return CumulativeConstraint(proto, this);
1270}
1271
1274 for (const int x : expr.variables()) {
1275 cp_model_.mutable_objective()->add_vars(x);
1276 }
1277 for (const int64_t coeff : expr.coefficients()) {
1278 cp_model_.mutable_objective()->add_coeffs(coeff);
1279 }
1280 cp_model_.mutable_objective()->set_offset(expr.constant());
1281}
1282
1285 for (const int x : expr.variables()) {
1286 cp_model_.mutable_objective()->add_vars(x);
1287 }
1288 for (const int64_t coeff : expr.coefficients()) {
1289 cp_model_.mutable_objective()->add_coeffs(-coeff);
1290 }
1291 cp_model_.mutable_objective()->set_offset(-expr.constant());
1292 cp_model_.mutable_objective()->set_scaling_factor(-1.0);
1293}
1294
1297 for (int i = 0; i < expr.variables().size(); ++i) {
1298 cp_model_.mutable_floating_point_objective()->add_vars(expr.variables()[i]);
1299 cp_model_.mutable_floating_point_objective()->add_coeffs(
1300 expr.coefficients()[i]);
1301 }
1302 cp_model_.mutable_floating_point_objective()->set_offset(expr.constant());
1303 cp_model_.mutable_floating_point_objective()->set_maximize(false);
1304}
1305
1308 for (int i = 0; i < expr.variables().size(); ++i) {
1309 cp_model_.mutable_floating_point_objective()->add_vars(expr.variables()[i]);
1310 cp_model_.mutable_floating_point_objective()->add_coeffs(
1311 expr.coefficients()[i]);
1312 }
1313 cp_model_.mutable_floating_point_objective()->set_offset(expr.constant());
1314 cp_model_.mutable_floating_point_objective()->set_maximize(true);
1315}
1316
1318 cp_model_.clear_objective();
1319 cp_model_.clear_floating_point_objective();
1320}
1321
1323 return cp_model_.has_objective() || cp_model_.has_floating_point_objective();
1324}
1325
1327 absl::Span<const IntVar> variables,
1328 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1329 DecisionStrategyProto::DomainReductionStrategy domain_strategy) {
1330 DecisionStrategyProto* const proto = cp_model_.add_search_strategy();
1331 for (const IntVar& var : variables) {
1332 LinearExpressionProto* expr = proto->add_exprs();
1333 if (var.index_ >= 0) {
1334 expr->add_vars(var.index_);
1335 expr->add_coeffs(1);
1336 } else {
1337 expr->add_vars(PositiveRef(var.index_));
1338 expr->add_coeffs(-1);
1339 expr->set_offset(1);
1340 }
1341 }
1342 proto->set_variable_selection_strategy(var_strategy);
1343 proto->set_domain_reduction_strategy(domain_strategy);
1344}
1345
1347 absl::Span<const BoolVar> variables,
1348 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1349 DecisionStrategyProto::DomainReductionStrategy domain_strategy) {
1350 DecisionStrategyProto* const proto = cp_model_.add_search_strategy();
1351 for (const BoolVar& var : variables) {
1352 LinearExpressionProto* expr = proto->add_exprs();
1353 if (var.index_ >= 0) {
1354 expr->add_vars(var.index_);
1355 expr->add_coeffs(1);
1356 } else {
1357 expr->add_vars(PositiveRef(var.index_));
1358 expr->add_coeffs(-1);
1359 expr->set_offset(1);
1360 }
1361 }
1362 proto->set_variable_selection_strategy(var_strategy);
1363 proto->set_domain_reduction_strategy(domain_strategy);
1364}
1365
1367 absl::Span<const LinearExpr> expressions,
1368 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1369 DecisionStrategyProto::DomainReductionStrategy domain_strategy) {
1370 DecisionStrategyProto* const proto = cp_model_.add_search_strategy();
1371 for (const LinearExpr& expr : expressions) {
1372 *proto->add_exprs() = LinearExprToProto(expr);
1373 }
1374 proto->set_variable_selection_strategy(var_strategy);
1375 proto->set_domain_reduction_strategy(domain_strategy);
1376}
1377
1379 std::initializer_list<LinearExpr> expressions,
1380 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1381 DecisionStrategyProto::DomainReductionStrategy domain_strategy) {
1382 DecisionStrategyProto* const proto = cp_model_.add_search_strategy();
1383 for (const LinearExpr& expr : expressions) {
1384 *proto->add_exprs() = LinearExprToProto(expr);
1385 }
1386 proto->set_variable_selection_strategy(var_strategy);
1387 proto->set_domain_reduction_strategy(domain_strategy);
1388}
1389
1390void CpModelBuilder::AddHint(IntVar var, int64_t value) {
1391 cp_model_.mutable_solution_hint()->add_vars(var.index_);
1392 cp_model_.mutable_solution_hint()->add_values(value);
1393}
1394
1395void CpModelBuilder::AddHint(BoolVar var, bool value) {
1396 if (var.index_ >= 0) {
1397 cp_model_.mutable_solution_hint()->add_vars(var.index_);
1398 cp_model_.mutable_solution_hint()->add_values(value);
1399 } else {
1400 cp_model_.mutable_solution_hint()->add_vars(PositiveRef(var.index_));
1401 cp_model_.mutable_solution_hint()->add_values(!value);
1402 }
1403}
1404
1406 cp_model_.mutable_solution_hint()->Clear();
1407}
1408
1410 cp_model_.mutable_assumptions()->Add(lit.index_);
1411}
1412
1413void CpModelBuilder::AddAssumptions(absl::Span<const BoolVar> literals) {
1414 for (const BoolVar& lit : literals) {
1415 cp_model_.mutable_assumptions()->Add(lit.index_);
1416 }
1417}
1418
1420 cp_model_.mutable_assumptions()->Clear();
1421}
1422
1424 CpModelBuilder clone;
1425 clone.ResetAndImport(cp_model_);
1426 return clone;
1427}
1428
1429void CpModelBuilder::ResetAndImport(const CpModelProto& model_proto) {
1430 cp_model_ = model_proto;
1431 // Rebuild constant to index map.
1432 constant_to_index_map_.clear();
1433 for (int i = 0; i < cp_model_.variables_size(); ++i) {
1434 const IntegerVariableProto& var = cp_model_.variables(i);
1435 if (var.domain_size() == 2 && var.domain(0) == var.domain(1)) {
1436 constant_to_index_map_[var.domain(0)] = i;
1437 }
1438 }
1439 // This one would be more complicated to rebuild. Let's just clear it.
1440 bool_to_integer_index_map_.clear();
1441}
1442
1444 CHECK_GE(index, 0);
1445 CHECK_LT(index, cp_model_.variables_size());
1446 const IntegerVariableProto& proto = cp_model_.variables(index);
1447 CHECK_EQ(2, proto.domain_size())
1448 << "CpModelBuilder::GetBoolVarFromProtoIndex: The domain of the variable "
1449 "is not Boolean";
1450 CHECK_GE(0, proto.domain(0))
1451 << "CpModelBuilder::GetBoolVarFromProtoIndex: The domain of the variable "
1452 "is not Boolean";
1453 CHECK_LE(1, proto.domain(1))
1454 << "CpModelBuilder::GetBoolVarFromProtoIndex: The domain of the variable "
1455 "is not Boolean";
1456 return BoolVar(index, this);
1457}
1458
1460 CHECK_GE(index, 0);
1461 CHECK_LT(index, cp_model_.variables_size());
1462 return IntVar(index, this);
1463}
1464
1466 CHECK_GE(index, 0);
1467 CHECK_LT(index, cp_model_.constraints_size());
1468 const ConstraintProto& ct = cp_model_.constraints(index);
1469 CHECK_EQ(ct.constraint_case(), ConstraintProto::kInterval)
1470 << "CpModelBuilder::GetIntervalVarFromProtoIndex: the referenced "
1471 "object is not an interval variable";
1472 return IntervalVar(index, this);
1473}
1474
1475bool CpModelBuilder::ExportToFile(absl::string_view filename) const {
1476 return WriteModelProtoToFile(cp_model_, filename);
1477}
1478
1479int64_t SolutionIntegerValue(const CpSolverResponse& r,
1480 const LinearExpr& expr) {
1481 int64_t result = expr.constant();
1482 const std::vector<int>& variables = expr.variables();
1483 const std::vector<int64_t>& coefficients = expr.coefficients();
1484 for (int i = 0; i < variables.size(); ++i) {
1485 result += r.solution(variables[i]) * coefficients[i];
1486 }
1487 return result;
1488}
1489
1490bool SolutionBooleanValue(const CpSolverResponse& r, BoolVar x) {
1491 const int ref = x.index_;
1492 if (RefIsPositive(ref)) {
1493 return r.solution(ref) == 1;
1494 } else {
1495 return r.solution(PositiveRef(ref)) == 0;
1496 }
1497}
1498
1499} // namespace sat
1500} // namespace operations_research
virtual std::string DebugString() const
IntVar(Solver *s)
-------— IntVar -------—
LinearExpr & operator+=(const LinearExpr &rhs)
LinearExpr & operator-=(const LinearExpr &rhs)
LinearExpr & operator*=(double rhs)
virtual std::string name() const
Object naming.
void AddTransition(int tail, int head, int64_t transition_label)
Adds a transitions to the automaton.
Definition cp_model.cc:554
BoolVar WithName(absl::string_view name)
Definition cp_model.cc:39
std::string Name() const
Returns the name of the variable.
Definition cp_model.cc:48
BoolVar Not() const
Returns the logical negation of the current Boolean variable.
Definition cp_model.h:91
std::string DebugString() const
Definition cp_model.cc:59
void AddArc(int tail, int head, BoolVar literal)
Definition cp_model.cc:514
Constraint WithName(absl::string_view name)
Sets the name of the constraint.
Definition cp_model.cc:495
Constraint OnlyEnforceIf(absl::Span< const BoolVar > literals)
Definition cp_model.cc:502
Constraint(ConstraintProto *proto)
Definition cp_model.cc:493
ConstraintProto * MutableProto() const
Returns the mutable underlying protobuf object (useful for model edition).
Definition cp_model.h:567
absl::string_view Name() const
Returns the name of the constraint (or the empty string if not set).
Definition cp_model.cc:500
bool HasObjective() const
Checks whether the model contains an objective.
Definition cp_model.cc:1322
BoolVar GetBoolVarFromProtoIndex(int index)
Returns the Boolean variable from its index in the proto.
Definition cp_model.cc:1443
IntVar NewIntVar(const Domain &domain)
Creates an integer variable with the given domain.
Definition cp_model.cc:682
Constraint AddInverseConstraint(absl::Span< const IntVar > variables, absl::Span< const IntVar > inverse_variables)
Definition cp_model.cc:1038
void Minimize(const LinearExpr &expr)
Adds a linear minimization objective.
Definition cp_model.cc:1272
NoOverlap2DConstraint AddNoOverlap2D()
Definition cp_model.cc:1261
Constraint AddBoolXor(absl::Span< const BoolVar > literals)
Adds the constraint that an odd number of literals is true.
Definition cp_model.cc:798
IntervalVar NewIntervalVar(const LinearExpr &start, const LinearExpr &size, const LinearExpr &end)
Creates an interval variable from 3 affine expressions.
Definition cp_model.cc:712
IntVar GetIntVarFromProtoIndex(int index)
Returns the integer variable from its index in the proto.
Definition cp_model.cc:1459
Constraint AddMultiplicationEquality(const LinearExpr &target, absl::Span< const LinearExpr > exprs)
Adds target == prod(exprs).
Definition cp_model.cc:1223
CpModelBuilder Clone() const
Returns a cloned version of the current model.
Definition cp_model.cc:1423
Constraint AddBoolAnd(absl::Span< const BoolVar > literals)
Adds the constraint that all literals must be true.
Definition cp_model.cc:790
Constraint AddMaxEquality(const LinearExpr &target, absl::Span< const IntVar > vars)
Adds target == max(vars).
Definition cp_model.cc:1153
void Maximize(const LinearExpr &expr)
Adds a linear maximization objective.
Definition cp_model.cc:1283
TableConstraint AddAllowedAssignments(absl::Span< const LinearExpr > expressions)
Definition cp_model.cc:988
void FixVariable(IntVar var, int64_t value)
Definition cp_model.cc:750
ReservoirConstraint AddReservoirConstraint(int64_t min_level, int64_t max_level)
Definition cp_model.cc:1051
void AddDecisionStrategy(absl::Span< const IntVar > variables, DecisionStrategyProto::VariableSelectionStrategy var_strategy, DecisionStrategyProto::DomainReductionStrategy domain_strategy)
Adds a decision strategy on a list of integer variables.
Definition cp_model.cc:1326
Constraint AddLessOrEqual(const LinearExpr &left, const LinearExpr &right)
Adds left <= right.
Definition cp_model.cc:843
IntervalVar NewOptionalIntervalVar(const LinearExpr &start, const LinearExpr &size, const LinearExpr &end, BoolVar presence)
Definition cp_model.cc:723
void ClearAssumptions()
Remove all assumptions from the model.
Definition cp_model.cc:1419
Constraint AddLinearConstraint(const LinearExpr &expr, const Domain &domain)
Adds expr in domain.
Definition cp_model.cc:873
void AddHint(IntVar var, int64_t value)
Adds hinting to a variable.
Definition cp_model.cc:1390
Constraint AddAllDifferent(absl::Span< const IntVar > vars)
This constraint forces all variables to have different values.
Definition cp_model.cc:902
IntervalVar GetIntervalVarFromProtoIndex(int index)
Returns the interval variable from its index in the proto.
Definition cp_model.cc:1465
AutomatonConstraint AddAutomaton(absl::Span< const LinearExpr > transition_expressions, int starting_state, absl::Span< const int > final_states)
Definition cp_model.cc:1059
Constraint AddExactlyOne(absl::Span< const BoolVar > literals)
Exactly one literal is true. Sum literals == 1.
Definition cp_model.cc:783
Constraint AddMinEquality(const LinearExpr &target, absl::Span< const IntVar > vars)
Adds target == min(vars).
Definition cp_model.cc:1117
void AddAssumption(BoolVar lit)
Adds a literal to the model as assumptions.
Definition cp_model.cc:1409
bool ExportToFile(absl::string_view filename) const
Export the model to file.
Definition cp_model.cc:1475
Constraint AddGreaterOrEqual(const LinearExpr &left, const LinearExpr &right)
Adds left >= right.
Definition cp_model.cc:833
Constraint AddLessThan(const LinearExpr &left, const LinearExpr &right)
Adds left < right.
Definition cp_model.cc:863
MultipleCircuitConstraint AddMultipleCircuitConstraint()
Definition cp_model.cc:984
Constraint AddNoOverlap(absl::Span< const IntervalVar > vars)
Definition cp_model.cc:1253
BoolVar NewBoolVar()
Creates a Boolean variable.
Definition cp_model.cc:692
Constraint AddNotEqual(const LinearExpr &left, const LinearExpr &right)
Adds left != right.
Definition cp_model.cc:890
Constraint AddAtLeastOne(absl::Span< const BoolVar > literals)
Same as AddBoolOr(). Sum literals >= 1.
Definition cp_model.cc:771
void ClearObjective()
Removes the objective from the model.
Definition cp_model.cc:1317
Constraint AddAtMostOne(absl::Span< const BoolVar > literals)
At most one literal is true. Sum literals <= 1.
Definition cp_model.cc:775
void ClearHints()
Removes all hints.
Definition cp_model.cc:1405
void AddAssumptions(absl::Span< const BoolVar > literals)
Adds multiple literals to the model as assumptions.
Definition cp_model.cc:1413
Constraint AddGreaterThan(const LinearExpr &left, const LinearExpr &right)
Adds left > right.
Definition cp_model.cc:853
Constraint AddDivisionEquality(const LinearExpr &target, const LinearExpr &numerator, const LinearExpr &denominator)
Adds target = num / denom (integer division rounded towards 0).
Definition cp_model.cc:1183
Constraint AddEquality(const LinearExpr &left, const LinearExpr &right)
Adds left == right.
Definition cp_model.cc:823
TableConstraint AddForbiddenAssignments(absl::Span< const LinearExpr > expression)
Definition cp_model.cc:1017
void SetName(absl::string_view name)
Sets the name of the model.
Definition cp_model.cc:646
Constraint AddAbsEquality(const LinearExpr &target, const LinearExpr &expr)
Adds target == abs(expr).
Definition cp_model.cc:1193
Constraint AddBoolOr(absl::Span< const BoolVar > literals)
Adds the constraint that at least one of the literals must be true.
Definition cp_model.cc:764
IntervalVar NewFixedSizeIntervalVar(const LinearExpr &start, int64_t size)
Creates an interval variable with a fixed size.
Definition cp_model.cc:718
CumulativeConstraint AddCumulative(LinearExpr capacity)
Definition cp_model.cc:1265
Constraint AddModuloEquality(const LinearExpr &target, const LinearExpr &var, const LinearExpr &mod)
Adds target = var % mod.
Definition cp_model.cc:1203
Constraint AddVariableElement(LinearExpr index, absl::Span< const IntVar > variables, LinearExpr target)
Adds the element constraint: variables[index] == target.
Definition cp_model.cc:929
IntervalVar NewOptionalFixedSizeIntervalVar(const LinearExpr &start, int64_t size, BoolVar presence)
Creates an optional interval variable with a fixed size.
Definition cp_model.cc:737
Constraint AddElement(LinearExpr index, absl::Span< const LinearExpr > expressions, LinearExpr target)
Adds the element constraint: expressions[index] == target.
Definition cp_model.cc:954
void AddDemand(IntervalVar interval, LinearExpr demand)
Adds a pair (interval, demand) to the constraint.
Definition cp_model.cc:571
const std::vector< double > & coefficients() const
Returns the vector of coefficients.
Definition cp_model.h:411
static DoubleLinearExpr Sum(absl::Span< const IntVar > vars)
Constructs the sum of a list of variables.
Definition cp_model.cc:331
DoubleLinearExpr & operator*=(double coeff)
Multiply the linear expression by a constant.
Definition cp_model.cc:442
DoubleLinearExpr & operator+=(double value)
Adds a constant value to the linear expression.
Definition cp_model.cc:367
DoubleLinearExpr & AddTerm(IntVar var, double coeff)
Adds a term (var * coeff) to the linear expression.
Definition cp_model.cc:391
double constant() const
Returns the constant term.
Definition cp_model.h:417
static DoubleLinearExpr WeightedSum(absl::Span< const IntVar > vars, absl::Span< const double > coeffs)
Constructs the scalar product of variables and coefficients.
Definition cp_model.cc:347
DoubleLinearExpr & operator-=(double value)
Adds a constant value to the linear expression.
Definition cp_model.cc:422
const std::vector< int > & variables() const
Returns the vector of variable indices.
Definition cp_model.h:408
std::string DebugString(const CpModelProto *proto=nullptr) const
Debug string. See the documentation for LinearExpr::DebugString().
Definition cp_model.cc:450
DoubleLinearExpr & AddExpression(const LinearExpr &exprs, double coeff=1.0)
Adds a linear expression to the double linear expression.
Definition cp_model.cc:410
std::string Name() const
Returns the name of the variable (or the empty string if not set).
Definition cp_model.cc:126
std::string DebugString() const
Definition cp_model.cc:136
int index() const
Returns the index of the variable in the model. This will be non-negative.
Definition cp_model.h:192
IntVar WithName(absl::string_view name)
Sets the name of the variable.
Definition cp_model.cc:119
::operations_research::Domain Domain() const
Definition cp_model.cc:131
IntervalVar WithName(absl::string_view name)
Sets the name of the variable.
Definition cp_model.cc:582
std::string Name() const
Returns the name of the interval (or the empty string if not set).
Definition cp_model.cc:617
std::string DebugString() const
Returns a debug string.
Definition cp_model.cc:622
static LinearExpr Sum(absl::Span< const IntVar > vars)
NOLINTEND(google-explicit-constructor)
Definition cp_model.cc:207
std::string DebugString(const CpModelProto *proto=nullptr) const
Definition cp_model.cc:280
static LinearExpr WeightedSum(absl::Span< const IntVar > vars, absl::Span< const int64_t > coeffs)
Constructs the scalar product of variables and coefficients.
Definition cp_model.cc:223
static LinearExpr Term(IntVar var, int64_t coefficient)
Constructs var * coefficient.
Definition cp_model.cc:243
int64_t constant() const
Returns the constant term.
Definition cp_model.h:303
LinearExpr()=default
Creates an empty linear expression with value zero.
static LinearExpr FromProto(const LinearExpressionProto &proto)
Constructs a linear expr from its proto representation.
Definition cp_model.cc:198
const std::vector< int > & variables() const
Returns the vector of variable indices.
Definition cp_model.h:294
const std::vector< int64_t > & coefficients() const
Returns the vector of coefficients.
Definition cp_model.h:297
void AddArc(int tail, int head, BoolVar literal)
Definition cp_model.cc:520
void AddRectangle(IntervalVar x_coordinate, IntervalVar y_coordinate)
Adds a rectangle (parallel to the axis) to the constraint.
Definition cp_model.cc:561
void AddOptionalEvent(LinearExpr time, int64_t level_change, BoolVar is_active)
Definition cp_model.cc:545
void AddEvent(LinearExpr time, int64_t level_change)
Definition cp_model.cc:537
void AddTuple(absl::Span< const int64_t > tuple)
Adds a tuple of possible values to the constraint.
Definition cp_model.cc:526
std::string VarDebugString(const CpModelProto &proto, int index)
Definition cp_model.cc:143
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
BoolVar Not(BoolVar x)
Definition cp_model.cc:87
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
Definition cp_model.cc:89
void FillDomainInProto(const Domain &domain, ProtoWithDomain *proto)
Serializes a Domain into the domain field of a proto.
Domain ReadDomainFromProto(const ProtoWithDomain &proto)
Reads a Domain from the domain field of a proto.
int64_t SolutionIntegerValue(const CpSolverResponse &r, const LinearExpr &expr)
Evaluates the value of an linear expression in a solver response.
Definition cp_model.cc:1479
int NegatedRef(int ref)
Small utility functions to deal with negative variable/literal references.
bool SolutionBooleanValue(const CpSolverResponse &r, BoolVar x)
Evaluates the value of a Boolean literal in a solver response.
Definition cp_model.cc:1490
In SWIG mode, we don't want anything besides these top-level includes.
std::ostream & operator<<(std::ostream &out, const Assignment &assignment)
std::ostream & operator<<(std::ostream &out, const std::pair< First, Second > &p)
Definition stl_logging.h:99