[Couenne] Different solutions depending on tree strategy

[Pietro Belotti]

Dear Damien,

I could reproduce the behavior you describe. I am not sure why this
happens, but I suspect it may have to do with 1) the coefficients you use
and 2) the structure of the problem. Regarding the latter, the feasible set
seems to be a very thin region around the segment from (l1,l2) to (u1,u2)
as you can see by plotting both functions.

Even trickier, the objective function has a zero eigenvalue on the same
direction as the segment. I think all of this makes Couenne believe that
the first solution found is the optimal one; I would need to investigate
this further, but I suppose the subsequent bound tightening restricts the
feasible set around the solution found. Although the difference in
objective function values are more than COUENNE_EPS, in practice Couenne
does not find anything better from then on.

This is a nice test problem for the numerical stability of solvers such as
Couenne.

Pietro



On Tue, May 6, 2014 at 12:49 AM, Damien Gerard <damien.gerard at ulg.ac.be>wrote:

> Dear all,
>
> If I run some models with different tree search strategies and node
> comparison methods, I sometimes end up with a difference in the optimal
> objective value which is bigger than COUENNE_EPS=1.e-07. Let me illustrate
> this with a small model - a continuous qcqp with 2 variables :
>
> top node & best bound : f* = -0.007036, x0 = 0.0617, x1 = 0.0374
> top node & best guess : f* = -0.007066, x0 = 0.0624, x1 = 0.0382
>
> Does anybody has any clue why such a difference ?
>
> Thank you very much and thanks to all the Couenne contributors for the
> great work !
>
> Best regards,
>
> Damien Gerard
>
>
> -- problem in AMPL format, solved with Couenne 0.4 --
>
> var X0 >= -0.175464, <= 0.088790;
> var X1 >= -0.205315, <= 0.088286;
> minimize f : X0^2 * -1.942191249 + X1^2 * -1.942191249 + 3.884382497 * X0
> * X1 - 0.005870047836474;
> subject to ctr01 : X0^2 * 1.942191249 - 1.942191249 * X0 * X1 -
> 10.035428230507371 * X1 + 9.457590773272191 * X0 + 1.458281314539863 -
> 1.942191249 * 0.9547837317091492 * 0.8998075223169929 <= 0;
> subject to ctr02 : X0^2 * 10.51068205  + -1.747598295628436 * X0 +
> -10.51068205 * X0 * X1 + 1.942191249 * 0.9547837317091492 * X1 +
> 9.052213345123171 - 9.029953811482843 <= 0;
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/couenne/attachments/20140510/f3c07e36/attachment.html>