<div dir="ltr"><div>Hi,</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>I now got what you mean. You mean the initial relaxation for that <br>
constraint.<br>
Indeed, nlhdlr_convex adds 5 times the same cut due to our naive way to <br>
choose the reference point.<br>
But it doesn't make much difference to me if I reduce this to just one <br>
cut (change 5 to 1 at <br>
<a href="https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881" rel="noreferrer" target="_blank">https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881</a>) <br>
The number of iterations per LP doesn't change much.<br>
But this is after I added an initial relaxation for the SOC constraints. <br>
Attached is a version of nlhdlr_soc.c that does this.</div></blockquote><div><br></div><div>Ok, I understand, this is a very specific issue for geometric means. Thanks for the .c file.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div> also get a finite dual bound now from the beginning on, but <br>
performance thereafter is awful. SCIP creates huge numbers of cuts for <br>
the SOC constraints and, as a sideeffect of that, also the sub-SCIP <br>
heuristics take a lot of time.</div></blockquote><div><br></div><div>I agree. Maybe some cuts can be aggregated to reduce the number. <br></div><div><br></div><div><br></div><div>Liding<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Stefan Vigerske <<a href="mailto:svigerske@gams.com">svigerske@gams.com</a>> 于2022年7月28日周四 16:59写道：<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
<br>
On 7/16/22 15:52, liding xu wrote:<br>
> Hi Stefan,<br>
> I find that the numerical problem comes from the estimation of signomial<br>
> term which represents a geometric mean: \prod x_i^{1/n} >= t.<br>
> SCIP will add several estimation gradient cuts for different points. In<br>
> theory, they should be all the same as \sum x_i / n >= t. But in float<br>
> point representation, they are \sum x_i / n >= t + epsilon, with different<br>
> epsilons. So cuts with almost the same coefficients are added, and LP<br>
> becomes ill conditioned.<br>
<br>
I now got what you mean. You mean the initial relaxation for that <br>
constraint.<br>
Indeed, nlhdlr_convex adds 5 times the same cut due to our naive way to <br>
choose the reference point.<br>
But it doesn't make much difference to me if I reduce this to just one <br>
cut (change 5 to 1 at <br>
<a href="https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881" rel="noreferrer" target="_blank">https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_convex.c#L1881</a>) <br>
The number of iterations per LP doesn't change much.<br>
But this is after I added an initial relaxation for the SOC constraints. <br>
Attached is a version of nlhdlr_soc.c that does this.<br>
<br>
> Anyway, I tried to manually adding init cuts for SOC constraints, and<br>
> signomial constraints. SCIP does not generate the above cuts, it works fine<br>
> now without any numerical problems.<br>
<br>
I also get a finite dual bound now from the beginning on, but <br>
performance thereafter is awful. SCIP creates huge numbers of cuts for <br>
the SOC constraints and, as a sideeffect of that, also the sub-SCIP <br>
heuristics take a lot of time.<br>
<br>
Stefan<br>
<br>
> Thanks.<br>
> <br>
> Best,<br>
> Liding<br>
> <br>
> <br>
> Stefan Vigerske <<a href="mailto:svigerske@gams.com" target="_blank">svigerske@gams.com</a>> 于2022年7月16日周六 13:31写道：<br>
> <br>
>> Hi,<br>
>><br>
>> there is no good reason. It's just one of the loose ends that hasn't<br>
>> been tied up so far<br>
>> (<a href="https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_soc.c#L2513" rel="noreferrer" target="_blank">https://github.com/scipopt/scip/blob/master/src/scip/nlhdlr_soc.c#L2513</a>).<br>
>><br>
>> You could try adding some initial cuts as linear constraints.<br>
>> 1. Think of the constraint as sqrt(4 z^2 + (x-y)^2) <= x+y<br>
>> 2. Take the gradient on the left side. This should be<br>
>> 1/f(x,y,z) (x,-y,4z), with f(x,y,z) = sqrt(4 z^2 + (x-y)^2)<br>
>> 3. For a point (x*,y*,z*), a valid cut is<br>
>> f(x*,y*,z*) + f'(x*,y*,z*) (x-x*, y-y*, z-z*) <= x+y,<br>
>> that is (please check),<br>
>> f(x*,y*,z*) + 1/f(x*,y*,z*) (x*(x-x*), -y*(y-y*), 4z*(z-z*)) <= x+y<br>
>> 4. Add these inequalities for a few choices of (x*,y*,z*), e.g.,<br>
>> (1,0,1), (0,1,1), (1,0,-1), (0,1,-1).<br>
>><br>
>> I agree that it would be nicer if SCIP were doing that automatically.<br>
>><br>
>> Stefan<br>
>><br>
>><br>
>> On 7/15/22 18:13, liding xu wrote:<br>
>>> Dear SCIP community,<br>
>>> I am solving a maximization MINLP problem with: a concave signomial<br>
>>> objective function (geometric mean, \prod_{i in [n]} w_i^{1/n}), SOC<br>
>>> constraints (z^2<=xy, x,y >=0), linear constraints. SCIP seems to have a<br>
>>> numerical problem. The root node run outputs "(node 1) unresolved<br>
>> numerical<br>
>>> troubles in LP 3 -- using pseudo solution instead (loop 1)".<br>
>>><br>
>>> I try to enable debugging output of two constraint handlers:<br>
>>> nlhdlr_convex.c and nlhdlr_soc.c. Both successfully detect the<br>
>>> SOC/signomial structure. However, soc handler does not generate any<br>
>>> estimation/initial cuts, thus making the LP relaxation numerically ill.<br>
>> Do<br>
>>> you know the reason why cuts for soc are not generated? The problem's gms<br>
>>> file is attached.<br>
>>> Thank you.<br>
>>><br>
>>> Best regards,<br>
>>> Liding Xu<br>
>>><br>
>>><br>
>>> _______________________________________________<br>
>>> Scip mailing list<br>
>>> <a href="mailto:Scip@zib.de" target="_blank">Scip@zib.de</a><br>
>>> <a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
>><br>
>><br>
> <br>
</blockquote></div>