[SCIP] Lack of initial estimation cuts by SOC constraint handler
Stefan Vigerske
svigerske at gams.com
Thu Jul 28 16:59:06 CEST 2022
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 --------------
A non-text attachment was scrubbed...
Name: nlhdlr_soc.c
Type: text/x-csrc
Size: 112944 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220728/e5e72e3e/attachment.bin>
More information about the Scip
mailing list