17#include <initializer_list>
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"
37 : builder_(builder), index_(index) {}
40 DCHECK(builder_ !=
nullptr);
41 if (builder_ ==
nullptr)
return *
this;
42 builder_->MutableProto()
49 if (builder_ ==
nullptr)
return "null";
50 const std::string& name =
51 builder_->Proto().variables(
PositiveRef(index_)).name();
55 return absl::StrCat(
"Not(", name,
")");
60 if (builder_ ==
nullptr)
return "null";
65 const IntegerVariableProto& var_proto = builder_->Proto().variables(index_);
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");
71 if (var_proto.name().empty()) {
72 absl::StrAppendFormat(&output,
"BoolVar%i(", index_);
74 absl::StrAppendFormat(&output,
"%s(", var_proto.name());
76 if (var_proto.domain(0) == var_proto.domain(1)) {
77 output.append(var_proto.domain(0) == 0 ?
"false)" :
"true)");
79 absl::StrAppend(&output, var_proto.domain(0),
", ", var_proto.domain(1),
95 : builder_(builder), index_(index) {
100 if (var.builder_ ==
nullptr) {
104 builder_ = var.builder_;
105 index_ = builder_->GetOrCreateIntegerIndex(var.index_);
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);
116 return BoolVar(index_, builder_);
120 DCHECK(builder_ !=
nullptr);
121 if (builder_ ==
nullptr)
return *
this;
122 builder_->MutableProto()->mutable_variables(index_)->set_name(
name);
127 if (builder_ ==
nullptr)
return "null";
128 return builder_->Proto().variables(index_).name();
132 if (builder_ ==
nullptr)
return Domain();
137 if (builder_ ==
nullptr)
return "null";
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));
152 if (var_proto.name().empty()) {
153 absl::StrAppend(&output,
"V", index,
"(");
155 absl::StrAppend(&output, var_proto.name(),
"(");
159 if (var_proto.domain_size() == 2 &&
160 var_proto.domain(0) == var_proto.domain(1)) {
161 absl::StrAppend(&output, var_proto.domain(0),
")");
163 absl::StrAppend(&output, var_proto.domain(0),
", ", var_proto.domain(1),
177 DCHECK(var.builder_ !=
nullptr);
178 const int index = var.index_;
180 variables_.push_back(index);
181 coefficients_.push_back(1);
185 coefficients_.push_back(-1);
191 DCHECK(var.builder_ !=
nullptr);
192 variables_.push_back(var.index_);
193 coefficients_.push_back(1);
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));
209 for (
const IntVar& var : vars) {
217 for (
const BoolVar& var : vars) {
224 absl::Span<const int64_t> coeffs) {
225 CHECK_EQ(vars.size(), coeffs.size());
227 for (
int i = 0;
i < vars.size(); ++
i) {
228 result += vars[
i] * coeffs[
i];
234 absl::Span<const int64_t> coeffs) {
235 CHECK_EQ(vars.size(), coeffs.size());
237 for (
int i = 0;
i < vars.size(); ++
i) {
238 result += vars[
i] * coeffs[
i];
245 result += var * coefficient;
251 result += var * coefficient;
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());
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);
276 for (int64_t& coeff : coefficients_) coeff *= factor;
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])
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);
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);
306 if (constant_ != 0) {
307 if (variables_.empty()) {
308 return absl::StrCat(constant_);
309 }
else if (constant_ > 0) {
310 absl::StrAppend(&result,
" + ", constant_);
312 absl::StrAppend(&result,
" - ", -constant_);
323DoubleLinearExpr::DoubleLinearExpr() =
default;
333 for (
const IntVar& var : vars) {
341 for (
const BoolVar& var : vars) {
348 absl::Span<const IntVar> vars, absl::Span<const double> coeffs) {
349 CHECK_EQ(vars.size(), coeffs.size());
351 for (
int i = 0;
i < vars.size(); ++
i) {
358 absl::Span<const BoolVar> vars, absl::Span<const double> coeffs) {
359 CHECK_EQ(vars.size(), coeffs.size());
361 for (
int i = 0;
i < vars.size(); ++
i) {
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());
392 variables_.push_back(var.index_);
393 coefficients_.push_back(coeff);
398 const int index = var.index_;
400 variables_.push_back(index);
401 coefficients_.push_back(coeff);
404 coefficients_.push_back(-coeff);
412 const std::vector<int>& indices = expr.
variables();
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);
433 constant_ -= expr.constant_;
434 variables_.insert(variables_.end(), expr.variables_.begin(),
435 expr.variables_.end());
437 coefficients_.push_back(-coeff);
444 for (
double& c : coefficients_) {
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])
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);
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);
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_);
482 absl::StrAppend(&result,
" - ", -constant_);
503 for (
const BoolVar& var : literals) {
504 proto_->add_enforcement_literal(var.index_);
510 proto_->add_enforcement_literal(literal.index_);
515 proto_->mutable_circuit()->add_tails(tail);
516 proto_->mutable_circuit()->add_heads(head);
517 proto_->mutable_circuit()->add_literals(literal.index_);
521 proto_->mutable_routes()->add_tails(tail);
522 proto_->mutable_routes()->add_heads(head);
523 proto_->mutable_routes()->add_literals(literal.index_);
527 CHECK_EQ(tuple.size(),
proto_->table().exprs_size());
528 for (
const int64_t t : tuple) {
529 proto_->mutable_table()->add_values(t);
533ReservoirConstraint::ReservoirConstraint(ConstraintProto* proto,
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));
546 int64_t level_change,
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_);
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);
563 proto_->mutable_no_overlap_2d()->add_x_intervals(x_coordinate.index_);
564 proto_->mutable_no_overlap_2d()->add_y_intervals(y_coordinate.index_);
567CumulativeConstraint::CumulativeConstraint(ConstraintProto* proto,
572 proto_->mutable_cumulative()->add_intervals(interval.index_);
573 *
proto_->mutable_cumulative()->add_demands() =
574 builder_->LinearExprToProto(demand);
580 : builder_(builder), index_(index) {}
583 DCHECK(builder_ !=
nullptr);
584 if (builder_ ==
nullptr)
return *
this;
585 builder_->MutableProto()->mutable_constraints(index_)->set_name(name);
590 DCHECK(builder_ !=
nullptr);
593 builder_->Proto().constraints(index_).interval().start());
597 DCHECK(builder_ !=
nullptr);
600 builder_->Proto().constraints(index_).interval().size());
604 DCHECK(builder_ !=
nullptr);
607 builder_->Proto().constraints(index_).interval().end());
611 DCHECK(builder_ !=
nullptr);
612 if (builder_ ==
nullptr)
return BoolVar();
613 return BoolVar(builder_->Proto().constraints(index_).enforcement_literal(0),
618 if (builder_ ==
nullptr)
return "null";
619 return builder_->Proto().constraints(index_).name();
623 if (builder_ ==
nullptr)
return "null";
626 const CpModelProto& proto = builder_->Proto();
627 const ConstraintProto& ct_proto = proto.constraints(index_);
629 if (ct_proto.name().empty()) {
630 absl::StrAppend(&output,
"IntervalVar", index_,
"(");
632 absl::StrAppend(&output, ct_proto.name(),
"(");
647 cp_model_.set_name(name);
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;
658 return constant_to_index_map_[value];
661int CpModelBuilder::GetOrCreateIntegerIndex(
int index) {
665 if (!bool_to_integer_index_map_.contains(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(),
")"));
676 bool_to_integer_index_map_[index] = new_index;
679 return bool_to_integer_index_map_[index];
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);
689 return IntVar(index,
this);
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);
701 return IntVar(IndexFromConstant(value),
this);
705 return BoolVar(IndexFromConstant(1),
this);
709 return BoolVar(IndexFromConstant(0),
this);
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);
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);
755 const int index = var.
index();
760 cp_model_.mutable_variables(
NegatedRef(index)));
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_);
776 ConstraintProto*
const proto = cp_model_.add_constraints();
777 for (
const BoolVar& lit : literals) {
778 proto->mutable_at_most_one()->add_literals(lit.index_);
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_);
791 ConstraintProto*
const proto = cp_model_.add_constraints();
792 for (
const BoolVar& lit : literals) {
793 proto->mutable_bool_and()->add_literals(lit.index_);
799 ConstraintProto*
const proto = cp_model_.add_constraints();
800 for (
const BoolVar& lit : literals) {
801 proto->mutable_bool_xor()->add_literals(lit.index_);
806void CpModelBuilder::FillLinearTerms(
const LinearExpr& left,
808 LinearConstraintProto* proto) {
813 proto->add_coeffs(coeff);
819 proto->add_coeffs(-coeff);
825 ConstraintProto*
const proto = cp_model_.add_constraints();
826 FillLinearTerms(left, right, proto->mutable_linear());
828 proto->mutable_linear()->add_domain(rhs);
829 proto->mutable_linear()->add_domain(rhs);
835 ConstraintProto*
const proto = cp_model_.add_constraints();
836 FillLinearTerms(left, right, proto->mutable_linear());
838 proto->mutable_linear()->add_domain(rhs);
839 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::max());
845 ConstraintProto*
const proto = cp_model_.add_constraints();
846 FillLinearTerms(left, right, proto->mutable_linear());
848 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::min());
849 proto->mutable_linear()->add_domain(rhs);
855 ConstraintProto*
const proto = cp_model_.add_constraints();
856 FillLinearTerms(left, right, proto->mutable_linear());
858 proto->mutable_linear()->add_domain(rhs + 1);
859 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::max());
865 ConstraintProto*
const proto = cp_model_.add_constraints();
866 FillLinearTerms(left, right, proto->mutable_linear());
868 proto->mutable_linear()->add_domain(std::numeric_limits<int64_t>::min());
869 proto->mutable_linear()->add_domain(rhs - 1);
875 ConstraintProto*
const proto = cp_model_.add_constraints();
877 proto->mutable_linear()->add_vars(x);
880 proto->mutable_linear()->add_coeffs(coeff);
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);
892 ConstraintProto*
const proto = cp_model_.add_constraints();
893 FillLinearTerms(left, right, proto->mutable_linear());
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());
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_);
913 ConstraintProto*
const proto = cp_model_.add_constraints();
915 *proto->mutable_all_diff()->add_exprs() = LinearExprToProto(expr);
921 std::initializer_list<LinearExpr> exprs) {
922 ConstraintProto*
const proto = cp_model_.add_constraints();
924 *proto->mutable_all_diff()->add_exprs() = LinearExprToProto(expr);
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);
942 absl::Span<const int64_t> values,
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);
955 absl::Span<const LinearExpr> expressions,
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);
962 *proto->mutable_element()->add_exprs() = LinearExprToProto(expr);
968 LinearExpr index, std::initializer_list<LinearExpr> expressions,
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);
975 *proto->mutable_element()->add_exprs() = LinearExprToProto(expr);
989 absl::Span<const LinearExpr> expressions) {
990 ConstraintProto*
const proto = cp_model_.add_constraints();
992 *proto->mutable_table()->add_exprs() = LinearExprToProto(expr);
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);
1009 std::initializer_list<LinearExpr> expressions) {
1010 ConstraintProto*
const proto = cp_model_.add_constraints();
1012 *proto->mutable_table()->add_exprs() = LinearExprToProto(expr);
1018 absl::Span<const LinearExpr> expressions) {
1025 absl::Span<const IntVar> variables) {
1032 std::initializer_list<LinearExpr> expressions) {
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_);
1045 for (
const IntVar& var : inverse_variables) {
1046 proto->mutable_inverse()->add_f_inverse(var.index_);
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);
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);
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);
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);
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);
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);
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);
1103LinearExpressionProto CpModelBuilder::LinearExprToProto(
const LinearExpr& expr,
1105 LinearExpressionProto expr_proto;
1106 for (
const int var : expr.
variables()) {
1107 expr_proto.add_vars(var);
1109 const int64_t mult = negate ? -1 : 1;
1111 expr_proto.add_coeffs(coeff * mult);
1113 expr_proto.set_offset(expr.
constant() * mult);
1118 absl::Span<const IntVar> vars) {
1119 ConstraintProto* ct = cp_model_.add_constraints();
1120 *ct->mutable_lin_max()->mutable_target() =
1121 LinearExprToProto(target,
true);
1122 for (
const IntVar& var : vars) {
1123 *ct->mutable_lin_max()->add_exprs() =
1124 LinearExprToProto(var,
true);
1130 absl::Span<const LinearExpr> exprs) {
1131 ConstraintProto* ct = cp_model_.add_constraints();
1132 *ct->mutable_lin_max()->mutable_target() =
1133 LinearExprToProto(target,
true);
1135 *ct->mutable_lin_max()->add_exprs() =
1136 LinearExprToProto(expr,
true);
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,
true);
1147 *ct->mutable_lin_max()->add_exprs() =
1148 LinearExprToProto(expr,
true);
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);
1164 absl::Span<const LinearExpr> exprs) {
1165 ConstraintProto* ct = cp_model_.add_constraints();
1166 *ct->mutable_lin_max()->mutable_target() = LinearExprToProto(target);
1168 *ct->mutable_lin_max()->add_exprs() = LinearExprToProto(expr);
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);
1178 *ct->mutable_lin_max()->add_exprs() = LinearExprToProto(expr);
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);
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,
true);
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);
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);
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);
1228 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(expr);
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);
1238 *proto->mutable_int_prod()->add_exprs() = LinearExprToProto(expr);
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);
1254 ConstraintProto*
const proto = cp_model_.add_constraints();
1256 proto->mutable_no_overlap()->add_intervals(var.index_);
1266 ConstraintProto*
const proto = cp_model_.add_constraints();
1267 *proto->mutable_cumulative()->mutable_capacity() =
1268 LinearExprToProto(capacity);
1275 cp_model_.mutable_objective()->add_vars(x);
1278 cp_model_.mutable_objective()->add_coeffs(coeff);
1280 cp_model_.mutable_objective()->set_offset(expr.
constant());
1286 cp_model_.mutable_objective()->add_vars(x);
1289 cp_model_.mutable_objective()->add_coeffs(-coeff);
1291 cp_model_.mutable_objective()->set_offset(-expr.
constant());
1292 cp_model_.mutable_objective()->set_scaling_factor(-1.0);
1298 cp_model_.mutable_floating_point_objective()->add_vars(expr.
variables()[
i]);
1299 cp_model_.mutable_floating_point_objective()->add_coeffs(
1302 cp_model_.mutable_floating_point_objective()->set_offset(expr.
constant());
1303 cp_model_.mutable_floating_point_objective()->set_maximize(
false);
1309 cp_model_.mutable_floating_point_objective()->add_vars(expr.
variables()[
i]);
1310 cp_model_.mutable_floating_point_objective()->add_coeffs(
1313 cp_model_.mutable_floating_point_objective()->set_offset(expr.
constant());
1314 cp_model_.mutable_floating_point_objective()->set_maximize(
true);
1318 cp_model_.clear_objective();
1319 cp_model_.clear_floating_point_objective();
1323 return cp_model_.has_objective() || cp_model_.has_floating_point_objective();
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);
1338 expr->add_coeffs(-1);
1339 expr->set_offset(1);
1342 proto->set_variable_selection_strategy(var_strategy);
1343 proto->set_domain_reduction_strategy(domain_strategy);
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);
1358 expr->add_coeffs(-1);
1359 expr->set_offset(1);
1362 proto->set_variable_selection_strategy(var_strategy);
1363 proto->set_domain_reduction_strategy(domain_strategy);
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();
1372 *proto->add_exprs() = LinearExprToProto(expr);
1374 proto->set_variable_selection_strategy(var_strategy);
1375 proto->set_domain_reduction_strategy(domain_strategy);
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();
1384 *proto->add_exprs() = LinearExprToProto(expr);
1386 proto->set_variable_selection_strategy(var_strategy);
1387 proto->set_domain_reduction_strategy(domain_strategy);
1391 cp_model_.mutable_solution_hint()->add_vars(var.index_);
1392 cp_model_.mutable_solution_hint()->add_values(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);
1400 cp_model_.mutable_solution_hint()->add_vars(
PositiveRef(var.index_));
1401 cp_model_.mutable_solution_hint()->add_values(!value);
1406 cp_model_.mutable_solution_hint()->Clear();
1410 cp_model_.mutable_assumptions()->Add(lit.index_);
1414 for (
const BoolVar& lit : literals) {
1415 cp_model_.mutable_assumptions()->Add(lit.index_);
1420 cp_model_.mutable_assumptions()->Clear();
1425 clone.ResetAndImport(cp_model_);
1429void CpModelBuilder::ResetAndImport(
const CpModelProto& model_proto) {
1430 cp_model_ = model_proto;
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;
1440 bool_to_integer_index_map_.clear();
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 "
1450 CHECK_GE(0, proto.domain(0))
1451 <<
"CpModelBuilder::GetBoolVarFromProtoIndex: The domain of the variable "
1453 CHECK_LE(1, proto.domain(1))
1454 <<
"CpModelBuilder::GetBoolVarFromProtoIndex: The domain of the variable "
1461 CHECK_LT(index, cp_model_.variables_size());
1462 return IntVar(index,
this);
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";
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];
1491 const int ref = x.index_;
1493 return r.solution(ref) == 1;
virtual std::string DebugString() const
Constraint(Solver *const solver)
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.
BoolVar WithName(absl::string_view name)
std::string Name() const
Returns the name of the variable.
BoolVar Not() const
Returns the logical negation of the current Boolean variable.
std::string DebugString() const
void AddArc(int tail, int head, BoolVar literal)
Constraint WithName(absl::string_view name)
Sets the name of the constraint.
Constraint OnlyEnforceIf(absl::Span< const BoolVar > literals)
Constraint(ConstraintProto *proto)
ConstraintProto * MutableProto() const
Returns the mutable underlying protobuf object (useful for model edition).
absl::string_view Name() const
Returns the name of the constraint (or the empty string if not set).
bool HasObjective() const
Checks whether the model contains an objective.
BoolVar GetBoolVarFromProtoIndex(int index)
Returns the Boolean variable from its index in the proto.
IntVar NewIntVar(const Domain &domain)
Creates an integer variable with the given domain.
Constraint AddInverseConstraint(absl::Span< const IntVar > variables, absl::Span< const IntVar > inverse_variables)
void Minimize(const LinearExpr &expr)
Adds a linear minimization objective.
NoOverlap2DConstraint AddNoOverlap2D()
Constraint AddBoolXor(absl::Span< const BoolVar > literals)
Adds the constraint that an odd number of literals is true.
IntervalVar NewIntervalVar(const LinearExpr &start, const LinearExpr &size, const LinearExpr &end)
Creates an interval variable from 3 affine expressions.
IntVar GetIntVarFromProtoIndex(int index)
Returns the integer variable from its index in the proto.
Constraint AddMultiplicationEquality(const LinearExpr &target, absl::Span< const LinearExpr > exprs)
Adds target == prod(exprs).
CpModelBuilder Clone() const
Returns a cloned version of the current model.
IntVar NewConstant(int64_t value)
Constraint AddBoolAnd(absl::Span< const BoolVar > literals)
Adds the constraint that all literals must be true.
Constraint AddMaxEquality(const LinearExpr &target, absl::Span< const IntVar > vars)
Adds target == max(vars).
void Maximize(const LinearExpr &expr)
Adds a linear maximization objective.
TableConstraint AddAllowedAssignments(absl::Span< const LinearExpr > expressions)
void FixVariable(IntVar var, int64_t value)
ReservoirConstraint AddReservoirConstraint(int64_t min_level, int64_t max_level)
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.
Constraint AddLessOrEqual(const LinearExpr &left, const LinearExpr &right)
Adds left <= right.
IntervalVar NewOptionalIntervalVar(const LinearExpr &start, const LinearExpr &size, const LinearExpr &end, BoolVar presence)
void ClearAssumptions()
Remove all assumptions from the model.
Constraint AddLinearConstraint(const LinearExpr &expr, const Domain &domain)
Adds expr in domain.
void AddHint(IntVar var, int64_t value)
Adds hinting to a variable.
Constraint AddAllDifferent(absl::Span< const IntVar > vars)
This constraint forces all variables to have different values.
IntervalVar GetIntervalVarFromProtoIndex(int index)
Returns the interval variable from its index in the proto.
AutomatonConstraint AddAutomaton(absl::Span< const LinearExpr > transition_expressions, int starting_state, absl::Span< const int > final_states)
Constraint AddExactlyOne(absl::Span< const BoolVar > literals)
Exactly one literal is true. Sum literals == 1.
Constraint AddMinEquality(const LinearExpr &target, absl::Span< const IntVar > vars)
Adds target == min(vars).
void AddAssumption(BoolVar lit)
Adds a literal to the model as assumptions.
bool ExportToFile(absl::string_view filename) const
Export the model to file.
Constraint AddGreaterOrEqual(const LinearExpr &left, const LinearExpr &right)
Adds left >= right.
Constraint AddLessThan(const LinearExpr &left, const LinearExpr &right)
Adds left < right.
MultipleCircuitConstraint AddMultipleCircuitConstraint()
Constraint AddNoOverlap(absl::Span< const IntervalVar > vars)
BoolVar NewBoolVar()
Creates a Boolean variable.
friend class CumulativeConstraint
Constraint AddNotEqual(const LinearExpr &left, const LinearExpr &right)
Adds left != right.
Constraint AddAtLeastOne(absl::Span< const BoolVar > literals)
Same as AddBoolOr(). Sum literals >= 1.
void ClearObjective()
Removes the objective from the model.
Constraint AddAtMostOne(absl::Span< const BoolVar > literals)
At most one literal is true. Sum literals <= 1.
void ClearHints()
Removes all hints.
void AddAssumptions(absl::Span< const BoolVar > literals)
Adds multiple literals to the model as assumptions.
Constraint AddGreaterThan(const LinearExpr &left, const LinearExpr &right)
Adds left > right.
CircuitConstraint AddCircuitConstraint()
Constraint AddDivisionEquality(const LinearExpr &target, const LinearExpr &numerator, const LinearExpr &denominator)
Adds target = num / denom (integer division rounded towards 0).
Constraint AddEquality(const LinearExpr &left, const LinearExpr &right)
Adds left == right.
TableConstraint AddForbiddenAssignments(absl::Span< const LinearExpr > expression)
void SetName(absl::string_view name)
Sets the name of the model.
Constraint AddAbsEquality(const LinearExpr &target, const LinearExpr &expr)
Adds target == abs(expr).
friend class ReservoirConstraint
Constraint AddBoolOr(absl::Span< const BoolVar > literals)
Adds the constraint that at least one of the literals must be true.
IntervalVar NewFixedSizeIntervalVar(const LinearExpr &start, int64_t size)
Creates an interval variable with a fixed size.
CumulativeConstraint AddCumulative(LinearExpr capacity)
Constraint AddModuloEquality(const LinearExpr &target, const LinearExpr &var, const LinearExpr &mod)
Adds target = var % mod.
Constraint AddVariableElement(LinearExpr index, absl::Span< const IntVar > variables, LinearExpr target)
Adds the element constraint: variables[index] == target.
IntervalVar NewOptionalFixedSizeIntervalVar(const LinearExpr &start, int64_t size, BoolVar presence)
Creates an optional interval variable with a fixed size.
Constraint AddElement(LinearExpr index, absl::Span< const LinearExpr > expressions, LinearExpr target)
Adds the element constraint: expressions[index] == target.
void AddDemand(IntervalVar interval, LinearExpr demand)
Adds a pair (interval, demand) to the constraint.
const std::vector< double > & coefficients() const
Returns the vector of coefficients.
static DoubleLinearExpr Sum(absl::Span< const IntVar > vars)
Constructs the sum of a list of variables.
DoubleLinearExpr & operator*=(double coeff)
Multiply the linear expression by a constant.
DoubleLinearExpr & operator+=(double value)
Adds a constant value to the linear expression.
DoubleLinearExpr & AddTerm(IntVar var, double coeff)
Adds a term (var * coeff) to the linear expression.
double constant() const
Returns the constant term.
static DoubleLinearExpr WeightedSum(absl::Span< const IntVar > vars, absl::Span< const double > coeffs)
Constructs the scalar product of variables and coefficients.
DoubleLinearExpr & operator-=(double value)
Adds a constant value to the linear expression.
const std::vector< int > & variables() const
Returns the vector of variable indices.
std::string DebugString(const CpModelProto *proto=nullptr) const
Debug string. See the documentation for LinearExpr::DebugString().
DoubleLinearExpr & AddExpression(const LinearExpr &exprs, double coeff=1.0)
Adds a linear expression to the double linear expression.
std::string Name() const
Returns the name of the variable (or the empty string if not set).
std::string DebugString() const
int index() const
Returns the index of the variable in the model. This will be non-negative.
IntVar WithName(absl::string_view name)
Sets the name of the variable.
BoolVar ToBoolVar() const
::operations_research::Domain Domain() const
IntervalVar WithName(absl::string_view name)
Sets the name of the variable.
LinearExpr StartExpr() const
std::string Name() const
Returns the name of the interval (or the empty string if not set).
LinearExpr EndExpr() const
LinearExpr SizeExpr() const
BoolVar PresenceBoolVar() const
std::string DebugString() const
Returns a debug string.
static LinearExpr Sum(absl::Span< const IntVar > vars)
NOLINTEND(google-explicit-constructor)
std::string DebugString(const CpModelProto *proto=nullptr) const
static LinearExpr WeightedSum(absl::Span< const IntVar > vars, absl::Span< const int64_t > coeffs)
Constructs the scalar product of variables and coefficients.
static LinearExpr Term(IntVar var, int64_t coefficient)
Constructs var * coefficient.
int64_t constant() const
Returns the constant term.
LinearExpr()=default
Creates an empty linear expression with value zero.
static LinearExpr FromProto(const LinearExpressionProto &proto)
Constructs a linear expr from its proto representation.
const std::vector< int > & variables() const
Returns the vector of variable indices.
const std::vector< int64_t > & coefficients() const
Returns the vector of coefficients.
void AddArc(int tail, int head, BoolVar literal)
void AddRectangle(IntervalVar x_coordinate, IntervalVar y_coordinate)
Adds a rectangle (parallel to the axis) to the constraint.
void AddOptionalEvent(LinearExpr time, int64_t level_change, BoolVar is_active)
void AddEvent(LinearExpr time, int64_t level_change)
void AddTuple(absl::Span< const int64_t > tuple)
Adds a tuple of possible values to the constraint.
std::string VarDebugString(const CpModelProto &proto, int index)
bool RefIsPositive(int ref)
bool WriteModelProtoToFile(const M &proto, absl::string_view filename)
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
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.
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.
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)