SCIPsimplifyExpr

scip_sys

Function SCIPsimplifyExpr 

Source 
pub unsafe extern "C" fn SCIPsimplifyExpr(
    scip: *mut SCIP,
    rootexpr: *mut SCIP_EXPR,
    simplified: *mut *mut SCIP_EXPR,
    changed: *mut c_uint,
    infeasible: *mut c_uint,
    ownercreate: Option<unsafe extern "C" fn(scip: *mut SCIP, expr: *mut SCIP_EXPR, ownerdata: *mut *mut SCIP_EXPR_OWNERDATA, ownerfree: *mut Option<unsafe extern "C" fn(scip: *mut SCIP, expr: *mut SCIP_EXPR, ownerdata: *mut *mut SCIP_EXPR_OWNERDATA) -> SCIP_RETCODE>, ownerprint: *mut Option<unsafe extern "C" fn(scip: *mut SCIP, file: *mut FILE, expr: *mut SCIP_EXPR, ownerdata: *mut SCIP_EXPR_OWNERDATA) -> SCIP_RETCODE>, ownerevalactivity: *mut Option<unsafe extern "C" fn(scip: *mut SCIP, expr: *mut SCIP_EXPR, ownerdata: *mut SCIP_EXPR_OWNERDATA) -> SCIP_RETCODE>, ownercreatedata: *mut c_void) -> SCIP_RETCODE>,
    ownercreatedata: *mut c_void,
) -> SCIP_RETCODE
Expand description

simplifies an expression

This is largely inspired by Joel Cohen’s Computer algebra and symbolic computation: Mathematical methods, in particular Chapter 3. The other fountain of inspiration are the simplifying methods of expr.c in SCIP 7.

Note: The things to keep in mind when adding simplification rules are the following. I will be using the product expressions (see expr_product.c) as an example. There are mainly 3 parts of the simplification process. You need to decide at which stage the simplification rule makes sense.

  1. Simplify each factor (simplifyFactor()): At this stage we got the children of the product expression. At this point, each child is simplified when viewed as a stand-alone expression, but not necessarily when viewed as child of a product expression. Rules like SP2, SP7, etc are enforced at this point.
  2. Multiply the factors (mergeProductExprlist()): At this point rules like SP4, SP5 and SP14 are enforced.
  3. Build the actual simplified product expression (buildSimplifiedProduct()): At this point rules like SP10, SP11, etc are enforced.

During steps 1 and 2 do not forget to set the flag changed to TRUE when something actually changes.

\par Definition of simplified expressions

An expression is simplified if it

  • is a value expression

  • is a var expression

  • is a product expression such that

    • SP1: every child is simplified
    • SP2: no child is a product
    • SP4: no two children are the same expression (those should be multiplied)
    • SP5: the children are sorted [commutative rule]
    • SP7: no child is a value
    • SP8: its coefficient is 1.0 (otherwise should be written as sum)
    • SP10: it has at least two children
    • TODO?: at most one child is an abs
    • SP11: no two children are expr*log(expr) (TODO: we could handle more complicated stuff like \f$xy\log(x) \to - y * \mathrm{entropy}(x)\f$, but I am not sure this should happen at the simplification level; similar for \f$(xy) \log(xy)\f$, which currently simplifies to \f$xy \log(xy)\f$)
    • SP12: if it has two children, then neither of them is a sum (expand sums)
    • SP12b: if it has at least two children and expandalways is set, then no child is a sum (expand sums always)
    • SP13: no child is a sum with a single term
    • SP14: at most one child is an exp

  • is a power expression such that

    • POW1: exponent is not 0
    • POW2: exponent is not 1
    • POW3: its child is not a value
    • POW4: its child is simplified
    • POW5: if exponent is integer, its child is not a product
    • POW5a: if exponent is fractional and distribfracexponent param is enabled, its child is not a product
    • POW6: if exponent is integer, its child is not a sum with a single term (\f$(2x)^2 \to 4x^2\f$)
    • POW7: if exponent is integer and at most expandmaxeponent param, its child is not a sum (expand sums)
    • POW8: its child is not a power unless \f$(x^n)^m\f$ with \f$nm\f$ being integer and \f$n\f$ or \f$m\f$ fractional and \f$n\f$ not being even integer
    • POW9: its child is not a sum with a single term with a positive coefficient: \f$(25x)^{0.5} \to 5 x^{0.5}\f$
    • POW10: its child is not a binary variable: \f$b^e, e > 0 \to b\f$; \f$b^e, e < 0 \to b := 1\f$
    • POW11: its child is not an exponential: \f$\exp(\text{expr})^e \to \exp(e\cdot\text{expr})\f$
    • POW12: its child is not an absolute value if the exponent is an even integer: \f$\abs(\text{expr})^e, e \text{ even} \to \text{expr}^e\f$

  • is a signedpower expression such that

    • SPOW1: exponent is not 0
    • SPOW2: exponent is not 1
    • SPOW3: its child is not a value
    • SPOW4: its child is simplified
    • SPOW5: (TODO) do we want to distribute signpowers over products like we do for powers?
    • SPOW6: exponent is not an odd integer: (signpow odd expr) -> (pow odd expr)
    • SPOW8: if exponent is integer, its child is not a power
    • SPOW9: its child is not a sum with a single term: \f$\mathrm{signpow}(25x,0.5) \to 5\mathrm{signpow}(x,0.5)\f$
    • SPOW10: its child is not a binary variable: \f$\mathrm{signpow}(b,e), e > 0 \to b\f$; \f$\mathrm{signpow}(b,e), e < 0 \to b := 1\f$
    • SPOW11: its child is not an exponential: \f$\mathrm{signpow}(\exp(\text{expr}),e) \to \exp(e\cdot\text{expr})\f$
    • TODO: what happens when child is another signed power?
    • TODO: if child ≥ 0 -> transform to normal power; if child < 0 -> transform to - normal power

    TODO: Some of these criteria are too restrictive for signed powers; for example, the exponent does not need to be an integer for signedpower to distribute over a product (SPOW5, SPOW6, SPOW8). Others can also be improved.

  • is a sum expression such that

    • SS1: every child is simplified
    • SS2: no child is a sum
    • SS3: no child is a value (values should go in the constant of the sum)
    • SS4: no two children are the same expression (those should be summed up)
    • SS5: the children are sorted [commutative rule]
    • SS6: it has at least one child
    • SS7: if it consists of a single child, then either constant is != 0.0 or coef != 1
    • SS8: no child has coefficient 0
    • SS9: if a child c is a product that has an exponential expression as one of its factors, then the coefficient of c is +/-1.0
    • SS10: if a child c is an exponential, then the coefficient of c is +/-1.0

  • it is a function with simplified arguments, but not all of them can be values

  • TODO? a logarithm doesn’t have a product as a child

  • TODO? the exponent of an exponential is always 1

\par Ordering Rules (see SCIPexprCompare()) \anchor EXPR_ORDER These rules define a total order on simplified expressions. There are two groups of rules, when comparing equal type expressions and different type expressions.

Equal type expressions:

  • OR1: u,v value expressions: u < v ⇔ val(u) < val(v)
  • OR2: u,v var expressions: u < v ⇔ SCIPvarGetIndex(var(u)) < SCIPvarGetIndex(var(v))
  • OR3: u,v are both sum or product expression: < is a lexicographical order on the terms
  • OR4: u,v are both pow: u < v ⇔ base(u) < base(v) or, base(u) = base(v) and expo(u) < expo(v)
  • OR5: u,v are \f$u = f(u_1, …, u_n), v = f(v_1, …, v_m)\f$: u < v ⇔ For the first k such that \f$u_k \neq v_k\f$, \f$u_k < v_k\f$, or if such a \f$k\f$ doesn’t exist, then \f$n < m\f$.

Different type expressions:

  • OR6: u value, v other: u < v always
  • OR7: u sum, v var or func: u < v ⇔ u < 0+v; In other words, if \f$u = \sum_{i=1}^n \alpha_i u_i\f$, then u < v ⇔ \f$u_n\f$ < v or if \f$u_n\f$ = v and \f$\alpha_n\f$ < 1.
  • OR8: u product, v pow, sum, var or func: u < v ⇔ u < 1*v; In other words, if \f$u = \prod_{i=1}^n u_i\f$, then u < v ⇔ \f$u_n\f$ < v. Note: since this applies only to simplified expressions, the form of the product is correct. Simplified products do not have constant coefficients.
  • OR9: u pow, v sum, var or func: u < v ⇔ u < v^1
  • OR10: u var, v func: u < v always
  • OR11: u func, v other type of func: u < v ⇔ name(type(u)) < name(type(v))
  • OR12: none of the rules apply: u < v ⇔ ! v < u

Examples:

  • x < x^2 ?: x is var and x^2 power, so none applies (OR12). Hence, we try to answer x^2 < x ?: x^2 < x ⇔ x < x or if x = x and 2 < 1 ⇔ 2 < 1 ⇔ False. So x < x^2 is True.
  • x < x^-1 –OR12→ ~(x^-1 < x) –OR9→ ~(x^-1 < x^1) –OR4→ ~(x < x or -1 < 1) → ~True → False
  • xy < x –OR8→ xy < 1*x –OR3→ y < x –OR2→ False
  • xy < y –OR8→ xy < 1*y –OR3→ y < x –OR2→ False

\par Algorithm

The recursive version of the algorithm is

EXPR simplify(expr)
   for c in 1..expr->nchildren
      expr->children[c] = simplify(expr->children[c])
   end
   return expr->exprhdlr->simplify(expr)
end

Important: Whatever is returned by a simplify callback has to be simplified. Also, all children of the given expression are already simplified.