view


Q: What happens if I type ?? ?
A: Normally if you type xx? and more than one parameter matches then a list of all parameters starting xx is printed out. If only one matches then a one line description of what it does is also printed out. If you use a double query then in the first case a one line description is printed for each parameter, while in the second case a longer description is also printed out and the possible options and current value.

Setting the hidden parameter verbose to a value greater than zero also has the same effect even with a single query.

Q: Are all the options for Cbc listed with a query?
A: You must be joking. To see all parameters, either use allC(ommands) or set verbose to 15 and then use ? or ??

Q: What can I do about degeneracy?
A: The stand-alone version of Clp by default switches on perturbation if it thinks the problem needs it. For primal it looks at values of bounds and rhs and if they have sufficiently different values it does not perturb, otherwise it modifies the bounds/rhs by small random amounts. For dual it looks at the costs. Even when it does not perturb it will switch on perturbation after so many iterations if it thinks it is a good idea.

Normally the perturbed problem takes fewer iterations but a few more iterations may be needed to clean up and use the original costs/bounds/rhs. For advanced use you can vary the amount of perturbation with the "pertValue" parameter. The default is 50, but it can be set to 51 through 61 where 51 is a very small perturbation and 61 is a large one. 50 normally is the same as 56 but gives the code a bit more freedom as to what to do. To give an idea of possibilities let us use a degenerate problem "nug12". On my laptop using Clp with Lapack installed (so factorization can switch to dense if it wants) the default uses the dual algorithm and takes 92,341 iterations and 177.8 seconds. Using a larger perturbation pertValue=59 it takes 52,102 iterations and 78.9 seconds.

However there is another thing we can do. In "Pivot selection methods in the Devex LP code" by PMJ Harris there is an explanation of how to use feasibility tolerances in a creative way to allow more options on exactly which variable to pivot in or out of basis. So the default value of the dual tolerance is 1.0e-7 but setting dualTolerance=5.0e-4 (which was Paula Harris' favourite value for the primal tolerance in primal - she argued that was the accuracy of the input data) takes 58,200 iterations and 83.7 seconds. Playing with perturbation and tolerance you can get it down below 40 seconds.

However for this particular problem you can do much better. Using barrier (even Clp's not too good one) gives 70.7 seconds while straightforward primal takes 25,390 iterations and 50.9 seconds. The easy champion is the Idiot heuristic followed by primal so

clp nug20.mps -idiot 200 -primals

takes 7.6 seconds!!! Using this approach you can solve nug20 in two hours but nug30 looked as if it would take a few weeks.

Q: What does tune(PreProcess) do?
A: The "documentation" is not quite correct as the clique size is now ignored (assumed to be 5) and the bottom bits are used for various options. Also if experimenting you may wish to use nnmmkkkk format where nn is number of major passes and mm is number of minor passes. The bit settings in kkkk are -

  • 2 - make some variables integer
  • 4 - make more variables integer
  • 32 - switch on some extra presolve options
  • 64 - try both clique replacement and dominated rows (if reasonable number of plus ones)
  • 128 - use Bron-Kerbosch to replace large numbers of two cliques with maximal cliques
  • 256 - more work if we are trying to find dominated rows
  • 512 - try clique cuts but replace rather than add

Many of these options were added for a client, and are not useful for all problems. However it may be worth experimenting. Note that these were added to Cgl/trunk but are quite safe to use with any version of Cbc - just modify the Externals file and use svn propset svn:externals -F Externals . (The dot is needed) followed by svn update.