Package com.google.ortools.sat

Class CpModel

java.lang.Object
com.google.ortools.sat.CpModel
public final class CpModel
extends java.lang.Object
Main modeling class.

Proposes a factory to create all modeling objects understood by the SAT solver.

  • Constructor Details

    • CpModel

      public CpModel()

  • Method Details

    • newIntVar

      public IntVar newIntVar​(long lb, long ub, java.lang.String name)
      Creates an integer variable with domain [lb, ub].

    • newIntVarFromDomain

      public IntVar newIntVarFromDomain​(Domain domain, java.lang.String name)
      Creates an integer variable with given domain.
      Parameters:
      domain - an instance of the Domain class.
      name - the name of the variable
      Returns:
      a variable with the given domain.

    • newBoolVar

      public IntVar newBoolVar​(java.lang.String name)
      Creates a Boolean variable with the given name.

    • newConstant

      public IntVar newConstant​(long value)
      Creates a constant variable.

    • trueLiteral

      public Literal trueLiteral()
      Returns the true literal.

    • falseLiteral

      public Literal falseLiteral()
      Returns the false literal.

    • addBoolOr

      public Constraint addBoolOr​(Literal[] literals)
      Adds Or(literals) == true.

    • addBoolAnd

      public Constraint addBoolAnd​(Literal[] literals)
      Adds And(literals) == true.

    • addBoolXor

      public Constraint addBoolXor​(Literal[] literals)
      Adds XOr(literals) == true.

    • addImplication

      public Constraint addImplication​(Literal a, Literal b)
      Adds a => b.

    • addLinearExpressionInDomain

      public Constraint addLinearExpressionInDomain​(LinearExpr expr, Domain domain)
      Adds expr in domain.

    • addLinearConstraint

      public Constraint addLinearConstraint​(LinearExpr expr, long lb, long ub)
      Adds lb <= expr <= ub.

    • addEquality

      public Constraint addEquality​(LinearExpr expr, long value)
      Adds expr == value.

    • addEquality

      public Constraint addEquality​(LinearExpr left, LinearExpr right)
      Adds left == right.

    • addEqualityWithOffset

      public Constraint addEqualityWithOffset​(LinearExpr left, LinearExpr right, long offset)
      Adds left + offset == right.

    • addLessOrEqual

      public Constraint addLessOrEqual​(LinearExpr expr, long value)
      Adds expr <= value.

    • addLessOrEqual

      public Constraint addLessOrEqual​(LinearExpr left, LinearExpr right)
      Adds left <= right.

    • addLessThan

      public Constraint addLessThan​(LinearExpr expr, long value)
      Adds expr < value.

    • addLessThan

      public Constraint addLessThan​(LinearExpr left, LinearExpr right)
      Adds left < right.

    • addLessOrEqualWithOffset

      public Constraint addLessOrEqualWithOffset​(LinearExpr left, LinearExpr right, long offset)
      Adds left + offset <= right.

    • addGreaterOrEqual

      public Constraint addGreaterOrEqual​(LinearExpr expr, long value)
      Adds expr >= value.

    • addGreaterOrEqual

      public Constraint addGreaterOrEqual​(LinearExpr left, LinearExpr right)
      Adds left >= right.

    • addGreaterThan

      public Constraint addGreaterThan​(LinearExpr expr, long value)
      Adds expr > value.

    • addGreaterThan

      public Constraint addGreaterThan​(LinearExpr left, LinearExpr right)
      Adds left > right.

    • addGreaterOrEqualWithOffset

      public Constraint addGreaterOrEqualWithOffset​(LinearExpr left, LinearExpr right, long offset)
      Adds left + offset >= right.

    • addDifferent

      public Constraint addDifferent​(LinearExpr expr, long value)
      Adds expr != value.

    • addDifferent

      public Constraint addDifferent​(IntVar left, IntVar right)
      Adds left != right.

    • addDifferentWithOffset

      public Constraint addDifferentWithOffset​(IntVar left, IntVar right, long offset)
      Adds left + offset != right.

    • addAllDifferent

      public Constraint addAllDifferent​(IntVar[] variables)
      Adds AllDifferent(variables).

      This constraint forces all variables to have different values.

      Parameters:
      variables - a list of integer variables
      Returns:
      an instance of the Constraint class

    • addElement

      public Constraint addElement​(IntVar index, IntVar[] variables, IntVar target)
      Adds the element constraint: variables[index] == target.

    • addElement

      public Constraint addElement​(IntVar index, long[] values, IntVar target)
      Adds the element constraint: values[index] == target.

    • addElement

      public Constraint addElement​(IntVar index, int[] values, IntVar target)
      Adds the element constraint: values[index] == target.

    • addCircuit

      public Constraint addCircuit​(int[] tails, int[] heads, Literal[] literals)
      Adds Circuit(tails, heads, literals).

      Adds a circuit constraint from a sparse list of arcs that encode the graph.

      A circuit is a unique Hamiltonian path in a subgraph of the total graph. In case a node 'i' is not in the path, then there must be a loop arc 'i -> i' associated with a true literal. Otherwise this constraint will fail.

      Parameters:
      tails - the tails of all arcs
      heads - the heads of all arcs
      literals - the literals that control whether an arc is selected or not
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.MismatchedArrayLengths - if the arrays have different sizes

    • addAllowedAssignments

      public Constraint addAllowedAssignments​(IntVar[] variables, long[][] tuplesList)
      Adds AllowedAssignments(variables, tuplesList).

      An AllowedAssignments constraint is a constraint on an array of variables that forces, when all variables are fixed to a single value, that the corresponding list of values is equal to one of the tuples of the tupleList.

      Parameters:
      variables - a list of variables
      tuplesList - a list of admissible tuples. Each tuple must have the same length as the variables, and the ith value of a tuple corresponds to the ith variable.
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.WrongLength - if one tuple does not have the same length as the variables

    • addAllowedAssignments

      public Constraint addAllowedAssignments​(IntVar[] variables, int[][] tuplesList)
      Adds AllowedAssignments(variables, tuplesList).
      See Also:
      addAllowedAssignments

    • addForbiddenAssignments

      public Constraint addForbiddenAssignments​(IntVar[] variables, long[][] tuplesList)
      Adds ForbiddenAssignments(variables, tuplesList).

      A ForbiddenAssignments constraint is a constraint on an array of variables where the list of impossible combinations is provided in the tuples list.

      Parameters:
      variables - a list of variables
      tuplesList - a list of forbidden tuples. Each tuple must have the same length as the variables, and the ith value of a tuple corresponds to the ith variable.
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.WrongLength - if one tuple does not have the same length as the variables

    • addForbiddenAssignments

      public Constraint addForbiddenAssignments​(IntVar[] variables, int[][] tuplesList)
      Adds ForbiddenAssignments(variables, tuplesList).
      See Also:
      addForbiddenAssignments

    • addAutomaton

      public Constraint addAutomaton​(IntVar[] transitionVariables, long startingState, long[] finalStates, long[][] transitions)
      Adds an automaton constraint.

      An automaton constraint takes a list of variables (of size n), an initial state, a set of final states, and a set of transitions. A transition is a triplet ('tail', 'transition', 'head'), where 'tail' and 'head' are states, and 'transition' is the label of an arc from 'head' to 'tail', corresponding to the value of one variable in the list of variables.

      This automaton will be unrolled into a flow with n + 1 phases. Each phase contains the possible states of the automaton. The first state contains the initial state. The last phase contains the final states.

      Between two consecutive phases i and i + 1, the automaton creates a set of arcs. For each transition (tail, label, head), it will add an arc from the state 'tail' of phase i and the state 'head' of phase i + 1. This arc labeled by the value 'label' of the variables 'variables[i]'. That is, this arc can only be selected if 'variables[i]' is assigned the value 'label'.

      A feasible solution of this constraint is an assignment of variables such that, starting from the initial state in phase 0, there is a path labeled by the values of the variables that ends in one of the final states in the final phase.

      Parameters:
      transitionVariables - a non empty list of variables whose values correspond to the labels of the arcs traversed by the automaton
      startingState - the initial state of the automaton
      finalStates - a non empty list of admissible final states
      transitions - a list of transition for the automaton, in the following format (currentState, variableValue, nextState)
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.WrongLength - if one transition does not have a length of 3

    • addInverse

      public Constraint addInverse​(IntVar[] variables, IntVar[] inverseVariables)
      Adds Inverse(variables, inverseVariables).

      An inverse constraint enforces that if 'variables[i]' is assigned a value 'j', then inverseVariables[j] is assigned a value 'i'. And vice versa.

      Parameters:
      variables - an array of integer variables
      inverseVariables - an array of integer variables
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.MismatchedArrayLengths - if variables and inverseVariables have different length

    • addReservoirConstraint

      public Constraint addReservoirConstraint​(IntVar[] times, long[] demands, long minLevel, long maxLevel)
      Adds Reservoir(times, demands, minLevel, maxLevel).

      Maintains a reservoir level within bounds. The water level starts at 0, and at any times, it must be between minLevel and maxLevel. If the variable times[i] is assigned a value t, and if actives[i] is true, then the current level changes by demands[i] (which is constant) at the time t.

      Note that minLevel must be less than 0, and maxLevel must be greater than 0. Therefore, forall t : minLevel <= sum(demands[i] if times[i] <= t) <= maxLevel.

      Parameters:
      times - a list of integer variables which specify the time of the filling or emptying the reservoir
      demands - a list of integer values that specifies the amount of the emptying or feeling
      minLevel - at any time, the level of the reservoir must be greater of equal than the min level. minLevel must me <= 0.
      maxLevel - at any time, the level of the reservoir must be less or equal than the max level. maxLevel must be >= 0.
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.MismatchedArrayLengths - if times and demands have different length
      java.lang.IllegalArgumentException - if minLevel > 0
      java.lang.IllegalArgumentException - if maxLevel < 0

    • addReservoirConstraint

      public Constraint addReservoirConstraint​(IntVar[] times, int[] demands, long minLevel, long maxLevel)
      Adds Reservoir(times, demands, minLevel, maxLevel).
      See Also:
      Reservoir

    • addReservoirConstraintWithActive

      public Constraint addReservoirConstraintWithActive​(IntVar[] times, long[] demands, IntVar[] actives, long minLevel, long maxLevel)
      Adds Reservoir(times, demands, actives, minLevel, maxLevel).

      Maintains a reservoir level within bounds. The water level starts at 0, and at any time, it must be between minLevel and maxLevel. If the variable times[i] is assigned a value t, then the current level changes by demands[i] (which is constant) at the time t.

      Note that minLevel must be less than 0, and maxLevel must be greater than 0. Therefore, forall t : minLevel <= sum(demands[i] * actives[i] if times[i] <= t) <= maxLevel.

      Parameters:
      times - a list of integer variables which specify the time of the filling or emptying the reservoir
      demands - a list of integer values that specifies the amount of the emptying or feeling
      minLevel - at any time, the level of the reservoir must be greater of equal than the min level. minLevel must me <= 0.
      maxLevel - at any time, the level of the reservoir must be less or equal than the max level. maxLevel must be >= 0.
      Returns:
      an instance of the Constraint class
      Throws:
      CpModel.MismatchedArrayLengths - if times, demands, or actives have different length
      java.lang.IllegalArgumentException - if minLevel > 0
      java.lang.IllegalArgumentException - if maxLevel < 0

    • addReservoirConstraintWithActive

      public Constraint addReservoirConstraintWithActive​(IntVar[] times, int[] demands, IntVar[] actives, long minLevel, long maxLevel)
      Adds Reservoir(times, demands, actives, minLevel, maxLevel).
      See Also:
      Reservoir

    • addMapDomain

      public void addMapDomain​(IntVar var, Literal[] booleans, long offset)
      Adds var == i + offset <=> booleans[i] == true for all i in [0, booleans.length).

    • addMinEquality

      public Constraint addMinEquality​(IntVar target, IntVar[] vars)
      Adds target == Min(vars).

    • addMaxEquality

      public Constraint addMaxEquality​(IntVar target, IntVar[] vars)
      Adds target == Max(vars).

    • addDivisionEquality

      public Constraint addDivisionEquality​(IntVar target, IntVar num, IntVar denom)
      Adds target == num / denom, rounded towards 0.

    • addAbsEquality

      public Constraint addAbsEquality​(IntVar target, IntVar var)
      Adds target == Abs(var).

    • addModuloEquality

      public Constraint addModuloEquality​(IntVar target, IntVar var, IntVar mod)
      Adds target == var % mod.

    • addModuloEquality

      public Constraint addModuloEquality​(IntVar target, IntVar var, long mod)
      Adds target == var % mod.

    • addProductEquality

      public Constraint addProductEquality​(IntVar target, IntVar[] vars)
      Adds target == Product(vars).

    • newIntervalVar

      public IntervalVar newIntervalVar​(IntVar start, IntVar size, IntVar end, java.lang.String name)
      Creates an interval variable from start, size, and end.

      An interval variable is a constraint, that is itself used in other constraints like NoOverlap.

      Internally, it ensures that start + size == end.

      Parameters:
      start - the start of the interval
      size - the size of the interval
      end - the end of the interval
      name - the name of the interval variable
      Returns:
      An IntervalVar object

    • newIntervalVar

      public IntervalVar newIntervalVar​(IntVar start, IntVar size, long end, java.lang.String name)
      Creates an interval variable with a fixed end.
      See Also:
      newIntervalVar

    • newIntervalVar

      public IntervalVar newIntervalVar​(IntVar start, long size, IntVar end, java.lang.String name)
      Creates an interval variable with a fixed size.
      See Also:
      newIntervalVar

    • newIntervalVar

      public IntervalVar newIntervalVar​(long start, IntVar size, IntVar end, java.lang.String name)
      Creates an interval variable with a fixed start.
      See Also:
      newIntervalVar

    • newFixedInterval

      public IntervalVar newFixedInterval​(long start, long size, java.lang.String name)
      Creates a fixed interval from its start and its size.

    • newOptionalIntervalVar

      public IntervalVar newOptionalIntervalVar​(IntVar start, IntVar size, IntVar end, Literal isPresent, java.lang.String name)
      Creates an optional interval variable from start, size, end, and isPresent.

      An optional interval variable is a constraint, that is itself used in other constraints like NoOverlap. This constraint is protected by an isPresent literal that indicates if it is active or not.

      Internally, it ensures that isPresent => start + size == end.

      Parameters:
      start - the start of the interval. It can be an integer value, or an integer variable.
      size - the size of the interval. It can be an integer value, or an integer variable.
      end - the end of the interval. It can be an integer value, or an integer variable.
      isPresent - a literal that indicates if the interval is active or not. A inactive interval is simply ignored by all constraints.
      name - The name of the interval variable
      Returns:
      an IntervalVar object

    • newOptionalIntervalVar

      public IntervalVar newOptionalIntervalVar​(IntVar start, IntVar size, long end, Literal isPresent, java.lang.String name)
      Creates an optional interval with a fixed end.
      See Also:
      newOptionalIntervalVar

    • newOptionalIntervalVar

      public IntervalVar newOptionalIntervalVar​(IntVar start, long size, IntVar end, Literal isPresent, java.lang.String name)
      Creates an optional interval with a fixed size.
      See Also:
      newOptionalIntervalVar

    • newOptionalIntervalVar

      public IntervalVar newOptionalIntervalVar​(long start, IntVar size, IntVar end, Literal isPresent, java.lang.String name)
      Creates an optional interval with a fixed start.

    • newOptionalFixedInterval

      public IntervalVar newOptionalFixedInterval​(long start, long size, Literal isPresent, java.lang.String name)
      Creates an optional fixed interval from start and size.
      See Also:
      newOptionalIntervalVar

    • addNoOverlap

      public Constraint addNoOverlap​(IntervalVar[] intervalVars)
      Adds NoOverlap(intervalVars).

      A NoOverlap constraint ensures that all present intervals do not overlap in time.

      Parameters:
      intervalVars - the list of interval variables to constrain
      Returns:
      an instance of the Constraint class

    • addNoOverlap2D

      public Constraint addNoOverlap2D​(IntervalVar[] xIntervals, IntervalVar[] yIntervals)
      Adds NoOverlap2D(xIntervals, yIntervals).

      A NoOverlap2D constraint ensures that all present rectangles do not overlap on a plan. Each rectangle is aligned with the X and Y axis, and is defined by two intervals which represent its projection onto the X and Y axis.

      Parameters:
      xIntervals - the X coordinates of the rectangles
      yIntervals - the Y coordinates of the rectangles
      Returns:
      an instance of the Constraint class

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, IntVar[] demands, IntVar capacity)
      Adds Cumulative(intervals, demands, capacity).

      This constraint enforces that:

      forall t: sum(demands[i] if (start(intervals[t]) <= t < end(intervals[t])) and (t is present)) <= capacity.

      Parameters:
      intervals - the list of intervals
      demands - the list of demands for each interval. Each demand must be a positive integer variable.
      capacity - the maximum capacity of the cumulative constraint. It must be a positive integer variable.
      Returns:
      an instance of the Constraint class

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, long[] demands, IntVar capacity)
      Adds Cumulative(intervals, demands, capacity) with fixed demands.
      See Also:
      AddCumulative

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, int[] demands, IntVar capacity)
      Adds Cumulative(intervals, demands, capacity) with fixed demands.
      See Also:
      AddCumulative

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, IntVar[] demands, long capacity)
      Adds Cumulative(intervals, demands, capacity) with fixed capacity.
      See Also:
      AddCumulative

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, long[] demands, long capacity)
      Adds Cumulative(intervals, demands, capacity) with fixed demands and fixed capacity.
      See Also:
      AddCumulative

    • addCumulative

      public Constraint addCumulative​(IntervalVar[] intervals, int[] demands, long capacity)
      Adds Cumulative(intervals, demands, capacity) with fixed demands and fixed capacity.
      See Also:
      AddCumulative

    • addHint

      public void addHint​(IntVar var, long value)
      Adds hinting to a variable

    • clearHints

      public void clearHints()
      Remove all solution hints

    • addAssumption

      public void addAssumption​(Literal lit)
      Adds a literal to the model as assumption

    • addAssumptions

      public void addAssumptions​(Literal[] literals)
      Adds multiple literals to the model as assumptions

    • clearAssumptions

      public void clearAssumptions()
      Remove all assumptions from the model

    • minimize

      public void minimize​(LinearExpr expr)
      Adds a minimization objective of a linear expression.

    • maximize

      public void maximize​(LinearExpr expr)
      Adds a maximization objective of a linear expression.

    • addDecisionStrategy

      public void addDecisionStrategy​(IntVar[] variables, DecisionStrategyProto.VariableSelectionStrategy varStr, DecisionStrategyProto.DomainReductionStrategy domStr)
      Adds DecisionStrategy(variables, varStr, domStr).

    • modelStats

      public java.lang.String modelStats()
      Returns some statistics on model as a string.

    • validate

      public java.lang.String validate()
      Returns a non empty string explaining the issue if the model is invalid.

    • exportToFile

      public java.lang.Boolean exportToFile​(java.lang.String file)
      Write the model as a protocol buffer to 'file'.
      Parameters:
      file - file to write the model to. If the filename ends with 'txt', the model will be written as a text file, otherwise, the binary format will be used.
      Returns:
      true if the model was correctly written.

    • model

      public CpModelProto model()

    • negated

      public int negated​(int index)

    • getBuilder

      public CpModelProto.Builder getBuilder()
      Returns the model builder.