[Coin-discuss] Suggestions on how to go about tuning?

[John J Forrest]

Philip,  (and Francois Margot),

Any help with preprocessing would be very welcome.  At present 
CglPreProcess uses ordinary presolve techniques plus coefficient 
strengthening and duplicate/dominated row removal and it can detect SOS. 
Symmetry breaking cuts sounds as if it should be here.  Francois - I see 
you gave a paper at IMA last July which sounds useful - can you send me a 
copy?

When I get time I will try and improve the robustness of ordering of 
discontinuity definitions e.g. SOS.  My remark about good weights in SOS 
being important probably won't help you here.  That is more for when The O 
in SOS means something - so if it is build in year N or don't build at all 
then give weight so don't build is at end i.e. off time horizon.  For 
building depots with economies of scale then using the correct sizes means 
that the branching is more useful.  Otherwise all you are getting from SOS 
is the logarithmic branching effect.

John



"Darla and Philip Walton" <hpwalton at comcast.net> 
Sent by: coin-discuss-bounces at list.coin-or.org
06/02/2006 02:46 AM
Please respond to
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>


To
<coin-discuss at list.coin-or.org>
cc

Subject
Re: [Coin-discuss] Suggestions on how to go about tuning?






Thanks for the replies!
 
I included the 3 responses at the bottom for completeness...
 
QUICK RESPONSES:
John:
I'll send you an MPS probably tomorrow.  I'm more interested in the 
process than the particular answer in this case...
What do I look for?  What knob do I twist?  more below
I know that nobody has all the answers...and I'm sure the tool at hand is 
more flexible than it appears. 
 
Michael and Weiguo:
These are "off the top" things.  At some point you're stuck with branch 
and cut...
I absolutely agree: 1) get a heuristic answer, and 2) get your bounds as 
tight as possible to start with...
I would also add, 3) know as much as possible about the data before you 
start.... (see zero-cost-cliques below)
Those 3 will absolutely make a dramatic difference.
What I'm asking for is more in terms of how to make CBC run faster based 
on the problem in hand.
e.g. What metrics of the matrix drive what settings in the parameters?  In 
what conditions should I apply XYZ heuristic? 
 
WHAT I FOUND:
I thought saw a reference in my web-surfing for auto-setting parameters 
somewhere....Brady H maybe?  That is probably part of what I'm looking for
...not sure it's all though.
 
Through digging in the samples, I found 2 things I could use which made 
differences...(and they do :-D  )
-- SOS constraints (type 1)
-- "Make round up more attractive (in longthin.cpp or crew.cpp?)" -- 
pseudocosts
-- tell CBC in the compile that it's using CLP.  This got me quite a bit 
of speed as well.  Bummer it isn't "out of the box" that fast.
 
I bumbled around and added SOS & pseudocosts in the wrong order and it 
crashed...but I eventually made it apparently better...I found that SOS is 
a bit flaky and apparently must go last?  Odd that.  This bit is what 
prompted the first posting.
 
QUESTION TAKE 2
Maybe I should rephrase the question:
- How do I go about finding the knobs on the machine which I can twist?
- How do I more quickly understand what the knobs do? 
 
MOTIVATING AN ANSWER
Here is an example of what I'd like to use, which I won't try because of 
the limits on my time. 
There is a comment in a sample something like this:...
"Adding appropriate weights such as time or cost dramatically improves SOS 
behavior"....so how do I figure out what a good set of weights are on one 
SOS constraint over the graph I'm using.  The modeling aspects aside, 
there are also SOS priorities.  Are those the key?  What settings imply 
what behavior?  I can certainly go through code that implements them, but 
that would be the purpose of the library right?  So that I don't have to 
fully embrace the implementation in order to use it.
 
ZERO-COST-CLIQUES
I believe I've found the cause of my current woes...it was a source data 
issue...basically, there were 3 sets of data-identical nodes...which had 
zero costs within the groups.  (some nasty little zero-cost-cliques). The 
impact was a LOT of tailing as CBC did a lot of swapping of the order in 
those sets trying to find an improvement.  I'm writing some code to bulid 
"super nodes(arcs?)" from the zero cost cliques in pre-processing and then 
restore them out in postprocessing.  This will shrink the problem size 
dramatically, and reduce the swapping of equal-value-solutions.
 
It does bug me, however, that another solver was in minutes rather than 
hours....
I'm guess 2 things:
- Preprocessor?  (might fight the zero-cost clique even though I didnt' 
tell the solver it was a graph of sorts?)..hmmm...probably something else 
it found.
- Auto-setting of certain parameters?
 
I know CLP may not be the fastest horse on the track, but it comes from 
good breeding stock.  CLP is not really the cause here I don't think.
So, I believe it to be CBC.  That being the case, who's workin' on the 
pre-processor?!  Do they need some extra hands?
 
Cheers! and Thanks!
Philip
 
ORIGINAL RESPONSES:
From: Michael Hennebry :
"...The question is how should CBC find the correct foot?
Possibly the best way is to find an initial feasible
solution from a heuristic and tell CBC that you want
a solution at least that good...."
 
From: "Weiguo Liu":
But yes, if you have a good initial IP solution, you can guide CBC with 
your solution in hope that this is a "good footing". Certainly in general 
it is hard to find an "good" initial solution. Usually you can not tell if 
a heuristic solution is good or not. But you can always tell CBC the 
objective value of the solution in order to reduce the initial gap between 
lower and upper bounds. The performance of the B&B is largely affected by 
this gap. 
The other thing you may be able to do is when you know what is wrong with 
the CBC's initial solution. For example, one arc can never be in an 
optimization solution, then you can fix the variable (force this arc to be 
0), before starts the branch and bound. 
From: John J Forrest :
"...If you can send me the model I will look at it and try and document 
the 
way I tuned it.  I might include such an example in my tutorial at DIMACS 
workshop if people think that a good idea.

.."
 
 
_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060602/464f82bd/attachment.html>