ortools.sat.python.cp_model

Methods for building and solving CP-SAT models.

The following two sections describe the main methods for building and solving CP-SAT models.

CpModel: Methods for creating models, including variables and constraints.
CPSolver: Methods for solving a model and evaluating solutions.

The following methods implement callbacks that the solver calls each time it finds a new solution.

CpSolverSolutionCallback: A general method for implementing callbacks.
ObjectiveSolutionPrinter: Print objective values and elapsed time for intermediate solutions.
VarArraySolutionPrinter: Print intermediate solutions (variable values, time).
[VarArrayAndObjectiveSolutionPrinter] (#cp_model.VarArrayAndObjectiveSolutionPrinter): Print both intermediate solutions and objective values.

Additional methods for solving CP-SAT models:

Constraint: A few utility methods for modifying constraints created by CpModel.
LinearExpr: Methods for creating constraints and the objective from large arrays of coefficients.

Other methods and functions listed are primarily used for developing OR-Tools, rather than for solving specific optimization problems.

View Source

   1# Copyright 2010-2024 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
  14"""Methods for building and solving CP-SAT models.
  15
  16The following two sections describe the main
  17methods for building and solving CP-SAT models.
  18
  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.
  23
  24The following methods implement callbacks that the
  25solver calls each time it finds a new solution.
  26
  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.
  36
  37Additional methods for solving CP-SAT models:
  38
  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.
  43
  44Other methods and functions listed are primarily used for developing OR-Tools,
  45rather than for solving specific optimization problems.
  46"""
  47
  48import collections
  49import itertools
  50import numbers
  51import threading
  52import time
  53from typing import (
  54    Any,
  55    Callable,
  56    Dict,
  57    Iterable,
  58    List,
  59    NoReturn,
  60    Optional,
  61    Sequence,
  62    Tuple,
  63    Union,
  64    cast,
  65    overload,
  66)
  67import warnings
  68
  69import pandas as pd
  70
  71from ortools.sat import cp_model_pb2
  72from ortools.sat import sat_parameters_pb2
  73from ortools.sat.python import cp_model_helper as cmh
  74from ortools.sat.python import swig_helper
  75from ortools.util.python import sorted_interval_list
  76
  77Domain = sorted_interval_list.Domain
  78
  79# The classes below allow linear expressions to be expressed naturally with the
  80# usual arithmetic operators + - * / and with constant numbers, which makes the
  81# python API very intuitive. See../ samples/*.py for examples.
  82
  83INT_MIN = -(2**63)  # hardcoded to be platform independent.
  84INT_MAX = 2**63 - 1
  85INT32_MIN = -(2**31)
  86INT32_MAX = 2**31 - 1
  87
  88# CpSolver status (exported to avoid importing cp_model_cp2).
  89UNKNOWN = cp_model_pb2.UNKNOWN
  90MODEL_INVALID = cp_model_pb2.MODEL_INVALID
  91FEASIBLE = cp_model_pb2.FEASIBLE
  92INFEASIBLE = cp_model_pb2.INFEASIBLE
  93OPTIMAL = cp_model_pb2.OPTIMAL
  94
  95# Variable selection strategy
  96CHOOSE_FIRST = cp_model_pb2.DecisionStrategyProto.CHOOSE_FIRST
  97CHOOSE_LOWEST_MIN = cp_model_pb2.DecisionStrategyProto.CHOOSE_LOWEST_MIN
  98CHOOSE_HIGHEST_MAX = cp_model_pb2.DecisionStrategyProto.CHOOSE_HIGHEST_MAX
  99CHOOSE_MIN_DOMAIN_SIZE = cp_model_pb2.DecisionStrategyProto.CHOOSE_MIN_DOMAIN_SIZE
 100CHOOSE_MAX_DOMAIN_SIZE = cp_model_pb2.DecisionStrategyProto.CHOOSE_MAX_DOMAIN_SIZE
 101
 102# Domain reduction strategy
 103SELECT_MIN_VALUE = cp_model_pb2.DecisionStrategyProto.SELECT_MIN_VALUE
 104SELECT_MAX_VALUE = cp_model_pb2.DecisionStrategyProto.SELECT_MAX_VALUE
 105SELECT_LOWER_HALF = cp_model_pb2.DecisionStrategyProto.SELECT_LOWER_HALF
 106SELECT_UPPER_HALF = cp_model_pb2.DecisionStrategyProto.SELECT_UPPER_HALF
 107
 108# Search branching
 109AUTOMATIC_SEARCH = sat_parameters_pb2.SatParameters.AUTOMATIC_SEARCH
 110FIXED_SEARCH = sat_parameters_pb2.SatParameters.FIXED_SEARCH
 111PORTFOLIO_SEARCH = sat_parameters_pb2.SatParameters.PORTFOLIO_SEARCH
 112LP_SEARCH = sat_parameters_pb2.SatParameters.LP_SEARCH
 113PSEUDO_COST_SEARCH = sat_parameters_pb2.SatParameters.PSEUDO_COST_SEARCH
 114PORTFOLIO_WITH_QUICK_RESTART_SEARCH = (
 115    sat_parameters_pb2.SatParameters.PORTFOLIO_WITH_QUICK_RESTART_SEARCH
 116)
 117HINT_SEARCH = sat_parameters_pb2.SatParameters.HINT_SEARCH
 118PARTIAL_FIXED_SEARCH = sat_parameters_pb2.SatParameters.PARTIAL_FIXED_SEARCH
 119RANDOMIZED_SEARCH = sat_parameters_pb2.SatParameters.RANDOMIZED_SEARCH
 120
 121# Type aliases
 122# We need to add int to numbers.Integral
 123IntegralT = Union[numbers.Integral, int]
 124# We need to add int and float, otherwise type checkers complain.
 125NumberT = Union[numbers.Integral, int, numbers.Number, float]
 126LiteralT = Union["IntVar", "_NotBooleanVariable", IntegralT, bool]
 127BoolVarT = Union["IntVar", "_NotBooleanVariable"]
 128VariableT = Union["IntVar", IntegralT]
 129LinearExprT = Union["LinearExpr", "IntVar", IntegralT]
 130ObjLinearExprT = Union["LinearExpr", "IntVar", NumberT]
 131BoundedLinearExprT = Union["BoundedLinearExpression", bool]
 132ArcT = Tuple[IntegralT, IntegralT, LiteralT]
 133_IndexOrSeries = Union[pd.Index, pd.Series]
 134
 135
 136def display_bounds(bounds: Sequence[int]) -> str:
 137    """Displays a flattened list of intervals."""
 138    out = ""
 139    for i in range(0, len(bounds), 2):
 140        if i != 0:
 141            out += ", "
 142        if bounds[i] == bounds[i + 1]:
 143            out += str(bounds[i])
 144        else:
 145            out += str(bounds[i]) + ".." + str(bounds[i + 1])
 146    return out
 147
 148
 149def short_name(model: cp_model_pb2.CpModelProto, i: int) -> str:
 150    """Returns a short name of an integer variable, or its negation."""
 151    if i < 0:
 152        return "not(%s)" % short_name(model, -i - 1)
 153    v = model.variables[i]
 154    if v.name:
 155        return v.name
 156    elif len(v.domain) == 2 and v.domain[0] == v.domain[1]:
 157        return str(v.domain[0])
 158    else:
 159        return "[%s]" % display_bounds(v.domain)
 160
 161
 162def short_expr_name(
 163    model: cp_model_pb2.CpModelProto, e: cp_model_pb2.LinearExpressionProto
 164) -> str:
 165    """Pretty-print LinearExpressionProto instances."""
 166    if not e.vars:
 167        return str(e.offset)
 168    if len(e.vars) == 1:
 169        var_name = short_name(model, e.vars[0])
 170        coeff = e.coeffs[0]
 171        result = ""
 172        if coeff == 1:
 173            result = var_name
 174        elif coeff == -1:
 175            result = f"-{var_name}"
 176        elif coeff != 0:
 177            result = f"{coeff} * {var_name}"
 178        if e.offset > 0:
 179            result = f"{result} + {e.offset}"
 180        elif e.offset < 0:
 181            result = f"{result} - {-e.offset}"
 182        return result
 183    # TODO(user): Support more than affine expressions.
 184    return str(e)
 185
 186
 187class LinearExpr:
 188    """Holds an integer linear expression.
 189
 190    A linear expression is built from integer constants and variables.
 191    For example, `x + 2 * (y - z + 1)`.
 192
 193    Linear expressions are used in CP-SAT models in constraints and in the
 194    objective:
 195
 196    * You can define linear constraints as in:
 197
 198    ```
 199    model.add(x + 2 * y <= 5)
 200    model.add(sum(array_of_vars) == 5)
 201    ```
 202
 203    * In CP-SAT, the objective is a linear expression:
 204
 205    ```
 206    model.minimize(x + 2 * y + z)
 207    ```
 208
 209    * For large arrays, using the LinearExpr class is faster that using the python
 210    `sum()` function. You can create constraints and the objective from lists of
 211    linear expressions or coefficients as follows:
 212
 213    ```
 214    model.minimize(cp_model.LinearExpr.sum(expressions))
 215    model.add(cp_model.LinearExpr.weighted_sum(expressions, coefficients) >= 0)
 216    ```
 217    """
 218
 219    @classmethod
 220    def sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
 221        """Creates the expression sum(expressions)."""
 222        if len(expressions) == 1:
 223            return expressions[0]
 224        return _SumArray(expressions)
 225
 226    @overload
 227    @classmethod
 228    def weighted_sum(
 229        cls,
 230        expressions: Sequence[LinearExprT],
 231        coefficients: Sequence[IntegralT],
 232    ) -> LinearExprT:
 233        ...
 234
 235    @overload
 236    @classmethod
 237    def weighted_sum(
 238        cls,
 239        expressions: Sequence[ObjLinearExprT],
 240        coefficients: Sequence[NumberT],
 241    ) -> ObjLinearExprT:
 242        ...
 243
 244    @classmethod
 245    def weighted_sum(cls, expressions, coefficients):
 246        """Creates the expression sum(expressions[i] * coefficients[i])."""
 247        if LinearExpr.is_empty_or_all_null(coefficients):
 248            return 0
 249        elif len(expressions) == 1:
 250            return expressions[0] * coefficients[0]
 251        else:
 252            return _WeightedSum(expressions, coefficients)
 253
 254    @overload
 255    @classmethod
 256    def term(
 257        cls,
 258        expressions: LinearExprT,
 259        coefficients: IntegralT,
 260    ) -> LinearExprT:
 261        ...
 262
 263    @overload
 264    @classmethod
 265    def term(
 266        cls,
 267        expressions: ObjLinearExprT,
 268        coefficients: NumberT,
 269    ) -> ObjLinearExprT:
 270        ...
 271
 272    @classmethod
 273    def term(cls, expression, coefficient):
 274        """Creates `expression * coefficient`."""
 275        if cmh.is_zero(coefficient):
 276            return 0
 277        else:
 278            return expression * coefficient
 279
 280    @classmethod
 281    def is_empty_or_all_null(cls, coefficients: Sequence[NumberT]) -> bool:
 282        for c in coefficients:
 283            if not cmh.is_zero(c):
 284                return False
 285        return True
 286
 287    @classmethod
 288    def rebuild_from_linear_expression_proto(
 289        cls,
 290        model: cp_model_pb2.CpModelProto,
 291        proto: cp_model_pb2.LinearExpressionProto,
 292    ) -> LinearExprT:
 293        """Recreate a LinearExpr from a LinearExpressionProto."""
 294        offset = proto.offset
 295        num_elements = len(proto.vars)
 296        if num_elements == 0:
 297            return offset
 298        elif num_elements == 1:
 299            return IntVar(model, proto.vars[0], None) * proto.coeffs[0] + offset
 300        else:
 301            variables = []
 302            coeffs = []
 303            all_ones = True
 304            for index, coeff in zip(proto.vars, proto.coeffs):
 305                variables.append(IntVar(model, index, None))
 306                coeffs.append(coeff)
 307                if not cmh.is_one(coeff):
 308                    all_ones = False
 309            if all_ones:
 310                return _SumArray(variables, offset)
 311            else:
 312                return _WeightedSum(variables, coeffs, offset)
 313
 314    def get_integer_var_value_map(self) -> Tuple[Dict["IntVar", IntegralT], int]:
 315        """Scans the expression, and returns (var_coef_map, constant)."""
 316        coeffs = collections.defaultdict(int)
 317        constant = 0
 318        to_process: List[Tuple[LinearExprT, IntegralT]] = [(self, 1)]
 319        while to_process:  # Flatten to avoid recursion.
 320            expr, coeff = to_process.pop()
 321            if isinstance(expr, numbers.Integral):
 322                constant += coeff * int(expr)
 323            elif isinstance(expr, _ProductCst):
 324                to_process.append((expr.expression(), coeff * expr.coefficient()))
 325            elif isinstance(expr, _Sum):
 326                to_process.append((expr.left(), coeff))
 327                to_process.append((expr.right(), coeff))
 328            elif isinstance(expr, _SumArray):
 329                for e in expr.expressions():
 330                    to_process.append((e, coeff))
 331                constant += expr.constant() * coeff
 332            elif isinstance(expr, _WeightedSum):
 333                for e, c in zip(expr.expressions(), expr.coefficients()):
 334                    to_process.append((e, coeff * c))
 335                constant += expr.constant() * coeff
 336            elif isinstance(expr, IntVar):
 337                coeffs[expr] += coeff
 338            elif isinstance(expr, _NotBooleanVariable):
 339                constant += coeff
 340                coeffs[expr.negated()] -= coeff
 341            else:
 342                raise TypeError("Unrecognized linear expression: " + str(expr))
 343
 344        return coeffs, constant
 345
 346    def get_float_var_value_map(
 347        self,
 348    ) -> Tuple[Dict["IntVar", float], float, bool]:
 349        """Scans the expression. Returns (var_coef_map, constant, is_integer)."""
 350        coeffs = {}
 351        constant = 0
 352        to_process: List[Tuple[LinearExprT, Union[IntegralT, float]]] = [(self, 1)]
 353        while to_process:  # Flatten to avoid recursion.
 354            expr, coeff = to_process.pop()
 355            if isinstance(expr, numbers.Integral):  # Keep integrality.
 356                constant += coeff * int(expr)
 357            elif isinstance(expr, numbers.Number):
 358                constant += coeff * float(expr)
 359            elif isinstance(expr, _ProductCst):
 360                to_process.append((expr.expression(), coeff * expr.coefficient()))
 361            elif isinstance(expr, _Sum):
 362                to_process.append((expr.left(), coeff))
 363                to_process.append((expr.right(), coeff))
 364            elif isinstance(expr, _SumArray):
 365                for e in expr.expressions():
 366                    to_process.append((e, coeff))
 367                constant += expr.constant() * coeff
 368            elif isinstance(expr, _WeightedSum):
 369                for e, c in zip(expr.expressions(), expr.coefficients()):
 370                    to_process.append((e, coeff * c))
 371                constant += expr.constant() * coeff
 372            elif isinstance(expr, IntVar):
 373                if expr in coeffs:
 374                    coeffs[expr] += coeff
 375                else:
 376                    coeffs[expr] = coeff
 377            elif isinstance(expr, _NotBooleanVariable):
 378                constant += coeff
 379                if expr.negated() in coeffs:
 380                    coeffs[expr.negated()] -= coeff
 381                else:
 382                    coeffs[expr.negated()] = -coeff
 383            else:
 384                raise TypeError("Unrecognized linear expression: " + str(expr))
 385        is_integer = isinstance(constant, numbers.Integral)
 386        if is_integer:
 387            for coeff in coeffs.values():
 388                if not isinstance(coeff, numbers.Integral):
 389                    is_integer = False
 390                    break
 391        return coeffs, constant, is_integer
 392
 393    def __hash__(self) -> int:
 394        return object.__hash__(self)
 395
 396    def __abs__(self) -> NoReturn:
 397        raise NotImplementedError(
 398            "calling abs() on a linear expression is not supported, "
 399            "please use CpModel.add_abs_equality"
 400        )
 401
 402    @overload
 403    def __add__(self, arg: LinearExprT) -> LinearExprT:
 404        ...
 405
 406    @overload
 407    def __add__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 408        ...
 409
 410    def __add__(self, arg):
 411        if cmh.is_zero(arg):
 412            return self
 413        return _Sum(self, arg)
 414
 415    @overload
 416    def __radd__(self, arg: LinearExprT) -> LinearExprT:
 417        ...
 418
 419    @overload
 420    def __radd__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 421        ...
 422
 423    def __radd__(self, arg):
 424        if cmh.is_zero(arg):
 425            return self
 426        return _Sum(self, arg)
 427
 428    @overload
 429    def __sub__(self, arg: LinearExprT) -> LinearExprT:
 430        ...
 431
 432    @overload
 433    def __sub__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 434        ...
 435
 436    def __sub__(self, arg):
 437        if cmh.is_zero(arg):
 438            return self
 439        if isinstance(arg, numbers.Number):
 440            arg = cmh.assert_is_a_number(arg)
 441            return _Sum(self, -arg)
 442        else:
 443            return _Sum(self, -arg)
 444
 445    @overload
 446    def __rsub__(self, arg: LinearExprT) -> LinearExprT:
 447        ...
 448
 449    @overload
 450    def __rsub__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 451        ...
 452
 453    def __rsub__(self, arg):
 454        return _Sum(-self, arg)
 455
 456    @overload
 457    def __mul__(self, arg: LinearExprT) -> LinearExprT:
 458        ...
 459
 460    @overload
 461    def __mul__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 462        ...
 463
 464    def __mul__(self, arg):
 465        arg = cmh.assert_is_a_number(arg)
 466        if cmh.is_one(arg):
 467            return self
 468        elif cmh.is_zero(arg):
 469            return 0
 470        return _ProductCst(self, arg)
 471
 472    @overload
 473    def __rmul__(self, arg: LinearExprT) -> LinearExprT:
 474        ...
 475
 476    @overload
 477    def __rmul__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
 478        ...
 479
 480    def __rmul__(self, arg):
 481        arg = cmh.assert_is_a_number(arg)
 482        if cmh.is_one(arg):
 483            return self
 484        elif cmh.is_zero(arg):
 485            return 0
 486        return _ProductCst(self, arg)
 487
 488    def __div__(self, _) -> NoReturn:
 489        raise NotImplementedError(
 490            "calling / on a linear expression is not supported, "
 491            "please use CpModel.add_division_equality"
 492        )
 493
 494    def __truediv__(self, _) -> NoReturn:
 495        raise NotImplementedError(
 496            "calling // on a linear expression is not supported, "
 497            "please use CpModel.add_division_equality"
 498        )
 499
 500    def __mod__(self, _) -> NoReturn:
 501        raise NotImplementedError(
 502            "calling %% on a linear expression is not supported, "
 503            "please use CpModel.add_modulo_equality"
 504        )
 505
 506    def __pow__(self, _) -> NoReturn:
 507        raise NotImplementedError(
 508            "calling ** on a linear expression is not supported, "
 509            "please use CpModel.add_multiplication_equality"
 510        )
 511
 512    def __lshift__(self, _) -> NoReturn:
 513        raise NotImplementedError(
 514            "calling left shift on a linear expression is not supported"
 515        )
 516
 517    def __rshift__(self, _) -> NoReturn:
 518        raise NotImplementedError(
 519            "calling right shift on a linear expression is not supported"
 520        )
 521
 522    def __and__(self, _) -> NoReturn:
 523        raise NotImplementedError(
 524            "calling and on a linear expression is not supported, "
 525            "please use CpModel.add_bool_and"
 526        )
 527
 528    def __or__(self, _) -> NoReturn:
 529        raise NotImplementedError(
 530            "calling or on a linear expression is not supported, "
 531            "please use CpModel.add_bool_or"
 532        )
 533
 534    def __xor__(self, _) -> NoReturn:
 535        raise NotImplementedError(
 536            "calling xor on a linear expression is not supported, "
 537            "please use CpModel.add_bool_xor"
 538        )
 539
 540    def __neg__(self) -> LinearExprT:
 541        return _ProductCst(self, -1)
 542
 543    def __bool__(self) -> NoReturn:
 544        raise NotImplementedError(
 545            "Evaluating a LinearExpr instance as a Boolean is not implemented."
 546        )
 547
 548    def __eq__(self, arg: LinearExprT) -> BoundedLinearExprT:
 549        if arg is None:
 550            return False
 551        if isinstance(arg, numbers.Integral):
 552            arg = cmh.assert_is_int64(arg)
 553            return BoundedLinearExpression(self, [arg, arg])
 554        else:
 555            return BoundedLinearExpression(self - arg, [0, 0])
 556
 557    def __ge__(self, arg: LinearExprT) -> BoundedLinearExprT:
 558        if isinstance(arg, numbers.Integral):
 559            arg = cmh.assert_is_int64(arg)
 560            return BoundedLinearExpression(self, [arg, INT_MAX])
 561        else:
 562            return BoundedLinearExpression(self - arg, [0, INT_MAX])
 563
 564    def __le__(self, arg: LinearExprT) -> BoundedLinearExprT:
 565        if isinstance(arg, numbers.Integral):
 566            arg = cmh.assert_is_int64(arg)
 567            return BoundedLinearExpression(self, [INT_MIN, arg])
 568        else:
 569            return BoundedLinearExpression(self - arg, [INT_MIN, 0])
 570
 571    def __lt__(self, arg: LinearExprT) -> BoundedLinearExprT:
 572        if isinstance(arg, numbers.Integral):
 573            arg = cmh.assert_is_int64(arg)
 574            if arg == INT_MIN:
 575                raise ArithmeticError("< INT_MIN is not supported")
 576            return BoundedLinearExpression(self, [INT_MIN, arg - 1])
 577        else:
 578            return BoundedLinearExpression(self - arg, [INT_MIN, -1])
 579
 580    def __gt__(self, arg: LinearExprT) -> BoundedLinearExprT:
 581        if isinstance(arg, numbers.Integral):
 582            arg = cmh.assert_is_int64(arg)
 583            if arg == INT_MAX:
 584                raise ArithmeticError("> INT_MAX is not supported")
 585            return BoundedLinearExpression(self, [arg + 1, INT_MAX])
 586        else:
 587            return BoundedLinearExpression(self - arg, [1, INT_MAX])
 588
 589    def __ne__(self, arg: LinearExprT) -> BoundedLinearExprT:
 590        if arg is None:
 591            return True
 592        if isinstance(arg, numbers.Integral):
 593            arg = cmh.assert_is_int64(arg)
 594            if arg == INT_MAX:
 595                return BoundedLinearExpression(self, [INT_MIN, INT_MAX - 1])
 596            elif arg == INT_MIN:
 597                return BoundedLinearExpression(self, [INT_MIN + 1, INT_MAX])
 598            else:
 599                return BoundedLinearExpression(
 600                    self, [INT_MIN, arg - 1, arg + 1, INT_MAX]
 601                )
 602        else:
 603            return BoundedLinearExpression(self - arg, [INT_MIN, -1, 1, INT_MAX])
 604
 605    # Compatibility with pre PEP8
 606    # pylint: disable=invalid-name
 607    @classmethod
 608    def Sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
 609        """Creates the expression sum(expressions)."""
 610        return cls.sum(expressions)
 611
 612    @overload
 613    @classmethod
 614    def WeightedSum(
 615        cls,
 616        expressions: Sequence[LinearExprT],
 617        coefficients: Sequence[IntegralT],
 618    ) -> LinearExprT:
 619        ...
 620
 621    @overload
 622    @classmethod
 623    def WeightedSum(
 624        cls,
 625        expressions: Sequence[ObjLinearExprT],
 626        coefficients: Sequence[NumberT],
 627    ) -> ObjLinearExprT:
 628        ...
 629
 630    @classmethod
 631    def WeightedSum(cls, expressions, coefficients):
 632        """Creates the expression sum(expressions[i] * coefficients[i])."""
 633        return cls.weighted_sum(expressions, coefficients)
 634
 635    @overload
 636    @classmethod
 637    def Term(
 638        cls,
 639        expressions: LinearExprT,
 640        coefficients: IntegralT,
 641    ) -> LinearExprT:
 642        ...
 643
 644    @overload
 645    @classmethod
 646    def Term(
 647        cls,
 648        expressions: ObjLinearExprT,
 649        coefficients: NumberT,
 650    ) -> ObjLinearExprT:
 651        ...
 652
 653    @classmethod
 654    def Term(cls, expression, coefficient):
 655        """Creates `expression * coefficient`."""
 656        return cls.term(expression, coefficient)
 657
 658    # pylint: enable=invalid-name
 659
 660
 661class _Sum(LinearExpr):
 662    """Represents the sum of two LinearExprs."""
 663
 664    def __init__(self, left, right):
 665        for x in [left, right]:
 666            if not isinstance(x, (numbers.Number, LinearExpr)):
 667                raise TypeError("not an linear expression: " + str(x))
 668        self.__left = left
 669        self.__right = right
 670
 671    def left(self):
 672        return self.__left
 673
 674    def right(self):
 675        return self.__right
 676
 677    def __str__(self):
 678        return f"({self.__left} + {self.__right})"
 679
 680    def __repr__(self):
 681        return f"sum({self.__left!r}, {self.__right!r})"
 682
 683
 684class _ProductCst(LinearExpr):
 685    """Represents the product of a LinearExpr by a constant."""
 686
 687    def __init__(self, expr, coeff):
 688        coeff = cmh.assert_is_a_number(coeff)
 689        if isinstance(expr, _ProductCst):
 690            self.__expr = expr.expression()
 691            self.__coef = expr.coefficient() * coeff
 692        else:
 693            self.__expr = expr
 694            self.__coef = coeff
 695
 696    def __str__(self):
 697        if self.__coef == -1:
 698            return "-" + str(self.__expr)
 699        else:
 700            return "(" + str(self.__coef) + " * " + str(self.__expr) + ")"
 701
 702    def __repr__(self):
 703        return f"ProductCst({self.__expr!r}, {self.__coef!r})"
 704
 705    def coefficient(self):
 706        return self.__coef
 707
 708    def expression(self):
 709        return self.__expr
 710
 711
 712class _SumArray(LinearExpr):
 713    """Represents the sum of a list of LinearExpr and a constant."""
 714
 715    def __init__(self, expressions, constant=0):
 716        self.__expressions = []
 717        self.__constant = constant
 718        for x in expressions:
 719            if isinstance(x, numbers.Number):
 720                if cmh.is_zero(x):
 721                    continue
 722                x = cmh.assert_is_a_number(x)
 723                self.__constant += x
 724            elif isinstance(x, LinearExpr):
 725                self.__expressions.append(x)
 726            else:
 727                raise TypeError("not an linear expression: " + str(x))
 728
 729    def __str__(self):
 730        constant_terms = (self.__constant,) if self.__constant != 0 else ()
 731        exprs_str = " + ".join(
 732            map(repr, itertools.chain(self.__expressions, constant_terms))
 733        )
 734        if not exprs_str:
 735            return "0"
 736        return f"({exprs_str})"
 737
 738    def __repr__(self):
 739        exprs_str = ", ".join(map(repr, self.__expressions))
 740        return f"SumArray({exprs_str}, {self.__constant})"
 741
 742    def expressions(self):
 743        return self.__expressions
 744
 745    def constant(self):
 746        return self.__constant
 747
 748
 749class _WeightedSum(LinearExpr):
 750    """Represents sum(ai * xi) + b."""
 751
 752    def __init__(self, expressions, coefficients, constant=0):
 753        self.__expressions = []
 754        self.__coefficients = []
 755        self.__constant = constant
 756        if len(expressions) != len(coefficients):
 757            raise TypeError(
 758                "In the LinearExpr.weighted_sum method, the expression array and the "
 759                " coefficient array must have the same length."
 760            )
 761        for e, c in zip(expressions, coefficients):
 762            c = cmh.assert_is_a_number(c)
 763            if cmh.is_zero(c):
 764                continue
 765            if isinstance(e, numbers.Number):
 766                e = cmh.assert_is_a_number(e)
 767                self.__constant += e * c
 768            elif isinstance(e, LinearExpr):
 769                self.__expressions.append(e)
 770                self.__coefficients.append(c)
 771            else:
 772                raise TypeError("not an linear expression: " + str(e))
 773
 774    def __str__(self):
 775        output = None
 776        for expr, coeff in zip(self.__expressions, self.__coefficients):
 777            if not output and cmh.is_one(coeff):
 778                output = str(expr)
 779            elif not output and cmh.is_minus_one(coeff):
 780                output = "-" + str(expr)
 781            elif not output:
 782                output = f"{coeff} * {expr}"
 783            elif cmh.is_one(coeff):
 784                output += f" + {expr}"
 785            elif cmh.is_minus_one(coeff):
 786                output += f" - {expr}"
 787            elif coeff > 1:
 788                output += f" + {coeff} * {expr}"
 789            elif coeff < -1:
 790                output += f" - {-coeff} * {expr}"
 791        if self.__constant > 0:
 792            output += f" + {self.__constant}"
 793        elif self.__constant < 0:
 794            output += f" - {-self.__constant}"
 795        if output is None:
 796            output = "0"
 797        return output
 798
 799    def __repr__(self):
 800        return (
 801            f"weighted_sum({self.__expressions!r}, {self.__coefficients!r},"
 802            f" {self.__constant})"
 803        )
 804
 805    def expressions(self):
 806        return self.__expressions
 807
 808    def coefficients(self):
 809        return self.__coefficients
 810
 811    def constant(self):
 812        return self.__constant
 813
 814
 815class IntVar(LinearExpr):
 816    """An integer variable.
 817
 818    An IntVar is an object that can take on any integer value within defined
 819    ranges. Variables appear in constraint like:
 820
 821        x + y >= 5
 822        AllDifferent([x, y, z])
 823
 824    Solving a model is equivalent to finding, for each variable, a single value
 825    from the set of initial values (called the initial domain), such that the
 826    model is feasible, or optimal if you provided an objective function.
 827    """
 828
 829    def __init__(
 830        self,
 831        model: cp_model_pb2.CpModelProto,
 832        domain: Union[int, Domain],
 833        name: Optional[str],
 834    ):
 835        """See CpModel.new_int_var below."""
 836        self.__negation: Optional[_NotBooleanVariable] = None
 837        # Python do not support multiple __init__ methods.
 838        # This method is only called from the CpModel class.
 839        # We hack the parameter to support the two cases:
 840        # case 1:
 841        #     model is a CpModelProto, domain is a Domain, and name is a string.
 842        # case 2:
 843        #     model is a CpModelProto, domain is an index (int), and name is None.
 844        if isinstance(domain, numbers.Integral) and name is None:
 845            self.__index: int = int(domain)
 846            self.__var: cp_model_pb2.IntegerVariableProto = model.variables[domain]
 847        else:
 848            self.__index: int = len(model.variables)
 849            self.__var: cp_model_pb2.IntegerVariableProto = model.variables.add()
 850            self.__var.domain.extend(cast(Domain, domain).flattened_intervals())
 851            self.__var.name = name
 852
 853    @property
 854    def index(self) -> int:
 855        """Returns the index of the variable in the model."""
 856        return self.__index
 857
 858    @property
 859    def proto(self) -> cp_model_pb2.IntegerVariableProto:
 860        """Returns the variable protobuf."""
 861        return self.__var
 862
 863    def is_equal_to(self, other: Any) -> bool:
 864        """Returns true if self == other in the python sense."""
 865        if not isinstance(other, IntVar):
 866            return False
 867        return self.index == other.index
 868
 869    def __str__(self) -> str:
 870        if not self.__var.name:
 871            if (
 872                len(self.__var.domain) == 2
 873                and self.__var.domain[0] == self.__var.domain[1]
 874            ):
 875                # Special case for constants.
 876                return str(self.__var.domain[0])
 877            else:
 878                return "unnamed_var_%i" % self.__index
 879        return self.__var.name
 880
 881    def __repr__(self) -> str:
 882        return "%s(%s)" % (self.__var.name, display_bounds(self.__var.domain))
 883
 884    @property
 885    def name(self) -> str:
 886        if not self.__var or not self.__var.name:
 887            return ""
 888        return self.__var.name
 889
 890    def negated(self) -> "_NotBooleanVariable":
 891        """Returns the negation of a Boolean variable.
 892
 893        This method implements the logical negation of a Boolean variable.
 894        It is only valid if the variable has a Boolean domain (0 or 1).
 895
 896        Note that this method is nilpotent: `x.negated().negated() == x`.
 897        """
 898
 899        for bound in self.__var.domain:
 900            if bound < 0 or bound > 1:
 901                raise TypeError(
 902                    f"cannot call negated on a non boolean variable: {self}"
 903                )
 904        if self.__negation is None:
 905            self.__negation = _NotBooleanVariable(self)
 906        return self.__negation
 907
 908    def __invert__(self) -> "_NotBooleanVariable":
 909        """Returns the logical negation of a Boolean variable."""
 910        return self.negated()
 911
 912    # Pre PEP8 compatibility.
 913    # pylint: disable=invalid-name
 914    Not = negated
 915
 916    def Name(self) -> str:
 917        return self.name
 918
 919    def Proto(self) -> cp_model_pb2.IntegerVariableProto:
 920        return self.proto
 921
 922    def Index(self) -> int:
 923        return self.index
 924
 925    # pylint: enable=invalid-name
 926
 927
 928class _NotBooleanVariable(LinearExpr):
 929    """Negation of a boolean variable."""
 930
 931    def __init__(self, boolvar: IntVar):
 932        self.__boolvar: IntVar = boolvar
 933
 934    @property
 935    def index(self) -> int:
 936        return -self.__boolvar.index - 1
 937
 938    def negated(self) -> IntVar:
 939        return self.__boolvar
 940
 941    def __invert__(self) -> IntVar:
 942        """Returns the logical negation of a Boolean literal."""
 943        return self.negated()
 944
 945    def __str__(self) -> str:
 946        return self.name
 947
 948    @property
 949    def name(self) -> str:
 950        return "not(%s)" % str(self.__boolvar)
 951
 952    def __bool__(self) -> NoReturn:
 953        raise NotImplementedError(
 954            "Evaluating a literal as a Boolean value is not implemented."
 955        )
 956
 957    # Pre PEP8 compatibility.
 958    # pylint: disable=invalid-name
 959    def Not(self) -> "IntVar":
 960        return self.negated()
 961
 962    def Index(self) -> int:
 963        return self.index
 964
 965    # pylint: enable=invalid-name
 966
 967
 968class BoundedLinearExpression:
 969    """Represents a linear constraint: `lb <= linear expression <= ub`.
 970
 971    The only use of this class is to be added to the CpModel through
 972    `CpModel.add(expression)`, as in:
 973
 974        model.add(x + 2 * y -1 >= z)
 975    """
 976
 977    def __init__(self, expr: LinearExprT, bounds: Sequence[int]):
 978        self.__expr: LinearExprT = expr
 979        self.__bounds: Sequence[int] = bounds
 980
 981    def __str__(self):
 982        if len(self.__bounds) == 2:
 983            lb, ub = self.__bounds
 984            if lb > INT_MIN and ub < INT_MAX:
 985                if lb == ub:
 986                    return str(self.__expr) + " == " + str(lb)
 987                else:
 988                    return str(lb) + " <= " + str(self.__expr) + " <= " + str(ub)
 989            elif lb > INT_MIN:
 990                return str(self.__expr) + " >= " + str(lb)
 991            elif ub < INT_MAX:
 992                return str(self.__expr) + " <= " + str(ub)
 993            else:
 994                return "True (unbounded expr " + str(self.__expr) + ")"
 995        elif (
 996            len(self.__bounds) == 4
 997            and self.__bounds[0] == INT_MIN
 998            and self.__bounds[1] + 2 == self.__bounds[2]
 999            and self.__bounds[3] == INT_MAX
1000        ):
1001            return str(self.__expr) + " != " + str(self.__bounds[1] + 1)
1002        else:
1003            return str(self.__expr) + " in [" + display_bounds(self.__bounds) + "]"
1004
1005    def expression(self) -> LinearExprT:
1006        return self.__expr
1007
1008    def bounds(self) -> Sequence[int]:
1009        return self.__bounds
1010
1011    def __bool__(self) -> bool:
1012        expr = self.__expr
1013        if isinstance(expr, LinearExpr):
1014            coeffs_map, constant = expr.get_integer_var_value_map()
1015            all_coeffs = set(coeffs_map.values())
1016            same_var = set([0])
1017            eq_bounds = [0, 0]
1018            different_vars = set([-1, 1])
1019            ne_bounds = [INT_MIN, -1, 1, INT_MAX]
1020            if (
1021                len(coeffs_map) == 1
1022                and all_coeffs == same_var
1023                and constant == 0
1024                and (self.__bounds == eq_bounds or self.__bounds == ne_bounds)
1025            ):
1026                return self.__bounds == eq_bounds
1027            if (
1028                len(coeffs_map) == 2
1029                and all_coeffs == different_vars
1030                and constant == 0
1031                and (self.__bounds == eq_bounds or self.__bounds == ne_bounds)
1032            ):
1033                return self.__bounds == ne_bounds
1034
1035        raise NotImplementedError(
1036            f'Evaluating a BoundedLinearExpression "{self}" as a Boolean value'
1037            + " is not supported."
1038        )
1039
1040
1041class Constraint:
1042    """Base class for constraints.
1043
1044    Constraints are built by the CpModel through the add<XXX> methods.
1045    Once created by the CpModel class, they are automatically added to the model.
1046    The purpose of this class is to allow specification of enforcement literals
1047    for this constraint.
1048
1049        b = model.new_bool_var('b')
1050        x = model.new_int_var(0, 10, 'x')
1051        y = model.new_int_var(0, 10, 'y')
1052
1053        model.add(x + 2 * y == 5).only_enforce_if(b.negated())
1054    """
1055
1056    def __init__(
1057        self,
1058        cp_model: "CpModel",
1059    ):
1060        self.__index: int = len(cp_model.proto.constraints)
1061        self.__cp_model: "CpModel" = cp_model
1062        self.__constraint: cp_model_pb2.ConstraintProto = (
1063            cp_model.proto.constraints.add()
1064        )
1065
1066    @overload
1067    def only_enforce_if(self, boolvar: Iterable[LiteralT]) -> "Constraint":
1068        ...
1069
1070    @overload
1071    def only_enforce_if(self, *boolvar: LiteralT) -> "Constraint":
1072        ...
1073
1074    def only_enforce_if(self, *boolvar) -> "Constraint":
1075        """Adds an enforcement literal to the constraint.
1076
1077        This method adds one or more literals (that is, a boolean variable or its
1078        negation) as enforcement literals. The conjunction of all these literals
1079        determines whether the constraint is active or not. It acts as an
1080        implication, so if the conjunction is true, it implies that the constraint
1081        must be enforced. If it is false, then the constraint is ignored.
1082
1083        BoolOr, BoolAnd, and linear constraints all support enforcement literals.
1084
1085        Args:
1086          *boolvar: One or more Boolean literals.
1087
1088        Returns:
1089          self.
1090        """
1091        for lit in expand_generator_or_tuple(boolvar):
1092            if (cmh.is_boolean(lit) and lit) or (
1093                isinstance(lit, numbers.Integral) and lit == 1
1094            ):
1095                # Always true. Do nothing.
1096                pass
1097            elif (cmh.is_boolean(lit) and not lit) or (
1098                isinstance(lit, numbers.Integral) and lit == 0
1099            ):
1100                self.__constraint.enforcement_literal.append(
1101                    self.__cp_model.new_constant(0).index
1102                )
1103            else:
1104                self.__constraint.enforcement_literal.append(
1105                    cast(Union[IntVar, _NotBooleanVariable], lit).index
1106                )
1107        return self
1108
1109    def with_name(self, name: str) -> "Constraint":
1110        """Sets the name of the constraint."""
1111        if name:
1112            self.__constraint.name = name
1113        else:
1114            self.__constraint.ClearField("name")
1115        return self
1116
1117    @property
1118    def name(self) -> str:
1119        """Returns the name of the constraint."""
1120        if not self.__constraint or not self.__constraint.name:
1121            return ""
1122        return self.__constraint.name
1123
1124    @property
1125    def index(self) -> int:
1126        """Returns the index of the constraint in the model."""
1127        return self.__index
1128
1129    @property
1130    def proto(self) -> cp_model_pb2.ConstraintProto:
1131        """Returns the constraint protobuf."""
1132        return self.__constraint
1133
1134    # Pre PEP8 compatibility.
1135    # pylint: disable=invalid-name
1136    OnlyEnforceIf = only_enforce_if
1137    WithName = with_name
1138
1139    def Name(self) -> str:
1140        return self.name
1141
1142    def Index(self) -> int:
1143        return self.index
1144
1145    def Proto(self) -> cp_model_pb2.ConstraintProto:
1146        return self.proto
1147
1148    # pylint: enable=invalid-name
1149
1150
1151class IntervalVar:
1152    """Represents an Interval variable.
1153
1154    An interval variable is both a constraint and a variable. It is defined by
1155    three integer variables: start, size, and end.
1156
1157    It is a constraint because, internally, it enforces that start + size == end.
1158
1159    It is also a variable as it can appear in specific scheduling constraints:
1160    NoOverlap, NoOverlap2D, Cumulative.
1161
1162    Optionally, an enforcement literal can be added to this constraint, in which
1163    case these scheduling constraints will ignore interval variables with
1164    enforcement literals assigned to false. Conversely, these constraints will
1165    also set these enforcement literals to false if they cannot fit these
1166    intervals into the schedule.
1167    """
1168
1169    def __init__(
1170        self,
1171        model: cp_model_pb2.CpModelProto,
1172        start: Union[cp_model_pb2.LinearExpressionProto, int],
1173        size: Optional[cp_model_pb2.LinearExpressionProto],
1174        end: Optional[cp_model_pb2.LinearExpressionProto],
1175        is_present_index: Optional[int],
1176        name: Optional[str],
1177    ):
1178        self.__model: cp_model_pb2.CpModelProto = model
1179        # As with the IntVar::__init__ method, we hack the __init__ method to
1180        # support two use cases:
1181        #   case 1: called when creating a new interval variable.
1182        #      {start|size|end} are linear expressions, is_present_index is either
1183        #      None or the index of a Boolean literal. name is a string
1184        #   case 2: called when querying an existing interval variable.
1185        #      start_index is an int, all parameters after are None.
1186        if size is None and end is None and is_present_index is None and name is None:
1187            self.__index: int = cast(int, start)
1188            self.__ct: cp_model_pb2.ConstraintProto = model.constraints[self.__index]
1189        else:
1190            self.__index: int = len(model.constraints)
1191            self.__ct: cp_model_pb2.ConstraintProto = self.__model.constraints.add()
1192            self.__ct.interval.start.CopyFrom(start)
1193            self.__ct.interval.size.CopyFrom(size)
1194            self.__ct.interval.end.CopyFrom(end)
1195            if is_present_index is not None:
1196                self.__ct.enforcement_literal.append(is_present_index)
1197            if name:
1198                self.__ct.name = name
1199
1200    @property
1201    def index(self) -> int:
1202        """Returns the index of the interval constraint in the model."""
1203        return self.__index
1204
1205    @property
1206    def proto(self) -> cp_model_pb2.IntervalConstraintProto:
1207        """Returns the interval protobuf."""
1208        return self.__ct.interval
1209
1210    def __str__(self):
1211        return self.__ct.name
1212
1213    def __repr__(self):
1214        interval = self.__ct.interval
1215        if self.__ct.enforcement_literal:
1216            return "%s(start = %s, size = %s, end = %s, is_present = %s)" % (
1217                self.__ct.name,
1218                short_expr_name(self.__model, interval.start),
1219                short_expr_name(self.__model, interval.size),
1220                short_expr_name(self.__model, interval.end),
1221                short_name(self.__model, self.__ct.enforcement_literal[0]),
1222            )
1223        else:
1224            return "%s(start = %s, size = %s, end = %s)" % (
1225                self.__ct.name,
1226                short_expr_name(self.__model, interval.start),
1227                short_expr_name(self.__model, interval.size),
1228                short_expr_name(self.__model, interval.end),
1229            )
1230
1231    @property
1232    def name(self) -> str:
1233        if not self.__ct or not self.__ct.name:
1234            return ""
1235        return self.__ct.name
1236
1237    def start_expr(self) -> LinearExprT:
1238        return LinearExpr.rebuild_from_linear_expression_proto(
1239            self.__model, self.__ct.interval.start
1240        )
1241
1242    def size_expr(self) -> LinearExprT:
1243        return LinearExpr.rebuild_from_linear_expression_proto(
1244            self.__model, self.__ct.interval.size
1245        )
1246
1247    def end_expr(self) -> LinearExprT:
1248        return LinearExpr.rebuild_from_linear_expression_proto(
1249            self.__model, self.__ct.interval.end
1250        )
1251
1252    # Pre PEP8 compatibility.
1253    # pylint: disable=invalid-name
1254    def Name(self) -> str:
1255        return self.name
1256
1257    def Index(self) -> int:
1258        return self.index
1259
1260    def Proto(self) -> cp_model_pb2.IntervalConstraintProto:
1261        return self.proto
1262
1263    StartExpr = start_expr
1264    SizeExpr = size_expr
1265    EndExpr = end_expr
1266
1267    # pylint: enable=invalid-name
1268
1269
1270def object_is_a_true_literal(literal: LiteralT) -> bool:
1271    """Checks if literal is either True, or a Boolean literals fixed to True."""
1272    if isinstance(literal, IntVar):
1273        proto = literal.proto
1274        return len(proto.domain) == 2 and proto.domain[0] == 1 and proto.domain[1] == 1
1275    if isinstance(literal, _NotBooleanVariable):
1276        proto = literal.negated().proto
1277        return len(proto.domain) == 2 and proto.domain[0] == 0 and proto.domain[1] == 0
1278    if isinstance(literal, numbers.Integral):
1279        return int(literal) == 1
1280    return False
1281
1282
1283def object_is_a_false_literal(literal: LiteralT) -> bool:
1284    """Checks if literal is either False, or a Boolean literals fixed to False."""
1285    if isinstance(literal, IntVar):
1286        proto = literal.proto
1287        return len(proto.domain) == 2 and proto.domain[0] == 0 and proto.domain[1] == 0
1288    if isinstance(literal, _NotBooleanVariable):
1289        proto = literal.negated().proto
1290        return len(proto.domain) == 2 and proto.domain[0] == 1 and proto.domain[1] == 1
1291    if isinstance(literal, numbers.Integral):
1292        return int(literal) == 0
1293    return False
1294
1295
1296class CpModel:
1297    """Methods for building a CP model.
1298
1299    Methods beginning with:
1300
1301    * ```New``` create integer, boolean, or interval variables.
1302    * ```add``` create new constraints and add them to the model.
1303    """
1304
1305    def __init__(self):
1306        self.__model: cp_model_pb2.CpModelProto = cp_model_pb2.CpModelProto()
1307        self.__constant_map = {}
1308
1309    # Naming.
1310    @property
1311    def name(self) -> str:
1312        """Returns the name of the model."""
1313        if not self.__model or not self.__model.name:
1314            return ""
1315        return self.__model.name
1316
1317    @name.setter
1318    def name(self, name: str):
1319        """Sets the name of the model."""
1320        self.__model.name = name
1321
1322    # Integer variable.
1323
1324    def new_int_var(self, lb: IntegralT, ub: IntegralT, name: str) -> IntVar:
1325        """Create an integer variable with domain [lb, ub].
1326
1327        The CP-SAT solver is limited to integer variables. If you have fractional
1328        values, scale them up so that they become integers; if you have strings,
1329        encode them as integers.
1330
1331        Args:
1332          lb: Lower bound for the variable.
1333          ub: Upper bound for the variable.
1334          name: The name of the variable.
1335
1336        Returns:
1337          a variable whose domain is [lb, ub].
1338        """
1339
1340        return IntVar(self.__model, Domain(lb, ub), name)
1341
1342    def new_int_var_from_domain(self, domain: Domain, name: str) -> IntVar:
1343        """Create an integer variable from a domain.
1344
1345        A domain is a set of integers specified by a collection of intervals.
1346        For example, `model.new_int_var_from_domain(cp_model.
1347             Domain.from_intervals([[1, 2], [4, 6]]), 'x')`
1348
1349        Args:
1350          domain: An instance of the Domain class.
1351          name: The name of the variable.
1352
1353        Returns:
1354            a variable whose domain is the given domain.
1355        """
1356        return IntVar(self.__model, domain, name)
1357
1358    def new_bool_var(self, name: str) -> IntVar:
1359        """Creates a 0-1 variable with the given name."""
1360        return IntVar(self.__model, Domain(0, 1), name)
1361
1362    def new_constant(self, value: IntegralT) -> IntVar:
1363        """Declares a constant integer."""
1364        return IntVar(self.__model, self.get_or_make_index_from_constant(value), None)
1365
1366    def new_int_var_series(
1367        self,
1368        name: str,
1369        index: pd.Index,
1370        lower_bounds: Union[IntegralT, pd.Series],
1371        upper_bounds: Union[IntegralT, pd.Series],
1372    ) -> pd.Series:
1373        """Creates a series of (scalar-valued) variables with the given name.
1374
1375        Args:
1376          name (str): Required. The name of the variable set.
1377          index (pd.Index): Required. The index to use for the variable set.
1378          lower_bounds (Union[int, pd.Series]): A lower bound for variables in the
1379            set. If a `pd.Series` is passed in, it will be based on the
1380            corresponding values of the pd.Series.
1381          upper_bounds (Union[int, pd.Series]): An upper bound for variables in the
1382            set. If a `pd.Series` is passed in, it will be based on the
1383            corresponding values of the pd.Series.
1384
1385        Returns:
1386          pd.Series: The variable set indexed by its corresponding dimensions.
1387
1388        Raises:
1389          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1390          ValueError: if the `name` is not a valid identifier or already exists.
1391          ValueError: if the `lowerbound` is greater than the `upperbound`.
1392          ValueError: if the index of `lower_bound`, or `upper_bound` does not match
1393          the input index.
1394        """
1395        if not isinstance(index, pd.Index):
1396            raise TypeError("Non-index object is used as index")
1397        if not name.isidentifier():
1398            raise ValueError("name={} is not a valid identifier".format(name))
1399        if (
1400            isinstance(lower_bounds, numbers.Integral)
1401            and isinstance(upper_bounds, numbers.Integral)
1402            and lower_bounds > upper_bounds
1403        ):
1404            raise ValueError(
1405                f"lower_bound={lower_bounds} is greater than"
1406                f" upper_bound={upper_bounds} for variable set={name}"
1407            )
1408
1409        lower_bounds = _convert_to_integral_series_and_validate_index(
1410            lower_bounds, index
1411        )
1412        upper_bounds = _convert_to_integral_series_and_validate_index(
1413            upper_bounds, index
1414        )
1415        return pd.Series(
1416            index=index,
1417            data=[
1418                # pylint: disable=g-complex-comprehension
1419                IntVar(
1420                    model=self.__model,
1421                    name=f"{name}[{i}]",
1422                    domain=Domain(lower_bounds[i], upper_bounds[i]),
1423                )
1424                for i in index
1425            ],
1426        )
1427
1428    def new_bool_var_series(
1429        self,
1430        name: str,
1431        index: pd.Index,
1432    ) -> pd.Series:
1433        """Creates a series of (scalar-valued) variables with the given name.
1434
1435        Args:
1436          name (str): Required. The name of the variable set.
1437          index (pd.Index): Required. The index to use for the variable set.
1438
1439        Returns:
1440          pd.Series: The variable set indexed by its corresponding dimensions.
1441
1442        Raises:
1443          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
1444          ValueError: if the `name` is not a valid identifier or already exists.
1445        """
1446        return self.new_int_var_series(
1447            name=name, index=index, lower_bounds=0, upper_bounds=1
1448        )
1449
1450    # Linear constraints.
1451
1452    def add_linear_constraint(
1453        self, linear_expr: LinearExprT, lb: IntegralT, ub: IntegralT
1454    ) -> Constraint:
1455        """Adds the constraint: `lb <= linear_expr <= ub`."""
1456        return self.add_linear_expression_in_domain(linear_expr, Domain(lb, ub))
1457
1458    def add_linear_expression_in_domain(
1459        self, linear_expr: LinearExprT, domain: Domain
1460    ) -> Constraint:
1461        """Adds the constraint: `linear_expr` in `domain`."""
1462        if isinstance(linear_expr, LinearExpr):
1463            ct = Constraint(self)
1464            model_ct = self.__model.constraints[ct.index]
1465            coeffs_map, constant = linear_expr.get_integer_var_value_map()
1466            for t in coeffs_map.items():
1467                if not isinstance(t[0], IntVar):
1468                    raise TypeError("Wrong argument" + str(t))
1469                c = cmh.assert_is_int64(t[1])
1470                model_ct.linear.vars.append(t[0].index)
1471                model_ct.linear.coeffs.append(c)
1472            model_ct.linear.domain.extend(
1473                [
1474                    cmh.capped_subtraction(x, constant)
1475                    for x in domain.flattened_intervals()
1476                ]
1477            )
1478            return ct
1479        if isinstance(linear_expr, numbers.Integral):
1480            if not domain.contains(int(linear_expr)):
1481                return self.add_bool_or([])  # Evaluate to false.
1482            else:
1483                return self.add_bool_and([])  # Evaluate to true.
1484        raise TypeError(
1485            "not supported: CpModel.add_linear_expression_in_domain("
1486            + str(linear_expr)
1487            + " "
1488            + str(domain)
1489            + ")"
1490        )
1491
1492    def add(self, ct: Union[BoundedLinearExpression, bool]) -> Constraint:
1493        """Adds a `BoundedLinearExpression` to the model.
1494
1495        Args:
1496          ct: A [`BoundedLinearExpression`](#boundedlinearexpression).
1497
1498        Returns:
1499          An instance of the `Constraint` class.
1500        """
1501        if isinstance(ct, BoundedLinearExpression):
1502            return self.add_linear_expression_in_domain(
1503                ct.expression(), Domain.from_flat_intervals(ct.bounds())
1504            )
1505        if ct and cmh.is_boolean(ct):
1506            return self.add_bool_or([True])
1507        if not ct and cmh.is_boolean(ct):
1508            return self.add_bool_or([])  # Evaluate to false.
1509        raise TypeError("not supported: CpModel.add(" + str(ct) + ")")
1510
1511    # General Integer Constraints.
1512
1513    @overload
1514    def add_all_different(self, expressions: Iterable[LinearExprT]) -> Constraint:
1515        ...
1516
1517    @overload
1518    def add_all_different(self, *expressions: LinearExprT) -> Constraint:
1519        ...
1520
1521    def add_all_different(self, *expressions):
1522        """Adds AllDifferent(expressions).
1523
1524        This constraint forces all expressions to have different values.
1525
1526        Args:
1527          *expressions: simple expressions of the form a * var + constant.
1528
1529        Returns:
1530          An instance of the `Constraint` class.
1531        """
1532        ct = Constraint(self)
1533        model_ct = self.__model.constraints[ct.index]
1534        expanded = expand_generator_or_tuple(expressions)
1535        model_ct.all_diff.exprs.extend(
1536            self.parse_linear_expression(x) for x in expanded
1537        )
1538        return ct
1539
1540    def add_element(
1541        self, index: VariableT, variables: Sequence[VariableT], target: VariableT
1542    ) -> Constraint:
1543        """Adds the element constraint: `variables[index] == target`.
1544
1545        Args:
1546          index: The index of the variable that's being constrained.
1547          variables: A list of variables.
1548          target: The value that the variable must be equal to.
1549
1550        Returns:
1551          An instance of the `Constraint` class.
1552        """
1553
1554        if not variables:
1555            raise ValueError("add_element expects a non-empty variables array")
1556
1557        if isinstance(index, numbers.Integral):
1558            return self.add(list(variables)[int(index)] == target)
1559
1560        ct = Constraint(self)
1561        model_ct = self.__model.constraints[ct.index]
1562        model_ct.element.index = self.get_or_make_index(index)
1563        model_ct.element.vars.extend([self.get_or_make_index(x) for x in variables])
1564        model_ct.element.target = self.get_or_make_index(target)
1565        return ct
1566
1567    def add_circuit(self, arcs: Sequence[ArcT]) -> Constraint:
1568        """Adds Circuit(arcs).
1569
1570        Adds a circuit constraint from a sparse list of arcs that encode the graph.
1571
1572        A circuit is a unique Hamiltonian path in a subgraph of the total
1573        graph. In case a node 'i' is not in the path, then there must be a
1574        loop arc 'i -> i' associated with a true literal. Otherwise
1575        this constraint will fail.
1576
1577        Args:
1578          arcs: a list of arcs. An arc is a tuple (source_node, destination_node,
1579            literal). The arc is selected in the circuit if the literal is true.
1580            Both source_node and destination_node must be integers between 0 and the
1581            number of nodes - 1.
1582
1583        Returns:
1584          An instance of the `Constraint` class.
1585
1586        Raises:
1587          ValueError: If the list of arcs is empty.
1588        """
1589        if not arcs:
1590            raise ValueError("add_circuit expects a non-empty array of arcs")
1591        ct = Constraint(self)
1592        model_ct = self.__model.constraints[ct.index]
1593        for arc in arcs:
1594            tail = cmh.assert_is_int32(arc[0])
1595            head = cmh.assert_is_int32(arc[1])
1596            lit = self.get_or_make_boolean_index(arc[2])
1597            model_ct.circuit.tails.append(tail)
1598            model_ct.circuit.heads.append(head)
1599            model_ct.circuit.literals.append(lit)
1600        return ct
1601
1602    def add_multiple_circuit(self, arcs: Sequence[ArcT]) -> Constraint:
1603        """Adds a multiple circuit constraint, aka the 'VRP' constraint.
1604
1605        The direct graph where arc #i (from tails[i] to head[i]) is present iff
1606        literals[i] is true must satisfy this set of properties:
1607        - #incoming arcs == 1 except for node 0.
1608        - #outgoing arcs == 1 except for node 0.
1609        - for node zero, #incoming arcs == #outgoing arcs.
1610        - There are no duplicate arcs.
1611        - Self-arcs are allowed except for node 0.
1612        - There is no cycle in this graph, except through node 0.
1613
1614        Args:
1615          arcs: a list of arcs. An arc is a tuple (source_node, destination_node,
1616            literal). The arc is selected in the circuit if the literal is true.
1617            Both source_node and destination_node must be integers between 0 and the
1618            number of nodes - 1.
1619
1620        Returns:
1621          An instance of the `Constraint` class.
1622
1623        Raises:
1624          ValueError: If the list of arcs is empty.
1625        """
1626        if not arcs:
1627            raise ValueError("add_multiple_circuit expects a non-empty array of arcs")
1628        ct = Constraint(self)
1629        model_ct = self.__model.constraints[ct.index]
1630        for arc in arcs:
1631            tail = cmh.assert_is_int32(arc[0])
1632            head = cmh.assert_is_int32(arc[1])
1633            lit = self.get_or_make_boolean_index(arc[2])
1634            model_ct.routes.tails.append(tail)
1635            model_ct.routes.heads.append(head)
1636            model_ct.routes.literals.append(lit)
1637        return ct
1638
1639    def add_allowed_assignments(
1640        self,
1641        variables: Sequence[VariableT],
1642        tuples_list: Iterable[Sequence[IntegralT]],
1643    ) -> Constraint:
1644        """Adds AllowedAssignments(variables, tuples_list).
1645
1646        An AllowedAssignments constraint is a constraint on an array of variables,
1647        which requires that when all variables are assigned values, the resulting
1648        array equals one of the  tuples in `tuple_list`.
1649
1650        Args:
1651          variables: A list of variables.
1652          tuples_list: A list of admissible tuples. Each tuple must have the same
1653            length as the variables, and the ith value of a tuple corresponds to the
1654            ith variable.
1655
1656        Returns:
1657          An instance of the `Constraint` class.
1658
1659        Raises:
1660          TypeError: If a tuple does not have the same size as the list of
1661              variables.
1662          ValueError: If the array of variables is empty.
1663        """
1664
1665        if not variables:
1666            raise ValueError(
1667                "add_allowed_assignments expects a non-empty variables array"
1668            )
1669
1670        ct = Constraint(self)
1671        model_ct = self.__model.constraints[ct.index]
1672        model_ct.table.vars.extend([self.get_or_make_index(x) for x in variables])
1673        arity = len(variables)
1674        for t in tuples_list:
1675            if len(t) != arity:
1676                raise TypeError("Tuple " + str(t) + " has the wrong arity")
1677            ar = []
1678            for v in t:
1679                ar.append(cmh.assert_is_int64(v))
1680            model_ct.table.values.extend(ar)
1681        return ct
1682
1683    def add_forbidden_assignments(
1684        self,
1685        variables: Sequence[VariableT],
1686        tuples_list: Iterable[Sequence[IntegralT]],
1687    ) -> Constraint:
1688        """Adds add_forbidden_assignments(variables, [tuples_list]).
1689
1690        A ForbiddenAssignments constraint is a constraint on an array of variables
1691        where the list of impossible combinations is provided in the tuples list.
1692
1693        Args:
1694          variables: A list of variables.
1695          tuples_list: A list of forbidden tuples. Each tuple must have the same
1696            length as the variables, and the *i*th value of a tuple corresponds to
1697            the *i*th variable.
1698
1699        Returns:
1700          An instance of the `Constraint` class.
1701
1702        Raises:
1703          TypeError: If a tuple does not have the same size as the list of
1704                     variables.
1705          ValueError: If the array of variables is empty.
1706        """
1707
1708        if not variables:
1709            raise ValueError(
1710                "add_forbidden_assignments expects a non-empty variables array"
1711            )
1712
1713        index = len(self.__model.constraints)
1714        ct = self.add_allowed_assignments(variables, tuples_list)
1715        self.__model.constraints[index].table.negated = True
1716        return ct
1717
1718    def add_automaton(
1719        self,
1720        transition_variables: Sequence[VariableT],
1721        starting_state: IntegralT,
1722        final_states: Sequence[IntegralT],
1723        transition_triples: Sequence[Tuple[IntegralT, IntegralT, IntegralT]],
1724    ) -> Constraint:
1725        """Adds an automaton constraint.
1726
1727        An automaton constraint takes a list of variables (of size *n*), an initial
1728        state, a set of final states, and a set of transitions. A transition is a
1729        triplet (*tail*, *transition*, *head*), where *tail* and *head* are states,
1730        and *transition* is the label of an arc from *head* to *tail*,
1731        corresponding to the value of one variable in the list of variables.
1732
1733        This automaton will be unrolled into a flow with *n* + 1 phases. Each phase
1734        contains the possible states of the automaton. The first state contains the
1735        initial state. The last phase contains the final states.
1736
1737        Between two consecutive phases *i* and *i* + 1, the automaton creates a set
1738        of arcs. For each transition (*tail*, *transition*, *head*), it will add
1739        an arc from the state *tail* of phase *i* and the state *head* of phase
1740        *i* + 1. This arc is labeled by the value *transition* of the variables
1741        `variables[i]`. That is, this arc can only be selected if `variables[i]`
1742        is assigned the value *transition*.
1743
1744        A feasible solution of this constraint is an assignment of variables such
1745        that, starting from the initial state in phase 0, there is a path labeled by
1746        the values of the variables that ends in one of the final states in the
1747        final phase.
1748
1749        Args:
1750          transition_variables: A non-empty list of variables whose values
1751            correspond to the labels of the arcs traversed by the automaton.
1752          starting_state: The initial state of the automaton.
1753          final_states: A non-empty list of admissible final states.
1754          transition_triples: A list of transitions for the automaton, in the
1755            following format (current_state, variable_value, next_state).
1756
1757        Returns:
1758          An instance of the `Constraint` class.
1759
1760        Raises:
1761          ValueError: if `transition_variables`, `final_states`, or
1762            `transition_triples` are empty.
1763        """
1764
1765        if not transition_variables:
1766            raise ValueError(
1767                "add_automaton expects a non-empty transition_variables array"
1768            )
1769        if not final_states:
1770            raise ValueError("add_automaton expects some final states")
1771
1772        if not transition_triples:
1773            raise ValueError("add_automaton expects some transition triples")
1774
1775        ct = Constraint(self)
1776        model_ct = self.__model.constraints[ct.index]
1777        model_ct.automaton.vars.extend(
1778            [self.get_or_make_index(x) for x in transition_variables]
1779        )
1780        starting_state = cmh.assert_is_int64(starting_state)
1781        model_ct.automaton.starting_state = starting_state
1782        for v in final_states:
1783            v = cmh.assert_is_int64(v)
1784            model_ct.automaton.final_states.append(v)
1785        for t in transition_triples:
1786            if len(t) != 3:
1787                raise TypeError("Tuple " + str(t) + " has the wrong arity (!= 3)")
1788            tail = cmh.assert_is_int64(t[0])
1789            label = cmh.assert_is_int64(t[1])
1790            head = cmh.assert_is_int64(t[2])
1791            model_ct.automaton.transition_tail.append(tail)
1792            model_ct.automaton.transition_label.append(label)
1793            model_ct.automaton.transition_head.append(head)
1794        return ct
1795
1796    def add_inverse(
1797        self,
1798        variables: Sequence[VariableT],
1799        inverse_variables: Sequence[VariableT],
1800    ) -> Constraint:
1801        """Adds Inverse(variables, inverse_variables).
1802
1803        An inverse constraint enforces that if `variables[i]` is assigned a value
1804        `j`, then `inverse_variables[j]` is assigned a value `i`. And vice versa.
1805
1806        Args:
1807          variables: An array of integer variables.
1808          inverse_variables: An array of integer variables.
1809
1810        Returns:
1811          An instance of the `Constraint` class.
1812
1813        Raises:
1814          TypeError: if variables and inverse_variables have different lengths, or
1815              if they are empty.
1816        """
1817
1818        if not variables or not inverse_variables:
1819            raise TypeError("The Inverse constraint does not accept empty arrays")
1820        if len(variables) != len(inverse_variables):
1821            raise TypeError(
1822                "In the inverse constraint, the two array variables and"
1823                " inverse_variables must have the same length."
1824            )
1825        ct = Constraint(self)
1826        model_ct = self.__model.constraints[ct.index]
1827        model_ct.inverse.f_direct.extend([self.get_or_make_index(x) for x in variables])
1828        model_ct.inverse.f_inverse.extend(
1829            [self.get_or_make_index(x) for x in inverse_variables]
1830        )
1831        return ct
1832
1833    def add_reservoir_constraint(
1834        self,
1835        times: Iterable[LinearExprT],
1836        level_changes: Iterable[LinearExprT],
1837        min_level: int,
1838        max_level: int,
1839    ) -> Constraint:
1840        """Adds Reservoir(times, level_changes, min_level, max_level).
1841
1842        Maintains a reservoir level within bounds. The water level starts at 0, and
1843        at any time, it must be between min_level and max_level.
1844
1845        If the affine expression `times[i]` is assigned a value t, then the current
1846        level changes by `level_changes[i]`, which is constant, at time t.
1847
1848         Note that min level must be <= 0, and the max level must be >= 0. Please
1849         use fixed level_changes to simulate initial state.
1850
1851         Therefore, at any time:
1852             sum(level_changes[i] if times[i] <= t) in [min_level, max_level]
1853
1854        Args:
1855          times: A list of 1-var affine expressions (a * x + b) which specify the
1856            time of the filling or emptying the reservoir.
1857          level_changes: A list of integer values that specifies the amount of the
1858            emptying or filling. Currently, variable demands are not supported.
1859          min_level: At any time, the level of the reservoir must be greater or
1860            equal than the min level.
1861          max_level: At any time, the level of the reservoir must be less or equal
1862            than the max level.
1863
1864        Returns:
1865          An instance of the `Constraint` class.
1866
1867        Raises:
1868          ValueError: if max_level < min_level.
1869
1870          ValueError: if max_level < 0.
1871
1872          ValueError: if min_level > 0
1873        """
1874
1875        if max_level < min_level:
1876            raise ValueError("Reservoir constraint must have a max_level >= min_level")
1877
1878        if max_level < 0:
1879            raise ValueError("Reservoir constraint must have a max_level >= 0")
1880
1881        if min_level > 0:
1882            raise ValueError("Reservoir constraint must have a min_level <= 0")
1883
1884        ct = Constraint(self)
1885        model_ct = self.__model.constraints[ct.index]
1886        model_ct.reservoir.time_exprs.extend(
1887            [self.parse_linear_expression(x) for x in times]
1888        )
1889        model_ct.reservoir.level_changes.extend(
1890            [self.parse_linear_expression(x) for x in level_changes]
1891        )
1892        model_ct.reservoir.min_level = min_level
1893        model_ct.reservoir.max_level = max_level
1894        return ct
1895
1896    def add_reservoir_constraint_with_active(
1897        self,
1898        times: Iterable[LinearExprT],
1899        level_changes: Iterable[LinearExprT],
1900        actives: Iterable[LiteralT],
1901        min_level: int,
1902        max_level: int,
1903    ) -> Constraint:
1904        """Adds Reservoir(times, level_changes, actives, min_level, max_level).
1905
1906        Maintains a reservoir level within bounds. The water level starts at 0, and
1907        at any time, it must be between min_level and max_level.
1908
1909        If the variable `times[i]` is assigned a value t, and `actives[i]` is
1910        `True`, then the current level changes by `level_changes[i]`, which is
1911        constant,
1912        at time t.
1913
1914         Note that min level must be <= 0, and the max level must be >= 0. Please
1915         use fixed level_changes to simulate initial state.
1916
1917         Therefore, at any time:
1918             sum(level_changes[i] * actives[i] if times[i] <= t) in [min_level,
1919             max_level]
1920
1921
1922        The array of boolean variables 'actives', if defined, indicates which
1923        actions are actually performed.
1924
1925        Args:
1926          times: A list of 1-var affine expressions (a * x + b) which specify the
1927            time of the filling or emptying the reservoir.
1928          level_changes: A list of integer values that specifies the amount of the
1929            emptying or filling. Currently, variable demands are not supported.
1930          actives: a list of boolean variables. They indicates if the
1931            emptying/refilling events actually take place.
1932          min_level: At any time, the level of the reservoir must be greater or
1933            equal than the min level.
1934          max_level: At any time, the level of the reservoir must be less or equal
1935            than the max level.
1936
1937        Returns:
1938          An instance of the `Constraint` class.
1939
1940        Raises:
1941          ValueError: if max_level < min_level.
1942
1943          ValueError: if max_level < 0.
1944
1945          ValueError: if min_level > 0
1946        """
1947
1948        if max_level < min_level:
1949            raise ValueError("Reservoir constraint must have a max_level >= min_level")
1950
1951        if max_level < 0:
1952            raise ValueError("Reservoir constraint must have a max_level >= 0")
1953
1954        if min_level > 0:
1955            raise ValueError("Reservoir constraint must have a min_level <= 0")
1956
1957        ct = Constraint(self)
1958        model_ct = self.__model.constraints[ct.index]
1959        model_ct.reservoir.time_exprs.extend(
1960            [self.parse_linear_expression(x) for x in times]
1961        )
1962        model_ct.reservoir.level_changes.extend(
1963            [self.parse_linear_expression(x) for x in level_changes]
1964        )
1965        model_ct.reservoir.active_literals.extend(
1966            [self.get_or_make_boolean_index(x) for x in actives]
1967        )
1968        model_ct.reservoir.min_level = min_level
1969        model_ct.reservoir.max_level = max_level
1970        return ct
1971
1972    def add_map_domain(
1973        self, var: IntVar, bool_var_array: Iterable[IntVar], offset: IntegralT = 0
1974    ):
1975        """Adds `var == i + offset <=> bool_var_array[i] == true for all i`."""
1976
1977        for i, bool_var in enumerate(bool_var_array):
1978            b_index = bool_var.index
1979            var_index = var.index
1980            model_ct = self.__model.constraints.add()
1981            model_ct.linear.vars.append(var_index)
1982            model_ct.linear.coeffs.append(1)
1983            model_ct.linear.domain.extend([offset + i, offset + i])
1984            model_ct.enforcement_literal.append(b_index)
1985
1986            model_ct = self.__model.constraints.add()
1987            model_ct.linear.vars.append(var_index)
1988            model_ct.linear.coeffs.append(1)
1989            model_ct.enforcement_literal.append(-b_index - 1)
1990            if offset + i - 1 >= INT_MIN:
1991                model_ct.linear.domain.extend([INT_MIN, offset + i - 1])
1992            if offset + i + 1 <= INT_MAX:
1993                model_ct.linear.domain.extend([offset + i + 1, INT_MAX])
1994
1995    def add_implication(self, a: LiteralT, b: LiteralT) -> Constraint:
1996        """Adds `a => b` (`a` implies `b`)."""
1997        ct = Constraint(self)
1998        model_ct = self.__model.constraints[ct.index]
1999        model_ct.bool_or.literals.append(self.get_or_make_boolean_index(b))
2000        model_ct.enforcement_literal.append(self.get_or_make_boolean_index(a))
2001        return ct
2002
2003    @overload
2004    def add_bool_or(self, literals: Iterable[LiteralT]) -> Constraint:
2005        ...
2006
2007    @overload
2008    def add_bool_or(self, *literals: LiteralT) -> Constraint:
2009        ...
2010
2011    def add_bool_or(self, *literals):
2012        """Adds `Or(literals) == true`: sum(literals) >= 1."""
2013        ct = Constraint(self)
2014        model_ct = self.__model.constraints[ct.index]
2015        model_ct.bool_or.literals.extend(
2016            [
2017                self.get_or_make_boolean_index(x)
2018                for x in expand_generator_or_tuple(literals)
2019            ]
2020        )
2021        return ct
2022
2023    @overload
2024    def add_at_least_one(self, literals: Iterable[LiteralT]) -> Constraint:
2025        ...
2026
2027    @overload
2028    def add_at_least_one(self, *literals: LiteralT) -> Constraint:
2029        ...
2030
2031    def add_at_least_one(self, *literals):
2032        """Same as `add_bool_or`: `sum(literals) >= 1`."""
2033        return self.add_bool_or(*literals)
2034
2035    @overload
2036    def add_at_most_one(self, literals: Iterable[LiteralT]) -> Constraint:
2037        ...
2038
2039    @overload
2040    def add_at_most_one(self, *literals: LiteralT) -> Constraint:
2041        ...
2042
2043    def add_at_most_one(self, *literals):
2044        """Adds `AtMostOne(literals)`: `sum(literals) <= 1`."""
2045        ct = Constraint(self)
2046        model_ct = self.__model.constraints[ct.index]
2047        model_ct.at_most_one.literals.extend(
2048            [
2049                self.get_or_make_boolean_index(x)
2050                for x in expand_generator_or_tuple(literals)
2051            ]
2052        )
2053        return ct
2054
2055    @overload
2056    def add_exactly_one(self, literals: Iterable[LiteralT]) -> Constraint:
2057        ...
2058
2059    @overload
2060    def add_exactly_one(self, *literals: LiteralT) -> Constraint:
2061        ...
2062
2063    def add_exactly_one(self, *literals):
2064        """Adds `ExactlyOne(literals)`: `sum(literals) == 1`."""
2065        ct = Constraint(self)
2066        model_ct = self.__model.constraints[ct.index]
2067        model_ct.exactly_one.literals.extend(
2068            [
2069                self.get_or_make_boolean_index(x)
2070                for x in expand_generator_or_tuple(literals)
2071            ]
2072        )
2073        return ct
2074
2075    @overload
2076    def add_bool_and(self, literals: Iterable[LiteralT]) -> Constraint:
2077        ...
2078
2079    @overload
2080    def add_bool_and(self, *literals: LiteralT) -> Constraint:
2081        ...
2082
2083    def add_bool_and(self, *literals):
2084        """Adds `And(literals) == true`."""
2085        ct = Constraint(self)
2086        model_ct = self.__model.constraints[ct.index]
2087        model_ct.bool_and.literals.extend(
2088            [
2089                self.get_or_make_boolean_index(x)
2090                for x in expand_generator_or_tuple(literals)
2091            ]
2092        )
2093        return ct
2094
2095    @overload
2096    def add_bool_xor(self, literals: Iterable[LiteralT]) -> Constraint:
2097        ...
2098
2099    @overload
2100    def add_bool_xor(self, *literals: LiteralT) -> Constraint:
2101        ...
2102
2103    def add_bool_xor(self, *literals):
2104        """Adds `XOr(literals) == true`.
2105
2106        In contrast to add_bool_or and add_bool_and, it does not support
2107            .only_enforce_if().
2108
2109        Args:
2110          *literals: the list of literals in the constraint.
2111
2112        Returns:
2113          An `Constraint` object.
2114        """
2115        ct = Constraint(self)
2116        model_ct = self.__model.constraints[ct.index]
2117        model_ct.bool_xor.literals.extend(
2118            [
2119                self.get_or_make_boolean_index(x)
2120                for x in expand_generator_or_tuple(literals)
2121            ]
2122        )
2123        return ct
2124
2125    def add_min_equality(
2126        self, target: LinearExprT, exprs: Iterable[LinearExprT]
2127    ) -> Constraint:
2128        """Adds `target == Min(exprs)`."""
2129        ct = Constraint(self)
2130        model_ct = self.__model.constraints[ct.index]
2131        model_ct.lin_max.exprs.extend(
2132            [self.parse_linear_expression(x, True) for x in exprs]
2133        )
2134        model_ct.lin_max.target.CopyFrom(self.parse_linear_expression(target, True))
2135        return ct
2136
2137    def add_max_equality(
2138        self, target: LinearExprT, exprs: Iterable[LinearExprT]
2139    ) -> Constraint:
2140        """Adds `target == Max(exprs)`."""
2141        ct = Constraint(self)
2142        model_ct = self.__model.constraints[ct.index]
2143        model_ct.lin_max.exprs.extend([self.parse_linear_expression(x) for x in exprs])
2144        model_ct.lin_max.target.CopyFrom(self.parse_linear_expression(target))
2145        return ct
2146
2147    def add_division_equality(
2148        self, target: LinearExprT, num: LinearExprT, denom: LinearExprT
2149    ) -> Constraint:
2150        """Adds `target == num // denom` (integer division rounded towards 0)."""
2151        ct = Constraint(self)
2152        model_ct = self.__model.constraints[ct.index]
2153        model_ct.int_div.exprs.append(self.parse_linear_expression(num))
2154        model_ct.int_div.exprs.append(self.parse_linear_expression(denom))
2155        model_ct.int_div.target.CopyFrom(self.parse_linear_expression(target))
2156        return ct
2157
2158    def add_abs_equality(self, target: LinearExprT, expr: LinearExprT) -> Constraint:
2159        """Adds `target == Abs(expr)`."""
2160        ct = Constraint(self)
2161        model_ct = self.__model.constraints[ct.index]
2162        model_ct.lin_max.exprs.append(self.parse_linear_expression(expr))
2163        model_ct.lin_max.exprs.append(self.parse_linear_expression(expr, True))
2164        model_ct.lin_max.target.CopyFrom(self.parse_linear_expression(target))
2165        return ct
2166
2167    def add_modulo_equality(
2168        self, target: LinearExprT, expr: LinearExprT, mod: LinearExprT
2169    ) -> Constraint:
2170        """Adds `target = expr % mod`."""
2171        ct = Constraint(self)
2172        model_ct = self.__model.constraints[ct.index]
2173        model_ct.int_mod.exprs.append(self.parse_linear_expression(expr))
2174        model_ct.int_mod.exprs.append(self.parse_linear_expression(mod))
2175        model_ct.int_mod.target.CopyFrom(self.parse_linear_expression(target))
2176        return ct
2177
2178    def add_multiplication_equality(
2179        self,
2180        target: LinearExprT,
2181        *expressions: Union[Iterable[LinearExprT], LinearExprT],
2182    ) -> Constraint:
2183        """Adds `target == expressions[0] * .. * expressions[n]`."""
2184        ct = Constraint(self)
2185        model_ct = self.__model.constraints[ct.index]
2186        model_ct.int_prod.exprs.extend(
2187            [
2188                self.parse_linear_expression(expr)
2189                for expr in expand_generator_or_tuple(expressions)
2190            ]
2191        )
2192        model_ct.int_prod.target.CopyFrom(self.parse_linear_expression(target))
2193        return ct
2194
2195    # Scheduling support
2196
2197    def new_interval_var(
2198        self, start: LinearExprT, size: LinearExprT, end: LinearExprT, name: str
2199    ) -> IntervalVar:
2200        """Creates an interval variable from start, size, and end.
2201
2202        An interval variable is a constraint, that is itself used in other
2203        constraints like NoOverlap.
2204
2205        Internally, it ensures that `start + size == end`.
2206
2207        Args:
2208          start: The start of the interval. It must be of the form a * var + b.
2209          size: The size of the interval. It must be of the form a * var + b.
2210          end: The end of the interval. It must be of the form a * var + b.
2211          name: The name of the interval variable.
2212
2213        Returns:
2214          An `IntervalVar` object.
2215        """
2216
2217        lin = self.add(start + size == end)
2218        if name:
2219            lin.with_name("lin_" + name)
2220
2221        start_expr = self.parse_linear_expression(start)
2222        size_expr = self.parse_linear_expression(size)
2223        end_expr = self.parse_linear_expression(end)
2224        if len(start_expr.vars) > 1:
2225            raise TypeError(
2226                "cp_model.new_interval_var: start must be 1-var affine or constant."
2227            )
2228        if len(size_expr.vars) > 1:
2229            raise TypeError(
2230                "cp_model.new_interval_var: size must be 1-var affine or constant."
2231            )
2232        if len(end_expr.vars) > 1:
2233            raise TypeError(
2234                "cp_model.new_interval_var: end must be 1-var affine or constant."
2235            )
2236        return IntervalVar(self.__model, start_expr, size_expr, end_expr, None, name)
2237
2238    def new_interval_var_series(
2239        self,
2240        name: str,
2241        index: pd.Index,
2242        starts: Union[LinearExprT, pd.Series],
2243        sizes: Union[LinearExprT, pd.Series],
2244        ends: Union[LinearExprT, pd.Series],
2245    ) -> pd.Series:
2246        """Creates a series of interval variables with the given name.
2247
2248        Args:
2249          name (str): Required. The name of the variable set.
2250          index (pd.Index): Required. The index to use for the variable set.
2251          starts (Union[LinearExprT, pd.Series]): The start of each interval in the
2252            set. If a `pd.Series` is passed in, it will be based on the
2253            corresponding values of the pd.Series.
2254          sizes (Union[LinearExprT, pd.Series]): The size of each interval in the
2255            set. If a `pd.Series` is passed in, it will be based on the
2256            corresponding values of the pd.Series.
2257          ends (Union[LinearExprT, pd.Series]): The ends of each interval in the
2258            set. If a `pd.Series` is passed in, it will be based on the
2259            corresponding values of the pd.Series.
2260
2261        Returns:
2262          pd.Series: The interval variable set indexed by its corresponding
2263          dimensions.
2264
2265        Raises:
2266          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
2267          ValueError: if the `name` is not a valid identifier or already exists.
2268          ValueError: if the all the indexes do not match.
2269        """
2270        if not isinstance(index, pd.Index):
2271            raise TypeError("Non-index object is used as index")
2272        if not name.isidentifier():
2273            raise ValueError("name={} is not a valid identifier".format(name))
2274
2275        starts = _convert_to_linear_expr_series_and_validate_index(starts, index)
2276        sizes = _convert_to_linear_expr_series_and_validate_index(sizes, index)
2277        ends = _convert_to_linear_expr_series_and_validate_index(ends, index)
2278        interval_array = []
2279        for i in index:
2280            interval_array.append(
2281                self.new_interval_var(
2282                    start=starts[i],
2283                    size=sizes[i],
2284                    end=ends[i],
2285                    name=f"{name}[{i}]",
2286                )
2287            )
2288        return pd.Series(index=index, data=interval_array)
2289
2290    def new_fixed_size_interval_var(
2291        self, start: LinearExprT, size: IntegralT, name: str
2292    ) -> IntervalVar:
2293        """Creates an interval variable from start, and a fixed size.
2294
2295        An interval variable is a constraint, that is itself used in other
2296        constraints like NoOverlap.
2297
2298        Args:
2299          start: The start of the interval. It must be of the form a * var + b.
2300          size: The size of the interval. It must be an integer value.
2301          name: The name of the interval variable.
2302
2303        Returns:
2304          An `IntervalVar` object.
2305        """
2306        size = cmh.assert_is_int64(size)
2307        start_expr = self.parse_linear_expression(start)
2308        size_expr = self.parse_linear_expression(size)
2309        end_expr = self.parse_linear_expression(start + size)
2310        if len(start_expr.vars) > 1:
2311            raise TypeError(
2312                "cp_model.new_interval_var: start must be affine or constant."
2313            )
2314        return IntervalVar(self.__model, start_expr, size_expr, end_expr, None, name)
2315
2316    def new_fixed_size_interval_var_series(
2317        self,
2318        name: str,
2319        index: pd.Index,
2320        starts: Union[LinearExprT, pd.Series],
2321        sizes: Union[IntegralT, pd.Series],
2322    ) -> pd.Series:
2323        """Creates a series of interval variables with the given name.
2324
2325        Args:
2326          name (str): Required. The name of the variable set.
2327          index (pd.Index): Required. The index to use for the variable set.
2328          starts (Union[LinearExprT, pd.Series]): The start of each interval in the
2329            set. If a `pd.Series` is passed in, it will be based on the
2330            corresponding values of the pd.Series.
2331          sizes (Union[IntegralT, pd.Series]): The fixed size of each interval in
2332            the set. If a `pd.Series` is passed in, it will be based on the
2333            corresponding values of the pd.Series.
2334
2335        Returns:
2336          pd.Series: The interval variable set indexed by its corresponding
2337          dimensions.
2338
2339        Raises:
2340          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
2341          ValueError: if the `name` is not a valid identifier or already exists.
2342          ValueError: if the all the indexes do not match.
2343        """
2344        if not isinstance(index, pd.Index):
2345            raise TypeError("Non-index object is used as index")
2346        if not name.isidentifier():
2347            raise ValueError("name={} is not a valid identifier".format(name))
2348
2349        starts = _convert_to_linear_expr_series_and_validate_index(starts, index)
2350        sizes = _convert_to_integral_series_and_validate_index(sizes, index)
2351        interval_array = []
2352        for i in index:
2353            interval_array.append(
2354                self.new_fixed_size_interval_var(
2355                    start=starts[i],
2356                    size=sizes[i],
2357                    name=f"{name}[{i}]",
2358                )
2359            )
2360        return pd.Series(index=index, data=interval_array)
2361
2362    def new_optional_interval_var(
2363        self,
2364        start: LinearExprT,
2365        size: LinearExprT,
2366        end: LinearExprT,
2367        is_present: LiteralT,
2368        name: str,
2369    ) -> IntervalVar:
2370        """Creates an optional interval var from start, size, end, and is_present.
2371
2372        An optional interval variable is a constraint, that is itself used in other
2373        constraints like NoOverlap. This constraint is protected by a presence
2374        literal that indicates if it is active or not.
2375
2376        Internally, it ensures that `is_present` implies `start + size ==
2377        end`.
2378
2379        Args:
2380          start: The start of the interval. It must be of the form a * var + b.
2381          size: The size of the interval. It must be of the form a * var + b.
2382          end: The end of the interval. It must be of the form a * var + b.
2383          is_present: A literal that indicates if the interval is active or not. A
2384            inactive interval is simply ignored by all constraints.
2385          name: The name of the interval variable.
2386
2387        Returns:
2388          An `IntervalVar` object.
2389        """
2390
2391        # add the linear constraint.
2392        lin = self.add(start + size == end).only_enforce_if(is_present)
2393        if name:
2394            lin.with_name("lin_opt_" + name)
2395
2396        # Creates the IntervalConstraintProto object.
2397        is_present_index = self.get_or_make_boolean_index(is_present)
2398        start_expr = self.parse_linear_expression(start)
2399        size_expr = self.parse_linear_expression(size)
2400        end_expr = self.parse_linear_expression(end)
2401        if len(start_expr.vars) > 1:
2402            raise TypeError(
2403                "cp_model.new_interval_var: start must be affine or constant."
2404            )
2405        if len(size_expr.vars) > 1:
2406            raise TypeError(
2407                "cp_model.new_interval_var: size must be affine or constant."
2408            )
2409        if len(end_expr.vars) > 1:
2410            raise TypeError(
2411                "cp_model.new_interval_var: end must be affine or constant."
2412            )
2413        return IntervalVar(
2414            self.__model, start_expr, size_expr, end_expr, is_present_index, name
2415        )
2416
2417    def new_optional_interval_var_series(
2418        self,
2419        name: str,
2420        index: pd.Index,
2421        starts: Union[LinearExprT, pd.Series],
2422        sizes: Union[LinearExprT, pd.Series],
2423        ends: Union[LinearExprT, pd.Series],
2424        are_present: Union[LiteralT, pd.Series],
2425    ) -> pd.Series:
2426        """Creates a series of interval variables with the given name.
2427
2428        Args:
2429          name (str): Required. The name of the variable set.
2430          index (pd.Index): Required. The index to use for the variable set.
2431          starts (Union[LinearExprT, pd.Series]): The start of each interval in the
2432            set. If a `pd.Series` is passed in, it will be based on the
2433            corresponding values of the pd.Series.
2434          sizes (Union[LinearExprT, pd.Series]): The size of each interval in the
2435            set. If a `pd.Series` is passed in, it will be based on the
2436            corresponding values of the pd.Series.
2437          ends (Union[LinearExprT, pd.Series]): The ends of each interval in the
2438            set. If a `pd.Series` is passed in, it will be based on the
2439            corresponding values of the pd.Series.
2440          are_present (Union[LiteralT, pd.Series]): The performed literal of each
2441            interval in the set. If a `pd.Series` is passed in, it will be based on
2442            the corresponding values of the pd.Series.
2443
2444        Returns:
2445          pd.Series: The interval variable set indexed by its corresponding
2446          dimensions.
2447
2448        Raises:
2449          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
2450          ValueError: if the `name` is not a valid identifier or already exists.
2451          ValueError: if the all the indexes do not match.
2452        """
2453        if not isinstance(index, pd.Index):
2454            raise TypeError("Non-index object is used as index")
2455        if not name.isidentifier():
2456            raise ValueError("name={} is not a valid identifier".format(name))
2457
2458        starts = _convert_to_linear_expr_series_and_validate_index(starts, index)
2459        sizes = _convert_to_linear_expr_series_and_validate_index(sizes, index)
2460        ends = _convert_to_linear_expr_series_and_validate_index(ends, index)
2461        are_present = _convert_to_literal_series_and_validate_index(are_present, index)
2462
2463        interval_array = []
2464        for i in index:
2465            interval_array.append(
2466                self.new_optional_interval_var(
2467                    start=starts[i],
2468                    size=sizes[i],
2469                    end=ends[i],
2470                    is_present=are_present[i],
2471                    name=f"{name}[{i}]",
2472                )
2473            )
2474        return pd.Series(index=index, data=interval_array)
2475
2476    def new_optional_fixed_size_interval_var(
2477        self,
2478        start: LinearExprT,
2479        size: IntegralT,
2480        is_present: LiteralT,
2481        name: str,
2482    ) -> IntervalVar:
2483        """Creates an interval variable from start, and a fixed size.
2484
2485        An interval variable is a constraint, that is itself used in other
2486        constraints like NoOverlap.
2487
2488        Args:
2489          start: The start of the interval. It must be of the form a * var + b.
2490          size: The size of the interval. It must be an integer value.
2491          is_present: A literal that indicates if the interval is active or not. A
2492            inactive interval is simply ignored by all constraints.
2493          name: The name of the interval variable.
2494
2495        Returns:
2496          An `IntervalVar` object.
2497        """
2498        size = cmh.assert_is_int64(size)
2499        start_expr = self.parse_linear_expression(start)
2500        size_expr = self.parse_linear_expression(size)
2501        end_expr = self.parse_linear_expression(start + size)
2502        if len(start_expr.vars) > 1:
2503            raise TypeError(
2504                "cp_model.new_interval_var: start must be affine or constant."
2505            )
2506        is_present_index = self.get_or_make_boolean_index(is_present)
2507        return IntervalVar(
2508            self.__model,
2509            start_expr,
2510            size_expr,
2511            end_expr,
2512            is_present_index,
2513            name,
2514        )
2515
2516    def new_optional_fixed_size_interval_var_series(
2517        self,
2518        name: str,
2519        index: pd.Index,
2520        starts: Union[LinearExprT, pd.Series],
2521        sizes: Union[IntegralT, pd.Series],
2522        are_present: Union[LiteralT, pd.Series],
2523    ) -> pd.Series:
2524        """Creates a series of interval variables with the given name.
2525
2526        Args:
2527          name (str): Required. The name of the variable set.
2528          index (pd.Index): Required. The index to use for the variable set.
2529          starts (Union[LinearExprT, pd.Series]): The start of each interval in the
2530            set. If a `pd.Series` is passed in, it will be based on the
2531            corresponding values of the pd.Series.
2532          sizes (Union[IntegralT, pd.Series]): The fixed size of each interval in
2533            the set. If a `pd.Series` is passed in, it will be based on the
2534            corresponding values of the pd.Series.
2535          are_present (Union[LiteralT, pd.Series]): The performed literal of each
2536            interval in the set. If a `pd.Series` is passed in, it will be based on
2537            the corresponding values of the pd.Series.
2538
2539        Returns:
2540          pd.Series: The interval variable set indexed by its corresponding
2541          dimensions.
2542
2543        Raises:
2544          TypeError: if the `index` is invalid (e.g. a `DataFrame`).
2545          ValueError: if the `name` is not a valid identifier or already exists.
2546          ValueError: if the all the indexes do not match.
2547        """
2548        if not isinstance(index, pd.Index):
2549            raise TypeError("Non-index object is used as index")
2550        if not name.isidentifier():
2551            raise ValueError("name={} is not a valid identifier".format(name))
2552
2553        starts = _convert_to_linear_expr_series_and_validate_index(starts, index)
2554        sizes = _convert_to_integral_series_and_validate_index(sizes, index)
2555        are_present = _convert_to_literal_series_and_validate_index(are_present, index)
2556        interval_array = []
2557        for i in index:
2558            interval_array.append(
2559                self.new_optional_fixed_size_interval_var(
2560                    start=starts[i],
2561                    size=sizes[i],
2562                    is_present=are_present[i],
2563                    name=f"{name}[{i}]",
2564                )
2565            )
2566        return pd.Series(index=index, data=interval_array)
2567
2568    def add_no_overlap(self, interval_vars: Iterable[IntervalVar]) -> Constraint:
2569        """Adds NoOverlap(interval_vars).
2570
2571        A NoOverlap constraint ensures that all present intervals do not overlap
2572        in time.
2573
2574        Args:
2575          interval_vars: The list of interval variables to constrain.
2576
2577        Returns:
2578          An instance of the `Constraint` class.
2579        """
2580        ct = Constraint(self)
2581        model_ct = self.__model.constraints[ct.index]
2582        model_ct.no_overlap.intervals.extend(
2583            [self.get_interval_index(x) for x in interval_vars]
2584        )
2585        return ct
2586
2587    def add_no_overlap_2d(
2588        self,
2589        x_intervals: Iterable[IntervalVar],
2590        y_intervals: Iterable[IntervalVar],
2591    ) -> Constraint:
2592        """Adds NoOverlap2D(x_intervals, y_intervals).
2593
2594        A NoOverlap2D constraint ensures that all present rectangles do not overlap
2595        on a plane. Each rectangle is aligned with the X and Y axis, and is defined
2596        by two intervals which represent its projection onto the X and Y axis.
2597
2598        Furthermore, one box is optional if at least one of the x or y interval is
2599        optional.
2600
2601        Args:
2602          x_intervals: The X coordinates of the rectangles.
2603          y_intervals: The Y coordinates of the rectangles.
2604
2605        Returns:
2606          An instance of the `Constraint` class.
2607        """
2608        ct = Constraint(self)
2609        model_ct = self.__model.constraints[ct.index]
2610        model_ct.no_overlap_2d.x_intervals.extend(
2611            [self.get_interval_index(x) for x in x_intervals]
2612        )
2613        model_ct.no_overlap_2d.y_intervals.extend(
2614            [self.get_interval_index(x) for x in y_intervals]
2615        )
2616        return ct
2617
2618    def add_cumulative(
2619        self,
2620        intervals: Iterable[IntervalVar],
2621        demands: Iterable[LinearExprT],
2622        capacity: LinearExprT,
2623    ) -> Constraint:
2624        """Adds Cumulative(intervals, demands, capacity).
2625
2626        This constraint enforces that:
2627
2628            for all t:
2629              sum(demands[i]
2630                if (start(intervals[i]) <= t < end(intervals[i])) and
2631                (intervals[i] is present)) <= capacity
2632
2633        Args:
2634          intervals: The list of intervals.
2635          demands: The list of demands for each interval. Each demand must be >= 0.
2636            Each demand can be a 1-var affine expression (a * x + b).
2637          capacity: The maximum capacity of the cumulative constraint. It can be a
2638            1-var affine expression (a * x + b).
2639
2640        Returns:
2641          An instance of the `Constraint` class.
2642        """
2643        cumulative = Constraint(self)
2644        model_ct = self.__model.constraints[cumulative.index]
2645        model_ct.cumulative.intervals.extend(
2646            [self.get_interval_index(x) for x in intervals]
2647        )
2648        for d in demands:
2649            model_ct.cumulative.demands.append(self.parse_linear_expression(d))
2650        model_ct.cumulative.capacity.CopyFrom(self.parse_linear_expression(capacity))
2651        return cumulative
2652
2653    # Support for model cloning.
2654    def clone(self) -> "CpModel":
2655        """Reset the model, and creates a new one from a CpModelProto instance."""
2656        clone = CpModel()
2657        clone.proto.CopyFrom(self.proto)
2658        clone.rebuild_constant_map()
2659        return clone
2660
2661    def rebuild_constant_map(self):
2662        """Internal method used during model cloning."""
2663        for i, var in enumerate(self.__model.variables):
2664            if len(var.domain) == 2 and var.domain[0] == var.domain[1]:
2665                self.__constant_map[var.domain[0]] = i
2666
2667    def get_bool_var_from_proto_index(self, index: int) -> IntVar:
2668        """Returns an already created Boolean variable from its index."""
2669        if index < 0 or index >= len(self.__model.variables):
2670            raise ValueError(
2671                f"get_bool_var_from_proto_index: out of bound index {index}"
2672            )
2673        var = self.__model.variables[index]
2674        if len(var.domain) != 2 or var.domain[0] < 0 or var.domain[1] > 1:
2675            raise ValueError(
2676                f"get_bool_var_from_proto_index: index {index} does not reference"
2677                + " a Boolean variable"
2678            )
2679
2680        return IntVar(self.__model, index, None)
2681
2682    def get_int_var_from_proto_index(self, index: int) -> IntVar:
2683        """Returns an already created integer variable from its index."""
2684        if index < 0 or index >= len(self.__model.variables):
2685            raise ValueError(
2686                f"get_int_var_from_proto_index: out of bound index {index}"
2687            )
2688        return IntVar(self.__model, index, None)
2689
2690    def get_interval_var_from_proto_index(self, index: int) -> IntervalVar:
2691        """Returns an already created interval variable from its index."""
2692        if index < 0 or index >= len(self.__model.constraints):
2693            raise ValueError(
2694                f"get_interval_var_from_proto_index: out of bound index {index}"
2695            )
2696        ct = self.__model.constraints[index]
2697        if not ct.HasField("interval"):
2698            raise ValueError(
2699                f"get_interval_var_from_proto_index: index {index} does not"
2700                " reference an" + " interval variable"
2701            )
2702
2703        return IntervalVar(self.__model, index, None, None, None, None)
2704
2705    # Helpers.
2706
2707    def __str__(self):
2708        return str(self.__model)
2709
2710    @property
2711    def proto(self) -> cp_model_pb2.CpModelProto:
2712        """Returns the underlying CpModelProto."""
2713        return self.__model
2714
2715    def negated(self, index: int) -> int:
2716        return -index - 1
2717
2718    def get_or_make_index(self, arg: VariableT) -> int:
2719        """Returns the index of a variable, its negation, or a number."""
2720        if isinstance(arg, IntVar):
2721            return arg.index
2722        if (
2723            isinstance(arg, _ProductCst)
2724            and isinstance(arg.expression(), IntVar)
2725            and arg.coefficient() == -1
2726        ):
2727            return -arg.expression().index - 1
2728        if isinstance(arg, numbers.Integral):
2729            arg = cmh.assert_is_int64(arg)
2730            return self.get_or_make_index_from_constant(arg)
2731        raise TypeError("NotSupported: model.get_or_make_index(" + str(arg) + ")")
2732
2733    def get_or_make_boolean_index(self, arg: LiteralT) -> int:
2734        """Returns an index from a boolean expression."""
2735        if isinstance(arg, IntVar):
2736            self.assert_is_boolean_variable(arg)
2737            return arg.index
2738        if isinstance(arg, _NotBooleanVariable):
2739            self.assert_is_boolean_variable(arg.negated())
2740            return arg.index
2741        if isinstance(arg, numbers.Integral):
2742            arg = cmh.assert_is_zero_or_one(arg)
2743            return self.get_or_make_index_from_constant(arg)
2744        if cmh.is_boolean(arg):
2745            return self.get_or_make_index_from_constant(int(arg))
2746        raise TypeError(f"not supported: model.get_or_make_boolean_index({arg})")
2747
2748    def get_interval_index(self, arg: IntervalVar) -> int:
2749        if not isinstance(arg, IntervalVar):
2750            raise TypeError("NotSupported: model.get_interval_index(%s)" % arg)
2751        return arg.index
2752
2753    def get_or_make_index_from_constant(self, value: IntegralT) -> int:
2754        if value in self.__constant_map:
2755            return self.__constant_map[value]
2756        index = len(self.__model.variables)
2757        self.__model.variables.add(domain=[value, value])
2758        self.__constant_map[value] = index
2759        return index
2760
2761    def var_index_to_var_proto(
2762        self, var_index: int
2763    ) -> cp_model_pb2.IntegerVariableProto:
2764        if var_index >= 0:
2765            return self.__model.variables[var_index]
2766        else:
2767            return self.__model.variables[-var_index - 1]
2768
2769    def parse_linear_expression(
2770        self, linear_expr: LinearExprT, negate: bool = False
2771    ) -> cp_model_pb2.LinearExpressionProto:
2772        """Returns a LinearExpressionProto built from a LinearExpr instance."""
2773        result: cp_model_pb2.LinearExpressionProto = (
2774            cp_model_pb2.LinearExpressionProto()
2775        )
2776        mult = -1 if negate else 1
2777        if isinstance(linear_expr, numbers.Integral):
2778            result.offset = int(linear_expr) * mult
2779            return result
2780
2781        if isinstance(linear_expr, IntVar):
2782            result.vars.append(self.get_or_make_index(linear_expr))
2783            result.coeffs.append(mult)
2784            return result
2785
2786        coeffs_map, constant = cast(LinearExpr, linear_expr).get_integer_var_value_map()
2787        result.offset = constant * mult
2788        for t in coeffs_map.items():
2789            if not isinstance(t[0], IntVar):
2790                raise TypeError("Wrong argument" + str(t))
2791            c = cmh.assert_is_int64(t[1])
2792            result.vars.append(t[0].index)
2793            result.coeffs.append(c * mult)
2794        return result
2795
2796    def _set_objective(self, obj: ObjLinearExprT, minimize: bool):
2797        """Sets the objective of the model."""
2798        self.clear_objective()
2799        if isinstance(obj, IntVar):
2800            self.__model.objective.coeffs.append(1)
2801            self.__model.objective.offset = 0
2802            if minimize:
2803                self.__model.objective.vars.append(obj.index)
2804                self.__model.objective.scaling_factor = 1
2805            else:
2806                self.__model.objective.vars.append(self.negated(obj.index))
2807                self.__model.objective.scaling_factor = -1
2808        elif isinstance(obj, LinearExpr):
2809            coeffs_map, constant, is_integer = obj.get_float_var_value_map()
2810            if is_integer:
2811                if minimize:
2812                    self.__model.objective.scaling_factor = 1
2813                    self.__model.objective.offset = constant
2814                else:
2815                    self.__model.objective.scaling_factor = -1
2816                    self.__model.objective.offset = -constant
2817                for v, c in coeffs_map.items():
2818                    self.__model.objective.coeffs.append(c)
2819                    if minimize:
2820                        self.__model.objective.vars.append(v.index)
2821                    else:
2822                        self.__model.objective.vars.append(self.negated(v.index))
2823            else:
2824                self.__model.floating_point_objective.maximize = not minimize
2825                self.__model.floating_point_objective.offset = constant
2826                for v, c in coeffs_map.items():
2827                    self.__model.floating_point_objective.coeffs.append(c)
2828                    self.__model.floating_point_objective.vars.append(v.index)
2829        elif isinstance(obj, numbers.Integral):
2830            self.__model.objective.offset = int(obj)
2831            self.__model.objective.scaling_factor = 1
2832        else:
2833            raise TypeError("TypeError: " + str(obj) + " is not a valid objective")
2834
2835    def minimize(self, obj: ObjLinearExprT):
2836        """Sets the objective of the model to minimize(obj)."""
2837        self._set_objective(obj, minimize=True)
2838
2839    def maximize(self, obj: ObjLinearExprT):
2840        """Sets the objective of the model to maximize(obj)."""
2841        self._set_objective(obj, minimize=False)
2842
2843    def has_objective(self) -> bool:
2844        return self.__model.HasField("objective") or self.__model.HasField(
2845            "floating_point_objective"
2846        )
2847
2848    def clear_objective(self):
2849        self.__model.ClearField("objective")
2850        self.__model.ClearField("floating_point_objective")
2851
2852    def add_decision_strategy(
2853        self,
2854        variables: Sequence[IntVar],
2855        var_strategy: cp_model_pb2.DecisionStrategyProto.VariableSelectionStrategy,
2856        domain_strategy: cp_model_pb2.DecisionStrategyProto.DomainReductionStrategy,
2857    ) -> None:
2858        """Adds a search strategy to the model.
2859
2860        Args:
2861          variables: a list of variables this strategy will assign.
2862          var_strategy: heuristic to choose the next variable to assign.
2863          domain_strategy: heuristic to reduce the domain of the selected variable.
2864            Currently, this is advanced code: the union of all strategies added to
2865            the model must be complete, i.e. instantiates all variables. Otherwise,
2866            solve() will fail.
2867        """
2868
2869        strategy = self.__model.search_strategy.add()
2870        for v in variables:
2871            expr = strategy.exprs.add()
2872            if v.index >= 0:
2873                expr.vars.append(v.index)
2874                expr.coeffs.append(1)
2875            else:
2876                expr.vars.append(self.negated(v.index))
2877                expr.coeffs.append(-1)
2878                expr.offset = 1
2879
2880        strategy.variable_selection_strategy = var_strategy
2881        strategy.domain_reduction_strategy = domain_strategy
2882
2883    def model_stats(self) -> str:
2884        """Returns a string containing some model statistics."""
2885        return swig_helper.CpSatHelper.model_stats(self.__model)
2886
2887    def validate(self) -> str:
2888        """Returns a string indicating that the model is invalid."""
2889        return swig_helper.CpSatHelper.validate_model(self.__model)
2890
2891    def export_to_file(self, file: str) -> bool:
2892        """Write the model as a protocol buffer to 'file'.
2893
2894        Args:
2895          file: file to write the model to. If the filename ends with 'txt', the
2896            model will be written as a text file, otherwise, the binary format will
2897            be used.
2898
2899        Returns:
2900          True if the model was correctly written.
2901        """
2902        return swig_helper.CpSatHelper.write_model_to_file(self.__model, file)
2903
2904    def add_hint(self, var: IntVar, value: int) -> None:
2905        """Adds 'var == value' as a hint to the solver."""
2906        self.__model.solution_hint.vars.append(self.get_or_make_index(var))
2907        self.__model.solution_hint.values.append(value)
2908
2909    def clear_hints(self):
2910        """Removes any solution hint from the model."""
2911        self.__model.ClearField("solution_hint")
2912
2913    def add_assumption(self, lit: LiteralT) -> None:
2914        """Adds the literal to the model as assumptions."""
2915        self.__model.assumptions.append(self.get_or_make_boolean_index(lit))
2916
2917    def add_assumptions(self, literals: Iterable[LiteralT]) -> None:
2918        """Adds the literals to the model as assumptions."""
2919        for lit in literals:
2920            self.add_assumption(lit)
2921
2922    def clear_assumptions(self) -> None:
2923        """Removes all assumptions from the model."""
2924        self.__model.ClearField("assumptions")
2925
2926    # Helpers.
2927    def assert_is_boolean_variable(self, x: LiteralT) -> None:
2928        if isinstance(x, IntVar):
2929            var = self.__model.variables[x.index]
2930            if len(var.domain) != 2 or var.domain[0] < 0 or var.domain[1] > 1:
2931                raise TypeError("TypeError: " + str(x) + " is not a boolean variable")
2932        elif not isinstance(x, _NotBooleanVariable):
2933            raise TypeError("TypeError: " + str(x) + " is not a boolean variable")
2934
2935    # Compatibility with pre PEP8
2936    # pylint: disable=invalid-name
2937
2938    def Name(self) -> str:
2939        return self.name
2940
2941    def SetName(self, name: str) -> None:
2942        self.name = name
2943
2944    def Proto(self) -> cp_model_pb2.CpModelProto:
2945        return self.proto
2946
2947    NewIntVar = new_int_var
2948    NewIntVarFromDomain = new_int_var_from_domain
2949    NewBoolVar = new_bool_var
2950    NewConstant = new_constant
2951    NewIntVarSeries = new_int_var_series
2952    NewBoolVarSeries = new_bool_var_series
2953    AddLinearConstraint = add_linear_constraint
2954    AddLinearExpressionInDomain = add_linear_expression_in_domain
2955    Add = add
2956    AddAllDifferent = add_all_different
2957    AddElement = add_element
2958    AddCircuit = add_circuit
2959    AddMultipleCircuit = add_multiple_circuit
2960    AddAllowedAssignments = add_allowed_assignments
2961    AddForbiddenAssignments = add_forbidden_assignments
2962    AddAutomaton = add_automaton
2963    AddInverse = add_inverse
2964    AddReservoirConstraint = add_reservoir_constraint
2965    AddImplication = add_implication
2966    AddBoolOr = add_bool_or
2967    AddAtLeastOne = add_at_least_one
2968    AddAtMostOne = add_at_most_one
2969    AddExactlyOne = add_exactly_one
2970    AddBoolAnd = add_bool_and
2971    AddBoolXOr = add_bool_xor
2972    AddMinEquality = add_min_equality
2973    AddMaxEquality = add_max_equality
2974    AddDivisionEquality = add_division_equality
2975    AddAbsEquality = add_abs_equality
2976    AddModuloEquality = add_modulo_equality
2977    AddMultiplicationEquality = add_multiplication_equality
2978    NewIntervalVar = new_interval_var
2979    NewIntervalVarSeries = new_interval_var_series
2980    NewFixedSizedIntervalVar = new_fixed_size_interval_var
2981    NewOptionalIntervalVar = new_optional_interval_var
2982    NewOptionalIntervalVarSeries = new_optional_interval_var_series
2983    NewOptionalFixedSizedIntervalVar = new_optional_fixed_size_interval_var
2984    NewOptionalFixedSizedIntervalVarSeries = new_optional_fixed_size_interval_var_series
2985    AddNoOverlap = add_no_overlap
2986    AddNoOverlap2D = add_no_overlap_2d
2987    AddCumulative = add_cumulative
2988    Clone = clone
2989    GetBoolVarFromProtoIndex = get_bool_var_from_proto_index
2990    GetIntVarFromProtoIndex = get_int_var_from_proto_index
2991    GetIntervalVarFromProtoIndex = get_interval_var_from_proto_index
2992    Minimize = minimize
2993    Maximize = maximize
2994    HasObjective = has_objective
2995    ClearObjective = clear_objective
2996    AddDecisionStrategy = add_decision_strategy
2997    ModelStats = model_stats
2998    Validate = validate
2999    ExportToFile = export_to_file
3000    AddHint = add_hint
3001    ClearHints = clear_hints
3002    AddAssumption = add_assumption
3003    AddAssumptions = add_assumptions
3004    ClearAssumptions = clear_assumptions
3005
3006    # pylint: enable=invalid-name
3007
3008
3009@overload
3010def expand_generator_or_tuple(
3011    args: Union[Tuple[LiteralT, ...], Iterable[LiteralT]]
3012) -> Union[Iterable[LiteralT], LiteralT]:
3013    ...
3014
3015
3016@overload
3017def expand_generator_or_tuple(
3018    args: Union[Tuple[LinearExprT, ...], Iterable[LinearExprT]]
3019) -> Union[Iterable[LinearExprT], LinearExprT]:
3020    ...
3021
3022
3023def expand_generator_or_tuple(args):
3024    if hasattr(args, "__len__"):  # Tuple
3025        if len(args) != 1:
3026            return args
3027        if isinstance(args[0], (numbers.Number, LinearExpr)):
3028            return args
3029    # Generator
3030    return args[0]
3031
3032
3033def evaluate_linear_expr(
3034    expression: LinearExprT, solution: cp_model_pb2.CpSolverResponse
3035) -> int:
3036    """Evaluate a linear expression against a solution."""
3037    if isinstance(expression, numbers.Integral):
3038        return int(expression)
3039    if not isinstance(expression, LinearExpr):
3040        raise TypeError("Cannot interpret %s as a linear expression." % expression)
3041
3042    value = 0
3043    to_process = [(expression, 1)]
3044    while to_process:
3045        expr, coeff = to_process.pop()
3046        if isinstance(expr, numbers.Integral):
3047            value += int(expr) * coeff
3048        elif isinstance(expr, _ProductCst):
3049            to_process.append((expr.expression(), coeff * expr.coefficient()))
3050        elif isinstance(expr, _Sum):
3051            to_process.append((expr.left(), coeff))
3052            to_process.append((expr.right(), coeff))
3053        elif isinstance(expr, _SumArray):
3054            for e in expr.expressions():
3055                to_process.append((e, coeff))
3056            value += expr.constant() * coeff
3057        elif isinstance(expr, _WeightedSum):
3058            for e, c in zip(expr.expressions(), expr.coefficients()):
3059                to_process.append((e, coeff * c))
3060            value += expr.constant() * coeff
3061        elif isinstance(expr, IntVar):
3062            value += coeff * solution.solution[expr.index]
3063        elif isinstance(expr, _NotBooleanVariable):
3064            value += coeff * (1 - solution.solution[expr.negated().index])
3065        else:
3066            raise TypeError(f"Cannot interpret {expr} as a linear expression.")
3067
3068    return value
3069
3070
3071def evaluate_boolean_expression(
3072    literal: LiteralT, solution: cp_model_pb2.CpSolverResponse
3073) -> bool:
3074    """Evaluate a boolean expression against a solution."""
3075    if isinstance(literal, numbers.Integral):
3076        return bool(literal)
3077    elif isinstance(literal, IntVar) or isinstance(literal, _NotBooleanVariable):
3078        index: int = cast(Union[IntVar, _NotBooleanVariable], literal).index
3079        if index >= 0:
3080            return bool(solution.solution[index])
3081        else:
3082            return not solution.solution[-index - 1]
3083    else:
3084        raise TypeError(f"Cannot interpret {literal} as a boolean expression.")
3085
3086
3087class CpSolver:
3088    """Main solver class.
3089
3090    The purpose of this class is to search for a solution to the model provided
3091    to the solve() method.
3092
3093    Once solve() is called, this class allows inspecting the solution found
3094    with the value() and boolean_value() methods, as well as general statistics
3095    about the solve procedure.
3096    """
3097
3098    def __init__(self):
3099        self.__solution: Optional[cp_model_pb2.CpSolverResponse] = None
3100        self.parameters: sat_parameters_pb2.SatParameters = (
3101            sat_parameters_pb2.SatParameters()
3102        )
3103        self.log_callback: Optional[swig_helper.LogCallback] = None
3104        self.__solve_wrapper: Optional[swig_helper.SolveWrapper] = None
3105        self.__lock: threading.Lock = threading.Lock()
3106
3107    def solve(
3108        self,
3109        model: CpModel,
3110        solution_callback: Optional["CpSolverSolutionCallback"] = None,
3111    ) -> cp_model_pb2.CpSolverStatus:
3112        """Solves a problem and passes each solution to the callback if not null."""
3113        with self.__lock:
3114            self.__solve_wrapper = swig_helper.SolveWrapper()
3115
3116        self.__solve_wrapper.set_parameters(self.parameters)
3117        if solution_callback is not None:
3118            self.__solve_wrapper.add_solution_callback(solution_callback)
3119
3120        if self.log_callback is not None:
3121            self.__solve_wrapper.add_log_callback(self.log_callback)
3122
3123        self.__solution = self.__solve_wrapper.solve(model.proto)
3124
3125        if solution_callback is not None:
3126            self.__solve_wrapper.clear_solution_callback(solution_callback)
3127
3128        with self.__lock:
3129            self.__solve_wrapper = None
3130
3131        return self.__solution.status
3132
3133    def stop_search(self) -> None:
3134        """Stops the current search asynchronously."""
3135        with self.__lock:
3136            if self.__solve_wrapper:
3137                self.__solve_wrapper.stop_search()
3138
3139    def value(self, expression: LinearExprT) -> int:
3140        """Returns the value of a linear expression after solve."""
3141        return evaluate_linear_expr(expression, self._solution)
3142
3143    def values(self, variables: _IndexOrSeries) -> pd.Series:
3144        """Returns the values of the input variables.
3145
3146        If `variables` is a `pd.Index`, then the output will be indexed by the
3147        variables. If `variables` is a `pd.Series` indexed by the underlying
3148        dimensions, then the output will be indexed by the same underlying
3149        dimensions.
3150
3151        Args:
3152          variables (Union[pd.Index, pd.Series]): The set of variables from which to
3153            get the values.
3154
3155        Returns:
3156          pd.Series: The values of all variables in the set.
3157        """
3158        solution = self._solution
3159        return _attribute_series(
3160            func=lambda v: solution.solution[v.index],
3161            values=variables,
3162        )
3163
3164    def boolean_value(self, literal: LiteralT) -> bool:
3165        """Returns the boolean value of a literal after solve."""
3166        return evaluate_boolean_expression(literal, self._solution)
3167
3168    def boolean_values(self, variables: _IndexOrSeries) -> pd.Series:
3169        """Returns the values of the input variables.
3170
3171        If `variables` is a `pd.Index`, then the output will be indexed by the
3172        variables. If `variables` is a `pd.Series` indexed by the underlying
3173        dimensions, then the output will be indexed by the same underlying
3174        dimensions.
3175
3176        Args:
3177          variables (Union[pd.Index, pd.Series]): The set of variables from which to
3178            get the values.
3179
3180        Returns:
3181          pd.Series: The values of all variables in the set.
3182        """
3183        solution = self._solution
3184        return _attribute_series(
3185            func=lambda literal: evaluate_boolean_expression(literal, solution),
3186            values=variables,
3187        )
3188
3189    @property
3190    def objective_value(self) -> float:
3191        """Returns the value of the objective after solve."""
3192        return self._solution.objective_value
3193
3194    @property
3195    def best_objective_bound(self) -> float:
3196        """Returns the best lower (upper) bound found when min(max)imizing."""
3197        return self._solution.best_objective_bound
3198
3199    @property
3200    def num_booleans(self) -> int:
3201        """Returns the number of boolean variables managed by the SAT solver."""
3202        return self._solution.num_booleans
3203
3204    @property
3205    def num_conflicts(self) -> int:
3206        """Returns the number of conflicts since the creation of the solver."""
3207        return self._solution.num_conflicts
3208
3209    @property
3210    def num_branches(self) -> int:
3211        """Returns the number of search branches explored by the solver."""
3212        return self._solution.num_branches
3213
3214    @property
3215    def wall_time(self) -> float:
3216        """Returns the wall time in seconds since the creation of the solver."""
3217        return self._solution.wall_time
3218
3219    @property
3220    def user_time(self) -> float:
3221        """Returns the user time in seconds since the creation of the solver."""
3222        return self._solution.user_time
3223
3224    @property
3225    def response_proto(self) -> cp_model_pb2.CpSolverResponse:
3226        """Returns the response object."""
3227        return self._solution
3228
3229    def response_stats(self) -> str:
3230        """Returns some statistics on the solution found as a string."""
3231        return swig_helper.CpSatHelper.solver_response_stats(self._solution)
3232
3233    def sufficient_assumptions_for_infeasibility(self) -> Sequence[int]:
3234        """Returns the indices of the infeasible assumptions."""
3235        return self._solution.sufficient_assumptions_for_infeasibility
3236
3237    def status_name(self, status: Optional[Any] = None) -> str:
3238        """Returns the name of the status returned by solve()."""
3239        if status is None:
3240            status = self._solution.status
3241        return cp_model_pb2.CpSolverStatus.Name(status)
3242
3243    def solution_info(self) -> str:
3244        """Returns some information on the solve process.
3245
3246        Returns some information on how the solution was found, or the reason
3247        why the model or the parameters are invalid.
3248
3249        Raises:
3250          RuntimeError: if solve() has not been called.
3251        """
3252        return self._solution.solution_info
3253
3254    @property
3255    def _solution(self) -> cp_model_pb2.CpSolverResponse:
3256        """Checks solve() has been called, and returns the solution."""
3257        if self.__solution is None:
3258            raise RuntimeError("solve() has not been called.")
3259        return self.__solution
3260
3261    # Compatibility with pre PEP8
3262    # pylint: disable=invalid-name
3263
3264    def BestObjectiveBound(self) -> float:
3265        return self.best_objective_bound
3266
3267    def BooleanValue(self, literal: LiteralT) -> bool:
3268        return self.boolean_value(literal)
3269
3270    def BooleanValues(self, variables: _IndexOrSeries) -> pd.Series:
3271        return self.boolean_values(variables)
3272
3273    def NumBooleans(self) -> int:
3274        return self.num_booleans
3275
3276    def NumConflicts(self) -> int:
3277        return self.num_conflicts
3278
3279    def NumBranches(self) -> int:
3280        return self.num_branches
3281
3282    def ObjectiveValue(self) -> float:
3283        return self.objective_value
3284
3285    def ResponseProto(self) -> cp_model_pb2.CpSolverResponse:
3286        return self.response_proto
3287
3288    def ResponseStats(self) -> str:
3289        return self.response_stats()
3290
3291    def Solve(
3292        self,
3293        model: CpModel,
3294        solution_callback: Optional["CpSolverSolutionCallback"] = None,
3295    ) -> cp_model_pb2.CpSolverStatus:
3296        return self.solve(model, solution_callback)
3297
3298    def SolutionInfo(self) -> str:
3299        return self.solution_info()
3300
3301    def StatusName(self, status: Optional[Any] = None) -> str:
3302        return self.status_name(status)
3303
3304    def StopSearch(self) -> None:
3305        self.stop_search()
3306
3307    def SufficientAssumptionsForInfeasibility(self) -> Sequence[int]:
3308        return self.sufficient_assumptions_for_infeasibility()
3309
3310    def UserTime(self) -> float:
3311        return self.user_time
3312
3313    def Value(self, expression: LinearExprT) -> int:
3314        return self.value(expression)
3315
3316    def Values(self, variables: _IndexOrSeries) -> pd.Series:
3317        return self.values(variables)
3318
3319    def WallTime(self) -> float:
3320        return self.wall_time
3321
3322    def SolveWithSolutionCallback(
3323        self, model: CpModel, callback: "CpSolverSolutionCallback"
3324    ) -> cp_model_pb2.CpSolverStatus:
3325        """DEPRECATED Use solve() with the callback argument."""
3326        warnings.warn(
3327            "solve_with_solution_callback is deprecated; use solve() with"
3328            + "the callback argument.",
3329            DeprecationWarning,
3330        )
3331        return self.solve(model, callback)
3332
3333    def SearchForAllSolutions(
3334        self, model: CpModel, callback: "CpSolverSolutionCallback"
3335    ) -> cp_model_pb2.CpSolverStatus:
3336        """DEPRECATED Use solve() with the right parameter.
3337
3338        Search for all solutions of a satisfiability problem.
3339
3340        This method searches for all feasible solutions of a given model.
3341        Then it feeds the solution to the callback.
3342
3343        Note that the model cannot contain an objective.
3344
3345        Args:
3346          model: The model to solve.
3347          callback: The callback that will be called at each solution.
3348
3349        Returns:
3350          The status of the solve:
3351
3352          * *FEASIBLE* if some solutions have been found
3353          * *INFEASIBLE* if the solver has proved there are no solution
3354          * *OPTIMAL* if all solutions have been found
3355        """
3356        warnings.warn(
3357            "search_for_all_solutions is deprecated; use solve() with"
3358            + "enumerate_all_solutions = True.",
3359            DeprecationWarning,
3360        )
3361        if model.has_objective():
3362            raise TypeError(
3363                "Search for all solutions is only defined on satisfiability problems"
3364            )
3365        # Store old parameter.
3366        enumerate_all = self.parameters.enumerate_all_solutions
3367        self.parameters.enumerate_all_solutions = True
3368
3369        self.solve(model, callback)
3370
3371        # Restore parameter.
3372        self.parameters.enumerate_all_solutions = enumerate_all
3373        return self.__solution.status
3374
3375
3376# pylint: enable=invalid-name
3377
3378
3379class CpSolverSolutionCallback(swig_helper.SolutionCallback):
3380    """Solution callback.
3381
3382    This class implements a callback that will be called at each new solution
3383    found during search.
3384
3385    The method on_solution_callback() will be called by the solver, and must be
3386    implemented. The current solution can be queried using the boolean_value()
3387    and value() methods.
3388
3389    These methods returns the same information as their counterpart in the
3390    `CpSolver` class.
3391    """
3392
3393    def __init__(self):
3394        swig_helper.SolutionCallback.__init__(self)
3395
3396    def OnSolutionCallback(self) -> None:
3397        """Proxy for the same method in snake case."""
3398        self.on_solution_callback()
3399
3400    def boolean_value(self, lit: LiteralT) -> bool:
3401        """Returns the boolean value of a boolean literal.
3402
3403        Args:
3404            lit: A boolean variable or its negation.
3405
3406        Returns:
3407            The Boolean value of the literal in the solution.
3408
3409        Raises:
3410            RuntimeError: if `lit` is not a boolean variable or its negation.
3411        """
3412        if not self.has_response():
3413            raise RuntimeError("solve() has not been called.")
3414        if isinstance(lit, numbers.Integral):
3415            return bool(lit)
3416        if isinstance(lit, IntVar) or isinstance(lit, _NotBooleanVariable):
3417            return self.SolutionBooleanValue(
3418                cast(Union[IntVar, _NotBooleanVariable], lit).index
3419            )
3420        if cmh.is_boolean(lit):
3421            return bool(lit)
3422        raise TypeError(f"Cannot interpret {lit} as a boolean expression.")
3423
3424    def value(self, expression: LinearExprT) -> int:
3425        """Evaluates an linear expression in the current solution.
3426
3427        Args:
3428            expression: a linear expression of the model.
3429
3430        Returns:
3431            An integer value equal to the evaluation of the linear expression
3432            against the current solution.
3433
3434        Raises:
3435            RuntimeError: if 'expression' is not a LinearExpr.
3436        """
3437        if not self.has_response():
3438            raise RuntimeError("solve() has not been called.")
3439
3440        value = 0
3441        to_process = [(expression, 1)]
3442        while to_process:
3443            expr, coeff = to_process.pop()
3444            if isinstance(expr, numbers.Integral):
3445                value += int(expr) * coeff
3446            elif isinstance(expr, _ProductCst):
3447                to_process.append((expr.expression(), coeff * expr.coefficient()))
3448            elif isinstance(expr, _Sum):
3449                to_process.append((expr.left(), coeff))
3450                to_process.append((expr.right(), coeff))
3451            elif isinstance(expr, _SumArray):
3452                for e in expr.expressions():
3453                    to_process.append((e, coeff))
3454                    value += expr.constant() * coeff
3455            elif isinstance(expr, _WeightedSum):
3456                for e, c in zip(expr.expressions(), expr.coefficients()):
3457                    to_process.append((e, coeff * c))
3458                value += expr.constant() * coeff
3459            elif isinstance(expr, IntVar):
3460                value += coeff * self.SolutionIntegerValue(expr.index)
3461            elif isinstance(expr, _NotBooleanVariable):
3462                value += coeff * (1 - self.SolutionIntegerValue(expr.negated().index))
3463            else:
3464                raise TypeError(
3465                    f"cannot interpret {expression} as a linear expression."
3466                )
3467
3468        return value
3469
3470    def has_response(self) -> bool:
3471        return self.HasResponse()
3472
3473    def stop_search(self) -> None:
3474        """Stops the current search asynchronously."""
3475        if not self.has_response():
3476            raise RuntimeError("solve() has not been called.")
3477        self.StopSearch()
3478
3479    @property
3480    def objective_value(self) -> float:
3481        """Returns the value of the objective after solve."""
3482        if not self.has_response():
3483            raise RuntimeError("solve() has not been called.")
3484        return self.ObjectiveValue()
3485
3486    @property
3487    def best_objective_bound(self) -> float:
3488        """Returns the best lower (upper) bound found when min(max)imizing."""
3489        if not self.has_response():
3490            raise RuntimeError("solve() has not been called.")
3491        return self.BestObjectiveBound()
3492
3493    @property
3494    def num_booleans(self) -> int:
3495        """Returns the number of boolean variables managed by the SAT solver."""
3496        if not self.has_response():
3497            raise RuntimeError("solve() has not been called.")
3498        return self.NumBooleans()
3499
3500    @property
3501    def num_conflicts(self) -> int:
3502        """Returns the number of conflicts since the creation of the solver."""
3503        if not self.has_response():
3504            raise RuntimeError("solve() has not been called.")
3505        return self.NumConflicts()
3506
3507    @property
3508    def num_branches(self) -> int:
3509        """Returns the number of search branches explored by the solver."""
3510        if not self.has_response():
3511            raise RuntimeError("solve() has not been called.")
3512        return self.NumBranches()
3513
3514    @property
3515    def num_integer_propagations(self) -> int:
3516        """Returns the number of integer propagations done by the solver."""
3517        if not self.has_response():
3518            raise RuntimeError("solve() has not been called.")
3519        return self.NumIntegerPropagations()
3520
3521    @property
3522    def num_boolean_propagations(self) -> int:
3523        """Returns the number of Boolean propagations done by the solver."""
3524        if not self.has_response():
3525            raise RuntimeError("solve() has not been called.")
3526        return self.NumBooleanPropagations()
3527
3528    @property
3529    def deterministic_time(self) -> float:
3530        """Returns the determistic time in seconds since the creation of the solver."""
3531        if not self.has_response():
3532            raise RuntimeError("solve() has not been called.")
3533        return self.DeterministicTime()
3534
3535    @property
3536    def wall_time(self) -> float:
3537        """Returns the wall time in seconds since the creation of the solver."""
3538        if not self.has_response():
3539            raise RuntimeError("solve() has not been called.")
3540        return self.WallTime()
3541
3542    @property
3543    def user_time(self) -> float:
3544        """Returns the user time in seconds since the creation of the solver."""
3545        if not self.has_response():
3546            raise RuntimeError("solve() has not been called.")
3547        return self.UserTime()
3548
3549    @property
3550    def response_proto(self) -> cp_model_pb2.CpSolverResponse:
3551        """Returns the response object."""
3552        if not self.has_response():
3553            raise RuntimeError("solve() has not been called.")
3554        return self.Response()
3555
3556    # Compatibility with pre PEP8
3557    # pylint: disable=invalid-name
3558    Value = value
3559    BooleanValue = boolean_value
3560    # pylint: enable=invalid-name
3561
3562
3563class ObjectiveSolutionPrinter(CpSolverSolutionCallback):
3564    """Display the objective value and time of intermediate solutions."""
3565
3566    def __init__(self):
3567        CpSolverSolutionCallback.__init__(self)
3568        self.__solution_count = 0
3569        self.__start_time = time.time()
3570
3571    def on_solution_callback(self) -> None:
3572        """Called on each new solution."""
3573        current_time = time.time()
3574        obj = self.objective_value
3575        print(
3576            "Solution %i, time = %0.2f s, objective = %i"
3577            % (self.__solution_count, current_time - self.__start_time, obj)
3578        )
3579        self.__solution_count += 1
3580
3581    def solution_count(self) -> int:
3582        """Returns the number of solutions found."""
3583        return self.__solution_count
3584
3585
3586class VarArrayAndObjectiveSolutionPrinter(CpSolverSolutionCallback):
3587    """Print intermediate solutions (objective, variable values, time)."""
3588
3589    def __init__(self, variables):
3590        CpSolverSolutionCallback.__init__(self)
3591        self.__variables: Sequence[IntVar] = variables
3592        self.__solution_count: int = 0
3593        self.__start_time: float = time.time()
3594
3595    def on_solution_callback(self) -> None:
3596        """Called on each new solution."""
3597        current_time = time.time()
3598        obj = self.objective_value
3599        print(
3600            "Solution %i, time = %0.2f s, objective = %i"
3601            % (self.__solution_count, current_time - self.__start_time, obj)
3602        )
3603        for v in self.__variables:
3604            print("  %s = %i" % (v, self.value(v)), end=" ")
3605        print()
3606        self.__solution_count += 1
3607
3608    @property
3609    def solution_count(self) -> int:
3610        """Returns the number of solutions found."""
3611        return self.__solution_count
3612
3613
3614class VarArraySolutionPrinter(CpSolverSolutionCallback):
3615    """Print intermediate solutions (variable values, time)."""
3616
3617    def __init__(self, variables: Sequence[IntVar]):
3618        CpSolverSolutionCallback.__init__(self)
3619        self.__variables: Sequence[IntVar] = variables
3620        self.__solution_count: int = 0
3621        self.__start_time: float = time.time()
3622
3623    def on_solution_callback(self) -> None:
3624        """Called on each new solution."""
3625        current_time = time.time()
3626        print(
3627            "Solution %i, time = %0.2f s"
3628            % (self.__solution_count, current_time - self.__start_time)
3629        )
3630        for v in self.__variables:
3631            print("  %s = %i" % (v, self.value(v)), end=" ")
3632        print()
3633        self.__solution_count += 1
3634
3635    @property
3636    def solution_count(self) -> int:
3637        """Returns the number of solutions found."""
3638        return self.__solution_count
3639
3640
3641def _get_index(obj: _IndexOrSeries) -> pd.Index:
3642    """Returns the indices of `obj` as a `pd.Index`."""
3643    if isinstance(obj, pd.Series):
3644        return obj.index
3645    return obj
3646
3647
3648def _attribute_series(
3649    *,
3650    func: Callable[[IntVar], IntegralT],
3651    values: _IndexOrSeries,
3652) -> pd.Series:
3653    """Returns the attributes of `values`.
3654
3655    Args:
3656      func: The function to call for getting the attribute data.
3657      values: The values that the function will be applied (element-wise) to.
3658
3659    Returns:
3660      pd.Series: The attribute values.
3661    """
3662    return pd.Series(
3663        data=[func(v) for v in values],
3664        index=_get_index(values),
3665    )
3666
3667
3668def _convert_to_integral_series_and_validate_index(
3669    value_or_series: Union[IntegralT, pd.Series], index: pd.Index
3670) -> pd.Series:
3671    """Returns a pd.Series of the given index with the corresponding values.
3672
3673    Args:
3674      value_or_series: the values to be converted (if applicable).
3675      index: the index of the resulting pd.Series.
3676
3677    Returns:
3678      pd.Series: The set of values with the given index.
3679
3680    Raises:
3681      TypeError: If the type of `value_or_series` is not recognized.
3682      ValueError: If the index does not match.
3683    """
3684    if isinstance(value_or_series, numbers.Integral):
3685        result = pd.Series(data=value_or_series, index=index)
3686    elif isinstance(value_or_series, pd.Series):
3687        if value_or_series.index.equals(index):
3688            result = value_or_series
3689        else:
3690            raise ValueError("index does not match")
3691    else:
3692        raise TypeError("invalid type={}".format(type(value_or_series)))
3693    return result
3694
3695
3696def _convert_to_linear_expr_series_and_validate_index(
3697    value_or_series: Union[LinearExprT, pd.Series], index: pd.Index
3698) -> pd.Series:
3699    """Returns a pd.Series of the given index with the corresponding values.
3700
3701    Args:
3702      value_or_series: the values to be converted (if applicable).
3703      index: the index of the resulting pd.Series.
3704
3705    Returns:
3706      pd.Series: The set of values with the given index.
3707
3708    Raises:
3709      TypeError: If the type of `value_or_series` is not recognized.
3710      ValueError: If the index does not match.
3711    """
3712    if isinstance(value_or_series, numbers.Integral):
3713        result = pd.Series(data=value_or_series, index=index)
3714    elif isinstance(value_or_series, pd.Series):
3715        if value_or_series.index.equals(index):
3716            result = value_or_series
3717        else:
3718            raise ValueError("index does not match")
3719    else:
3720        raise TypeError("invalid type={}".format(type(value_or_series)))
3721    return result
3722
3723
3724def _convert_to_literal_series_and_validate_index(
3725    value_or_series: Union[LiteralT, pd.Series], index: pd.Index
3726) -> pd.Series:
3727    """Returns a pd.Series of the given index with the corresponding values.
3728
3729    Args:
3730      value_or_series: the values to be converted (if applicable).
3731      index: the index of the resulting pd.Series.
3732
3733    Returns:
3734      pd.Series: The set of values with the given index.
3735
3736    Raises:
3737      TypeError: If the type of `value_or_series` is not recognized.
3738      ValueError: If the index does not match.
3739    """
3740    if isinstance(value_or_series, numbers.Integral):
3741        result = pd.Series(data=value_or_series, index=index)
3742    elif isinstance(value_or_series, pd.Series):
3743        if value_or_series.index.equals(index):
3744            result = value_or_series
3745        else:
3746            raise ValueError("index does not match")
3747    else:
3748        raise TypeError("invalid type={}".format(type(value_or_series)))
3749    return result

class Domain(pybind11_builtins.pybind11_object):

We call domain any subset of Int64 = [kint64min, kint64max].

This class can be used to represent such set efficiently as a sorted and non-adjacent list of intervals. This is efficient as long as the size of such list stays reasonable.

In the comments below, the domain of *this will always be written 'D'. Note that all the functions are safe with respect to integer overflow.

Domain()

__init__(self: Domain, arg0: int, arg1: int) -> None

By default, Domain will be empty.

def all_values(unknown):

all_values() -> Domain

Returns the full domain Int64.

def from_values(unknown):

from_values(values: List[int]) -> Domain

Creates a domain from the union of an unsorted list of integer values. Input values may be repeated, with no consequence on the output

def from_intervals(unknown):

from_intervals(intervals: List[List[int]]) -> Domain

This method is available in Python, Java and .NET. It allows building a Domain object from a list of intervals (long[][] in Java and .NET, [[0, 2], [5, 5], [8, 10]] in python).

def from_flat_intervals(unknown):

from_flat_intervals(flat_intervals: List[int]) -> Domain

This method is available in Python, Java and .NET. It allows building a Domain object from a flattened list of intervals (long[] in Java and .NET, [0, 2, 5, 5, 8, 10] in python).

def addition_with(unknown):

addition_with(self: Domain, domain: Domain) -> Domain

Returns {x ∈ Int64, ∃ a ∈ D, ∃ b ∈ domain, x = a + b}.

def complement(unknown):

complement(self: Domain) -> Domain

Returns the set Int64 ∖ D.

def contains(unknown):

contains(self: Domain, value: int) -> bool

Returns true iff value is in Domain.

def flattened_intervals(unknown):

flattened_intervals(self: Domain) -> List[int]

This method returns the flattened list of interval bounds of the domain.

Thus the domain {0, 1, 2, 5, 8, 9, 10} will return [0, 2, 5, 5, 8, 10] (as a C++ std::vector, as a java or C# long[], as a python list of integers).

def intersection_with(unknown):

intersection_with(self: Domain, domain: Domain) -> Domain

Returns the intersection of D and domain.

def is_empty(unknown):

is_empty(self: Domain) -> bool

Returns true if this is the empty set.

def size(unknown):

size(self: Domain) -> int

Returns the number of elements in the domain. It is capped at kint64max

def max(unknown):

max(self: Domain) -> int

Returns the max value of the domain. The domain must not be empty.

def min(unknown):

min(self: Domain) -> int

Returns the min value of the domain. The domain must not be empty.

def negation(unknown):

negation(self: Domain) -> Domain

Returns {x ∈ Int64, ∃ e ∈ D, x = -e}.

Note in particular that if the negation of Int64 is not Int64 but Int64 \ {kint64min} !!

def union_with(unknown):

union_with(self: Domain, domain: Domain) -> Domain

Returns the union of D and domain.

def AllValues(unknown):

AllValues() -> Domain

Returns the full domain Int64.

def FromValues(unknown):

FromValues(values: List[int]) -> Domain

Creates a domain from the union of an unsorted list of integer values. Input values may be repeated, with no consequence on the output

def FromIntervals(unknown):

FromIntervals(intervals: List[List[int]]) -> Domain

This method is available in Python, Java and .NET. It allows building a Domain object from a list of intervals (long[][] in Java and .NET, [[0, 2], [5, 5], [8, 10]] in python).

def FromFlatIntervals(unknown):

FromFlatIntervals(flat_intervals: List[int]) -> Domain

This method is available in Python, Java and .NET. It allows building a Domain object from a flattened list of intervals (long[] in Java and .NET, [0, 2, 5, 5, 8, 10] in python).

def FlattenedIntervals(unknown):

FlattenedIntervals(self: Domain) -> List[int]

This method returns the flattened list of interval bounds of the domain.

Thus the domain {0, 1, 2, 5, 8, 9, 10} will return [0, 2, 5, 5, 8, 10] (as a C++ std::vector, as a java or C# long[], as a python list of integers).

INT_MIN = -9223372036854775808

INT_MAX = 9223372036854775807

INT32_MIN = -2147483648

INT32_MAX = 2147483647

UNKNOWN = 0

MODEL_INVALID = 1

FEASIBLE = 2

INFEASIBLE = 3

OPTIMAL = 4

CHOOSE_FIRST = 0

CHOOSE_LOWEST_MIN = 1

CHOOSE_HIGHEST_MAX = 2

CHOOSE_MIN_DOMAIN_SIZE = 3

CHOOSE_MAX_DOMAIN_SIZE = 4

SELECT_MIN_VALUE = 0

SELECT_MAX_VALUE = 1

SELECT_LOWER_HALF = 2

SELECT_UPPER_HALF = 3

AUTOMATIC_SEARCH = 0

FIXED_SEARCH = 1

PORTFOLIO_SEARCH = 2

LP_SEARCH = 3

PSEUDO_COST_SEARCH = 4

PORTFOLIO_WITH_QUICK_RESTART_SEARCH = 5

HINT_SEARCH = 6

PARTIAL_FIXED_SEARCH = 7

RANDOMIZED_SEARCH = 8

IntegralT = typing.Union[numbers.Integral, int]

NumberT = typing.Union[numbers.Integral, int, numbers.Number, float]

LiteralT = typing.Union[ForwardRef('IntVar'), ForwardRef('_NotBooleanVariable'), numbers.Integral, int, bool]

BoolVarT = typing.Union[ForwardRef('IntVar'), ForwardRef('_NotBooleanVariable')]

VariableT = typing.Union[ForwardRef('IntVar'), numbers.Integral, int]

LinearExprT = typing.Union[ForwardRef('LinearExpr'), ForwardRef('IntVar'), numbers.Integral, int]

ObjLinearExprT = typing.Union[ForwardRef('LinearExpr'), ForwardRef('IntVar'), numbers.Integral, int, numbers.Number, float]

BoundedLinearExprT = typing.Union[ForwardRef('BoundedLinearExpression'), bool]

ArcT = typing.Tuple[typing.Union[numbers.Integral, int], typing.Union[numbers.Integral, int], typing.Union[ForwardRef('IntVar'), ForwardRef('_NotBooleanVariable'), numbers.Integral, int, bool]]

def display_bounds(bounds: Sequence[int]) -> str: View Source

137def display_bounds(bounds: Sequence[int]) -> str:
138    """Displays a flattened list of intervals."""
139    out = ""
140    for i in range(0, len(bounds), 2):
141        if i != 0:
142            out += ", "
143        if bounds[i] == bounds[i + 1]:
144            out += str(bounds[i])
145        else:
146            out += str(bounds[i]) + ".." + str(bounds[i + 1])
147    return out

Displays a flattened list of intervals.

def short_name(model: ortools.sat.cp_model_pb2.CpModelProto, i: int) -> str: View Source

150def short_name(model: cp_model_pb2.CpModelProto, i: int) -> str:
151    """Returns a short name of an integer variable, or its negation."""
152    if i < 0:
153        return "not(%s)" % short_name(model, -i - 1)
154    v = model.variables[i]
155    if v.name:
156        return v.name
157    elif len(v.domain) == 2 and v.domain[0] == v.domain[1]:
158        return str(v.domain[0])
159    else:
160        return "[%s]" % display_bounds(v.domain)

Returns a short name of an integer variable, or its negation.

def short_expr_name( model: ortools.sat.cp_model_pb2.CpModelProto, e: ortools.sat.cp_model_pb2.LinearExpressionProto) -> str: View Source

163def short_expr_name(
164    model: cp_model_pb2.CpModelProto, e: cp_model_pb2.LinearExpressionProto
165) -> str:
166    """Pretty-print LinearExpressionProto instances."""
167    if not e.vars:
168        return str(e.offset)
169    if len(e.vars) == 1:
170        var_name = short_name(model, e.vars[0])
171        coeff = e.coeffs[0]
172        result = ""
173        if coeff == 1:
174            result = var_name
175        elif coeff == -1:
176            result = f"-{var_name}"
177        elif coeff != 0:
178            result = f"{coeff} * {var_name}"
179        if e.offset > 0:
180            result = f"{result} + {e.offset}"
181        elif e.offset < 0:
182            result = f"{result} - {-e.offset}"
183        return result
184    # TODO(user): Support more than affine expressions.
185    return str(e)

Pretty-print LinearExpressionProto instances.

class LinearExpr: View Source

188class LinearExpr:
189    """Holds an integer linear expression.
190
191    A linear expression is built from integer constants and variables.
192    For example, `x + 2 * (y - z + 1)`.
193
194    Linear expressions are used in CP-SAT models in constraints and in the
195    objective:
196
197    * You can define linear constraints as in:
198
199    ```
200    model.add(x + 2 * y <= 5)
201    model.add(sum(array_of_vars) == 5)
202    ```
203
204    * In CP-SAT, the objective is a linear expression:
205
206    ```
207    model.minimize(x + 2 * y + z)
208    ```
209
210    * For large arrays, using the LinearExpr class is faster that using the python
211    `sum()` function. You can create constraints and the objective from lists of
212    linear expressions or coefficients as follows:
213
214    ```
215    model.minimize(cp_model.LinearExpr.sum(expressions))
216    model.add(cp_model.LinearExpr.weighted_sum(expressions, coefficients) >= 0)
217    ```
218    """
219
220    @classmethod
221    def sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
222        """Creates the expression sum(expressions)."""
223        if len(expressions) == 1:
224            return expressions[0]
225        return _SumArray(expressions)
226
227    @overload
228    @classmethod
229    def weighted_sum(
230        cls,
231        expressions: Sequence[LinearExprT],
232        coefficients: Sequence[IntegralT],
233    ) -> LinearExprT:
234        ...
235
236    @overload
237    @classmethod
238    def weighted_sum(
239        cls,
240        expressions: Sequence[ObjLinearExprT],
241        coefficients: Sequence[NumberT],
242    ) -> ObjLinearExprT:
243        ...
244
245    @classmethod
246    def weighted_sum(cls, expressions, coefficients):
247        """Creates the expression sum(expressions[i] * coefficients[i])."""
248        if LinearExpr.is_empty_or_all_null(coefficients):
249            return 0
250        elif len(expressions) == 1:
251            return expressions[0] * coefficients[0]
252        else:
253            return _WeightedSum(expressions, coefficients)
254
255    @overload
256    @classmethod
257    def term(
258        cls,
259        expressions: LinearExprT,
260        coefficients: IntegralT,
261    ) -> LinearExprT:
262        ...
263
264    @overload
265    @classmethod
266    def term(
267        cls,
268        expressions: ObjLinearExprT,
269        coefficients: NumberT,
270    ) -> ObjLinearExprT:
271        ...
272
273    @classmethod
274    def term(cls, expression, coefficient):
275        """Creates `expression * coefficient`."""
276        if cmh.is_zero(coefficient):
277            return 0
278        else:
279            return expression * coefficient
280
281    @classmethod
282    def is_empty_or_all_null(cls, coefficients: Sequence[NumberT]) -> bool:
283        for c in coefficients:
284            if not cmh.is_zero(c):
285                return False
286        return True
287
288    @classmethod
289    def rebuild_from_linear_expression_proto(
290        cls,
291        model: cp_model_pb2.CpModelProto,
292        proto: cp_model_pb2.LinearExpressionProto,
293    ) -> LinearExprT:
294        """Recreate a LinearExpr from a LinearExpressionProto."""
295        offset = proto.offset
296        num_elements = len(proto.vars)
297        if num_elements == 0:
298            return offset
299        elif num_elements == 1:
300            return IntVar(model, proto.vars[0], None) * proto.coeffs[0] + offset
301        else:
302            variables = []
303            coeffs = []
304            all_ones = True
305            for index, coeff in zip(proto.vars, proto.coeffs):
306                variables.append(IntVar(model, index, None))
307                coeffs.append(coeff)
308                if not cmh.is_one(coeff):
309                    all_ones = False
310            if all_ones:
311                return _SumArray(variables, offset)
312            else:
313                return _WeightedSum(variables, coeffs, offset)
314
315    def get_integer_var_value_map(self) -> Tuple[Dict["IntVar", IntegralT], int]:
316        """Scans the expression, and returns (var_coef_map, constant)."""
317        coeffs = collections.defaultdict(int)
318        constant = 0
319        to_process: List[Tuple[LinearExprT, IntegralT]] = [(self, 1)]
320        while to_process:  # Flatten to avoid recursion.
321            expr, coeff = to_process.pop()
322            if isinstance(expr, numbers.Integral):
323                constant += coeff * int(expr)
324            elif isinstance(expr, _ProductCst):
325                to_process.append((expr.expression(), coeff * expr.coefficient()))
326            elif isinstance(expr, _Sum):
327                to_process.append((expr.left(), coeff))
328                to_process.append((expr.right(), coeff))
329            elif isinstance(expr, _SumArray):
330                for e in expr.expressions():
331                    to_process.append((e, coeff))
332                constant += expr.constant() * coeff
333            elif isinstance(expr, _WeightedSum):
334                for e, c in zip(expr.expressions(), expr.coefficients()):
335                    to_process.append((e, coeff * c))
336                constant += expr.constant() * coeff
337            elif isinstance(expr, IntVar):
338                coeffs[expr] += coeff
339            elif isinstance(expr, _NotBooleanVariable):
340                constant += coeff
341                coeffs[expr.negated()] -= coeff
342            else:
343                raise TypeError("Unrecognized linear expression: " + str(expr))
344
345        return coeffs, constant
346
347    def get_float_var_value_map(
348        self,
349    ) -> Tuple[Dict["IntVar", float], float, bool]:
350        """Scans the expression. Returns (var_coef_map, constant, is_integer)."""
351        coeffs = {}
352        constant = 0
353        to_process: List[Tuple[LinearExprT, Union[IntegralT, float]]] = [(self, 1)]
354        while to_process:  # Flatten to avoid recursion.
355            expr, coeff = to_process.pop()
356            if isinstance(expr, numbers.Integral):  # Keep integrality.
357                constant += coeff * int(expr)
358            elif isinstance(expr, numbers.Number):
359                constant += coeff * float(expr)
360            elif isinstance(expr, _ProductCst):
361                to_process.append((expr.expression(), coeff * expr.coefficient()))
362            elif isinstance(expr, _Sum):
363                to_process.append((expr.left(), coeff))
364                to_process.append((expr.right(), coeff))
365            elif isinstance(expr, _SumArray):
366                for e in expr.expressions():
367                    to_process.append((e, coeff))
368                constant += expr.constant() * coeff
369            elif isinstance(expr, _WeightedSum):
370                for e, c in zip(expr.expressions(), expr.coefficients()):
371                    to_process.append((e, coeff * c))
372                constant += expr.constant() * coeff
373            elif isinstance(expr, IntVar):
374                if expr in coeffs:
375                    coeffs[expr] += coeff
376                else:
377                    coeffs[expr] = coeff
378            elif isinstance(expr, _NotBooleanVariable):
379                constant += coeff
380                if expr.negated() in coeffs:
381                    coeffs[expr.negated()] -= coeff
382                else:
383                    coeffs[expr.negated()] = -coeff
384            else:
385                raise TypeError("Unrecognized linear expression: " + str(expr))
386        is_integer = isinstance(constant, numbers.Integral)
387        if is_integer:
388            for coeff in coeffs.values():
389                if not isinstance(coeff, numbers.Integral):
390                    is_integer = False
391                    break
392        return coeffs, constant, is_integer
393
394    def __hash__(self) -> int:
395        return object.__hash__(self)
396
397    def __abs__(self) -> NoReturn:
398        raise NotImplementedError(
399            "calling abs() on a linear expression is not supported, "
400            "please use CpModel.add_abs_equality"
401        )
402
403    @overload
404    def __add__(self, arg: LinearExprT) -> LinearExprT:
405        ...
406
407    @overload
408    def __add__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
409        ...
410
411    def __add__(self, arg):
412        if cmh.is_zero(arg):
413            return self
414        return _Sum(self, arg)
415
416    @overload
417    def __radd__(self, arg: LinearExprT) -> LinearExprT:
418        ...
419
420    @overload
421    def __radd__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
422        ...
423
424    def __radd__(self, arg):
425        if cmh.is_zero(arg):
426            return self
427        return _Sum(self, arg)
428
429    @overload
430    def __sub__(self, arg: LinearExprT) -> LinearExprT:
431        ...
432
433    @overload
434    def __sub__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
435        ...
436
437    def __sub__(self, arg):
438        if cmh.is_zero(arg):
439            return self
440        if isinstance(arg, numbers.Number):
441            arg = cmh.assert_is_a_number(arg)
442            return _Sum(self, -arg)
443        else:
444            return _Sum(self, -arg)
445
446    @overload
447    def __rsub__(self, arg: LinearExprT) -> LinearExprT:
448        ...
449
450    @overload
451    def __rsub__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
452        ...
453
454    def __rsub__(self, arg):
455        return _Sum(-self, arg)
456
457    @overload
458    def __mul__(self, arg: LinearExprT) -> LinearExprT:
459        ...
460
461    @overload
462    def __mul__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
463        ...
464
465    def __mul__(self, arg):
466        arg = cmh.assert_is_a_number(arg)
467        if cmh.is_one(arg):
468            return self
469        elif cmh.is_zero(arg):
470            return 0
471        return _ProductCst(self, arg)
472
473    @overload
474    def __rmul__(self, arg: LinearExprT) -> LinearExprT:
475        ...
476
477    @overload
478    def __rmul__(self, arg: ObjLinearExprT) -> ObjLinearExprT:
479        ...
480
481    def __rmul__(self, arg):
482        arg = cmh.assert_is_a_number(arg)
483        if cmh.is_one(arg):
484            return self
485        elif cmh.is_zero(arg):
486            return 0
487        return _ProductCst(self, arg)
488
489    def __div__(self, _) -> NoReturn:
490        raise NotImplementedError(
491            "calling / on a linear expression is not supported, "
492            "please use CpModel.add_division_equality"
493        )
494
495    def __truediv__(self, _) -> NoReturn:
496        raise NotImplementedError(
497            "calling // on a linear expression is not supported, "
498            "please use CpModel.add_division_equality"
499        )
500
501    def __mod__(self, _) -> NoReturn:
502        raise NotImplementedError(
503            "calling %% on a linear expression is not supported, "
504            "please use CpModel.add_modulo_equality"
505        )
506
507    def __pow__(self, _) -> NoReturn:
508        raise NotImplementedError(
509            "calling ** on a linear expression is not supported, "
510            "please use CpModel.add_multiplication_equality"
511        )
512
513    def __lshift__(self, _) -> NoReturn:
514        raise NotImplementedError(
515            "calling left shift on a linear expression is not supported"
516        )
517
518    def __rshift__(self, _) -> NoReturn:
519        raise NotImplementedError(
520            "calling right shift on a linear expression is not supported"
521        )
522
523    def __and__(self, _) -> NoReturn:
524        raise NotImplementedError(
525            "calling and on a linear expression is not supported, "
526            "please use CpModel.add_bool_and"
527        )
528
529    def __or__(self, _) -> NoReturn:
530        raise NotImplementedError(
531            "calling or on a linear expression is not supported, "
532            "please use CpModel.add_bool_or"
533        )
534
535    def __xor__(self, _) -> NoReturn:
536        raise NotImplementedError(
537            "calling xor on a linear expression is not supported, "
538            "please use CpModel.add_bool_xor"
539        )
540
541    def __neg__(self) -> LinearExprT:
542        return _ProductCst(self, -1)
543
544    def __bool__(self) -> NoReturn:
545        raise NotImplementedError(
546            "Evaluating a LinearExpr instance as a Boolean is not implemented."
547        )
548
549    def __eq__(self, arg: LinearExprT) -> BoundedLinearExprT:
550        if arg is None:
551            return False
552        if isinstance(arg, numbers.Integral):
553            arg = cmh.assert_is_int64(arg)
554            return BoundedLinearExpression(self, [arg, arg])
555        else:
556            return BoundedLinearExpression(self - arg, [0, 0])
557
558    def __ge__(self, arg: LinearExprT) -> BoundedLinearExprT:
559        if isinstance(arg, numbers.Integral):
560            arg = cmh.assert_is_int64(arg)
561            return BoundedLinearExpression(self, [arg, INT_MAX])
562        else:
563            return BoundedLinearExpression(self - arg, [0, INT_MAX])
564
565    def __le__(self, arg: LinearExprT) -> BoundedLinearExprT:
566        if isinstance(arg, numbers.Integral):
567            arg = cmh.assert_is_int64(arg)
568            return BoundedLinearExpression(self, [INT_MIN, arg])
569        else:
570            return BoundedLinearExpression(self - arg, [INT_MIN, 0])
571
572    def __lt__(self, arg: LinearExprT) -> BoundedLinearExprT:
573        if isinstance(arg, numbers.Integral):
574            arg = cmh.assert_is_int64(arg)
575            if arg == INT_MIN:
576                raise ArithmeticError("< INT_MIN is not supported")
577            return BoundedLinearExpression(self, [INT_MIN, arg - 1])
578        else:
579            return BoundedLinearExpression(self - arg, [INT_MIN, -1])
580
581    def __gt__(self, arg: LinearExprT) -> BoundedLinearExprT:
582        if isinstance(arg, numbers.Integral):
583            arg = cmh.assert_is_int64(arg)
584            if arg == INT_MAX:
585                raise ArithmeticError("> INT_MAX is not supported")
586            return BoundedLinearExpression(self, [arg + 1, INT_MAX])
587        else:
588            return BoundedLinearExpression(self - arg, [1, INT_MAX])
589
590    def __ne__(self, arg: LinearExprT) -> BoundedLinearExprT:
591        if arg is None:
592            return True
593        if isinstance(arg, numbers.Integral):
594            arg = cmh.assert_is_int64(arg)
595            if arg == INT_MAX:
596                return BoundedLinearExpression(self, [INT_MIN, INT_MAX - 1])
597            elif arg == INT_MIN:
598                return BoundedLinearExpression(self, [INT_MIN + 1, INT_MAX])
599            else:
600                return BoundedLinearExpression(
601                    self, [INT_MIN, arg - 1, arg + 1, INT_MAX]
602                )
603        else:
604            return BoundedLinearExpression(self - arg, [INT_MIN, -1, 1, INT_MAX])
605
606    # Compatibility with pre PEP8
607    # pylint: disable=invalid-name
608    @classmethod
609    def Sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
610        """Creates the expression sum(expressions)."""
611        return cls.sum(expressions)
612
613    @overload
614    @classmethod
615    def WeightedSum(
616        cls,
617        expressions: Sequence[LinearExprT],
618        coefficients: Sequence[IntegralT],
619    ) -> LinearExprT:
620        ...
621
622    @overload
623    @classmethod
624    def WeightedSum(
625        cls,
626        expressions: Sequence[ObjLinearExprT],
627        coefficients: Sequence[NumberT],
628    ) -> ObjLinearExprT:
629        ...
630
631    @classmethod
632    def WeightedSum(cls, expressions, coefficients):
633        """Creates the expression sum(expressions[i] * coefficients[i])."""
634        return cls.weighted_sum(expressions, coefficients)
635
636    @overload
637    @classmethod
638    def Term(
639        cls,
640        expressions: LinearExprT,
641        coefficients: IntegralT,
642    ) -> LinearExprT:
643        ...
644
645    @overload
646    @classmethod
647    def Term(
648        cls,
649        expressions: ObjLinearExprT,
650        coefficients: NumberT,
651    ) -> ObjLinearExprT:
652        ...
653
654    @classmethod
655    def Term(cls, expression, coefficient):
656        """Creates `expression * coefficient`."""
657        return cls.term(expression, coefficient)
658
659    # pylint: enable=invalid-name

Holds an integer linear expression.

A linear expression is built from integer constants and variables. For example, x + 2 * (y - z + 1).

Linear expressions are used in CP-SAT models in constraints and in the objective:

You can define linear constraints as in:

model.add(x + 2 * y <= 5)
model.add(sum(array_of_vars) == 5)

In CP-SAT, the objective is a linear expression:

model.minimize(x + 2 * y + z)

For large arrays, using the LinearExpr class is faster that using the python sum() function. You can create constraints and the objective from lists of linear expressions or coefficients as follows:

model.minimize(cp_model.LinearExpr.sum(expressions))
model.add(cp_model.LinearExpr.weighted_sum(expressions, coefficients) >= 0)

@classmethod

def sum( cls, expressions: Sequence[Union[LinearExpr, IntVar, numbers.Integral, int]]) -> Union[LinearExpr, IntVar, numbers.Integral, int]: View Source

220    @classmethod
221    def sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
222        """Creates the expression sum(expressions)."""
223        if len(expressions) == 1:
224            return expressions[0]
225        return _SumArray(expressions)

Creates the expression sum(expressions).

@classmethod

def weighted_sum(cls, expressions, coefficients): View Source

245    @classmethod
246    def weighted_sum(cls, expressions, coefficients):
247        """Creates the expression sum(expressions[i] * coefficients[i])."""
248        if LinearExpr.is_empty_or_all_null(coefficients):
249            return 0
250        elif len(expressions) == 1:
251            return expressions[0] * coefficients[0]
252        else:
253            return _WeightedSum(expressions, coefficients)

Creates the expression sum(expressions[i] * coefficients[i]).

@classmethod

def term(cls, expression, coefficient): View Source

273    @classmethod
274    def term(cls, expression, coefficient):
275        """Creates `expression * coefficient`."""
276        if cmh.is_zero(coefficient):
277            return 0
278        else:
279            return expression * coefficient

Creates expression * coefficient.

@classmethod

def is_empty_or_all_null( cls, coefficients: Sequence[Union[numbers.Integral, int, numbers.Number, float]]) -> bool: View Source

281    @classmethod
282    def is_empty_or_all_null(cls, coefficients: Sequence[NumberT]) -> bool:
283        for c in coefficients:
284            if not cmh.is_zero(c):
285                return False
286        return True

@classmethod

def rebuild_from_linear_expression_proto( cls, model: ortools.sat.cp_model_pb2.CpModelProto, proto: ortools.sat.cp_model_pb2.LinearExpressionProto) -> Union[LinearExpr, IntVar, numbers.Integral, int]: View Source

288    @classmethod
289    def rebuild_from_linear_expression_proto(
290        cls,
291        model: cp_model_pb2.CpModelProto,
292        proto: cp_model_pb2.LinearExpressionProto,
293    ) -> LinearExprT:
294        """Recreate a LinearExpr from a LinearExpressionProto."""
295        offset = proto.offset
296        num_elements = len(proto.vars)
297        if num_elements == 0:
298            return offset
299        elif num_elements == 1:
300            return IntVar(model, proto.vars[0], None) * proto.coeffs[0] + offset
301        else:
302            variables = []
303            coeffs = []
304            all_ones = True
305            for index, coeff in zip(proto.vars, proto.coeffs):
306                variables.append(IntVar(model, index, None))
307                coeffs.append(coeff)
308                if not cmh.is_one(coeff):
309                    all_ones = False
310            if all_ones:
311                return _SumArray(variables, offset)
312            else:
313                return _WeightedSum(variables, coeffs, offset)

Recreate a LinearExpr from a LinearExpressionProto.

def get_integer_var_value_map( self) -> Tuple[Dict[IntVar, Union[numbers.Integral, int]], int]: View Source

315    def get_integer_var_value_map(self) -> Tuple[Dict["IntVar", IntegralT], int]:
316        """Scans the expression, and returns (var_coef_map, constant)."""
317        coeffs = collections.defaultdict(int)
318        constant = 0
319        to_process: List[Tuple[LinearExprT, IntegralT]] = [(self, 1)]
320        while to_process:  # Flatten to avoid recursion.
321            expr, coeff = to_process.pop()
322            if isinstance(expr, numbers.Integral):
323                constant += coeff * int(expr)
324            elif isinstance(expr, _ProductCst):
325                to_process.append((expr.expression(), coeff * expr.coefficient()))
326            elif isinstance(expr, _Sum):
327                to_process.append((expr.left(), coeff))
328                to_process.append((expr.right(), coeff))
329            elif isinstance(expr, _SumArray):
330                for e in expr.expressions():
331                    to_process.append((e, coeff))
332                constant += expr.constant() * coeff
333            elif isinstance(expr, _WeightedSum):
334                for e, c in zip(expr.expressions(), expr.coefficients()):
335                    to_process.append((e, coeff * c))
336                constant += expr.constant() * coeff
337            elif isinstance(expr, IntVar):
338                coeffs[expr] += coeff
339            elif isinstance(expr, _NotBooleanVariable):
340                constant += coeff
341                coeffs[expr.negated()] -= coeff
342            else:
343                raise TypeError("Unrecognized linear expression: " + str(expr))
344
345        return coeffs, constant

Scans the expression, and returns (var_coef_map, constant).

def get_float_var_value_map( self) -> Tuple[Dict[IntVar, float], float, bool]: View Source

347    def get_float_var_value_map(
348        self,
349    ) -> Tuple[Dict["IntVar", float], float, bool]:
350        """Scans the expression. Returns (var_coef_map, constant, is_integer)."""
351        coeffs = {}
352        constant = 0
353        to_process: List[Tuple[LinearExprT, Union[IntegralT, float]]] = [(self, 1)]
354        while to_process:  # Flatten to avoid recursion.
355            expr, coeff = to_process.pop()
356            if isinstance(expr, numbers.Integral):  # Keep integrality.
357                constant += coeff * int(expr)
358            elif isinstance(expr, numbers.Number):
359                constant += coeff * float(expr)
360            elif isinstance(expr, _ProductCst):
361                to_process.append((expr.expression(), coeff * expr.coefficient()))
362            elif isinstance(expr, _Sum):
363                to_process.append((expr.left(), coeff))
364                to_process.append((expr.right(), coeff))
365            elif isinstance(expr, _SumArray):
366                for e in expr.expressions():
367                    to_process.append((e, coeff))
368                constant += expr.constant() * coeff
369            elif isinstance(expr, _WeightedSum):
370                for e, c in zip(expr.expressions(), expr.coefficients()):
371                    to_process.append((e, coeff * c))
372                constant += expr.constant() * coeff
373            elif isinstance(expr, IntVar):
374                if expr in coeffs:
375                    coeffs[expr] += coeff
376                else:
377                    coeffs[expr] = coeff
378            elif isinstance(expr, _NotBooleanVariable):
379                constant += coeff
380                if expr.negated() in coeffs:
381                    coeffs[expr.negated()] -= coeff
382                else:
383                    coeffs[expr.negated()] = -coeff
384            else:
385                raise TypeError("Unrecognized linear expression: " + str(expr))
386        is_integer = isinstance(constant, numbers.Integral)
387        if is_integer:
388            for coeff in coeffs.values():
389                if not isinstance(coeff, numbers.Integral):
390                    is_integer = False
391                    break
392        return coeffs, constant, is_integer

Scans the expression. Returns (var_coef_map, constant, is_integer).

@classmethod

def Sum( cls, expressions: Sequence[Union[LinearExpr, IntVar, numbers.Integral, int]]) -> Union[LinearExpr, IntVar, numbers.Integral, int]: View Source

608    @classmethod
609    def Sum(cls, expressions: Sequence[LinearExprT]) -> LinearExprT:
610        """Creates the expression sum(expressions)."""
611        return cls.sum(expressions)

Creates the expression sum(expressions).

@classmethod

def WeightedSum(cls, expressions, coefficients): View Source

631    @classmethod
632    def WeightedSum(cls, expressions, coefficients):
633        """Creates the expression sum(expressions[i] * coefficients[i])."""
634        return cls.weighted_sum(expressions, coefficients)

Creates the expression sum(expressions[i] * coefficients[i]).

@classmethod

def Term(cls, expression, coefficient): View Source

654    @classmethod
655    def Term(cls, expression, coefficient):
656        """Creates `expression * coefficient`."""
657        return cls.term(expression, coefficient)

Creates expression * coefficient.

class IntVar(LinearExpr): View Source

816class IntVar(LinearExpr):
817    """An integer variable.
818
819    An IntVar is an object that can take on any integer value within defined
820    ranges. Variables appear in constraint like:
821
822        x + y >= 5
823        AllDifferent([x, y, z])
824
825    Solving a model is equivalent to finding, for each variable, a single value
826    from the set of initial values (called the initial domain), such that the
827    model is feasible, or optimal if you provided an objective function.
828    """
829
830    def __init__(
831        self,
832        model: cp_model_pb2.CpModelProto,
833        domain: Union[int, Domain],
834        name: Optional[str],
835    ):
836        """See CpModel.new_int_var below."""
837        self.__negation: Optional[_NotBooleanVariable] = None
838        # Python do not support multiple __init__ methods.
839        # This method is only called from the CpModel class.
840        # We hack the parameter to support the two cases:
841        # case 1:
842        #     model is a CpModelProto, domain is a Domain, and name is a string.
843        # case 2:
844        #     model is a CpModelProto, domain is an index (int), and name is None.
845        if isinstance(domain, numbers.Integral) and name is None:
846            self.__index: int = int(domain)
847            self.__var: cp_model_pb2.IntegerVariableProto = model.variables[domain]
848        else:
849            self.__index: int = len(model.variables)
850            self.__var: cp_model_pb2.IntegerVariableProto = model.variables.add()
851            self.__var.domain.extend(cast(Domain, domain).flattened_intervals())
852            self.__var.name = name
853
854    @property
855    def index(self) -> int:
856        """Returns the index of the variable in the model."""
857        return self.__index
858
859    @property
860    def proto(self) -> cp_model_pb2.IntegerVariableProto:
861        """Returns the variable protobuf."""
862        return self.__var
863
864    def is_equal_to(self, other: Any) -> bool:
865        """Returns true if self == other in the python sense."""
866        if not isinstance(other, IntVar):
867            return False
868        return self.index == other.index
869
870    def __str__(self) -> str:
871        if not self.__var.name:
872            if (
873                len(self.__var.domain) == 2
874                and self.__var.domain[0] == self.__var.domain[1]
875            ):
876                # Special case for constants.
877                return str(self.__var.domain[0])
878            else:
879                return "unnamed_var_%i" % self.__index
880        return self.__var.name
881
882    def __repr__(self) -> str:
883        return "%s(%s)" % (self.__var.name, display_bounds(self.__var.domain))
884
885    @property
886    def name(self) -> str:
887        if not self.__var or not self.__var.name:
888            return ""
889        return self.__var.name
890
891    def negated(self) -> "_NotBooleanVariable":
892        """Returns the negation of a Boolean variable.
893
894        This method implements the logical negation of a Boolean variable.
895        It is only valid if the variable has a Boolean domain (0 or 1).
896
897        Note that this method is nilpotent: `x.negated().negated() == x`.
898        """
899
900        for bound in self.__var.domain:
901            if bound < 0 or bound > 1:
902                raise TypeError(
903                    f"cannot call negated on a non boolean variable: {self}"
904                )
905        if self.__negation is None:
906            self.__negation = _NotBooleanVariable(self)
907        return self.__negation
908
909    def __invert__(self) -> "_NotBooleanVariable":
910        """Returns the logical negation of a Boolean variable."""
911        return self.negated()
912
913    # Pre PEP8 compatibility.
914    # pylint: disable=invalid-name
915    Not = negated
916
917    def Name(self) -> str:
918        return self.name
919
920    def Proto(self) -> cp_model_pb2.IntegerVariableProto:
921        return self.proto
922
923    def Index(self) -> int:
924        return self.index
925
926    # pylint: enable=invalid-name

An integer variable.

An IntVar is an object that can take on any integer value within defined ranges. Variables appear in constraint like:

x + y >= 5
AllDifferent([x, y, z])

Solving a model is equivalent to finding, for each variable, a single value from the set of initial values (called the initial domain), such that the model is feasible, or optimal if you provided an objective function.

IntVar( model: ortools.sat.cp_model_pb2.CpModelProto, domain: Union[int, Domain], name: Optional[str]) View Source

830    def __init__(
831        self,
832        model: cp_model_pb2.CpModelProto,
833        domain: Union[int, Domain],
834        name: Optional[str],
835    ):
836        """See CpModel.new_int_var below."""
837        self.__negation: Optional[_NotBooleanVariable] = None
838        # Python do not support multiple __init__ methods.
839        # This method is only called from the CpModel class.
840        # We hack the parameter to support the two cases:
841        # case 1:
842        #     model is a CpModelProto, domain is a Domain, and name is a string.
843        # case 2:
844        #     model is a CpModelProto, domain is an index (int), and name is None.
845        if isinstance(domain, numbers.Integral) and name is None:
846            self.__index: int = int(domain)
847            self.__var: cp_model_pb2.IntegerVariableProto = model.variables[domain]
848        else:
849            self.__index: int = len(model.variables)
850            self.__var: cp_model_pb2.IntegerVariableProto = model.variables.add()
851            self.__var.domain.extend(cast(Domain, domain).flattened_intervals())
852            self.__var.name = name

See CpModel.new_int_var below.

index: int View Source

854    @property
855    def index(self) -> int:
856        """Returns the index of the variable in the model."""
857        return self.__index

Returns the index of the variable in the model.

proto: ortools.sat.cp_model_pb2.IntegerVariableProto View Source

859    @property
860    def proto(self) -> cp_model_pb2.IntegerVariableProto:
861        """Returns the variable protobuf."""
862        return self.__var

Returns the variable protobuf.

def is_equal_to(self, other: Any) -> bool: View Source

864    def is_equal_to(self, other: Any) -> bool:
865        """Returns true if self == other in the python sense."""
866        if not isinstance(other, IntVar):
867            return False
868        return self.index == other.index

Returns true if self == other in the python sense.

name: str View Source

885    @property
886    def name(self) -> str:
887        if not self.__var or not self.__var.name:
888            return ""
889        return self.__var.name

def negated(self) -> ortools.sat.python.cp_model._NotBooleanVariable: View Source

891    def negated(self) -> "_NotBooleanVariable":
892        """Returns the negation of a Boolean variable.
893
894        This method implements the logical negation of a Boolean variable.
895        It is only valid if the variable has a Boolean domain (0 or 1).
896
897        Note that this method is nilpotent: `x.negated().negated() == x`.
898        """
899
900        for bound in self.__var.domain:
901            if bound < 0 or bound > 1:
902                raise TypeError(
903                    f"cannot call negated on a non boolean variable: {self}"
904                )
905        if self.__negation is None:
906            self.__negation = _NotBooleanVariable(self)
907        return self.__negation

Returns the negation of a Boolean variable.

This method implements the logical negation of a Boolean variable. It is only valid if the variable has a Boolean domain (0 or 1).

Note that this method is nilpotent: x.negated().negated() == x.

def Not(self) -> ortools.sat.python.cp_model._NotBooleanVariable: View Source

891    def negated(self) -> "_NotBooleanVariable":
892        """Returns the negation of a Boolean variable.
893
894        This method implements the logical negation of a Boolean variable.
895        It is only valid if the variable has a Boolean domain (0 or 1).
896
897        Note that this method is nilpotent: `x.negated().negated() == x`.
898        """
899
900        for bound in self.__var.domain:
901            if bound < 0 or bound > 1:
902                raise TypeError(
903                    f"cannot call negated on a non boolean variable: {self}"
904                )
905        if self.__negation is None:
906            self.__negation = _NotBooleanVariable(self)
907        return self.__negation

Returns the negation of a Boolean variable.

This method implements the logical negation of a Boolean variable. It is only valid if the variable has a Boolean domain (0 or 1).

Note that this method is nilpotent: x.negated().negated() == x.

def Name(self) -> str: View Source

917    def Name(self) -> str:
918        return self.name

def Proto(self) -> ortools.sat.cp_model_pb2.IntegerVariableProto: View Source

920    def Proto(self) -> cp_model_pb2.IntegerVariableProto:
921        return self.proto

def Index(self) -> int: View Source

923    def Index(self) -> int:
924        return self.index

Inherited Members

LinearExpr: sum; weighted_sum; term; is_empty_or_all_null; rebuild_from_linear_expression_proto; get_integer_var_value_map; get_float_var_value_map; Sum; WeightedSum; Term

class BoundedLinearExpression: View Source

 969class BoundedLinearExpression:
 970    """Represents a linear constraint: `lb <= linear expression <= ub`.
 971
 972    The only use of this class is to be added to the CpModel through
 973    `CpModel.add(expression)`, as in:
 974
 975        model.add(x + 2 * y -1 >= z)
 976    """
 977
 978    def __init__(self, expr: LinearExprT, bounds: Sequence[int]):
 979        self.__expr: LinearExprT = expr
 980        self.__bounds: Sequence[int] = bounds
 981
 982    def __str__(self):
 983        if len(self.__bounds) == 2:
 984            lb, ub = self.__bounds
 985            if lb > INT_MIN and ub < INT_MAX:
 986                if lb == ub:
 987                    return str(self.__expr) + " == " + str(lb)
 988                else:
 989                    return str(lb) + " <= " + str(self.__expr) + " <= " + str(ub)
 990            elif lb > INT_MIN:
 991                return str(self.__expr) + " >= " + str(lb)
 992            elif ub < INT_MAX:
 993                return str(self.__expr) + " <= " + str(ub)
 994            else:
 995                return "True (unbounded expr " + str(self.__expr) + ")"
 996        elif (
 997            len(self.__bounds) == 4
 998            and self.__bounds[0] == INT_MIN
 999            and self.__bounds[1] + 2 == self.__bounds[2]
1000            and self.__bounds[3] == INT_MAX
1001        ):
1002            return str(self.__expr) + " != " + str(self.__bounds[1] + 1)
1003        else:
1004            return str(self.__expr) + " in [" + display_bounds(self.__bounds) + "]"
1005
1006    def expression(self) -> LinearExprT:
1007        return self.__expr
1008
1009    def bounds(self) -> Sequence[int]:
1010        return self.__bounds
1011
1012    def __bool__(self) -> bool:
1013        expr = self.__expr
1014        if isinstance(expr, LinearExpr):
1015            coeffs_map, constant = expr.get_integer_var_value_map()
1016            all_coeffs = set(coeffs_map.values())
1017            same_var = set([0])
1018            eq_bounds = [0, 0]
1019            different_vars = set([-1, 1])
1020            ne_bounds = [INT_MIN, -1, 1, INT_MAX]
1021            if (
1022                len(coeffs_map) == 1
1023                and all_coeffs == same_var
1024                and constant == 0
1025                and (self.__bounds == eq_bounds or self.__bounds == ne_bounds)
1026            ):
1027                return self.__bounds == eq_bounds
1028            if (
1029                len(coeffs_map) == 2
1030                and all_coeffs == different_vars
1031                and constant == 0
1032                and (self.__bounds == eq_bounds or self.__bounds == ne_bounds)
1033            ):
1034                return self.__bounds == ne_bounds
1035
1036        raise NotImplementedError(
1037            f'Evaluating a BoundedLinearExpression "{self}" as a Boolean value'
1038            + " is not supported."
1039        )

Represents a linear constraint: lb <= linear expression <= ub.

The only use of this class is to be added to the CpModel through CpModel.add(expression), as in:

model.add(x + 2 * y -1 >= z)

BoundedLinearExpression( expr: Union[LinearExpr, IntVar, numbers.Integral, int], bounds: Sequence[int]) View Source

978    def __init__(self, expr: LinearExprT, bounds: Sequence[int]):
979        self.__expr: LinearExprT = expr
980        self.__bounds: Sequence[int] = bounds

def expression( self) -> Union[LinearExpr, IntVar, numbers.Integral, int]: View Source

1006    def expression(self) -> LinearExprT:
1007        return self.__expr

def bounds(self) -> Sequence[int]: View Source

1009    def bounds(self) -> Sequence[int]:
1010        return self.__bounds

class Constraint: View Source

1042class Constraint:
1043    """Base class for constraints.
1044
1045    Constraints are built by the CpModel through the add<XXX> methods.
1046    Once created by the CpModel class, they are automatically added to the model.
1047    The purpose of this class is to allow specification of enforcement literals
1048    for this constraint.
1049
1050        b = model.new_bool_var('b')
1051        x = model.new_int_var(0, 10, 'x')
1052        y = model.new_int_var(0, 10, 'y')
1053
1054        model.add(x + 2 * y == 5).only_enforce_if(b.negated())
1055    """
1056
1057    def __init__(
1058        self,
1059        cp_model: "CpModel",
1060    ):
1061        self.__index: int = len(cp_model.proto.constraints)
1062        self.__cp_model: "CpModel" = cp_model
1063        self.__constraint: cp_model_pb2.ConstraintProto = (
1064            cp_model.proto.constraints.add()
1065        )
1066
1067    @overload
1068    def only_enforce_if(self, boolvar: Iterable[LiteralT]) -> "Constraint":
1069        ...
1070
1071    @overload
1072    def only_enforce_if(self, *boolvar: LiteralT) -> "Constraint":
1073        ...
1074
1075    def only_enforce_if(self, *boolvar) -> "Constraint":
1076        """Adds an enforcement literal to the constraint.
1077
1078        This method adds one or more literals (that is, a boolean variable or its
1079        negation) as enforcement literals. The conjunction of all these literals
1080        determines whether the constraint is active or not. It acts as an
1081        implication, so if the conjunction is true, it implies that the constraint
1082        must be enforced. If it is false, then the constraint is ignored.
1083
1084        BoolOr, BoolAnd, and linear constraints all support enforcement literals.
1085
1086        Args:
1087          *boolvar: One or more Boolean literals.
1088
1089        Returns:
1090          self.
1091        """
1092        for lit in expand_generator_or_tuple(boolvar):
1093            if (cmh.is_boolean(lit) and lit) or (
1094                isinstance(lit, numbers.Integral) and lit == 1
1095            ):
1096                # Always true. Do nothing.
1097                pass
1098            elif (cmh.is_boolean(lit) and not lit) or (
1099                isinstance(lit, numbers.Integral) and lit == 0
1100            ):
1101                self.__constraint.enforcement_literal.append(
1102                    self.__cp_model.new_constant(0).index
1103                )
1104            else:
1105                self.__constraint.enforcement_literal.append(
1106                    cast(Union[IntVar, _NotBooleanVariable], lit).index
1107                )
1108        return self
1109
1110    def with_name(self, name: str) -> "Constraint":
1111        """Sets the name of the constraint."""
1112        if name:
1113            self.__constraint.name = name
1114        else:
1115            self.__constraint.ClearField("name")
1116        return self
1117
1118    @property
1119    def name(self) -> str:
1120        """Returns the name of the constraint."""
1121        if not self.__constraint or not self.__constraint.name:
1122            return ""
1123        return self.__constraint.name
1124
1125    @property
1126    def index(self) -> int:
1127        """Returns the index of the constraint in the model."""
1128        return self.__index
1129
1130    @property
1131    def proto(self) -> cp_model_pb2.ConstraintProto:
1132        """Returns the constraint protobuf."""
1133        return self.__constraint
1134
1135    # Pre PEP8 compatibility.
1136    # pylint: disable=invalid-name
1137    OnlyEnforceIf = only_enforce_if
1138    WithName = with_name
1139
1140    def Name(self) -> str:
1141        return self.name
1142
1143    def Index(self) -> int:
1144        return self.index
1145
1146    def Proto(self) -> cp_model_pb2.ConstraintProto:
1147        return self.proto
1148
1149    # pylint: enable=invalid-name

Base class for constraints.

Constraints are built by the CpModel through the add methods. Once created by the CpModel class, they are automatically added to the model. The purpose of this class is to allow specification of enforcement literals for this constraint.

b = model.new_bool_var('b')
x = model.new_int_var(0, 10, 'x')
y = model.new_int_var(0, 10, 'y')

model.add(x + 2 * y == 5).only_enforce_if(b.negated())

Constraint(cp_model: CpModel) View Source

1057    def __init__(
1058        self,
1059        cp_model: "CpModel",
1060    ):
1061        self.__index: int = len(cp_model.proto.constraints)
1062        self.__cp_model: "CpModel" = cp_model
1063        self.__constraint: cp_model_pb2.ConstraintProto = (
1064            cp_model.proto.constraints.add()
1065        )

def only_enforce_if(self, *boolvar) -> Constraint: View Source

1075    def only_enforce_if(self, *boolvar) -> "Constraint":
1076        """Adds an enforcement literal to the constraint.
1077
1078        This method adds one or more literals (that is, a boolean variable or its
1079        negation) as enforcement literals. The conjunction of all these literals
1080        determines whether the constraint is active or not. It acts as an
1081        implication, so if the conjunction is true, it implies that the constraint
1082        must be enforced. If it is false, then the constraint is ignored.
1083
1084        BoolOr, BoolAnd, and linear constraints all support enforcement literals.
1085
1086        Args:
1087          *boolvar: One or more Boolean literals.
1088
1089        Returns:
1090          self.
1091        """
1092        for lit in expand_generator_or_tuple(boolvar):
1093            if (cmh.is_boolean(lit) and lit) or (
1094                isinstance(lit, numbers.Integral) and lit == 1
1095            ):
1096                # Always true. Do nothing.
1097                pass
1098            elif (cmh.is_boolean(lit) and not lit) or (
1099                isinstance(lit, numbers.Integral) and lit == 0
1100            ):
1101                self.__constraint.enforcement_literal.append(
1102                    self.__cp_model.new_constant(0).index
1103                )
1104            else:
1105                self.__constraint.enforcement_literal.append(
1106                    cast(Union[IntVar, _NotBooleanVariable], lit).index
1107                )
1108        return self

Adds an enforcement literal to the constraint.

This method adds one or more literals (that is, a boolean variable or its negation) as enforcement literals. The conjunction of all these literals determines whether the constraint is active or not. It acts as an implication, so if the conjunction is true, it implies that the constraint must be enforced. If it is false, then the constraint is ignored.

BoolOr, BoolAnd, and linear constraints all support enforcement literals.

Arguments:

*boolvar: One or more Boolean literals.

Returns:

self.

def with_name(self, name: str) -> Constraint: View Source

1110    def with_name(self, name: str) -> "Constraint":
1111        """Sets the name of the constraint."""
1112        if name:
1113            self.__constraint.name = name
1114        else:
1115            self.__constraint.ClearField("name")
1116        return self

Sets the name of the constraint.

name: str View Source

1118    @property
1119    def name(self) -> str:
1120        """Returns the name of the constraint."""
1121        if not self.__constraint or not self.__constraint.name:
1122            return ""
1123        return self.__constraint.name

Returns the name of the constraint.

index: int View Source

1125    @property
1126    def index(self) -> int:
1127        """Returns the index of the constraint in the model."""
1128        return self.__index

Returns the index of the constraint in the model.

proto: ortools.sat.cp_model_pb2.ConstraintProto View Source

1130    @property
1131    def proto(self) -> cp_model_pb2.ConstraintProto:
1132        """Returns the constraint protobuf."""
1133        return self.__constraint

Returns the constraint protobuf.

def OnlyEnforceIf(self, *boolvar) -> Constraint: View Source

1075    def only_enforce_if(self, *boolvar) -> "Constraint":
1076        """Adds an enforcement literal to the constraint.
1077
1078        This method adds one or more literals (that is, a boolean variable or its
1079        negation) as enforcement literals. The conjunction of all these literals
1080        determines whether the constraint is active or not. It acts as an
1081        implication, so if the conjunction is true, it implies that the constraint
1082        must be enforced. If it is false, then the constraint is ignored.
1083
1084        BoolOr, BoolAnd, and linear constraints all support enforcement literals.
1085
1086        Args:
1087          *boolvar: One or more Boolean literals.
1088
1089        Returns:
1090          self.
1091        """
1092        for lit in expand_generator_or_tuple(boolvar):
1093            if (cmh.is_boolean(lit) and lit) or (
1094                isinstance(lit, numbers.Integral) and lit == 1
1095            ):
1096                # Always true. Do nothing.
1097                pass
1098            elif (cmh.is_boolean(lit) and not lit) or (
1099                isinstance(lit, numbers.Integral) and lit == 0
1100            ):
1101                self.__constraint.enforcement_literal.append(
1102                    self.__cp_model.new_constant(0).index
1103                )
1104            else:
1105                self.__constraint.enforcement_literal.append(
1106                    cast(Union[IntVar, _NotBooleanVariable], lit).index
1107                )
1108        return self

Adds an enforcement literal to the constraint.

BoolOr, BoolAnd, and linear constraints all support enforcement literals.

Arguments:

*boolvar: One or more Boolean literals.

Returns:

self.

def WithName(self, name: str) -> Constraint: View Source

1110    def with_name(self, name: str) -> "Constraint":
1111        """Sets the name of the constraint."""
1112        if name:
1113            self.__constraint.name = name
1114        else:
1115            self.__constraint.ClearField("name")
1116        return self

Sets the name of the constraint.

def Name(self) -> str: View Source

1140    def Name(self) -> str:
1141        return self.name

def Index(self) -> int: View Source

1143    def Index(self) -> int:
1144        return self.index

def Proto(self) -> ortools.sat.cp_model_pb2.ConstraintProto: View Source

1146    def Proto(self) -> cp_model_pb2.ConstraintProto:
1147        return self.proto

def object_is_a_true_literal( literal: Union[IntVar, ortools.sat.python.cp_model._NotBooleanVariable, numbers.Integral, int, bool]) -> bool: View Source

1271def object_is_a_true_literal(literal: LiteralT) -> bool:
1272    """Checks if literal is either True, or a Boolean literals fixed to True."""
1273    if isinstance(literal, IntVar):
1274        proto = literal.proto
1275        return len(proto.domain) == 2 and proto.domain[0] == 1 and proto.domain[1] == 1
1276    if isinstance(literal, _NotBooleanVariable):
1277        proto = literal.negated().proto
1278        return len(proto.domain) == 2 and proto.domain[0] == 0 and proto.domain[1] == 0
1279    if isinstance(literal, numbers.Integral):
1280        return int(literal) == 1
1281    return False

Checks if literal is either True, or a Boolean literals fixed to True.

def object_is_a_false_literal( literal: Union[IntVar, ortools.sat.python.cp_model._NotBooleanVariable, numbers.Integral, int, bool]) -> bool: View Source

1284def object_is_a_false_literal(literal: LiteralT) -> bool:
1285    """Checks if literal is either False, or a Boolean literals fixed to False."""
1286    if isinstance(literal, IntVar):
1287        proto = literal.proto
1288        return len(proto.domain) == 2 and proto.domain[0] == 0 and proto.domain[1] == 0
1289    if isinstance(literal, _NotBooleanVariable):
1290        proto = literal.negated().proto
1291        return len(proto.domain) == 2 and proto.domain[0] == 1 and proto.domain[1] == 1
1292    if isinstance(literal, numbers.Integral):
1293        return int(literal) == 0
1294    return False

Checks if literal is either False, or a Boolean literals fixed to False.

def expand_generator_or_tuple(args): View Source

3024def expand_generator_or_tuple(args):
3025    if hasattr(args, "__len__"):  # Tuple
3026        if len(args) != 1:
3027            return args
3028        if isinstance(args[0], (numbers.Number, LinearExpr)):
3029            return args
3030    # Generator
3031    return args[0]

def evaluate_linear_expr( expression: Union[LinearExpr, IntVar, numbers.Integral, int], solution: ortools.sat.cp_model_pb2.CpSolverResponse) -> int: View Source

3034def evaluate_linear_expr(
3035    expression: LinearExprT, solution: cp_model_pb2.CpSolverResponse
3036) -> int:
3037    """Evaluate a linear expression against a solution."""
3038    if isinstance(expression, numbers.Integral):
3039        return int(expression)
3040    if not isinstance(expression, LinearExpr):
3041        raise TypeError("Cannot interpret %s as a linear expression." % expression)
3042
3043    value = 0
3044    to_process = [(expression, 1)]
3045    while to_process:
3046        expr, coeff = to_process.pop()
3047        if isinstance(expr, numbers.Integral):
3048            value += int(expr) * coeff
3049        elif isinstance(expr, _ProductCst):
3050            to_process.append((expr.expression(), coeff * expr.coefficient()))
3051        elif isinstance(expr, _Sum):
3052            to_process.append((expr.left(), coeff))
3053            to_process.append((expr.right(), coeff))
3054        elif isinstance(expr, _SumArray):
3055            for e in expr.expressions():
3056                to_process.append((e, coeff))
3057            value += expr.constant() * coeff
3058        elif isinstance(expr, _WeightedSum):
3059            for e, c in zip(expr.expressions(), expr.coefficients()):
3060                to_process.append((e, coeff * c))
3061            value += expr.constant() * coeff
3062        elif isinstance(expr, IntVar):
3063            value += coeff * solution.solution[expr.index]
3064        elif isinstance(expr, _NotBooleanVariable):
3065            value += coeff * (1 - solution.solution[expr.negated().index])
3066        else:
3067            raise TypeError(f"Cannot interpret {expr} as a linear expression.")
3068
3069    return value

Evaluate a linear expression against a solution.

def evaluate_boolean_expression( literal: Union[IntVar, ortools.sat.python.cp_model._NotBooleanVariable, numbers.Integral, int, bool], solution: ortools.sat.cp_model_pb2.CpSolverResponse) -> bool: View Source

3072def evaluate_boolean_expression(
3073    literal: LiteralT, solution: cp_model_pb2.CpSolverResponse
3074) -> bool:
3075    """Evaluate a boolean expression against a solution."""
3076    if isinstance(literal, numbers.Integral):
3077        return bool(literal)
3078    elif isinstance(literal, IntVar) or isinstance(literal, _NotBooleanVariable):
3079        index: int = cast(Union[IntVar, _NotBooleanVariable], literal).index
3080        if index >= 0:
3081            return bool(solution.solution[index])
3082        else:
3083            return not solution.solution[-index - 1]
3084    else:
3085        raise TypeError(f"Cannot interpret {literal} as a boolean expression.")

Evaluate a boolean expression against a solution.

class ObjectiveSolutionPrinter(CpSolverSolutionCallback): View Source

3564class ObjectiveSolutionPrinter(CpSolverSolutionCallback):
3565    """Display the objective value and time of intermediate solutions."""
3566
3567    def __init__(self):
3568        CpSolverSolutionCallback.__init__(self)
3569        self.__solution_count = 0
3570        self.__start_time = time.time()
3571
3572    def on_solution_callback(self) -> None:
3573        """Called on each new solution."""
3574        current_time = time.time()
3575        obj = self.objective_value
3576        print(
3577            "Solution %i, time = %0.2f s, objective = %i"
3578            % (self.__solution_count, current_time - self.__start_time, obj)
3579        )
3580        self.__solution_count += 1
3581
3582    def solution_count(self) -> int:
3583        """Returns the number of solutions found."""
3584        return self.__solution_count

Display the objective value and time of intermediate solutions.

ObjectiveSolutionPrinter() View Source

3567    def __init__(self):
3568        CpSolverSolutionCallback.__init__(self)
3569        self.__solution_count = 0
3570        self.__start_time = time.time()

__init__(self: ortools.sat.python.swig_helper.SolutionCallback) -> None

def on_solution_callback(self) -> None: View Source

3572    def on_solution_callback(self) -> None:
3573        """Called on each new solution."""
3574        current_time = time.time()
3575        obj = self.objective_value
3576        print(
3577            "Solution %i, time = %0.2f s, objective = %i"
3578            % (self.__solution_count, current_time - self.__start_time, obj)
3579        )
3580        self.__solution_count += 1

Called on each new solution.

def solution_count(self) -> int: View Source

3582    def solution_count(self) -> int:
3583        """Returns the number of solutions found."""
3584        return self.__solution_count

Returns the number of solutions found.

Inherited Members

CpSolverSolutionCallback: OnSolutionCallback; boolean_value; value; has_response; stop_search; objective_value; best_objective_bound; num_booleans; num_conflicts; num_branches; num_integer_propagations; num_boolean_propagations; deterministic_time; wall_time; user_time; response_proto; Value; BooleanValue
ortools.sat.python.swig_helper.SolutionCallback: BestObjectiveBound; DeterministicTime; HasResponse; NumBinaryPropagations; NumBooleans; NumBranches; NumConflicts; NumIntegerPropagations; ObjectiveValue; Response; SolutionBooleanValue; SolutionIntegerValue; StopSearch; UserTime; WallTime

class VarArrayAndObjectiveSolutionPrinter(CpSolverSolutionCallback): View Source

3587class VarArrayAndObjectiveSolutionPrinter(CpSolverSolutionCallback):
3588    """Print intermediate solutions (objective, variable values, time)."""
3589
3590    def __init__(self, variables):
3591        CpSolverSolutionCallback.__init__(self)
3592        self.__variables: Sequence[IntVar] = variables
3593        self.__solution_count: int = 0
3594        self.__start_time: float = time.time()
3595
3596    def on_solution_callback(self) -> None:
3597        """Called on each new solution."""
3598        current_time = time.time()
3599        obj = self.objective_value
3600        print(
3601            "Solution %i, time = %0.2f s, objective = %i"
3602            % (self.__solution_count, current_time - self.__start_time, obj)
3603        )
3604        for v in self.__variables:
3605            print("  %s = %i" % (v, self.value(v)), end=" ")
3606        print()
3607        self.__solution_count += 1
3608
3609    @property
3610    def solution_count(self) -> int:
3611        """Returns the number of solutions found."""
3612        return self.__solution_count

Print intermediate solutions (objective, variable values, time).

VarArrayAndObjectiveSolutionPrinter(variables) View Source

3590    def __init__(self, variables):
3591        CpSolverSolutionCallback.__init__(self)
3592        self.__variables: Sequence[IntVar] = variables
3593        self.__solution_count: int = 0
3594        self.__start_time: float = time.time()

__init__(self: ortools.sat.python.swig_helper.SolutionCallback) -> None

def on_solution_callback(self) -> None: View Source

3596    def on_solution_callback(self) -> None:
3597        """Called on each new solution."""
3598        current_time = time.time()
3599        obj = self.objective_value
3600        print(
3601            "Solution %i, time = %0.2f s, objective = %i"
3602            % (self.__solution_count, current_time - self.__start_time, obj)
3603        )
3604        for v in self.__variables:
3605            print("  %s = %i" % (v, self.value(v)), end=" ")
3606        print()
3607        self.__solution_count += 1

Called on each new solution.

solution_count: int View Source

3609    @property
3610    def solution_count(self) -> int:
3611        """Returns the number of solutions found."""
3612        return self.__solution_count

Returns the number of solutions found.

Inherited Members

CpSolverSolutionCallback: OnSolutionCallback; boolean_value; value; has_response; stop_search; objective_value; best_objective_bound; num_booleans; num_conflicts; num_branches; num_integer_propagations; num_boolean_propagations; deterministic_time; wall_time; user_time; response_proto; Value; BooleanValue
ortools.sat.python.swig_helper.SolutionCallback: BestObjectiveBound; DeterministicTime; HasResponse; NumBinaryPropagations; NumBooleans; NumBranches; NumConflicts; NumIntegerPropagations; ObjectiveValue; Response; SolutionBooleanValue; SolutionIntegerValue; StopSearch; UserTime; WallTime

class VarArraySolutionPrinter(CpSolverSolutionCallback): View Source

3615class VarArraySolutionPrinter(CpSolverSolutionCallback):
3616    """Print intermediate solutions (variable values, time)."""
3617
3618    def __init__(self, variables: Sequence[IntVar]):
3619        CpSolverSolutionCallback.__init__(self)
3620        self.__variables: Sequence[IntVar] = variables
3621        self.__solution_count: int = 0
3622        self.__start_time: float = time.time()
3623
3624    def on_solution_callback(self) -> None:
3625        """Called on each new solution."""
3626        current_time = time.time()
3627        print(
3628            "Solution %i, time = %0.2f s"
3629            % (self.__solution_count, current_time - self.__start_time)
3630        )
3631        for v in self.__variables:
3632            print("  %s = %i" % (v, self.value(v)), end=" ")
3633        print()
3634        self.__solution_count += 1
3635
3636    @property
3637    def solution_count(self) -> int:
3638        """Returns the number of solutions found."""
3639        return self.__solution_count

Print intermediate solutions (variable values, time).

VarArraySolutionPrinter(variables: Sequence[IntVar]) View Source

3618    def __init__(self, variables: Sequence[IntVar]):
3619        CpSolverSolutionCallback.__init__(self)
3620        self.__variables: Sequence[IntVar] = variables
3621        self.__solution_count: int = 0
3622        self.__start_time: float = time.time()

__init__(self: ortools.sat.python.swig_helper.SolutionCallback) -> None

def on_solution_callback(self) -> None: View Source

3624    def on_solution_callback(self) -> None:
3625        """Called on each new solution."""
3626        current_time = time.time()
3627        print(
3628            "Solution %i, time = %0.2f s"
3629            % (self.__solution_count, current_time - self.__start_time)
3630        )
3631        for v in self.__variables:
3632            print("  %s = %i" % (v, self.value(v)), end=" ")
3633        print()
3634        self.__solution_count += 1

Called on each new solution.

solution_count: int View Source

3636    @property
3637    def solution_count(self) -> int:
3638        """Returns the number of solutions found."""
3639        return self.__solution_count

Returns the number of solutions found.

Inherited Members

CpSolverSolutionCallback: OnSolutionCallback; boolean_value; value; has_response; stop_search; objective_value; best_objective_bound; num_booleans; num_conflicts; num_branches; num_integer_propagations; num_boolean_propagations; deterministic_time; wall_time; user_time; response_proto; Value; BooleanValue
ortools.sat.python.swig_helper.SolutionCallback: BestObjectiveBound; DeterministicTime; HasResponse; NumBinaryPropagations; NumBooleans; NumBranches; NumConflicts; NumIntegerPropagations; ObjectiveValue; Response; SolutionBooleanValue; SolutionIntegerValue; StopSearch; UserTime; WallTime