[Coin-discuss] Suggestions on how to go about tuning?
achterberg at zib.de
Fri Jun 2 04:53:54 EDT 2006
your model (or at least this single instance) seems to be very
interesting, and a good candidate for playing around with and trying
to improve solvers.
Is it possible (are you allowed?) to send me the instance, such that I
can try whether SCIP is able to solve it in minutes or also takes
hours...? If SCIP is able to solve it, I could play with the parameter
settings and try to figure out which component is missing in CBC.
Btw: Which solver was able to solve it? CPLEX? XPress? Regarding your
assumptions on the equivalence of these zero-cost-clique members: I
know that CPLEX 10 has some kind of symmetry breaking in presolving
and/or cutting plane separation. Probably, something like this can be
the key for solving your instance.
Darla and Philip Walton wrote:
> Thanks for the replies!
> I included the 3 responses at the bottom for completeness...
> QUICK RESPONSES:
> 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?)" --
> -- 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.
> 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
> 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!
> 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
Tobias Achterberg Konrad-Zuse-Zentrum fuer
Tel: +49 (0)30 84185-301 Takustr. 7
Email: achterberg at zib.de D-14195 Berlin, Germany
More information about the Coin-discuss