[Couenne] Obscure error message when running Couenne

[Pietro Belotti]

Dear Sergey,

> I have found some strange cutting planes.
> If (x in -32000.0..32000.0) then constraint z = x ^ 2 gives the planes:
> z+2*x>=-1
> z+x>=-0.25
> z-x>=-0.25
> z-2*x>=-1
>
> If (x in -31000.0..31000.0) then constraint z = x ^ 2 gives "normal" planes:
>
> z+62000*x>=-961000000
> z+31000*x>=-240250000
> z-31000*x>=-240250000
> z-62000*x>=-961000000
>
> It looks conditions with "powThres" sets range to -1..1 for variable x.

this is a somewhat odd behavior of Couenne, but it is justified by the  
need to have a limit on the ratio between coefficients in the  
linearization cuts. These cuts are, for the expression z = x^2, of the  
form

z - a^2 >= 2a (x-a)    or equivalently     z - 2ax + a^2 >= 0

and they are valid for any a. Usually couenne adds 4 of them, for four  
values of a equally spaced in the interval [l,u], i.e., a is in the  
set {l, l+.33(u-l), l+.66(u-l), u}. For values of l or u greater, in  
absolute value, than 32000, the constant term becomes greater than  
1e9, which should be avoided at least when using Clp as an LP solver.  
When one of the two is that large, therefore, it is reduced to allow  
for a numerically better constant term.

I agree that this is an abrupt change, but both sets of cuts are  
valid. The second set of cuts should be used for any l < -powThres and  
for any u > powThres, so as to have numerically stable cuts.

> Unfortunately I can not have tests in C++. Sources were converted to VB. Of
> course strange cutting planes maybe a result of my conversion error. But it
> seems the follow code in "exprPow::generateCuts" has a "bug":

I'm positive it would do the same in Couenne. No conversion error, but  
actually a bug. Linearizations of a nonlinear constraint like that  
should be exact at the bounds of x, therefore the first set of cuts is  
incorrect. I'll fix it soon.

Thanks,
Pietro

_________________________________________
Pietro Belotti, Lehigh University
Dept. of Industrial and Systems Engineering
200 W Packer Ave, Bethlehem PA 18015.
phone: 610-758-3865   fax: 610-758-4886
email: belotti at lehigh.edu
web:   http://www.lehigh.edu/~pib208


On 06/01/2010, design at np-soft.ru wrote:

> Dear developers,
>
> I have found some strange cutting planes.
> If (x in -32000.0..32000.0) then constraint z = x ^ 2 gives the planes:
> z+2*x>=-1
> z+x>=-0.25
> z-x>=-0.25
> z-2*x>=-1
>
> If (x in -31000.0..31000.0) then constraint z = x ^ 2 gives "normal" planes:
>
> z+62000*x>=-961000000
> z+31000*x>=-240250000
> z-31000*x>=-240250000
> z-62000*x>=-961000000
>
> It looks conditions with "powThres" sets range to -1..1 for variable x.
>
> Unfortunately I can not have tests in C++. Sources were converted to VB. Of
> course strange cutting planes maybe a result of my conversion error. But it
> seems the follow code in "exprPow::generateCuts" has a "bug":
>
>     if (k > COUENNE_EPS) {
>       if (u >   powThres) u = CoinMax (x,l) + powStep;
>       if (l < - powThres) l = CoinMin (x,u) - powStep;
>     }
>     else {
>       if (fabs (l) < COUENNE_EPS) l =  1. / powThres; // l --> 0+
>       if (fabs (u) < COUENNE_EPS) u = -1. / powThres; // u --> 0-
>     }
>     addPowEnvelope (cg, cs, w_ind, x_ind, x, w, k, l, u, sign);
>
> k is 2, l is -32000, h is 32000, x is zero, powStep is 1. If execute below
> code then  l is sets to -1 and u is sets to 1 ...
>  
> Sergey
>
>
>
>
> _______________________________________________
> Couenne mailing list
> Couenne at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/couenne
>



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.