Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
cp_model.h
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
37
38#ifndef OR_TOOLS_SAT_CP_MODEL_H_
39#define OR_TOOLS_SAT_CP_MODEL_H_
40
41#include <cstdint>
42#include <initializer_list>
43#include <iosfwd>
44#include <limits>
45#include <ostream>
46#include <string>
47#include <utility>
48#include <vector>
49
50#include "absl/container/flat_hash_map.h"
51#include "absl/strings/string_view.h"
52#include "absl/types/span.h"
53#include "ortools/sat/cp_model.pb.h"
54#include "ortools/sat/cp_model_solver.h" // IWYU pragma: export.
56#include "ortools/sat/model.h" // IWYU pragma: export.
57#include "ortools/sat/sat_parameters.pb.h"
59
60namespace operations_research {
61namespace sat {
62
63class CpModelBuilder;
64class IntVar;
65class LinearExpr;
66
75class BoolVar {
76 public:
81 BoolVar() = default;
82
85 BoolVar WithName(absl::string_view name);
86
88 std::string Name() const;
89
91 BoolVar Not() const { return BoolVar(NegatedRef(index_), builder_); }
92
93 bool operator==(const BoolVar& other) const {
94 return other.builder_ == builder_ && other.index_ == index_;
95 }
96
97 bool operator!=(const BoolVar& other) const {
98 return other.builder_ != builder_ || other.index_ != index_;
99 }
100
101 BoolVar operator~() const { return Not(); }
102
103 std::string DebugString() const;
104
111 int index() const { return index_; }
112
113 private:
114 friend class CircuitConstraint;
115 friend class Constraint;
116 friend class CpModelBuilder;
117 friend class DoubleLinearExpr;
118 friend class IntVar;
119 friend class IntervalVar;
121 friend class LinearExpr;
123 friend bool SolutionBooleanValue(const CpSolverResponse& r, BoolVar x);
124
125 BoolVar(int index, CpModelBuilder* builder);
126
127 CpModelBuilder* builder_ = nullptr;
128 int index_ = std::numeric_limits<int32_t>::min();
129};
130
131std::ostream& operator<<(std::ostream& os, const BoolVar& var);
132
138
145class IntVar {
146 public:
151 IntVar() = default;
152
159 explicit IntVar(const BoolVar& var);
160
166 BoolVar ToBoolVar() const;
167
169 IntVar WithName(absl::string_view name);
170
172 std::string Name() const;
173
174 bool operator==(const IntVar& other) const {
175 return other.builder_ == builder_ && other.index_ == index_;
177
178 bool operator!=(const IntVar& other) const {
179 return other.builder_ != builder_ || other.index_ != index_;
181
182 // Returns the domain of the variable.
183 // Note that we keep the fully qualified return type as compilation fails with
184 // gcc otherwise.
186
187 std::string DebugString() const;
188
190 int index() const { return index_; }
191
192 private:
193 friend class BoolVar;
194 friend class CpModelBuilder;
196 friend class DoubleLinearExpr;
197 friend class LinearExpr;
198 friend class IntervalVar;
200 friend int64_t SolutionIntegerValue(const CpSolverResponse& r,
201 const LinearExpr& expr);
202
203 IntVar(int index, CpModelBuilder* builder);
204
205 CpModelBuilder* builder_ = nullptr;
206 int index_ = std::numeric_limits<int32_t>::min();
207};
208
209std::ostream& operator<<(std::ostream& os, const IntVar& var);
210
244class LinearExpr {
245 public:
246 /// Creates an empty linear expression with value zero.
247 LinearExpr() = default;
248
249 // NOLINTBEGIN(google-explicit-constructor)
250
253 LinearExpr(BoolVar var);
254
256 LinearExpr(IntVar var);
257
259 LinearExpr(int64_t constant);
260
261 // NOLINTEND(google-explicit-constructor)
262
264 static LinearExpr Sum(absl::Span<const IntVar> vars);
265
267 static LinearExpr Sum(absl::Span<const BoolVar> vars);
268
270 static LinearExpr WeightedSum(absl::Span<const IntVar> vars,
271 absl::Span<const int64_t> coeffs);
272
274 static LinearExpr WeightedSum(absl::Span<const BoolVar> vars,
275 absl::Span<const int64_t> coeffs);
276
278 static LinearExpr Term(IntVar var, int64_t coefficient);
279
281 static LinearExpr Term(BoolVar var, int64_t coefficient);
282
284 static LinearExpr FromProto(const LinearExpressionProto& proto);
285
286 // Operators.
287 LinearExpr& operator+=(const LinearExpr& other);
288 LinearExpr& operator-=(const LinearExpr& other);
289 LinearExpr& operator*=(int64_t factor);
290
292 const std::vector<int>& variables() const { return variables_; }
293
295 const std::vector<int64_t>& coefficients() const { return coefficients_; }
296
298 bool IsConstant() const { return variables_.empty(); }
299
301 int64_t constant() const { return constant_; }
302
308 std::string DebugString(const CpModelProto* proto = nullptr) const;
309
310 private:
311 std::vector<int> variables_;
312 std::vector<int64_t> coefficients_;
313 int64_t constant_ = 0;
314};
315
316std::ostream& operator<<(std::ostream& os, const LinearExpr& e);
317
348class DoubleLinearExpr {
349 public:
351
354 explicit DoubleLinearExpr(BoolVar var);
355
357 explicit DoubleLinearExpr(IntVar var);
358
360 explicit DoubleLinearExpr(double constant);
361
363 DoubleLinearExpr& operator+=(double value);
364
368
371
373 DoubleLinearExpr& AddTerm(IntVar var, double coeff);
374 DoubleLinearExpr& AddTerm(BoolVar var, double coeff);
375
377 DoubleLinearExpr& AddExpression(const LinearExpr& exprs, double coeff = 1.0);
378
380 DoubleLinearExpr& operator-=(double value);
381
384
387
389 DoubleLinearExpr& operator*=(double coeff);
390
392 static DoubleLinearExpr Sum(absl::Span<const IntVar> vars);
393
395 static DoubleLinearExpr Sum(absl::Span<const BoolVar> vars);
396
398 static DoubleLinearExpr WeightedSum(absl::Span<const IntVar> vars,
399 absl::Span<const double> coeffs);
400
402 static DoubleLinearExpr WeightedSum(absl::Span<const BoolVar> vars,
403 absl::Span<const double> coeffs);
404
406 const std::vector<int>& variables() const { return variables_; }
407
409 const std::vector<double>& coefficients() const { return coefficients_; }
410
411 // Returns true if the expression has no variable.
412 bool IsConstant() const { return variables_.empty(); }
413
415 double constant() const { return constant_; }
416
418 std::string DebugString(const CpModelProto* proto = nullptr) const;
419
420 private:
421 std::vector<int> variables_;
422 std::vector<double> coefficients_;
423 double constant_ = 0;
424};
425
426std::ostream& operator<<(std::ostream& os, const DoubleLinearExpr& e);
427
448class IntervalVar {
449 public:
450 /// A default constructed IntervalVar can be used to mean not defined yet.
451 /// However, it shouldn't be passed to any of the functions in this file.
452 /// Doing so will crash in debug mode and will result in an invalid model in
453 /// opt mode.
454 IntervalVar();
455
457 IntervalVar WithName(absl::string_view name);
458
460 std::string Name() const;
461
464 LinearExpr StartExpr() const;
465
468 LinearExpr SizeExpr() const;
469
472 LinearExpr EndExpr() const;
473
479 BoolVar PresenceBoolVar() const;
480
482 bool operator==(const IntervalVar& other) const {
483 return other.builder_ == builder_ && other.index_ == index_;
485
487 bool operator!=(const IntervalVar& other) const {
488 return other.builder_ != builder_ || other.index_ != index_;
490
492 std::string DebugString() const;
493
495 int index() const { return index_; }
496
497 private:
498 friend class CpModelBuilder;
499 friend class CumulativeConstraint;
501 friend std::ostream& operator<<(std::ostream& os, const IntervalVar& var);
503 IntervalVar(int index, CpModelBuilder* builder);
504
505 CpModelBuilder* builder_ = nullptr;
506 int index_ = std::numeric_limits<int32_t>::min();
507};
508
509std::ostream& operator<<(std::ostream& os, const IntervalVar& var);
510
511// -- ABSL HASHING SUPPORT -----------------------------------------------------
512template <typename H>
513H AbslHashValue(H h, const IntVar& i) {
514 return H::combine(std::move(h), i.index());
516
517template <typename H>
518H AbslHashValue(H h, const IntervalVar& i) {
519 return H::combine(std::move(h), i.index());
521
523
531class Constraint {
532 public:
533 /**
534 * The constraint will be enforced iff all literals listed here are true.
535 *
536 * If this is empty, then the constraint will always be enforced. An enforced
537 * constraint must be satisfied, and an un-enforced one will simply be
538 * ignored.
539 *
540 * This is also called half-reification. To have an equivalence between a
541 * literal and a constraint (full reification), one must add both a constraint
542 * (controlled by a literal l) and its negation (controlled by the negation of
543 * l).
544 *
545 * [Important] currently, only a few constraints support enforcement:
546 * - bool_or, bool_and, linear: fully supported.
547 * - interval: only support a single enforcement literal.
548 * - other: no support (but can be added on a per-demand basis).
549 */
550 Constraint OnlyEnforceIf(absl::Span<const BoolVar> literals);
551
554
556 Constraint WithName(absl::string_view name);
557
559 absl::string_view Name() const;
560
562 const ConstraintProto& Proto() const { return *proto_; }
563
565 ConstraintProto* MutableProto() const { return proto_; }
566
567 protected:
568 friend class CpModelBuilder;
569
570 explicit Constraint(ConstraintProto* proto);
571
572 ConstraintProto* proto_ = nullptr;
573};
576
580class CircuitConstraint : public Constraint {
581 public:
582 /**
583 * Add an arc to the circuit.
584 *
585 * @param tail the index of the tail node.
586 * @param head the index of the head node.
587 * @param literal it will be set to true if the arc is selected.
588 */
589 void AddArc(int tail, int head, BoolVar literal);
590
591 private:
592 friend class CpModelBuilder;
593
595};
596
598
604 public:
605 /**
606 * Add an arc to the circuit.
607 *
608 * @param tail the index of the tail node.
609 * @param head the index of the head node.
610 * @param literal it will be set to true if the arc is selected.
611 */
612 void AddArc(int tail, int head, BoolVar literal);
613
614 private:
615 friend class CpModelBuilder;
616
618};
619
621
626class TableConstraint : public Constraint {
627 public:
628 /// Adds a tuple of possible values to the constraint.
629 void AddTuple(absl::Span<const int64_t> tuple);
630
631 private:
632 friend class CpModelBuilder;
633
635};
636
638
643class ReservoirConstraint : public Constraint {
644 public:
645 /**
646 * Adds a mandatory event
647 *
648 * It will increase the used capacity by `level_change` at time `time`.
649 * `time` must be an affine expression.
650 */
651 void AddEvent(LinearExpr time, int64_t level_change);
652
659 void AddOptionalEvent(LinearExpr time, int64_t level_change,
660 BoolVar is_active);
661
662 private:
663 friend class CpModelBuilder;
664
665 ReservoirConstraint(ConstraintProto* proto, CpModelBuilder* builder);
666
667 CpModelBuilder* builder_;
668};
669
671
676class AutomatonConstraint : public Constraint {
677 public:
678 /// Adds a transitions to the automaton.
679 void AddTransition(int tail, int head, int64_t transition_label);
680
681 private:
682 friend class CpModelBuilder;
683
685};
686
688
693class NoOverlap2DConstraint : public Constraint {
694 public:
695 /// Adds a rectangle (parallel to the axis) to the constraint.
696 void AddRectangle(IntervalVar x_coordinate, IntervalVar y_coordinate);
697
698 private:
699 friend class CpModelBuilder;
700
702};
703
705
713class CumulativeConstraint : public Constraint {
714 public:
715 /// Adds a pair (interval, demand) to the constraint.
716 void AddDemand(IntervalVar interval, LinearExpr demand);
717
718 private:
719 friend class CpModelBuilder;
720
721 CumulativeConstraint(ConstraintProto* proto, CpModelBuilder* builder);
722
723 CpModelBuilder* builder_;
724};
725
727
733class CpModelBuilder {
734 public:
735 /// Sets the name of the model.
736 void SetName(absl::string_view name);
737
739 IntVar NewIntVar(const Domain& domain);
740
743
747 IntVar NewConstant(int64_t value);
748
753
758
760 IntervalVar NewIntervalVar(const LinearExpr& start, const LinearExpr& size,
761 const LinearExpr& end);
762
764 IntervalVar NewFixedSizeIntervalVar(const LinearExpr& start, int64_t size);
765
769 const LinearExpr& size,
770 const LinearExpr& end, BoolVar presence);
771
774 int64_t size, BoolVar presence);
775
785 void FixVariable(IntVar var, int64_t value);
786 void FixVariable(BoolVar var, bool value);
787
789 Constraint AddBoolOr(absl::Span<const BoolVar> literals);
790
792 Constraint AddAtLeastOne(absl::Span<const BoolVar> literals);
793
795 Constraint AddAtMostOne(absl::Span<const BoolVar> literals);
796
798 Constraint AddExactlyOne(absl::Span<const BoolVar> literals);
799
801 Constraint AddBoolAnd(absl::Span<const BoolVar> literals);
802
804 Constraint AddBoolXor(absl::Span<const BoolVar> literals);
805
808 return AddBoolOr({a.Not(), b});
809 }
812 Constraint AddImplication(absl::Span<const BoolVar> lhs,
813 absl::Span<const BoolVar> rhs) {
814 return AddBoolAnd(rhs).OnlyEnforceIf(lhs);
816
818 Constraint AddEquality(const LinearExpr& left, const LinearExpr& right);
819
821 Constraint AddGreaterOrEqual(const LinearExpr& left, const LinearExpr& right);
822
824 Constraint AddGreaterThan(const LinearExpr& left, const LinearExpr& right);
825
827 Constraint AddLessOrEqual(const LinearExpr& left, const LinearExpr& right);
828
830 Constraint AddLessThan(const LinearExpr& left, const LinearExpr& right);
831
833 Constraint AddLinearConstraint(const LinearExpr& expr, const Domain& domain);
834
836 Constraint AddNotEqual(const LinearExpr& left, const LinearExpr& right);
837
839 Constraint AddAllDifferent(absl::Span<const IntVar> vars);
840
842 Constraint AddAllDifferent(absl::Span<const LinearExpr> exprs);
843
845 Constraint AddAllDifferent(std::initializer_list<LinearExpr> exprs);
846
849 absl::Span<const IntVar> variables,
850 LinearExpr target);
851
854 absl::Span<const LinearExpr> expressions,
855 LinearExpr target);
856
859 std::initializer_list<LinearExpr> expressions,
860 LinearExpr target);
861
863 Constraint AddElement(LinearExpr index, absl::Span<const int64_t> values,
864 LinearExpr target);
865
883
898
911 absl::Span<const LinearExpr> expressions);
912
916 TableConstraint AddAllowedAssignments(absl::Span<const IntVar> variables);
917
922 std::initializer_list<LinearExpr> expressions);
923
935 absl::Span<const LinearExpr> expression);
936
940 TableConstraint AddForbiddenAssignments(absl::Span<const IntVar> variables);
941
946 std::initializer_list<LinearExpr> expressions);
947
953 Constraint AddInverseConstraint(absl::Span<const IntVar> variables,
954 absl::Span<const IntVar> inverse_variables);
955
976 int64_t max_level);
977
1005 absl::Span<const LinearExpr> transition_expressions, int starting_state,
1006 absl::Span<const int> final_states);
1007
1012 absl::Span<const IntVar> transition_variables, int starting_state,
1013 absl::Span<const int> final_states);
1014
1019 std::initializer_list<LinearExpr> transition_expressions,
1020 int starting_state, absl::Span<const int> final_states);
1021
1023 Constraint AddMinEquality(const LinearExpr& target,
1024 absl::Span<const IntVar> vars);
1025
1027 Constraint AddMinEquality(const LinearExpr& target,
1028 absl::Span<const LinearExpr> exprs);
1029
1031 Constraint AddMinEquality(const LinearExpr& target,
1032 std::initializer_list<LinearExpr> exprs);
1033
1035 Constraint AddMaxEquality(const LinearExpr& target,
1036 absl::Span<const IntVar> vars);
1037
1039 Constraint AddMaxEquality(const LinearExpr& target,
1040 absl::Span<const LinearExpr> exprs);
1041
1043 Constraint AddMaxEquality(const LinearExpr& target,
1044 std::initializer_list<LinearExpr> exprs);
1045
1048 const LinearExpr& numerator,
1049 const LinearExpr& denominator);
1050
1052 Constraint AddAbsEquality(const LinearExpr& target, const LinearExpr& expr);
1053
1055 Constraint AddModuloEquality(const LinearExpr& target, const LinearExpr& var,
1056 const LinearExpr& mod);
1057
1060 absl::Span<const LinearExpr> exprs);
1061
1064 absl::Span<const IntVar> vars);
1065
1068 std::initializer_list<LinearExpr> exprs);
1069
1072 const LinearExpr& left,
1073 const LinearExpr& right);
1074
1079 Constraint AddNoOverlap(absl::Span<const IntervalVar> vars);
1080
1085
1093
1095 void Minimize(const LinearExpr& expr);
1096
1099 void Minimize(const DoubleLinearExpr& expr);
1100
1102 void Maximize(const LinearExpr& expr);
1103
1106 void Maximize(const DoubleLinearExpr& expr);
1107
1109 void ClearObjective();
1110
1112 bool HasObjective() const;
1113
1116 absl::Span<const IntVar> variables,
1117 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1118 DecisionStrategyProto::DomainReductionStrategy domain_strategy);
1119
1122 absl::Span<const BoolVar> variables,
1123 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1124 DecisionStrategyProto::DomainReductionStrategy domain_strategy);
1125
1128 absl::Span<const LinearExpr> expressions,
1129 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1130 DecisionStrategyProto::DomainReductionStrategy domain_strategy);
1131
1134 std::initializer_list<LinearExpr> expressions,
1135 DecisionStrategyProto::VariableSelectionStrategy var_strategy,
1136 DecisionStrategyProto::DomainReductionStrategy domain_strategy);
1137
1139 void AddHint(IntVar var, int64_t value);
1140
1142 void AddHint(BoolVar var, bool value);
1143
1145 void ClearHints();
1146
1148 void AddAssumption(BoolVar lit);
1149
1151 void AddAssumptions(absl::Span<const BoolVar> literals);
1152
1154 void ClearAssumptions();
1155
1156 const CpModelProto& Build() const { return cp_model_; }
1157 const CpModelProto& Proto() const { return cp_model_; }
1158 CpModelProto* MutableProto() { return &cp_model_; }
1161 bool ExportToFile(absl::string_view filename) const;
1162
1164 CpModelBuilder Clone() const;
1165
1168
1171
1174
1175 private:
1176 friend class CumulativeConstraint;
1177 friend class ReservoirConstraint;
1178 friend class IntervalVar;
1179 friend class IntVar;
1181 // Used for cloning a model.
1182 void ResetAndImport(const CpModelProto& model_proto);
1183
1184 // Fills the 'expr_proto' with the linear expression represented by 'expr'.
1185 LinearExpressionProto LinearExprToProto(const LinearExpr& expr,
1186 bool negate = false);
1187
1188 // Returns a (cached) integer variable index with a constant value.
1189 int IndexFromConstant(int64_t value);
1190
1191 // Returns a valid integer index from a BoolVar index.
1192 // If the input index is a positive, it returns this index.
1193 // If the input index is negative, it creates a cached IntVar equal to
1194 // 1 - BoolVar(PositiveRef(index)), and returns the index of this new
1195 // variable.
1196 int GetOrCreateIntegerIndex(int index);
1197
1198 void FillLinearTerms(const LinearExpr& left, const LinearExpr& right,
1199 LinearConstraintProto* proto);
1200
1201 CpModelProto cp_model_;
1202 absl::flat_hash_map<int64_t, int> constant_to_index_map_;
1203 absl::flat_hash_map<int, int> bool_to_integer_index_map_;
1204};
1205
1207int64_t SolutionIntegerValue(const CpSolverResponse& r, const LinearExpr& expr);
1208
1210bool SolutionBooleanValue(const CpSolverResponse& r, BoolVar x);
1211
1212// Returns a more readable and compact DebugString() than
1213// proto.variables(index).DebugString(). This is used by IntVar::DebugString()
1214// but also allow to get the same string from a const proto.
1215std::string VarDebugString(const CpModelProto& proto, int index);
1216
1217// ============================================================================
1218// Minimal support for "natural" API to create LinearExpr.
1219//
1220// Note(user): This might be optimized further by optimizing LinearExpr for
1221// holding one term, or introducing an LinearTerm class, but these should mainly
1222// be used to construct small expressions. Revisit if we run into performance
1223// issues. Note that if perf become a bottleneck for a client, then probably
1224// directly writing the proto will be even faster.
1225// ============================================================================
1226
1227inline LinearExpr operator-(LinearExpr expr) { return expr *= -1; }
1228
1229inline LinearExpr operator+(const LinearExpr& lhs, const LinearExpr& rhs) {
1230 LinearExpr temp(lhs);
1231 temp += rhs;
1232 return temp;
1233}
1234inline LinearExpr operator+(LinearExpr&& lhs, const LinearExpr& rhs) {
1235 lhs += rhs;
1236 return std::move(lhs);
1237}
1238inline LinearExpr operator+(const LinearExpr& lhs, LinearExpr&& rhs) {
1239 rhs += lhs;
1240 return std::move(rhs);
1241}
1242inline LinearExpr operator+(LinearExpr&& lhs, LinearExpr&& rhs) {
1243 if (lhs.variables().size() < rhs.variables().size()) {
1244 rhs += std::move(lhs);
1245 return std::move(rhs);
1246 } else {
1247 lhs += std::move(rhs);
1248 return std::move(lhs);
1249 }
1250}
1251
1252inline LinearExpr operator-(const LinearExpr& lhs, const LinearExpr& rhs) {
1253 LinearExpr temp(lhs);
1254 temp -= rhs;
1255 return temp;
1256}
1257inline LinearExpr operator-(LinearExpr&& lhs, const LinearExpr& rhs) {
1258 lhs -= rhs;
1259 return std::move(lhs);
1260}
1261inline LinearExpr operator-(const LinearExpr& lhs, LinearExpr&& rhs) {
1262 rhs *= -1;
1263 rhs += lhs;
1264 return std::move(rhs);
1265}
1267 lhs -= std::move(rhs);
1268 return std::move(lhs);
1269}
1270
1271inline LinearExpr operator*(LinearExpr expr, int64_t factor) {
1272 expr *= factor;
1273 return expr;
1274}
1275inline LinearExpr operator*(int64_t factor, LinearExpr expr) {
1276 expr *= factor;
1277 return expr;
1278}
1279
1280// For DoubleLinearExpr.
1281
1283 expr *= -1;
1284 return expr;
1285}
1286
1288 const DoubleLinearExpr& rhs) {
1289 DoubleLinearExpr temp(lhs);
1290 temp += rhs;
1291 return temp;
1293inline DoubleLinearExpr operator+(DoubleLinearExpr&& lhs,
1294 const DoubleLinearExpr& rhs) {
1295 lhs += rhs;
1296 return std::move(lhs);
1297}
1299 DoubleLinearExpr&& rhs) {
1300 rhs += lhs;
1301 return std::move(rhs);
1302}
1304 DoubleLinearExpr&& rhs) {
1305 if (lhs.variables().size() < rhs.variables().size()) {
1306 rhs += std::move(lhs);
1307 return std::move(rhs);
1308 } else {
1309 lhs += std::move(rhs);
1310 return std::move(lhs);
1311 }
1312}
1313
1314inline DoubleLinearExpr operator+(DoubleLinearExpr expr, double rhs) {
1315 expr += rhs;
1316 return expr;
1317}
1318inline DoubleLinearExpr operator+(double lhs, DoubleLinearExpr expr) {
1319 expr += lhs;
1320 return expr;
1321}
1322
1324 const DoubleLinearExpr& rhs) {
1325 DoubleLinearExpr temp(lhs);
1326 temp -= rhs;
1327 return temp;
1329inline DoubleLinearExpr operator-(DoubleLinearExpr&& lhs,
1330 const DoubleLinearExpr& rhs) {
1331 lhs -= rhs;
1332 return std::move(lhs);
1333}
1335 DoubleLinearExpr&& rhs) {
1336 rhs *= -1;
1337 rhs += lhs;
1338 return std::move(rhs);
1340inline DoubleLinearExpr operator-(DoubleLinearExpr&& lhs,
1341 DoubleLinearExpr&& rhs) {
1342 lhs -= std::move(rhs);
1343 return std::move(lhs);
1344}
1346inline DoubleLinearExpr operator-(DoubleLinearExpr epxr, double rhs) {
1347 epxr -= rhs;
1348 return epxr;
1349}
1350inline DoubleLinearExpr operator-(double lhs, DoubleLinearExpr expr) {
1351 expr *= -1;
1352 expr += lhs;
1353 return expr;
1354}
1356inline DoubleLinearExpr operator*(DoubleLinearExpr expr, double factor) {
1357 expr *= factor;
1358 return expr;
1359}
1360
1361inline DoubleLinearExpr operator*(double factor, DoubleLinearExpr expr) {
1362 expr *= factor;
1363 return expr;
1364}
1365
1366} // namespace sat
1367} // namespace operations_research
1368
1369#endif // OR_TOOLS_SAT_CP_MODEL_H_
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
bool operator!=(const BoolVar &other) const
Definition cp_model.h:97
std::string Name() const
Returns the name of the variable.
Definition cp_model.cc:48
friend bool SolutionBooleanValue(const CpSolverResponse &r, BoolVar x)
Evaluates the value of a Boolean literal in a solver response.
Definition cp_model.cc:1490
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
bool operator==(const BoolVar &other) const
Definition cp_model.h:93
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
const ConstraintProto & Proto() const
Returns the underlying protobuf object (useful for testing).
Definition cp_model.h:564
bool HasObjective() const
Checks whether the model contains an objective.
Definition cp_model.cc:1322
const CpModelProto & Build() const
Definition cp_model.h:1159
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
Constraint AddImplication(BoolVar a, BoolVar b)
Adds a => b.
Definition cp_model.h:810
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
const CpModelProto & Proto() const
Definition cp_model.h:1160
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
bool IsConstant() const
Returns true if the expression has no variable.
Definition cp_model.h:414
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
bool operator==(const IntVar &other) const
Definition cp_model.h:176
bool operator!=(const IntVar &other) const
Definition cp_model.h:180
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
friend 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 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
bool operator==(const IntervalVar &other) const
Equality test with another interval variable.
Definition cp_model.h:484
std::string Name() const
Returns the name of the interval (or the empty string if not set).
Definition cp_model.cc:617
bool operator!=(const IntervalVar &other) const
Difference test with another interval variable.
Definition cp_model.h:489
int index() const
Returns the index of the interval constraint in the model.
Definition cp_model.h:497
std::string DebugString() const
Returns a debug string.
Definition cp_model.cc:622
friend std::ostream & operator<<(std::ostream &os, const IntervalVar &var)
Definition cp_model.cc:641
bool IsConstant() const
Returns true if the expression has no variables.
Definition cp_model.h:300
LinearExpr & operator*=(int64_t factor)
Definition cp_model.cc:274
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
LinearExpr & operator-=(const LinearExpr &other)
Definition cp_model.cc:264
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
LinearExpr & operator+=(const LinearExpr &other)
Operators.
Definition cp_model.cc:255
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
LinearExpr operator+(const LinearExpr &lhs, const LinearExpr &rhs)
Definition cp_model.h:1234
LinearExpr operator-(LinearExpr expr)
Definition cp_model.h:1232
BoolVar Not(BoolVar x)
Definition cp_model.cc:87
std::ostream & operator<<(std::ostream &os, const BoolVar &var)
Definition cp_model.cc:89
H AbslHashValue(H h, const IntVar &i)
– ABSL HASHING SUPPORT --------------------------------------------------—
Definition cp_model.h:515
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.
LinearExpr operator*(LinearExpr expr, int64_t factor)
Definition cp_model.h:1276
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.