[Cbc] Antw: Re: Cut efficiency in cbcSolve for versions 2.0.0, 2.1.0, 2.2.2and 2.3.0

[John J Forrest]

Torsten,

I have found the problem.  Before Cbc 2.2 probing was done on all rows.
Then it was decided that it was best to leave out dense rows to try and
improve the speed of probing.  However my brain was not working very well
as I forgot that if we have a solution, then the objective row is added as
a constraint.  Very often this constraint will be dense - so in some cases
it was being added and then thrown out again.  This is what made the
difference as in some cases heuristics were getting good solutions.

I have made some changes in trunk, but need to test them a bit more before
they go in stable.  As I am one of the few people with limited access to
broadband (during part of the year) and for various other reasons,  I may
not be able to update stable for a few days.  If you are using stable/2.3
you could change lines 4149,4150 of CbcSolver.cpp to 10000.  As the quality
of the solutions from the heuristics vary a lot on the problem you sent me,
the objective after cuts varies.  Playing around with 2.3 I did get 246.295
on one run.

John



                                                                                                   
  From:       "Torsten Fahle" <Torsten.Fahle at inform-ac.com>                                        
                                                                                                   
  To:         <cbc at list.coin-or.org>                                                               
                                                                                                   
  Date:       08/27/2009 01:00 PM                                                                  
                                                                                                   
  Subject:    [Cbc] Antw: Re:  Cut efficiency in cbcSolve for versions 2.0.0,	2.1.0, 2.2.2and    
              2.3.0                                                                                
                                                                                                   
  Sent by:    cbc-bounces at list.coin-or.org                                                         
                                                                                                   





Haroldo,

> Did you get the integer optimal solution with all versions ?
> I'm just thinking that perhaps the better bounds of previous versions
could
> include inequalities which could cut integer optimal solutions - these
> issues perhaps are fixed in newest releases....

This could be the case. However, solution values found by
* CBC 2.0.0 with probing on and no other cuts  (246.295513999)
* CBC 2.3.0 without any cuts (246.2995200001)
differ only slightly by less than 1e-5. This is probably in the area of
internal epsilons
in the code, so it's hard to say from the outside whether some cuts removed
an optimal solution
in the older code.
By the way: CPLEX 9 claims that 246.299514 is optimal, XPRESS 2008 stops at
246.299524.
Thus, it's hard to say which result is really better and which one is due
to numerical issues.

Torsten




_______________________________________________
Cbc mailing list
Cbc at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/cbc

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/cbc/attachments/20090829/94ae0164/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
Url : http://list.coin-or.org/pipermail/cbc/attachments/20090829/94ae0164/attachment.gif 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ecblank.gif
Type: image/gif
Size: 45 bytes
Desc: not available
Url : http://list.coin-or.org/pipermail/cbc/attachments/20090829/94ae0164/attachment-0001.gif