Convert constraints to linear form (cpmpy.transformations.linearize)

Transformations regarding linearization of constraints.

Linearized constraints have one of the following forms:

Unsatisfiable:

  • BoolVal(False)

Linear comparison:

  • LinExpr == Constant

  • LinExpr >= Constant

  • LinExpr <= Constant

    LinExpr can be any of:

    • NumVar

    • sum

    • wsum

Indicator constraints:

  • BoolVar -> LinExpr == Constant

  • BoolVar -> LinExpr >= Constant

  • BoolVar -> LinExpr <= Constant

  • BoolVar -> GenExpr (GenExpr.name in supported, GenExpr.is_bool())

  • BoolVar -> GenExpr >= Var/Constant (GenExpr.name in supported, GenExpr.is_num())

  • BoolVar -> GenExpr <= Var/Constant (GenExpr.name in supported, GenExpr.is_num())

  • BoolVar -> GenExpr == Var/Constant (GenExpr.name in supported, GenExpr.is_num())

Where BoolVar is a boolean variable or its negation.

General comparisons or expressions

  • GenExpr (GenExpr.name in supported, GenExpr.is_bool())

  • GenExpr == Var/Constant (GenExpr.name in supported, GenExpr.is_num())

  • GenExpr <= Var/Constant (GenExpr.name in supported, GenExpr.is_num())

  • GenExpr >= Var/Constant (GenExpr.name in supported, GenExpr.is_num())

cpmpy.transformations.linearize.canonical_comparison(lst_of_expr)[source]
cpmpy.transformations.linearize.linearize_constraint(lst_of_expr, supported={'sum', 'wsum'}, reified=False)[source]

Transforms all constraints to a linear form. This function assumes all constraints are in ‘flat normal form’ with only boolean variables on the lhs of an implication. Only apply after ‘cpmpy.transformations.flatten_model.flatten_constraint()’ ‘and only_implies()’.

Arguments: - supported: which constraint and variable types are supported, i.e. sum, and, or, alldifferent AllDifferent has a special linearization and is decomposed as such if not in supported. Any other unsupported global constraint should be decomposed using cpmpy.transformations.decompose_global.decompose_global() - reified: whether the constraint is fully reified

cpmpy.transformations.linearize.only_positive_bv(lst_of_expr)[source]

Replaces constraints containing NegBoolView with equivalent expression using only BoolVar. cpm_expr is expected to be linearized. Only apply after applying linearize_constraint(cpm_expr)

Resulting expression is linear.

cpmpy.transformations.linearize.only_positive_coefficients(lst_of_expr)[source]

Replaces Boolean terms with negative coefficients in linear constraints with terms with positive coefficients by negating its literal. This can simplify a wsum into sum. cpm_expr is expected to be a canonical comparison. Only apply after applying canonical_comparison(cpm_expr)

Resulting expression is linear.