14"""Methods for building and solving CP-SAT models.
16The following two sections describe the main
17methods for building and solving CP-SAT models.
19* [`CpModel`](#cp_model.CpModel): Methods for creating
20models, including variables and constraints.
21* [`CPSolver`](#cp_model.CpSolver): Methods for solving
22a model and evaluating solutions.
24The following methods implement callbacks that the
25solver calls each time it finds a new solution.
27* [`CpSolverSolutionCallback`](#cp_model.CpSolverSolutionCallback):
28 A general method for implementing callbacks.
29* [`ObjectiveSolutionPrinter`](#cp_model.ObjectiveSolutionPrinter):
30 Print objective values and elapsed time for intermediate solutions.
31* [`VarArraySolutionPrinter`](#cp_model.VarArraySolutionPrinter):
32 Print intermediate solutions (variable values, time).
33* [`VarArrayAndObjectiveSolutionPrinter`]
34 (#cp_model.VarArrayAndObjectiveSolutionPrinter):
35 Print both intermediate solutions and objective values.
37Additional methods for solving CP-SAT models:
39* [`Constraint`](#cp_model.Constraint): A few utility methods for modifying
40 constraints created by `CpModel`.
41* [`LinearExpr`](#lineacp_model.LinearExpr): Methods for creating constraints
42 and the objective from large arrays of coefficients.
44Other methods and functions listed are primarily used for developing OR-Tools,
45rather than for solving specific optimization problems.
75Domain = sorted_interval_list.Domain
76BoundedLinearExpression = cmh.BoundedLinearExpression
77FlatFloatExpr = cmh.FlatFloatExpr
78FlatIntExpr = cmh.FlatIntExpr
79LinearExpr = cmh.LinearExpr
80NotBooleanVariable = cmh.NotBooleanVariable
93UNKNOWN = cp_model_pb2.UNKNOWN
94MODEL_INVALID = cp_model_pb2.MODEL_INVALID
95FEASIBLE = cp_model_pb2.FEASIBLE
96INFEASIBLE = cp_model_pb2.INFEASIBLE
97OPTIMAL = cp_model_pb2.OPTIMAL
100CHOOSE_FIRST = cp_model_pb2.DecisionStrategyProto.CHOOSE_FIRST
101CHOOSE_LOWEST_MIN = cp_model_pb2.DecisionStrategyProto.CHOOSE_LOWEST_MIN
102CHOOSE_HIGHEST_MAX = cp_model_pb2.DecisionStrategyProto.CHOOSE_HIGHEST_MAX
103CHOOSE_MIN_DOMAIN_SIZE = cp_model_pb2.DecisionStrategyProto.CHOOSE_MIN_DOMAIN_SIZE
104CHOOSE_MAX_DOMAIN_SIZE = cp_model_pb2.DecisionStrategyProto.CHOOSE_MAX_DOMAIN_SIZE
107SELECT_MIN_VALUE = cp_model_pb2.DecisionStrategyProto.SELECT_MIN_VALUE
108SELECT_MAX_VALUE = cp_model_pb2.DecisionStrategyProto.SELECT_MAX_VALUE
109SELECT_LOWER_HALF = cp_model_pb2.DecisionStrategyProto.SELECT_LOWER_HALF
110SELECT_UPPER_HALF = cp_model_pb2.DecisionStrategyProto.SELECT_UPPER_HALF
111SELECT_MEDIAN_VALUE = cp_model_pb2.DecisionStrategyProto.SELECT_MEDIAN_VALUE
112SELECT_RANDOM_HALF = cp_model_pb2.DecisionStrategyProto.SELECT_RANDOM_HALF
115AUTOMATIC_SEARCH = sat_parameters_pb2.SatParameters.AUTOMATIC_SEARCH
116FIXED_SEARCH = sat_parameters_pb2.SatParameters.FIXED_SEARCH
117PORTFOLIO_SEARCH = sat_parameters_pb2.SatParameters.PORTFOLIO_SEARCH
118LP_SEARCH = sat_parameters_pb2.SatParameters.LP_SEARCH
119PSEUDO_COST_SEARCH = sat_parameters_pb2.SatParameters.PSEUDO_COST_SEARCH
120PORTFOLIO_WITH_QUICK_RESTART_SEARCH = (
121 sat_parameters_pb2.SatParameters.PORTFOLIO_WITH_QUICK_RESTART_SEARCH
123HINT_SEARCH = sat_parameters_pb2.SatParameters.HINT_SEARCH
124PARTIAL_FIXED_SEARCH = sat_parameters_pb2.SatParameters.PARTIAL_FIXED_SEARCH
125RANDOMIZED_SEARCH = sat_parameters_pb2.SatParameters.RANDOMIZED_SEARCH
128IntegralT = Union[int, np.int8, np.uint8, np.int32, np.uint32, np.int64, np.uint64]
161LiteralT = Union[cmh.Literal, IntegralT, bool]
162BoolVarT = cmh.Literal
163VariableT = Union[
"IntVar", IntegralT]
166LinearExprT = Union[LinearExpr,
"IntVar", IntegralT]
167ObjLinearExprT = Union[LinearExpr, NumberT]
169ArcT = Tuple[IntegralT, IntegralT, LiteralT]
170_IndexOrSeries = Union[pd.Index, pd.Series]
174 """Displays a flattened list of intervals."""
176 for i
in range(0, len(bounds), 2):
179 if bounds[i] == bounds[i + 1]:
180 out += str(bounds[i])
182 out += str(bounds[i]) +
".." + str(bounds[i + 1])
186def short_name(model: cp_model_pb2.CpModelProto, i: int) -> str:
187 """Returns a short name of an integer variable, or its negation."""
189 return f
"not({short_name(model, -i - 1)})"
190 v = model.variables[i]
193 elif len(v.domain) == 2
and v.domain[0] == v.domain[1]:
194 return str(v.domain[0])
196 return f
"[{display_bounds(v.domain)}]"
200 model: cp_model_pb2.CpModelProto, e: cp_model_pb2.LinearExpressionProto
202 """Pretty-print LinearExpressionProto instances."""
212 result = f
"-{var_name}"
214 result = f
"{coeff} * {var_name}"
216 result = f
"{result} + {e.offset}"
218 result = f
"{result} - {-e.offset}"
225 """An integer variable.
227 An IntVar is an object that can take on any integer value within defined
228 ranges. Variables appear in constraint like:
231 AllDifferent([x, y, z])
233 Solving a model is equivalent to finding, for each variable, a single value
234 from the set of initial values (called the initial domain), such that the
235 model is feasible, or optimal if you provided an objective function.
240 model: cp_model_pb2.CpModelProto,
241 domain: Union[int, sorted_interval_list.Domain],
245 """See CpModel.new_int_var below."""
246 self.
__model: cp_model_pb2.CpModelProto = model
254 if isinstance(domain, IntegralTypes)
and name
is None:
255 cmh.BaseIntVar.__init__(self, int(domain), is_boolean)
257 cmh.BaseIntVar.__init__(self, len(model.variables), is_boolean)
258 proto: cp_model_pb2.IntegerVariableProto = self.
__model.variables.add()
260 cast(sorted_interval_list.Domain, domain).flattened_intervals()
266 """Returns a shallowcopy of the variable."""
270 """Returns a deepcopy of the variable."""
276 def proto(self) -> cp_model_pb2.IntegerVariableProto:
277 """Returns the variable protobuf."""
282 """Returns the model protobuf."""
286 """Returns true if self == other in the python sense."""
287 if not isinstance(other, IntVar):
289 return self.
index == other.index
292 if not self.
proto.name:
294 len(self.
proto.domain) == 2
295 and self.
proto.domain[0] == self.
proto.domain[1]
298 return str(self.
proto.domain[0])
300 return f
"BooleanVar({self.__index})"
302 return f
"IntVar({self.__index})"
304 return self.
proto.name
307 return f
"{self}({display_bounds(self.proto.domain)})"
313 return self.
proto.name
320 def Proto(self) -> cp_model_pb2.IntegerVariableProto:
327 """Base class for constraints.
329 Constraints are built by the CpModel through the add<XXX> methods.
330 Once created by the CpModel class, they are automatically added to the model.
331 The purpose of this class is to allow specification of enforcement literals
334 b = model.new_bool_var('b')
335 x = model.new_int_var(0, 10, 'x')
336 y = model.new_int_var(0, 10, 'y')
338 model.add(x + 2 * y == 5).only_enforce_if(b.negated())
345 self.
__index: int = len(cp_model.proto.constraints)
348 cp_model.proto.constraints.add()
358 """Adds an enforcement literal to the constraint.
360 This method adds one or more literals (that is, a boolean variable or its
361 negation) as enforcement literals. The conjunction of all these literals
362 determines whether the constraint is active or not. It acts as an
363 implication, so if the conjunction is true, it implies that the constraint
364 must be enforced. If it is false, then the constraint is ignored.
366 BoolOr, BoolAnd, and linear constraints all support enforcement literals.
369 *boolvar: One or more Boolean literals.
375 if (cmn.is_boolean(lit)
and lit)
or (
376 isinstance(lit, IntegralTypes)
and lit == 1
380 elif (cmn.is_boolean(lit)
and not lit)
or (
381 isinstance(lit, IntegralTypes)
and lit == 0
388 cast(cmh.Literal, lit).index
393 """Sets the name of the constraint."""
402 """Returns the name of the constraint."""
409 """Returns the index of the constraint in the model."""
413 def proto(self) -> cp_model_pb2.ConstraintProto:
414 """Returns the constraint protobuf."""
419 OnlyEnforceIf = only_enforce_if
428 def Proto(self) -> cp_model_pb2.ConstraintProto:
435 """Stores all integer variables of the model."""
444 def get(self, index: int) -> IntVar:
445 if index < 0
or index >= len(self.
__var_list):
446 raise ValueError(
"Index out of bounds.")
451 proto: cp_model_pb2.LinearExpressionProto,
453 """Recreate a LinearExpr from a LinearExpressionProto."""
454 num_elements = len(proto.vars)
455 if num_elements == 0:
457 elif num_elements == 1:
458 var = self.
get(proto.vars[0])
459 return LinearExpr.affine(
460 var, proto.coeffs[0], proto.offset
464 for var_index
in range(len(proto.vars)):
465 var = self.
get(var_index)
466 variables.append(var)
467 if proto.offset != 0:
469 coeffs.extend(proto.coeffs)
471 variables.append(proto.offset)
472 return LinearExpr.weighted_sum(variables, coeffs)
474 return LinearExpr.weighted_sum(variables, proto.coeffs)
478 """Represents an Interval variable.
480 An interval variable is both a constraint and a variable. It is defined by
481 three integer variables: start, size, and end.
483 It is a constraint because, internally, it enforces that start + size == end.
485 It is also a variable as it can appear in specific scheduling constraints:
486 NoOverlap, NoOverlap2D, Cumulative.
488 Optionally, an enforcement literal can be added to this constraint, in which
489 case these scheduling constraints will ignore interval variables with
490 enforcement literals assigned to false. Conversely, these constraints will
491 also set these enforcement literals to false if they cannot fit these
492 intervals into the schedule.
495 ValueError: if start, size, end are not defined, or have the wrong type.
500 model: cp_model_pb2.CpModelProto,
501 var_list: VariableList,
502 start: Union[cp_model_pb2.LinearExpressionProto, int],
503 size: Optional[cp_model_pb2.LinearExpressionProto],
504 end: Optional[cp_model_pb2.LinearExpressionProto],
505 is_present_index: Optional[int],
508 self.
__model: cp_model_pb2.CpModelProto = model
511 self.
__ct: cp_model_pb2.ConstraintProto
519 if isinstance(start, int):
521 raise ValueError(
"size should be None")
523 raise ValueError(
"end should be None")
524 if is_present_index
is not None:
525 raise ValueError(
"is_present_index should be None")
526 self.
__index = cast(int, start)
529 self.
__index = len(model.constraints)
532 raise TypeError(
"start is not defined")
533 self.
__ct.interval.start.CopyFrom(start)
535 raise TypeError(
"size is not defined")
536 self.
__ct.interval.size.CopyFrom(size)
538 raise TypeError(
"end is not defined")
539 self.
__ct.interval.end.CopyFrom(end)
540 if is_present_index
is not None:
541 self.
__ct.enforcement_literal.append(is_present_index)
543 self.
__ct.name = name
547 """Returns the index of the interval constraint in the model."""
551 def proto(self) -> cp_model_pb2.ConstraintProto:
552 """Returns the interval protobuf."""
557 """Returns the model protobuf."""
561 return self.
proto.name
564 interval = self.
proto.interval
565 if self.
proto.enforcement_literal:
567 f
"{self.proto.name}(start ="
568 f
" {short_expr_name(self.__model, interval.start)}, size ="
569 f
" {short_expr_name(self.__model, interval.size)}, end ="
570 f
" {short_expr_name(self.__model, interval.end)}, is_present ="
571 f
" {short_name(self.__model, self.proto.enforcement_literal[0])})"
575 f
"{self.proto.name}(start ="
576 f
" {short_expr_name(self.__model, interval.start)}, size ="
577 f
" {short_expr_name(self.__model, interval.size)}, end ="
578 f
" {short_expr_name(self.__model, interval.end)})"
585 return self.
proto.name
604 def Proto(self) -> cp_model_pb2.ConstraintProto:
607 StartExpr = start_expr
615 """Checks if literal is either True, or a Boolean literals fixed to True."""
616 if isinstance(literal, IntVar):
617 proto = literal.proto
618 return len(proto.domain) == 2
and proto.domain[0] == 1
and proto.domain[1] == 1
619 if isinstance(literal, cmh.NotBooleanVariable):
620 proto = literal.negated().proto
621 return len(proto.domain) == 2
and proto.domain[0] == 0
and proto.domain[1] == 0
622 if isinstance(literal, IntegralTypes):
623 return int(literal) == 1
628 """Checks if literal is either False, or a Boolean literals fixed to False."""
629 if isinstance(literal, IntVar):
630 proto = literal.proto
631 return len(proto.domain) == 2
and proto.domain[0] == 0
and proto.domain[1] == 0
632 if isinstance(literal, cmh.NotBooleanVariable):
633 proto = literal.negated().proto
634 return len(proto.domain) == 2
and proto.domain[0] == 1
and proto.domain[1] == 1
635 if isinstance(literal, IntegralTypes):
636 return int(literal) == 0
641 """Methods for building a CP model.
643 Methods beginning with:
645 * ```New``` create integer, boolean, or interval variables.
646 * ```add``` create new constraints and add them to the model.
650 self.
__model: cp_model_pb2.CpModelProto = cp_model_pb2.CpModelProto()
657 """Returns the name of the model."""
664 """Sets the name of the model."""
670 """Appends an integer variable to the list of variables."""
679 proto: cp_model_pb2.LinearExpressionProto,
683 def new_int_var(self, lb: IntegralT, ub: IntegralT, name: str) -> IntVar:
684 """Create an integer variable with domain [lb, ub].
686 The CP-SAT solver is limited to integer variables. If you have fractional
687 values, scale them up so that they become integers; if you have strings,
688 encode them as integers.
691 lb: Lower bound for the variable.
692 ub: Upper bound for the variable.
693 name: The name of the variable.
696 a variable whose domain is [lb, ub].
698 domain_is_boolean = lb >= 0
and ub <= 1
702 sorted_interval_list.Domain(lb, ub),
709 self, domain: sorted_interval_list.Domain, name: str
711 """Create an integer variable from a domain.
713 A domain is a set of integers specified by a collection of intervals.
714 For example, `model.new_int_var_from_domain(cp_model.
715 Domain.from_intervals([[1, 2], [4, 6]]), 'x')`
718 domain: An instance of the Domain class.
719 name: The name of the variable.
722 a variable whose domain is the given domain.
724 domain_is_boolean = domain.min() >= 0
and domain.max() <= 1
730 """Creates a 0-1 variable with the given name."""
732 IntVar(self.
__model, sorted_interval_list.Domain(0, 1),
True, name)
736 """Declares a constant integer."""
744 lower_bounds: Union[IntegralT, pd.Series],
745 upper_bounds: Union[IntegralT, pd.Series],
747 """Creates a series of (scalar-valued) variables with the given name.
750 name (str): Required. The name of the variable set.
751 index (pd.Index): Required. The index to use for the variable set.
752 lower_bounds (Union[int, pd.Series]): A lower bound for variables in the
753 set. If a `pd.Series` is passed in, it will be based on the
754 corresponding values of the pd.Series.
755 upper_bounds (Union[int, pd.Series]): An upper bound for variables in the
756 set. If a `pd.Series` is passed in, it will be based on the
757 corresponding values of the pd.Series.
760 pd.Series: The variable set indexed by its corresponding dimensions.
763 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
764 ValueError: if the `name` is not a valid identifier or already exists.
765 ValueError: if the `lowerbound` is greater than the `upperbound`.
766 ValueError: if the index of `lower_bound`, or `upper_bound` does not match
769 if not isinstance(index, pd.Index):
770 raise TypeError(
"Non-index object is used as index")
771 if not name.isidentifier():
772 raise ValueError(f
"name={name!r} is not a valid identifier")
774 isinstance(lower_bounds, IntegralTypes)
775 and isinstance(upper_bounds, IntegralTypes)
776 and lower_bounds > upper_bounds
779 f
"lower_bound={lower_bounds} is greater than"
780 f
" upper_bound={upper_bounds} for variable set={name}"
797 domain=sorted_interval_list.Domain(
798 lower_bounds[i], upper_bounds[i]
800 is_boolean=lower_bounds[i] >= 0
and upper_bounds[i] <= 1,
812 """Creates a series of (scalar-valued) variables with the given name.
815 name (str): Required. The name of the variable set.
816 index (pd.Index): Required. The index to use for the variable set.
819 pd.Series: The variable set indexed by its corresponding dimensions.
822 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
823 ValueError: if the `name` is not a valid identifier or already exists.
825 if not isinstance(index, pd.Index):
826 raise TypeError(
"Non-index object is used as index")
827 if not name.isidentifier():
828 raise ValueError(f
"name={name!r} is not a valid identifier")
837 domain=sorted_interval_list.Domain(0, 1),
848 self, linear_expr: LinearExprT, lb: IntegralT, ub: IntegralT
850 """Adds the constraint: `lb <= linear_expr <= ub`."""
852 linear_expr, sorted_interval_list.Domain(lb, ub)
857 linear_expr: LinearExprT,
858 domain: sorted_interval_list.Domain,
860 """Adds the constraint: `linear_expr` in `domain`."""
861 if isinstance(linear_expr, LinearExpr):
865 "Cannot add a linear expression containing floating point"
866 f
" coefficients or constants: {type(linear_expr).__name__!r}"
869 if isinstance(linear_expr, IntegralTypes):
870 if not domain.contains(int(linear_expr)):
876 f
" CpModel.add_linear_expression_in_domain({type(linear_expr).__name__!r})"
879 def add(self, ct: Union[BoundedLinearExpression, bool, np.bool_]) -> Constraint:
880 """Adds a `BoundedLinearExpression` to the model.
883 ct: A [`BoundedLinearExpression`](#boundedlinearexpression).
886 An instance of the `Constraint` class.
889 TypeError: If the `ct` is not a `BoundedLinearExpression` or a Boolean.
891 if isinstance(ct, BoundedLinearExpression):
893 model_ct = self.
__model.constraints[result.index]
895 model_ct.linear.vars.append(var.index)
896 model_ct.linear.coeffs.extend(ct.coeffs)
897 model_ct.linear.domain.extend(
899 cmn.capped_subtraction(x, ct.offset)
900 for x
in ct.bounds.flattened_intervals()
904 if ct
and cmn.is_boolean(ct):
906 if not ct
and cmn.is_boolean(ct):
908 raise TypeError(f
"not supported: CpModel.add({type(ct).__name__!r})")
919 """Adds AllDifferent(expressions).
921 This constraint forces all expressions to have different values.
924 *expressions: simple expressions of the form a * var + constant.
927 An instance of the `Constraint` class.
930 model_ct = self.
__model.constraints[ct.index]
932 model_ct.all_diff.exprs.extend(
940 expressions: Sequence[LinearExprT],
943 """Adds the element constraint: `expressions[index] == target`.
946 index: The index of the selected expression in the array. It must be an
947 affine expression (a * var + b).
948 expressions: A list of affine expressions.
949 target: The expression constrained to be equal to the selected expression.
950 It must be an affine expression (a * var + b).
953 An instance of the `Constraint` class.
957 raise ValueError(
"add_element expects a non-empty expressions array")
959 if isinstance(index, IntegralTypes):
960 expression: LinearExprT = list(expressions)[int(index)]
961 return self.
add(expression == target)
964 model_ct = self.
__model.constraints[ct.index]
966 model_ct.element.exprs.extend(
973 """Adds Circuit(arcs).
975 Adds a circuit constraint from a sparse list of arcs that encode the graph.
977 A circuit is a unique Hamiltonian cycle in a subgraph of the total
978 graph. In case a node 'i' is not in the cycle, then there must be a
979 loop arc 'i -> i' associated with a true literal. Otherwise
980 this constraint will fail.
983 arcs: a list of arcs. An arc is a tuple (source_node, destination_node,
984 literal). The arc is selected in the circuit if the literal is true.
985 Both source_node and destination_node must be integers between 0 and the
989 An instance of the `Constraint` class.
992 ValueError: If the list of arcs is empty.
995 raise ValueError(
"add_circuit expects a non-empty array of arcs")
997 model_ct = self.
__model.constraints[ct.index]
999 model_ct.circuit.tails.append(arc[0])
1000 model_ct.circuit.heads.append(arc[1])
1005 """Adds a multiple circuit constraint, aka the 'VRP' constraint.
1007 The direct graph where arc #i (from tails[i] to head[i]) is present iff
1008 literals[i] is true must satisfy this set of properties:
1009 - #incoming arcs == 1 except for node 0.
1010 - #outgoing arcs == 1 except for node 0.
1011 - for node zero, #incoming arcs == #outgoing arcs.
1012 - There are no duplicate arcs.
1013 - Self-arcs are allowed except for node 0.
1014 - There is no cycle in this graph, except through node 0.
1017 arcs: a list of arcs. An arc is a tuple (source_node, destination_node,
1018 literal). The arc is selected in the circuit if the literal is true.
1019 Both source_node and destination_node must be integers between 0 and the
1020 number of nodes - 1.
1023 An instance of the `Constraint` class.
1026 ValueError: If the list of arcs is empty.
1029 raise ValueError(
"add_multiple_circuit expects a non-empty array of arcs")
1031 model_ct = self.
__model.constraints[ct.index]
1033 model_ct.routes.tails.append(arc[0])
1034 model_ct.routes.heads.append(arc[1])
1040 expressions: Sequence[LinearExprT],
1041 tuples_list: Iterable[Sequence[IntegralT]],
1043 """Adds AllowedAssignments(expressions, tuples_list).
1045 An AllowedAssignments constraint is a constraint on an array of affine
1046 expressions, which requires that when all expressions are assigned values,
1048 resulting array equals one of the tuples in `tuple_list`.
1051 expressions: A list of affine expressions (a * var + b).
1052 tuples_list: A list of admissible tuples. Each tuple must have the same
1053 length as the expressions, and the ith value of a tuple corresponds to
1057 An instance of the `Constraint` class.
1060 TypeError: If a tuple does not have the same size as the list of
1062 ValueError: If the array of expressions is empty.
1067 "add_allowed_assignments expects a non-empty expressions array"
1071 model_ct = self.
__model.constraints[ct.index]
1072 model_ct.table.exprs.extend(
1075 arity: int = len(expressions)
1076 for one_tuple
in tuples_list:
1077 if len(one_tuple) != arity:
1078 raise TypeError(f
"Tuple {one_tuple!r} has the wrong arity")
1082 for one_tuple
in tuples_list:
1083 model_ct.table.values.extend(one_tuple)
1084 except ValueError
as ex:
1086 "add_xxx_assignment: Not an integer or does not fit in an int64_t:"
1087 f
" {type(ex.args).__name__!r}"
1094 expressions: Sequence[LinearExprT],
1095 tuples_list: Iterable[Sequence[IntegralT]],
1097 """Adds add_forbidden_assignments(expressions, [tuples_list]).
1099 A ForbiddenAssignments constraint is a constraint on an array of affine
1100 expressions where the list of impossible combinations is provided in the
1104 expressions: A list of affine expressions (a * var + b).
1105 tuples_list: A list of forbidden tuples. Each tuple must have the same
1106 length as the expressions, and the *i*th value of a tuple corresponds to
1107 the *i*th expression.
1110 An instance of the `Constraint` class.
1113 TypeError: If a tuple does not have the same size as the list of
1115 ValueError: If the array of expressions is empty.
1120 "add_forbidden_assignments expects a non-empty expressions array"
1123 index: int = len(self.
__model.constraints)
1125 self.
__model.constraints[index].table.negated =
True
1130 transition_expressions: Sequence[LinearExprT],
1131 starting_state: IntegralT,
1132 final_states: Sequence[IntegralT],
1133 transition_triples: Sequence[Tuple[IntegralT, IntegralT, IntegralT]],
1135 """Adds an automaton constraint.
1137 An automaton constraint takes a list of affine expressions (a * var + b) (of
1138 size *n*), an initial state, a set of final states, and a set of
1139 transitions. A transition is a triplet (*tail*, *transition*, *head*), where
1140 *tail* and *head* are states, and *transition* is the label of an arc from
1141 *head* to *tail*, corresponding to the value of one expression in the list
1145 This automaton will be unrolled into a flow with *n* + 1 phases. Each phase
1146 contains the possible states of the automaton. The first state contains the
1147 initial state. The last phase contains the final states.
1149 Between two consecutive phases *i* and *i* + 1, the automaton creates a set
1150 of arcs. For each transition (*tail*, *transition*, *head*), it will add
1151 an arc from the state *tail* of phase *i* and the state *head* of phase
1152 *i* + 1. This arc is labeled by the value *transition* of the expression
1153 `expressions[i]`. That is, this arc can only be selected if `expressions[i]`
1154 is assigned the value *transition*.
1156 A feasible solution of this constraint is an assignment of expressions such
1157 that, starting from the initial state in phase 0, there is a path labeled by
1158 the values of the expressions that ends in one of the final states in the
1162 transition_expressions: A non-empty list of affine expressions (a * var +
1163 b) whose values correspond to the labels of the arcs traversed by the
1165 starting_state: The initial state of the automaton.
1166 final_states: A non-empty list of admissible final states.
1167 transition_triples: A list of transitions for the automaton, in the
1168 following format (current_state, variable_value, next_state).
1171 An instance of the `Constraint` class.
1174 ValueError: if `transition_expressions`, `final_states`, or
1175 `transition_triples` are empty.
1178 if not transition_expressions:
1180 "add_automaton expects a non-empty transition_expressions array"
1182 if not final_states:
1183 raise ValueError(
"add_automaton expects some final states")
1185 if not transition_triples:
1186 raise ValueError(
"add_automaton expects some transition triples")
1189 model_ct = self.
__model.constraints[ct.index]
1190 model_ct.automaton.exprs.extend(
1193 model_ct.automaton.starting_state = starting_state
1194 for v
in final_states:
1195 model_ct.automaton.final_states.append(v)
1196 for t
in transition_triples:
1198 raise TypeError(f
"Tuple {t!r} has the wrong arity (!= 3)")
1199 model_ct.automaton.transition_tail.append(t[0])
1200 model_ct.automaton.transition_label.append(t[1])
1201 model_ct.automaton.transition_head.append(t[2])
1206 variables: Sequence[VariableT],
1207 inverse_variables: Sequence[VariableT],
1209 """Adds Inverse(variables, inverse_variables).
1211 An inverse constraint enforces that if `variables[i]` is assigned a value
1212 `j`, then `inverse_variables[j]` is assigned a value `i`. And vice versa.
1215 variables: An array of integer variables.
1216 inverse_variables: An array of integer variables.
1219 An instance of the `Constraint` class.
1222 TypeError: if variables and inverse_variables have different lengths, or
1226 if not variables
or not inverse_variables:
1227 raise TypeError(
"The Inverse constraint does not accept empty arrays")
1228 if len(variables) != len(inverse_variables):
1230 "In the inverse constraint, the two array variables and"
1231 " inverse_variables must have the same length."
1234 model_ct = self.
__model.constraints[ct.index]
1235 model_ct.inverse.f_direct.extend([self.
get_or_make_index(x)
for x
in variables])
1236 model_ct.inverse.f_inverse.extend(
1243 times: Iterable[LinearExprT],
1244 level_changes: Iterable[LinearExprT],
1248 """Adds Reservoir(times, level_changes, min_level, max_level).
1250 Maintains a reservoir level within bounds. The water level starts at 0, and
1251 at any time, it must be between min_level and max_level.
1253 If the affine expression `times[i]` is assigned a value t, then the current
1254 level changes by `level_changes[i]`, which is constant, at time t.
1256 Note that min level must be <= 0, and the max level must be >= 0. Please
1257 use fixed level_changes to simulate initial state.
1259 Therefore, at any time:
1260 sum(level_changes[i] if times[i] <= t) in [min_level, max_level]
1263 times: A list of 1-var affine expressions (a * x + b) which specify the
1264 time of the filling or emptying the reservoir.
1265 level_changes: A list of integer values that specifies the amount of the
1266 emptying or filling. Currently, variable demands are not supported.
1267 min_level: At any time, the level of the reservoir must be greater or
1268 equal than the min level.
1269 max_level: At any time, the level of the reservoir must be less or equal
1273 An instance of the `Constraint` class.
1276 ValueError: if max_level < min_level.
1278 ValueError: if max_level < 0.
1280 ValueError: if min_level > 0
1283 if max_level < min_level:
1284 raise ValueError(
"Reservoir constraint must have a max_level >= min_level")
1287 raise ValueError(
"Reservoir constraint must have a max_level >= 0")
1290 raise ValueError(
"Reservoir constraint must have a min_level <= 0")
1293 model_ct = self.
__model.constraints[ct.index]
1294 model_ct.reservoir.time_exprs.extend(
1297 model_ct.reservoir.level_changes.extend(
1300 model_ct.reservoir.min_level = min_level
1301 model_ct.reservoir.max_level = max_level
1306 times: Iterable[LinearExprT],
1307 level_changes: Iterable[LinearExprT],
1308 actives: Iterable[LiteralT],
1312 """Adds Reservoir(times, level_changes, actives, min_level, max_level).
1314 Maintains a reservoir level within bounds. The water level starts at 0, and
1315 at any time, it must be between min_level and max_level.
1317 If the variable `times[i]` is assigned a value t, and `actives[i]` is
1318 `True`, then the current level changes by `level_changes[i]`, which is
1322 Note that min level must be <= 0, and the max level must be >= 0. Please
1323 use fixed level_changes to simulate initial state.
1325 Therefore, at any time:
1326 sum(level_changes[i] * actives[i] if times[i] <= t) in [min_level,
1330 The array of boolean variables 'actives', if defined, indicates which
1331 actions are actually performed.
1334 times: A list of 1-var affine expressions (a * x + b) which specify the
1335 time of the filling or emptying the reservoir.
1336 level_changes: A list of integer values that specifies the amount of the
1337 emptying or filling. Currently, variable demands are not supported.
1338 actives: a list of boolean variables. They indicates if the
1339 emptying/refilling events actually take place.
1340 min_level: At any time, the level of the reservoir must be greater or
1341 equal than the min level.
1342 max_level: At any time, the level of the reservoir must be less or equal
1346 An instance of the `Constraint` class.
1349 ValueError: if max_level < min_level.
1351 ValueError: if max_level < 0.
1353 ValueError: if min_level > 0
1356 if max_level < min_level:
1357 raise ValueError(
"Reservoir constraint must have a max_level >= min_level")
1360 raise ValueError(
"Reservoir constraint must have a max_level >= 0")
1363 raise ValueError(
"Reservoir constraint must have a min_level <= 0")
1366 model_ct = self.
__model.constraints[ct.index]
1367 model_ct.reservoir.time_exprs.extend(
1370 model_ct.reservoir.level_changes.extend(
1373 model_ct.reservoir.active_literals.extend(
1376 model_ct.reservoir.min_level = min_level
1377 model_ct.reservoir.max_level = max_level
1381 self, var: IntVar, bool_var_array: Iterable[IntVar], offset: IntegralT = 0
1383 """Adds `var == i + offset <=> bool_var_array[i] == true for all i`."""
1385 for i, bool_var
in enumerate(bool_var_array):
1386 b_index = bool_var.index
1387 var_index = var.index
1388 model_ct = self.
__model.constraints.add()
1389 model_ct.linear.vars.append(var_index)
1390 model_ct.linear.coeffs.append(1)
1391 offset_as_int = int(offset)
1392 model_ct.linear.domain.extend([offset_as_int + i, offset_as_int + i])
1393 model_ct.enforcement_literal.append(b_index)
1395 model_ct = self.
__model.constraints.add()
1396 model_ct.linear.vars.append(var_index)
1397 model_ct.linear.coeffs.append(1)
1398 model_ct.enforcement_literal.append(-b_index - 1)
1399 if offset + i - 1 >= INT_MIN:
1400 model_ct.linear.domain.extend([INT_MIN, offset_as_int + i - 1])
1401 if offset + i + 1 <= INT_MAX:
1402 model_ct.linear.domain.extend([offset_as_int + i + 1, INT_MAX])
1405 """Adds `a => b` (`a` implies `b`)."""
1407 model_ct = self.
__model.constraints[ct.index]
1413 def add_bool_or(self, literals: Iterable[LiteralT]) -> Constraint: ...
1419 """Adds `Or(literals) == true`: sum(literals) >= 1."""
1421 model_ct = self.
__model.constraints[ct.index]
1422 model_ct.bool_or.literals.extend(
1437 """Same as `add_bool_or`: `sum(literals) >= 1`."""
1447 """Adds `AtMostOne(literals)`: `sum(literals) <= 1`."""
1449 model_ct = self.
__model.constraints[ct.index]
1450 model_ct.at_most_one.literals.extend(
1465 """Adds `ExactlyOne(literals)`: `sum(literals) == 1`."""
1467 model_ct = self.
__model.constraints[ct.index]
1468 model_ct.exactly_one.literals.extend(
1483 """Adds `And(literals) == true`."""
1485 model_ct = self.
__model.constraints[ct.index]
1486 model_ct.bool_and.literals.extend(
1501 """Adds `XOr(literals) == true`.
1503 In contrast to add_bool_or and add_bool_and, it does not support
1507 *literals: the list of literals in the constraint.
1510 An `Constraint` object.
1513 model_ct = self.
__model.constraints[ct.index]
1514 model_ct.bool_xor.literals.extend(
1523 self, target: LinearExprT, exprs: Iterable[LinearExprT]
1525 """Adds `target == Min(exprs)`."""
1527 model_ct = self.
__model.constraints[ct.index]
1528 model_ct.lin_max.exprs.extend(
1535 self, target: LinearExprT, exprs: Iterable[LinearExprT]
1537 """Adds `target == Max(exprs)`."""
1539 model_ct = self.
__model.constraints[ct.index]
1545 self, target: LinearExprT, num: LinearExprT, denom: LinearExprT
1547 """Adds `target == num // denom` (integer division rounded towards 0)."""
1549 model_ct = self.
__model.constraints[ct.index]
1556 """Adds `target == Abs(expr)`."""
1558 model_ct = self.
__model.constraints[ct.index]
1565 self, target: LinearExprT, expr: LinearExprT, mod: LinearExprT
1567 """Adds `target = expr % mod`.
1569 It uses the C convention, that is the result is the remainder of the
1570 integral division rounded towards 0.
1579 target: the target expression.
1580 expr: the expression to compute the modulo of.
1581 mod: the modulus expression.
1584 A `Constraint` object.
1587 model_ct = self.
__model.constraints[ct.index]
1595 target: LinearExprT,
1596 *expressions: Union[Iterable[LinearExprT], LinearExprT],
1598 """Adds `target == expressions[0] * .. * expressions[n]`."""
1600 model_ct = self.
__model.constraints[ct.index]
1601 model_ct.int_prod.exprs.extend(
1613 self, start: LinearExprT, size: LinearExprT, end: LinearExprT, name: str
1615 """Creates an interval variable from start, size, and end.
1617 An interval variable is a constraint, that is itself used in other
1618 constraints like NoOverlap.
1620 Internally, it ensures that `start + size == end`.
1623 start: The start of the interval. It must be of the form a * var + b.
1624 size: The size of the interval. It must be of the form a * var + b.
1625 end: The end of the interval. It must be of the form a * var + b.
1626 name: The name of the interval variable.
1629 An `IntervalVar` object.
1635 if len(start_expr.vars) > 1:
1637 "cp_model.new_interval_var: start must be 1-var affine or constant."
1639 if len(size_expr.vars) > 1:
1641 "cp_model.new_interval_var: size must be 1-var affine or constant."
1643 if len(end_expr.vars) > 1:
1645 "cp_model.new_interval_var: end must be 1-var affine or constant."
1661 starts: Union[LinearExprT, pd.Series],
1662 sizes: Union[LinearExprT, pd.Series],
1663 ends: Union[LinearExprT, pd.Series],
1665 """Creates a series of interval variables with the given name.
1668 name (str): Required. The name of the variable set.
1669 index (pd.Index): Required. The index to use for the variable set.
1670 starts (Union[LinearExprT, pd.Series]): The start of each interval in the
1671 set. If a `pd.Series` is passed in, it will be based on the
1672 corresponding values of the pd.Series.
1673 sizes (Union[LinearExprT, pd.Series]): The size of each interval in the
1674 set. If a `pd.Series` is passed in, it will be based on the
1675 corresponding values of the pd.Series.
1676 ends (Union[LinearExprT, pd.Series]): The ends of each interval in the
1677 set. If a `pd.Series` is passed in, it will be based on the
1678 corresponding values of the pd.Series.
1681 pd.Series: The interval variable set indexed by its corresponding
1685 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1686 ValueError: if the `name` is not a valid identifier or already exists.
1687 ValueError: if the all the indexes do not match.
1689 if not isinstance(index, pd.Index):
1690 raise TypeError(
"Non-index object is used as index")
1691 if not name.isidentifier():
1692 raise ValueError(f
"name={name!r} is not a valid identifier")
1699 interval_array.append(
1704 name=f
"{name}[{i}]",
1707 return pd.Series(index=index, data=interval_array)
1710 self, start: LinearExprT, size: IntegralT, name: str
1712 """Creates an interval variable from start, and a fixed size.
1714 An interval variable is a constraint, that is itself used in other
1715 constraints like NoOverlap.
1718 start: The start of the interval. It must be of the form a * var + b.
1719 size: The size of the interval. It must be an integer value.
1720 name: The name of the interval variable.
1723 An `IntervalVar` object.
1728 if len(start_expr.vars) > 1:
1730 "cp_model.new_interval_var: start must be affine or constant."
1746 starts: Union[LinearExprT, pd.Series],
1747 sizes: Union[IntegralT, pd.Series],
1749 """Creates a series of interval variables with the given name.
1752 name (str): Required. The name of the variable set.
1753 index (pd.Index): Required. The index to use for the variable set.
1754 starts (Union[LinearExprT, pd.Series]): The start of each interval in the
1755 set. If a `pd.Series` is passed in, it will be based on the
1756 corresponding values of the pd.Series.
1757 sizes (Union[IntegralT, pd.Series]): The fixed size of each interval in
1758 the set. If a `pd.Series` is passed in, it will be based on the
1759 corresponding values of the pd.Series.
1762 pd.Series: The interval variable set indexed by its corresponding
1766 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1767 ValueError: if the `name` is not a valid identifier or already exists.
1768 ValueError: if the all the indexes do not match.
1770 if not isinstance(index, pd.Index):
1771 raise TypeError(
"Non-index object is used as index")
1772 if not name.isidentifier():
1773 raise ValueError(f
"name={name!r} is not a valid identifier")
1779 interval_array.append(
1783 name=f
"{name}[{i}]",
1786 return pd.Series(index=index, data=interval_array)
1793 is_present: LiteralT,
1796 """Creates an optional interval var from start, size, end, and is_present.
1798 An optional interval variable is a constraint, that is itself used in other
1799 constraints like NoOverlap. This constraint is protected by a presence
1800 literal that indicates if it is active or not.
1802 Internally, it ensures that `is_present` implies `start + size ==
1806 start: The start of the interval. It must be of the form a * var + b.
1807 size: The size of the interval. It must be of the form a * var + b.
1808 end: The end of the interval. It must be of the form a * var + b.
1809 is_present: A literal that indicates if the interval is active or not. A
1810 inactive interval is simply ignored by all constraints.
1811 name: The name of the interval variable.
1814 An `IntervalVar` object.
1822 if len(start_expr.vars) > 1:
1824 "cp_model.new_interval_var: start must be affine or constant."
1826 if len(size_expr.vars) > 1:
1828 "cp_model.new_interval_var: size must be affine or constant."
1830 if len(end_expr.vars) > 1:
1832 "cp_model.new_interval_var: end must be affine or constant."
1848 starts: Union[LinearExprT, pd.Series],
1849 sizes: Union[LinearExprT, pd.Series],
1850 ends: Union[LinearExprT, pd.Series],
1851 are_present: Union[LiteralT, pd.Series],
1853 """Creates a series of interval variables with the given name.
1856 name (str): Required. The name of the variable set.
1857 index (pd.Index): Required. The index to use for the variable set.
1858 starts (Union[LinearExprT, pd.Series]): The start of each interval in the
1859 set. If a `pd.Series` is passed in, it will be based on the
1860 corresponding values of the pd.Series.
1861 sizes (Union[LinearExprT, pd.Series]): The size of each interval in the
1862 set. If a `pd.Series` is passed in, it will be based on the
1863 corresponding values of the pd.Series.
1864 ends (Union[LinearExprT, pd.Series]): The ends of each interval in the
1865 set. If a `pd.Series` is passed in, it will be based on the
1866 corresponding values of the pd.Series.
1867 are_present (Union[LiteralT, pd.Series]): The performed literal of each
1868 interval in the set. If a `pd.Series` is passed in, it will be based on
1869 the corresponding values of the pd.Series.
1872 pd.Series: The interval variable set indexed by its corresponding
1876 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1877 ValueError: if the `name` is not a valid identifier or already exists.
1878 ValueError: if the all the indexes do not match.
1880 if not isinstance(index, pd.Index):
1881 raise TypeError(
"Non-index object is used as index")
1882 if not name.isidentifier():
1883 raise ValueError(f
"name={name!r} is not a valid identifier")
1892 interval_array.append(
1897 is_present=are_present[i],
1898 name=f
"{name}[{i}]",
1901 return pd.Series(index=index, data=interval_array)
1907 is_present: LiteralT,
1910 """Creates an interval variable from start, and a fixed size.
1912 An interval variable is a constraint, that is itself used in other
1913 constraints like NoOverlap.
1916 start: The start of the interval. It must be of the form a * var + b.
1917 size: The size of the interval. It must be an integer value.
1918 is_present: A literal that indicates if the interval is active or not. A
1919 inactive interval is simply ignored by all constraints.
1920 name: The name of the interval variable.
1923 An `IntervalVar` object.
1928 if len(start_expr.vars) > 1:
1930 "cp_model.new_interval_var: start must be affine or constant."
1947 starts: Union[LinearExprT, pd.Series],
1948 sizes: Union[IntegralT, pd.Series],
1949 are_present: Union[LiteralT, pd.Series],
1951 """Creates a series of interval variables with the given name.
1954 name (str): Required. The name of the variable set.
1955 index (pd.Index): Required. The index to use for the variable set.
1956 starts (Union[LinearExprT, pd.Series]): The start of each interval in the
1957 set. If a `pd.Series` is passed in, it will be based on the
1958 corresponding values of the pd.Series.
1959 sizes (Union[IntegralT, pd.Series]): The fixed size of each interval in
1960 the set. If a `pd.Series` is passed in, it will be based on the
1961 corresponding values of the pd.Series.
1962 are_present (Union[LiteralT, pd.Series]): The performed literal of each
1963 interval in the set. If a `pd.Series` is passed in, it will be based on
1964 the corresponding values of the pd.Series.
1967 pd.Series: The interval variable set indexed by its corresponding
1971 TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1972 ValueError: if the `name` is not a valid identifier or already exists.
1973 ValueError: if the all the indexes do not match.
1975 if not isinstance(index, pd.Index):
1976 raise TypeError(
"Non-index object is used as index")
1977 if not name.isidentifier():
1978 raise ValueError(f
"name={name!r} is not a valid identifier")
1985 interval_array.append(
1989 is_present=are_present[i],
1990 name=f
"{name}[{i}]",
1993 return pd.Series(index=index, data=interval_array)
1996 """Adds NoOverlap(interval_vars).
1998 A NoOverlap constraint ensures that all present intervals do not overlap
2002 interval_vars: The list of interval variables to constrain.
2005 An instance of the `Constraint` class.
2008 model_ct = self.
__model.constraints[ct.index]
2009 model_ct.no_overlap.intervals.extend(
2016 x_intervals: Iterable[IntervalVar],
2017 y_intervals: Iterable[IntervalVar],
2019 """Adds NoOverlap2D(x_intervals, y_intervals).
2021 A NoOverlap2D constraint ensures that all present rectangles do not overlap
2022 on a plane. Each rectangle is aligned with the X and Y axis, and is defined
2023 by two intervals which represent its projection onto the X and Y axis.
2025 Furthermore, one box is optional if at least one of the x or y interval is
2029 x_intervals: The X coordinates of the rectangles.
2030 y_intervals: The Y coordinates of the rectangles.
2033 An instance of the `Constraint` class.
2036 model_ct = self.
__model.constraints[ct.index]
2037 model_ct.no_overlap_2d.x_intervals.extend(
2040 model_ct.no_overlap_2d.y_intervals.extend(
2047 intervals: Iterable[IntervalVar],
2048 demands: Iterable[LinearExprT],
2049 capacity: LinearExprT,
2051 """Adds Cumulative(intervals, demands, capacity).
2053 This constraint enforces that:
2057 if (start(intervals[i]) <= t < end(intervals[i])) and
2058 (intervals[i] is present)) <= capacity
2061 intervals: The list of intervals.
2062 demands: The list of demands for each interval. Each demand must be >= 0.
2063 Each demand can be a 1-var affine expression (a * x + b).
2064 capacity: The maximum capacity of the cumulative constraint. It can be a
2065 1-var affine expression (a * x + b).
2068 An instance of the `Constraint` class.
2071 model_ct = self.
__model.constraints[cumulative.index]
2072 model_ct.cumulative.intervals.extend(
2082 """Reset the model, and creates a new one from a CpModelProto instance."""
2085 clone.rebuild_var_and_constant_map()
2089 """Internal method used during model cloning."""
2090 for i, var
in enumerate(self.
__model.variables):
2091 if len(var.domain) == 2
and var.domain[0] == var.domain[1]:
2094 len(var.domain) == 2
and var.domain[0] >= 0
and var.domain[1] <= 1
2099 """Returns an already created Boolean variable from its index."""
2101 if not result.is_boolean:
2103 f
"get_bool_var_from_proto_index: index {index} does not reference a"
2109 """Returns an already created integer variable from its index."""
2113 """Returns an already created interval variable from its index."""
2114 if index < 0
or index >= len(self.
__model.constraints):
2116 f
"get_interval_var_from_proto_index: out of bound index {index}"
2118 ct = self.
__model.constraints[index]
2119 if not ct.HasField(
"interval"):
2121 f
"get_interval_var_from_proto_index: index {index} does not"
2122 " reference an" +
" interval variable"
2133 def proto(self) -> cp_model_pb2.CpModelProto:
2134 """Returns the underlying CpModelProto."""
2141 """Returns the index of a variable, its negation, or a number."""
2142 if isinstance(arg, IntVar):
2144 if isinstance(arg, IntegralTypes):
2147 f
"NotSupported: model.get_or_make_index({type(arg).__name__!r})"
2151 """Returns an index from a boolean expression."""
2152 if isinstance(arg, IntVar):
2155 if isinstance(arg, cmh.NotBooleanVariable):
2158 if isinstance(arg, IntegralTypes):
2159 if arg == ~int(
False):
2161 if arg == ~int(
True):
2163 arg = cmn.assert_is_zero_or_one(arg)
2165 if cmn.is_boolean(arg):
2168 "not supported:" f
" model.get_or_make_boolean_index({type(arg).__name__!r})"
2172 if not isinstance(arg, IntervalVar):
2174 f
"NotSupported: model.get_interval_index({type(arg).__name__!r})"
2183 return constant_var.index
2186 self, linear_expr: LinearExprT, negate: bool =
False
2187 ) -> cp_model_pb2.LinearExpressionProto:
2188 """Returns a LinearExpressionProto built from a LinearExpr instance."""
2189 result: cp_model_pb2.LinearExpressionProto = (
2190 cp_model_pb2.LinearExpressionProto()
2192 mult = -1
if negate
else 1
2193 if isinstance(linear_expr, IntegralTypes):
2194 result.offset = int(linear_expr) * mult
2198 flat_expr = cmh.FlatIntExpr(linear_expr)
2199 result.offset = flat_expr.offset * mult
2200 for var
in flat_expr.vars:
2201 result.vars.append(var.index)
2202 for coeff
in flat_expr.coeffs:
2203 result.coeffs.append(coeff * mult)
2207 """Sets the objective of the model."""
2209 if isinstance(obj, IntegralTypes):
2210 self.
__model.objective.offset = int(obj)
2211 self.
__model.objective.scaling_factor = 1.0
2212 elif isinstance(obj, LinearExpr):
2213 if obj.is_integer():
2214 int_obj = cmh.FlatIntExpr(obj)
2215 for var
in int_obj.vars:
2216 self.
__model.objective.vars.append(var.index)
2218 self.
__model.objective.scaling_factor = 1.0
2219 self.
__model.objective.offset = int_obj.offset
2220 self.
__model.objective.coeffs.extend(int_obj.coeffs)
2222 self.
__model.objective.scaling_factor = -1.0
2223 self.
__model.objective.offset = -int_obj.offset
2224 for c
in int_obj.coeffs:
2225 self.
__model.objective.coeffs.append(-c)
2227 float_obj = cmh.FlatFloatExpr(obj)
2228 for var
in float_obj.vars:
2229 self.
__model.floating_point_objective.vars.append(var.index)
2230 self.
__model.floating_point_objective.coeffs.extend(float_obj.coeffs)
2231 self.
__model.floating_point_objective.maximize =
not minimize
2232 self.
__model.floating_point_objective.offset = float_obj.offset
2235 f
"TypeError: {type(obj).__name__!r} is not a valid objective"
2239 """Sets the objective of the model to minimize(obj)."""
2243 """Sets the objective of the model to maximize(obj)."""
2247 return self.
__model.HasField(
"objective")
or self.
__model.HasField(
2248 "floating_point_objective"
2252 self.
__model.ClearField(
"objective")
2253 self.
__model.ClearField(
"floating_point_objective")
2257 variables: Sequence[IntVar],
2258 var_strategy: cp_model_pb2.DecisionStrategyProto.VariableSelectionStrategy,
2259 domain_strategy: cp_model_pb2.DecisionStrategyProto.DomainReductionStrategy,
2261 """Adds a search strategy to the model.
2264 variables: a list of variables this strategy will assign.
2265 var_strategy: heuristic to choose the next variable to assign.
2266 domain_strategy: heuristic to reduce the domain of the selected variable.
2267 Currently, this is advanced code: the union of all strategies added to
2268 the model must be complete, i.e. instantiates all variables. Otherwise,
2272 strategy: cp_model_pb2.DecisionStrategyProto = (
2273 self.
__model.search_strategy.add()
2276 expr = strategy.exprs.add()
2278 expr.vars.append(v.index)
2279 expr.coeffs.append(1)
2281 expr.vars.append(self.
negated(v.index))
2282 expr.coeffs.append(-1)
2285 strategy.variable_selection_strategy = var_strategy
2286 strategy.domain_reduction_strategy = domain_strategy
2289 """Returns a string containing some model statistics."""
2290 return cmh.CpSatHelper.model_stats(self.
__model)
2293 """Returns a string indicating that the model is invalid."""
2294 return cmh.CpSatHelper.validate_model(self.
__model)
2297 """Write the model as a protocol buffer to 'file'.
2300 file: file to write the model to. If the filename ends with 'txt', the
2301 model will be written as a text file, otherwise, the binary format will
2305 True if the model was correctly written.
2307 return cmh.CpSatHelper.write_model_to_file(self.
__model, file)
2310 """Removes all names from the model."""
2311 self.
__model.ClearField(
"name")
2312 for v
in self.
__model.variables:
2313 v.ClearField(
"name")
2314 for c
in self.
__model.constraints:
2315 c.ClearField(
"name")
2318 def add_hint(self, var: IntVar, value: int) ->
None: ...
2321 def add_hint(self, literal: BoolVarT, value: bool) ->
None: ...
2324 """Adds 'var == value' as a hint to the solver."""
2327 self.
__model.solution_hint.values.append(int(value))
2330 self.
__model.solution_hint.values.append(int(
not value))
2333 """Removes any solution hint from the model."""
2334 self.
__model.ClearField(
"solution_hint")
2337 """Adds the literal to the model as assumptions."""
2341 """Adds the literals to the model as assumptions."""
2342 for lit
in literals:
2346 """Removes all assumptions from the model."""
2347 self.
__model.ClearField(
"assumptions")
2351 if isinstance(x, IntVar):
2352 var = self.
__model.variables[x.index]
2353 if len(var.domain) != 2
or var.domain[0] < 0
or var.domain[1] > 1:
2355 f
"TypeError: {type(x).__name__!r} is not a boolean variable"
2357 elif not isinstance(x, cmh.NotBooleanVariable):
2359 f
"TypeError: {type(x).__name__!r} is not a boolean variable"
2371 def Proto(self) -> cp_model_pb2.CpModelProto:
2374 NewIntVar = new_int_var
2375 NewIntVarFromDomain = new_int_var_from_domain
2376 NewBoolVar = new_bool_var
2377 NewConstant = new_constant
2378 NewIntVarSeries = new_int_var_series
2379 NewBoolVarSeries = new_bool_var_series
2380 AddLinearConstraint = add_linear_constraint
2381 AddLinearExpressionInDomain = add_linear_expression_in_domain
2383 AddAllDifferent = add_all_different
2384 AddElement = add_element
2385 AddCircuit = add_circuit
2386 AddMultipleCircuit = add_multiple_circuit
2387 AddAllowedAssignments = add_allowed_assignments
2388 AddForbiddenAssignments = add_forbidden_assignments
2389 AddAutomaton = add_automaton
2390 AddInverse = add_inverse
2391 AddReservoirConstraint = add_reservoir_constraint
2392 AddReservoirConstraintWithActive = add_reservoir_constraint_with_active
2393 AddImplication = add_implication
2394 AddBoolOr = add_bool_or
2395 AddAtLeastOne = add_at_least_one
2396 AddAtMostOne = add_at_most_one
2397 AddExactlyOne = add_exactly_one
2398 AddBoolAnd = add_bool_and
2399 AddBoolXOr = add_bool_xor
2400 AddMinEquality = add_min_equality
2401 AddMaxEquality = add_max_equality
2402 AddDivisionEquality = add_division_equality
2403 AddAbsEquality = add_abs_equality
2404 AddModuloEquality = add_modulo_equality
2405 AddMultiplicationEquality = add_multiplication_equality
2406 NewIntervalVar = new_interval_var
2407 NewIntervalVarSeries = new_interval_var_series
2408 NewFixedSizeIntervalVar = new_fixed_size_interval_var
2409 NewOptionalIntervalVar = new_optional_interval_var
2410 NewOptionalIntervalVarSeries = new_optional_interval_var_series
2411 NewOptionalFixedSizeIntervalVar = new_optional_fixed_size_interval_var
2412 NewOptionalFixedSizeIntervalVarSeries = new_optional_fixed_size_interval_var_series
2413 AddNoOverlap = add_no_overlap
2414 AddNoOverlap2D = add_no_overlap_2d
2415 AddCumulative = add_cumulative
2417 GetBoolVarFromProtoIndex = get_bool_var_from_proto_index
2418 GetIntVarFromProtoIndex = get_int_var_from_proto_index
2419 GetIntervalVarFromProtoIndex = get_interval_var_from_proto_index
2422 HasObjective = has_objective
2423 ClearObjective = clear_objective
2424 AddDecisionStrategy = add_decision_strategy
2425 ModelStats = model_stats
2427 ExportToFile = export_to_file
2429 ClearHints = clear_hints
2430 AddAssumption = add_assumption
2431 AddAssumptions = add_assumptions
2432 ClearAssumptions = clear_assumptions
2439 args: Union[Tuple[LiteralT, ...], Iterable[LiteralT]],
2440) -> Union[Iterable[LiteralT], LiteralT]: ...
2445 args: Union[Tuple[LinearExprT, ...], Iterable[LinearExprT]],
2446) -> Union[Iterable[LinearExprT], LinearExprT]: ...
2450 if hasattr(args,
"__len__"):
2453 if isinstance(args[0], (NumberTypes, LinearExpr)):
2460 """Main solver class.
2462 The purpose of this class is to search for a solution to the model provided
2463 to the solve() method.
2465 Once solve() is called, this class allows inspecting the solution found
2466 with the value() and boolean_value() methods, as well as general statistics
2467 about the solve procedure.
2473 sat_parameters_pb2.SatParameters()
2478 self.
__lock: threading.Lock = threading.Lock()
2483 solution_callback: Optional[
"CpSolverSolutionCallback"] =
None,
2484 ) -> cp_model_pb2.CpSolverStatus:
2485 """Solves a problem and passes each solution to the callback if not null."""
2490 if solution_callback
is not None:
2503 if solution_callback
is not None:
2512 """Stops the current search asynchronously."""
2517 def value(self, expression: LinearExprT) -> int:
2518 """Returns the value of a linear expression after solve."""
2521 def values(self, variables: _IndexOrSeries) -> pd.Series:
2522 """Returns the values of the input variables.
2524 If `variables` is a `pd.Index`, then the output will be indexed by the
2525 variables. If `variables` is a `pd.Series` indexed by the underlying
2526 dimensions, then the output will be indexed by the same underlying
2530 variables (Union[pd.Index, pd.Series]): The set of variables from which to
2534 pd.Series: The values of all variables in the set.
2537 RuntimeError: if solve() has not been called.
2540 raise RuntimeError(
"solve() has not been called.")
2547 """Returns the value of a linear expression after solve."""
2551 """Returns the float values of the input linear expressions.
2553 If `expressions` is a `pd.Index`, then the output will be indexed by the
2554 variables. If `variables` is a `pd.Series` indexed by the underlying
2555 dimensions, then the output will be indexed by the same underlying
2559 expressions (Union[pd.Index, pd.Series]): The set of expressions from
2560 which to get the values.
2563 pd.Series: The values of all variables in the set.
2566 RuntimeError: if solve() has not been called.
2569 raise RuntimeError(
"solve() has not been called.")
2576 """Returns the boolean value of a literal after solve."""
2580 """Returns the values of the input variables.
2582 If `variables` is a `pd.Index`, then the output will be indexed by the
2583 variables. If `variables` is a `pd.Series` indexed by the underlying
2584 dimensions, then the output will be indexed by the same underlying
2588 variables (Union[pd.Index, pd.Series]): The set of variables from which to
2592 pd.Series: The values of all variables in the set.
2595 RuntimeError: if solve() has not been called.
2598 raise RuntimeError(
"solve() has not been called.")
2608 """Returns the value of the objective after solve."""
2613 """Returns the best lower (upper) bound found when min(max)imizing."""
2618 """Returns the number of boolean variables managed by the SAT solver."""
2623 """Returns the number of conflicts since the creation of the solver."""
2628 """Returns the number of search branches explored by the solver."""
2633 """Returns the wall time in seconds since the creation of the solver."""
2638 """Returns the user time in seconds since the creation of the solver."""
2643 """Returns the response object."""
2647 """Returns some statistics on the solution found as a string."""
2651 """Returns the indices of the infeasible assumptions."""
2655 """Returns the name of the status returned by solve()."""
2658 return cp_model_pb2.CpSolverStatus.Name(status)
2661 """Returns some information on the solve process.
2663 Returns some information on how the solution was found, or the reason
2664 why the model or the parameters are invalid.
2667 RuntimeError: if solve() has not been called.
2673 """Checks solve() has been called, and returns a response wrapper."""
2675 raise RuntimeError(
"solve() has not been called.")
2711 solution_callback: Optional[
"CpSolverSolutionCallback"] =
None,
2712 ) -> cp_model_pb2.CpSolverStatus:
2713 return self.
solve(model, solution_callback)
2730 def Value(self, expression: LinearExprT) -> int:
2731 return self.
value(expression)
2733 def Values(self, variables: _IndexOrSeries) -> pd.Series:
2734 return self.
values(variables)
2740 self, model: CpModel, callback:
"CpSolverSolutionCallback"
2741 ) -> cp_model_pb2.CpSolverStatus:
2742 """DEPRECATED Use solve() with the callback argument."""
2744 "solve_with_solution_callback is deprecated; use solve() with"
2745 +
"the callback argument.",
2748 return self.
solve(model, callback)
2751 self, model: CpModel, callback:
"CpSolverSolutionCallback"
2752 ) -> cp_model_pb2.CpSolverStatus:
2753 """DEPRECATED Use solve() with the right parameter.
2755 Search for all solutions of a satisfiability problem.
2757 This method searches for all feasible solutions of a given model.
2758 Then it feeds the solution to the callback.
2760 Note that the model cannot contain an objective.
2763 model: The model to solve.
2764 callback: The callback that will be called at each solution.
2767 The status of the solve:
2769 * *FEASIBLE* if some solutions have been found
2770 * *INFEASIBLE* if the solver has proved there are no solution
2771 * *OPTIMAL* if all solutions have been found
2774 "search_for_all_solutions is deprecated; use solve() with"
2775 +
"enumerate_all_solutions = True.",
2778 if model.has_objective():
2780 "Search for all solutions is only defined on satisfiability problems"
2783 enumerate_all = self.
parameters.enumerate_all_solutions
2784 self.
parameters.enumerate_all_solutions =
True
2786 status: cp_model_pb2.CpSolverStatus = self.
solve(model, callback)
2789 self.
parameters.enumerate_all_solutions = enumerate_all
2797 """Solution callback.
2799 This class implements a callback that will be called at each new solution
2800 found during search.
2802 The method on_solution_callback() will be called by the solver, and must be
2803 implemented. The current solution can be queried using the boolean_value()
2804 and value() methods.
2806 These methods returns the same information as their counterpart in the
2811 cmh.SolutionCallback.__init__(self)
2814 """Proxy for the same method in snake case."""
2815 self.on_solution_callback()
2818 """Returns the boolean value of a boolean literal.
2821 lit: A boolean variable or its negation.
2824 The Boolean value of the literal in the solution.
2827 RuntimeError: if `lit` is not a boolean variable or its negation.
2830 raise RuntimeError(
"solve() has not been called.")
2831 return self.BooleanValue(lit)
2833 def value(self, expression: LinearExprT) -> int:
2834 """Evaluates an linear expression in the current solution.
2837 expression: a linear expression of the model.
2840 An integer value equal to the evaluation of the linear expression
2841 against the current solution.
2844 RuntimeError: if 'expression' is not a LinearExpr.
2847 raise RuntimeError(
"solve() has not been called.")
2848 return self.Value(expression)
2851 """Evaluates an linear expression in the current solution.
2854 expression: a linear expression of the model.
2857 An integer value equal to the evaluation of the linear expression
2858 against the current solution.
2861 RuntimeError: if 'expression' is not a LinearExpr.
2864 raise RuntimeError(
"solve() has not been called.")
2865 return self.FloatValue(expression)
2868 return self.HasResponse()
2871 """Stops the current search asynchronously."""
2873 raise RuntimeError(
"solve() has not been called.")
2878 """Returns the value of the objective after solve."""
2880 raise RuntimeError(
"solve() has not been called.")
2881 return self.ObjectiveValue()
2885 """Returns the best lower (upper) bound found when min(max)imizing."""
2887 raise RuntimeError(
"solve() has not been called.")
2888 return self.BestObjectiveBound()
2892 """Returns the number of boolean variables managed by the SAT solver."""
2894 raise RuntimeError(
"solve() has not been called.")
2895 return self.NumBooleans()
2899 """Returns the number of conflicts since the creation of the solver."""
2901 raise RuntimeError(
"solve() has not been called.")
2902 return self.NumConflicts()
2906 """Returns the number of search branches explored by the solver."""
2908 raise RuntimeError(
"solve() has not been called.")
2909 return self.NumBranches()
2913 """Returns the number of integer propagations done by the solver."""
2915 raise RuntimeError(
"solve() has not been called.")
2916 return self.NumIntegerPropagations()
2920 """Returns the number of Boolean propagations done by the solver."""
2922 raise RuntimeError(
"solve() has not been called.")
2923 return self.NumBooleanPropagations()
2927 """Returns the determistic time in seconds since the creation of the solver."""
2929 raise RuntimeError(
"solve() has not been called.")
2930 return self.DeterministicTime()
2934 """Returns the wall time in seconds since the creation of the solver."""
2936 raise RuntimeError(
"solve() has not been called.")
2937 return self.WallTime()
2941 """Returns the user time in seconds since the creation of the solver."""
2943 raise RuntimeError(
"solve() has not been called.")
2944 return self.UserTime()
2948 """Returns the response object."""
2950 raise RuntimeError(
"solve() has not been called.")
2951 return self.Response()
2955 """Display the objective value and time of intermediate solutions."""
2958 CpSolverSolutionCallback.__init__(self)
2963 """Called on each new solution."""
2964 current_time = time.time()
2967 f
"Solution {self.__solution_count}, time ="
2968 f
" {current_time - self.__start_time:0.2f} s, objective = {obj}",
2974 """Returns the number of solutions found."""
2979 """Print intermediate solutions (objective, variable values, time)."""
2981 def __init__(self, variables: Sequence[IntVar]) ->
None:
2982 CpSolverSolutionCallback.__init__(self)
2988 """Called on each new solution."""
2989 current_time = time.time()
2992 f
"Solution {self.__solution_count}, time ="
2993 f
" {current_time - self.__start_time:0.2f} s, objective = {obj}"
2996 print(f
" {v} = {self.value(v)}", end=
" ")
3002 """Returns the number of solutions found."""
3007 """Print intermediate solutions (variable values, time)."""
3009 def __init__(self, variables: Sequence[IntVar]) ->
None:
3010 CpSolverSolutionCallback.__init__(self)
3016 """Called on each new solution."""
3017 current_time = time.time()
3019 f
"Solution {self.__solution_count}, time ="
3020 f
" {current_time - self.__start_time:0.2f} s"
3023 print(f
" {v} = {self.value(v)}", end=
" ")
3029 """Returns the number of solutions found."""
3034 """Returns the indices of `obj` as a `pd.Index`."""
3035 if isinstance(obj, pd.Series):
3041 value_or_series: Union[IntegralT, pd.Series], index: pd.Index
3043 """Returns a pd.Series of the given index with the corresponding values.
3046 value_or_series: the values to be converted (if applicable).
3047 index: the index of the resulting pd.Series.
3050 pd.Series: The set of values with the given index.
3053 TypeError: If the type of `value_or_series` is not recognized.
3054 ValueError: If the index does not match.
3056 if isinstance(value_or_series, IntegralTypes):
3057 return pd.Series(data=value_or_series, index=index)
3058 elif isinstance(value_or_series, pd.Series):
3059 if value_or_series.index.equals(index):
3060 return value_or_series
3062 raise ValueError(
"index does not match")
3064 raise TypeError(f
"invalid type={type(value_or_series).__name__!r}")
3068 value_or_series: Union[LinearExprT, pd.Series], index: pd.Index
3070 """Returns a pd.Series of the given index with the corresponding values.
3073 value_or_series: the values to be converted (if applicable).
3074 index: the index of the resulting pd.Series.
3077 pd.Series: The set of values with the given index.
3080 TypeError: If the type of `value_or_series` is not recognized.
3081 ValueError: If the index does not match.
3083 if isinstance(value_or_series, IntegralTypes):
3084 return pd.Series(data=value_or_series, index=index)
3085 elif isinstance(value_or_series, pd.Series):
3086 if value_or_series.index.equals(index):
3087 return value_or_series
3089 raise ValueError(
"index does not match")
3091 raise TypeError(f
"invalid type={type(value_or_series).__name__!r}")
3095 value_or_series: Union[LiteralT, pd.Series], index: pd.Index
3097 """Returns a pd.Series of the given index with the corresponding values.
3100 value_or_series: the values to be converted (if applicable).
3101 index: the index of the resulting pd.Series.
3104 pd.Series: The set of values with the given index.
3107 TypeError: If the type of `value_or_series` is not recognized.
3108 ValueError: If the index does not match.
3110 if isinstance(value_or_series, IntegralTypes):
3111 return pd.Series(data=value_or_series, index=index)
3112 elif isinstance(value_or_series, pd.Series):
3113 if value_or_series.index.equals(index):
3114 return value_or_series
3116 raise ValueError(
"index does not match")
3118 raise TypeError(f
"invalid type={type(value_or_series).__name__!r}")