<br><font size=2 face="sans-serif">Philip, (and Francois Margot),</font>
<br>
<br><font size=2 face="sans-serif">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?</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">John</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>"Darla and Philip
Walton" <hpwalton@comcast.net></b> </font>
<br><font size=1 face="sans-serif">Sent by: coin-discuss-bounces@list.coin-or.org</font>
<p><font size=1 face="sans-serif">06/02/2006 02:46 AM</font>
<table border>
<tr valign=top>
<td bgcolor=white>
<div align=center><font size=1 face="sans-serif">Please respond to<br>
Discussions about open source software for Operations Research
<coin-discuss@list.coin-or.org></font></div></table>
<br>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif"><coin-discuss@list.coin-or.org></font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">Re: [Coin-discuss] Suggestions on how
to go about tuning?</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2 face="Arial">Thanks for the replies!</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">I included the 3 responses at the bottom
for completeness...</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">QUICK RESPONSES:</font>
<br><font size=2 face="Arial">John:</font>
<br><font size=2 face="Arial">I'll send you an MPS probably tomorrow. I'm
more interested in the process than the particular answer in this case...</font>
<br><font size=2 face="Arial">What do I look for? What knob do I
twist? more below</font>
<br><font size=2 face="Arial">I know that nobody has all the answers...and
I'm sure the tool at hand is more flexible than it appears. </font>
<br><font size=2 face="Arial"> </font>
<br><font size=2 face="Arial">Michael and Weiguo:</font>
<br><font size=2 face="Arial">These are "off the top" things.
At some point you're stuck with branch and cut...</font>
<br><font size=2 face="Arial">I absolutely agree: 1) get a heuristic answer,
and 2) get your bounds as tight as possible to start with...</font>
<br><font size=2 face="Arial">I would also add, 3) know as much as possible
about the data before you start.... (see zero-cost-cliques below)</font>
<br><font size=2 face="Arial">Those 3 will absolutely make a dramatic difference.</font>
<br><font size=2 face="Arial">What I'm asking for is more in terms of how
to make CBC run faster based on the problem in hand.</font>
<br><font size=2 face="Arial">e.g. What metrics of the matrix drive what
settings in the parameters? In what conditions should I apply XYZ
heuristic? </font>
<br><font size=3> </font>
<br><font size=2 face="Arial">WHAT I FOUND:</font>
<br><font size=2 face="Arial">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</font>
<br><font size=2 face="Arial">...not sure it's all though.</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">Through digging in the samples, I found 2
things I could use which made differences...(and they do :-D )</font>
<br><font size=2 face="Arial">-- SOS constraints (type 1)</font>
<br><font size=2 face="Arial">-- "Make round up more attractive (in
longthin.cpp or crew.cpp?)" -- pseudocosts</font>
<br><font size=2 face="Arial">-- 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.</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">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.</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">QUESTION TAKE 2</font>
<br><font size=2 face="Arial">Maybe I should rephrase the question:</font>
<br><font size=2 face="Arial">- How do I go about finding the knobs on
the machine which I can twist?</font>
<br><font size=2 face="Arial">- How do I more quickly understand what the
knobs do? </font>
<br><font size=3> </font>
<br><font size=2 face="Arial">MOTIVATING AN ANSWER</font>
<br><font size=2 face="Arial">Here is an example of what I'd like to use,
which I won't try because of the limits on my time. </font>
<br><font size=2 face="Arial">There is a comment in a sample something
like this:...</font>
<br><font size=2 face="Arial">"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.</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">ZERO-COST-CLIQUES</font>
<br><font size=2 face="Arial">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.</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">It does bug me, however, that another solver
was in minutes rather than hours....</font>
<br><font size=2 face="Arial">I'm guess 2 things:</font>
<br><font size=2 face="Arial">- 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.</font>
<br><font size=2 face="Arial">- Auto-setting of certain parameters?</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">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.</font>
<br><font size=2 face="Arial">So, I believe it to be CBC. That being
the case, who's workin' on the pre-processor?! Do they need some
extra hands?</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">Cheers! and Thanks!</font>
<br><font size=2 face="Arial">Philip</font>
<br><font size=3> </font>
<br><font size=2 face="Arial">ORIGINAL RESPONSES:</font>
<br><font size=3>From: Michael Hennebry :</font>
<br><font size=3>"...The question is how should CBC find the correct
foot?<br>
Possibly the best way is to find an initial feasible<br>
solution from a heuristic and tell CBC that you want<br>
a solution at least that good...."</font>
<br><font size=3> </font>
<br><font size=3>From: "Weiguo Liu":</font>
<br><font size=3>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. <br>
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. </font>
<br><font size=3>From: John J Forrest :</font>
<br><font size=3>"...If you can send me the model I will look at it
and try and document the <br>
way I tuned it. I might include such an example in my tutorial at
DIMACS <br>
workshop if people think that a good idea.<br>
</font><font size=2 face="Arial"><br>
.."</font>
<br><font size=3> </font>
<br><font size=3> </font>
<br><tt><font size=2>_______________________________________________<br>
Coin-discuss mailing list<br>
Coin-discuss@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/coin-discuss<br>
</font></tt>
<br>