[SCIP] Nonlinear constraints / expression trees

[Stefan Vigerske]

Hi,

On 03/31/2016 04:37 PM, Johannes Thürauf wrote:
> Dear SCIP-Team,
>
> I would really appreciate if you can help me by providing some information
> about how Scip handles nonlinear constraints.
>
> I want to implement an algorithm which computes a linearisation
> (delta-method) and a relaxation of nonlinear constraints such as
> exp(x)-y=0.
> I have already understood that Scip uses Expression Trees to store the
> representation of nonlinear constraints. Unfortunately I have never worked
> with expression Trees before. So hopefully you can give me an advise where
> I can find some information about how Scip works with expression trees.

The CallableLibrary example is usually a good starting point to see how 
expression trees are constructed.

> Moreover Scip is doing a lot of "presolve" when reading the problem. For
> example when I have the constraint exp(x)*ln(s)-y=0
> Scip transforms this constraint to the following kind:
> exp(x)-z=0 (1)
> ln(s)-w=0  (2)
> z*w-y=0    (3)
> My question is will Scip always transform all nonlinear constraint this way?
> So that you have always constraints with maximum one nonlinear term?

No.

> If this would be the case, there would be no need for me to transform the
> nonlinear constraint to the following type: (one) nonlinearexpr - (one)
> variable =0 such as (1) or product of vars - vars =0 such as (3).
> Thank you very much

Nonlinear constraints have the form as described in the documentation:
http://scip.zib.de/doc/html/cons__nonlinear_8h.php
So you have a sum of expression trees.
After presolve (where reformulation takes places), each of the 
expression trees in a nonlinear constraint corresponds to a function 
that SCIP knows is either convex or concave, but not necessarily univariate.
It shouldn't be difficult to add something that disaggregates nonlinear 
constraints into having only one expression tree, but you could also 
imagine the sum of expression trees as one expression tree.
Additionally, there might be more than one linear variable in a 
cons_nonlinear.

When the reformulation code in cons_nonlinear encounters products (or 
divisions), it often creates quadratic constraints to handle these. In 
general, quadratic constraints look like described at
http://scip.zib.de/doc/html/cons__quadratic_8h.php

Finally, for terms like x^3 or sign(x)|x|^2, the cons_abspower is 
utilized: http://scip.zib.de/doc/html/cons__abspower_8h.php

So, to summarize, after reformulation, the problem should be such that 
<nonlinear> constraints consist of a sum of expressions, each one being 
either convex or concave, <quadratic> constraints that handle the 
products, and <abspower> constraints that handle the odd powers.
Additionally, there can be additional upgrades to <soc> or <and> or 
<bounddisjunction> in special cases.

Other constraints can interact with the reformulation process of 
nonlinear constraints by registering an upgrade function in 
SCIPincludeNonlinconsUpgrade(), see the definition for 
SCIP_DECL_EXPRGRAPHNODEREFORM for the signature of such a callback.
If you register an upgrade, it will be called by cons_nonlinear in every 
node of its expression graph (think of it as the union of all expression 
trees). I believe there you could implement something to ensure a 
reformulation into a form like (1),(2),(3), but you may have to relax 
your requirements a bit as well (allow more than one linear variable, 
allow <= or >= and nonzero right-hand-side).
Have a look into other constraint handlers that implement this callback 
(e.g., abspower).

Hope that helps,
Stefan




>
> Yours sincerely,
>
> Johannes Thürauf
>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>


-- 
http://www.gams.com/~stefan