[Coin-discuss] Suggestions on how to go about tuning?
John J Forrest
jjforre at us.ibm.com
Fri Jun 2 03:18:59 EDT 2006
Philip, Laci, Lou etc etc
As I am the chief culprit here are a few points -
a) Philip - I will try and document process. I ought to try and harden
SOS (and order of definitions).
b) CglPreProcess is solver independent and does exactly what Laci wants -
it needs more work but what doesn't.
c) There is a hotstart procedure in Cbc but I have not really tested it
much as I could not find a worthwhile candidate problem. So as it is not
fully tested it is mainly undocumented.
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/6d7733ae/attachment.html>
More information about the Coin-discuss
mailing list