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

[Tobias Achterberg]

Hi Philip,

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.


Best, Tobias



Darla and Philip Walton wrote:
> 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

-- 
Tobias Achterberg          Konrad-Zuse-Zentrum fuer
                           Informationstechnik Berlin
Tel: +49 (0)30 84185-301   Takustr. 7
Email: achterberg at zib.de   D-14195 Berlin, Germany