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)[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 :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)[source]

Replaces constraints containing NegBoolView with equivalent expression using only BoolVar. lst_of_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.