[SCIP] Lack of initial estimation cuts by SOC constraint handler

[liding xu]

Hi Stefan,
  I find that the numerical problem comes from the estimation of signomial
term which represents a geometric mean: \prod x_i^{1/n} >= t.
  SCIP will add several estimation gradient cuts for different points. In
theory, they should be all the same as \sum x_i / n >= t. But in float
point representation, they are  \sum x_i / n >= t + epsilon, with different
epsilons. So cuts with almost the same coefficients are added, and LP
becomes ill conditioned.
  Anyway, I tried to manually adding init cuts for SOC constraints, and
signomial constraints. SCIP does not generate the above cuts, it works fine
now without any numerical problems.
  Thanks.

Best,
Liding


Stefan Vigerske <svigerske at gams.com> 于2022年7月16日周六 13:31写道：

> Hi,
>
> there is no good reason. It's just one of the loose ends that hasn't
> been tied up so far
> (https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_soc.c#L2513).
>
> You could try adding some initial cuts as linear constraints.
> 1. Think of the constraint as sqrt(4 z^2 + (x-y)^2) <= x+y
> 2. Take the gradient on the left side. This should be
>     1/f(x,y,z) (x,-y,4z), with f(x,y,z) = sqrt(4 z^2 + (x-y)^2)
> 3. For a point (x*,y*,z*), a valid cut is
>     f(x*,y*,z*) + f'(x*,y*,z*) (x-x*, y-y*, z-z*) <= x+y,
>     that is (please check),
>     f(x*,y*,z*) + 1/f(x*,y*,z*) (x*(x-x*), -y*(y-y*), 4z*(z-z*)) <= x+y
> 4. Add these inequalities for a few choices of (x*,y*,z*), e.g.,
>     (1,0,1), (0,1,1), (1,0,-1), (0,1,-1).
>
> I agree that it would be nicer if SCIP were doing that automatically.
>
> Stefan
>
>
> On 7/15/22 18:13, liding xu wrote:
> > Dear SCIP community,
> >     I am solving a maximization MINLP problem with: a concave signomial
> > objective function (geometric mean, \prod_{i in [n]} w_i^{1/n}), SOC
> > constraints (z^2<=xy, x,y >=0), linear constraints. SCIP seems to have a
> > numerical problem. The root node run outputs "(node 1) unresolved
> numerical
> > troubles in LP 3 -- using pseudo solution instead (loop 1)".
> >
> >    I try to enable debugging output of two constraint handlers:
> > nlhdlr_convex.c and nlhdlr_soc.c. Both successfully detect the
> > SOC/signomial structure. However, soc handler does not generate any
> > estimation/initial cuts,  thus making the LP relaxation numerically ill.
> Do
> > you know the reason why cuts for soc are not generated? The problem's gms
> > file is attached.
> >    Thank you.
> >
> > Best regards,
> > Liding Xu
> >
> >
> > _______________________________________________
> > Scip mailing list
> > Scip at zib.de
> > https://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220716/7493090e/attachment.html>