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

[liding xu]

Hi,

> I now got what you mean. You mean the initial relaxation for that
> constraint.
> Indeed, nlhdlr_convex adds 5 times the same cut due to our naive way to
> choose the reference point.
> But it doesn't make much difference to me if I reduce this to just one
> cut (change 5 to 1 at
> https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881)
>
> The number of iterations per LP doesn't change much.
> But this is after I added an initial relaxation for the SOC constraints.
> Attached is a version of nlhdlr_soc.c that does this.
>

Ok, I understand, this is a very specific issue for geometric means.
Thanks for the .c file.

also get a finite dual bound now from the beginning on, but
> performance thereafter is awful. SCIP creates huge numbers of cuts for
> the SOC constraints and, as a sideeffect of that, also the sub-SCIP
> heuristics take a lot of time.
>

I agree. Maybe some cuts can be aggregated to reduce the number.


Liding

Stefan Vigerske <svigerske at gams.com> 于2022年7月28日周四 16:59写道：

> Hi,
>
>
> On 7/16/22 15:52, liding xu wrote:
> > 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.
>
> I now got what you mean. You mean the initial relaxation for that
> constraint.
> Indeed, nlhdlr_convex adds 5 times the same cut due to our naive way to
> choose the reference point.
> But it doesn't make much difference to me if I reduce this to just one
> cut (change 5 to 1 at
> https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881)
>
> The number of iterations per LP doesn't change much.
> But this is after I added an initial relaxation for the SOC constraints.
> Attached is a version of nlhdlr_soc.c that does this.
>
> >    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.
>
> I also get a finite dual bound now from the beginning on, but
> performance thereafter is awful. SCIP creates huge numbers of cuts for
> the SOC constraints and, as a sideeffect of that, also the sub-SCIP
> heuristics take a lot of time.
>
> Stefan
>
> >    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/20220728/c8b00d94/attachment.html>