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

Transforms flat constraints into linear constraints.

Linearized constraints have one of the following forms:

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)

Canonicalize a comparison expression. Transforms linear expressions, or a reification thereof into canonical form by:

• moving all variables to the left-hand side

• moving constants to the right-hand side

Expects the input constraints to be flat. Only apply after applying flatten_constraint()

cpmpy.transformations.linearize.linearize_constraint(lst_of_expr, supported={'sum', 'wsum'}, reified=False, csemap=None)

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 :func:’cpmpy.transformations.flatten_model.flatten_constraint()’ and :func:’cpmpy.transformations.reification.only_implies()’.

Parameters:

• 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_in_tree()

• reified – whether the constraint is fully reified

cpmpy.transformations.linearize.only_positive_bv(lst_of_expr, csemap=None)

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

Resulting expression is linear if the original expression was linear.

cpmpy.transformations.linearize.only_positive_bv_wsum(expr)

Replaces a var/sum/wsum expression containing NegBoolView with an equivalent expression using only BoolVar.

It might add a constant term to the expression, if you want the constant separately, use only_positive_bv_wsum_const().

Arguments: - cpm_expr: linear expression (sum, wsum, var)

Returns tuple of: - pos_expr: linear expression (sum, wsum, var) without NegBoolView

cpmpy.transformations.linearize.only_positive_bv_wsum_const(cpm_expr)

Replaces a var/sum/wsum expression containing NegBoolView with an equivalent expression using only BoolVar as well as a constant term that must be added to the new expression to be equivalent.

If you want the expression where the constant term is part of the wsum returned, use only_positive_bv_wsum().

Arguments: - cpm_expr: linear expression (sum, wsum, var)

Returns tuple of: - pos_expr: linear expression (sum, wsum, var) without NegBoolView - const: The difference between the original expression and the new expression,

i.e. a constant term that must be added to pos_expr to be an equivalent linear expression.

cpmpy.transformations.linearize.only_positive_coefficients(lst_of_expr)

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.