[Couenne] SetCutoff()

[Francois Margot]

Pietro:

On Sun, 2011-05-08 at 23:15 -0400, Pietro Belotti wrote:
> Francois,
> 
> > In Couenne/stable/0.3, the code for CouenneProblem::setCutoff(double 
> > value) always sets the value to
> >
> > cutoff + SafeCutoff * (1. + fabs(cutoff))
> >
> > where SafeCutoff is 1e-4. While that might be safe, it might also be 
> > disastrous for problems with many optimal solutions or many feasible 
> > solutions within SafeCutoff * (1. + fabs(optimal_value)) of the optimal 
> > value. While it might be a reasonable thing to do in some situations, it 
> > seems that when the code claims to have found a feasible solution with 
> > value v, the cutoff should be set to v, not slightly higher.
> 
> I agree. I did that precisely for safety reasons, as bound reduction 
> procedures were cutting out optimal solutions because of tight cutoffs. 
> This shouldn't happen, but this is mostly a problem that shows up when the 
> model contains very small or very large constants, or both. 1e-4 seems a 
> reasonable tradeoff between not eliminating feasible solutions and 
> avoiding suboptimal regions.
> 

On some problem (ex1233, for example), it happens that the value of the
LP relaxation becomes larger than the value of the best known solution
for a large number of nodes. The nodes are not pruned, as the cutoff is
set to roughly 155026 while the best known solution has value 155011.
This does not look like much, but the lower bound inches up very slowly
and going from 155011 to 155026 is quite some work.  

> Do you have specific examples? For example, if all those solutions have 
> (just like the cutoff) a very large value such as 1e+6, the cutoff is set 
> 100 above where it should be. This can be avoided simply by adding an 
> _absolute_ term instead, i.e., by setting the cutoff as
> 
> cutoff + min (1., SafeCutoff * (1. + fabs (cutoff)))
> 
> but if, again, apart from large solution values, there were very large or 
> very small quantities in the problem, we may cut optima.
> 

I test on roughly 40 standard instances with different parameters for
Couenne. When setting the cutoff to the exact value of any found
solution, I see problems finding a solution reasonably close to the
optimal one only sometimes on csched1. That problem has bad numerics and
I don't think that worrying about it makes much sense. Whatever the
safety settings you put in, one can find a badly formulated problem for
which the solution will not be found.   

> > I also noted that Couenne/stable/0.3 (downloaded today) does not 
> > terminate on nvs19. On a Fedora 13 (linux 64 bits) install, I get:
> >
> > Cbc0015I Node 175 Obj -1103.72 Unsat 100 depth 88
> > ## WEAK up-br: [9.00000000 ,(9.00000000)] -> 9.00000000
> >
> > and then the last line repeats with no end. This is using
> >
> > bb_log_level 3
> > variable_selection osi-strong
> >
> > and all other defaults as in the provided couenne.opt file.
> 
> I committed a revision in Couenne/stable that should take care of that. 
> Again, numerical issues: an integer variable whose value looks integer to 
> Cbc (which, I believe, has an infeasibility of 1e-7 or above) but not 
> Couenne, whose COUENNE_EPS, used in computing branching infeasibility, was 
> set to 1e-8. I simply restored COUENNE_EPS=1e-7, as it was not long ago. 
> nvs19 is now solved with the settings you provided (note: the very same 
> problem is giving troubles to Couenne/trunk...).
> 

That might fix it for nvs19, but I also observed that the code enters an
infinite loop when the following happens: An integer variable x_i has
bounds [a, a] (i.e. it is fixed) but has value a - 1e-7 in the solution
of the LP relaxation. The Cbc object for x_i says that it has an
infeasibility of 0. The Couenne object has a violation of 0 for the
"couenne part" but adds the violation of 1e-7 for violation of the
integrality. Then strong branching branches on x_i, sees that setting
x_i = a + 1 is infeasible, keeps the branch x_i = a and returns. Since
the LP solver keeps returning the same solution, the whole thing
repeats. I could fix it by not adding the integer violation in the
couenne object if the bounds of x_i are identical. That fixes it. (Maybe
a better solution is not to add the integer violation in the couenne
object if the value of x_i is slightly out of bounds.)

Francois