[SCIP] Is it worth to reduce degree of polynomial multi-linear terms in constraints?

Vladimir V. Voloshinov vladimir.voloshinov at gmail.com
Thu Nov 30 00:36:05 CET 2017


Dear Ambros, Benjamin, Serrano and Stefan,
I address you this question because at http://scip.zib.de you are "marked"
as developers related to "nonlinear problems".

We have a problem with polynomial constraints of the form (x, y, z - are
variables)
(1) x*y*z*z = 1;

The question is:
are there reasons (performance or accuracy) to reduce degree of
multi-linear term at the cost of additional (auxiliary) variables in
nonlinear non-convex continuous problems solved by SCIP ?

E.g. above constraint may be replaced by two constraints of less degree
with additional variable v:
(2) x*y = v;  v*z*z = 1;

Preliminary test starts of SCIP 4.* and SCIP 3.2.1 shows that for both
variants of the same problem (dozens of variables) results are very close.
The case (1) is solved slightly "faster", but sometimes the following
warning appears in the output (problem is solved):
....
[nonlinear] <cons_z[1,2]>: ((((<v[1,1]> + ((-1) * <v[2,1]>)) * (<v[1,1]> +
((-1) * <v[2,1]>))) + ... )))) * (<z[1,2]> * <z[1,2]>)) == 1;
violation: left hand side is violated by 1.08...e-06
.....
The case (2) is solved a little bit longer but without any constraints'
violations...

I took a look at the following report (it was not very deep reading though)
Stefan Vigerske, Ambros Gleixner. SCIP: Global Optimization of
Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework (ZIB Report,
May 2016)
https://opus4.kobv.de/opus4-zib/files/5937/ZR-16-24.pdf
but couldn't find some explicit recommendations on the subject.

Are there any unambiguous rules relating to above alternative (1)vs(2)?

Regards,
Vladimir V. Voloshinov,
---------------
Center of Distributed Computing, http://distcomp.ru,
Institute for Information Transmission Problems RAS, http://www.iitp.ru
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20171130/50861bce/attachment.html>


More information about the Scip mailing list